Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/harfbuzz/src/hb-priority-queue.hh @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*
2 * Copyright © 2020 Google, Inc.
3 *
4 * This is part of HarfBuzz, a text shaping library.
5 *
6 * Permission is hereby granted, without written agreement and without
7 * license or royalty fees, to use, copy, modify, and distribute this
8 * software and its documentation for any purpose, provided that the
9 * above copyright notice and the following two paragraphs appear in
10 * all copies of this software.
11 *
12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16 * DAMAGE.
17 *
18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23 *
24 * Google Author(s): Garret Rieger
25 */
26
27 #ifndef HB_PRIORITY_QUEUE_HH
28 #define HB_PRIORITY_QUEUE_HH
29
30 #include "hb.hh"
31 #include "hb-vector.hh"
32
33 /*
34 * hb_priority_queue_t
35 *
36 * Priority queue implemented as a binary heap. Supports extract minimum
37 * and insert operations.
38 */
39 struct hb_priority_queue_t
40 {
41 private:
42 typedef hb_pair_t<int64_t, unsigned> item_t;
43 hb_vector_t<item_t> heap;
44
45 public:
46
47 void reset () { heap.resize (0); }
48
49 bool in_error () const { return heap.in_error (); }
50
51 void insert (int64_t priority, unsigned value)
52 {
53 heap.push (item_t (priority, value));
54 if (unlikely (heap.in_error ())) return;
55 bubble_up (heap.length - 1);
56 }
57
58 item_t pop_minimum ()
59 {
60 assert (!is_empty ());
61
62 item_t result = heap.arrayZ[0];
63
64 heap.arrayZ[0] = heap.arrayZ[heap.length - 1];
65 heap.shrink (heap.length - 1);
66
67 if (!is_empty ())
68 bubble_down (0);
69
70 return result;
71 }
72
73 const item_t& minimum ()
74 {
75 return heap[0];
76 }
77
78 bool is_empty () const { return heap.length == 0; }
79 explicit operator bool () const { return !is_empty (); }
80 unsigned int get_population () const { return heap.length; }
81
82 /* Sink interface. */
83 hb_priority_queue_t& operator << (item_t item)
84 { insert (item.first, item.second); return *this; }
85
86 private:
87
88 static constexpr unsigned parent (unsigned index)
89 {
90 return (index - 1) / 2;
91 }
92
93 static constexpr unsigned left_child (unsigned index)
94 {
95 return 2 * index + 1;
96 }
97
98 static constexpr unsigned right_child (unsigned index)
99 {
100 return 2 * index + 2;
101 }
102
103 void bubble_down (unsigned index)
104 {
105 assert (index < heap.length);
106
107 unsigned left = left_child (index);
108 unsigned right = right_child (index);
109
110 bool has_left = left < heap.length;
111 if (!has_left)
112 // If there's no left, then there's also no right.
113 return;
114
115 bool has_right = right < heap.length;
116 if (heap.arrayZ[index].first <= heap.arrayZ[left].first
117 && (!has_right || heap.arrayZ[index].first <= heap.arrayZ[right].first))
118 return;
119
120 if (!has_right || heap.arrayZ[left].first < heap.arrayZ[right].first)
121 {
122 swap (index, left);
123 bubble_down (left);
124 return;
125 }
126
127 swap (index, right);
128 bubble_down (right);
129 }
130
131 void bubble_up (unsigned index)
132 {
133 assert (index < heap.length);
134
135 if (index == 0) return;
136
137 unsigned parent_index = parent (index);
138 if (heap.arrayZ[parent_index].first <= heap.arrayZ[index].first)
139 return;
140
141 swap (index, parent_index);
142 bubble_up (parent_index);
143 }
144
145 void swap (unsigned a, unsigned b)
146 {
147 assert (a < heap.length);
148 assert (b < heap.length);
149 hb_swap (heap.arrayZ[a], heap.arrayZ[b]);
150 }
151 };
152
153 #endif /* HB_PRIORITY_QUEUE_HH */