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 * The priority queue is implemented as a binary heap, which is a complete
40 * binary tree. The root of the tree is the minimum element. The heap
41 * property is that the priority of a node is less than or equal to the
42 * priority of its children. The heap is stored in an array, with the
43 * children of node i stored at indices 2i + 1 and 2i + 2.
44 */
45struct hb_priority_queue_t
46{
47 private:
48 typedef hb_pair_t<int64_t, unsigned> item_t;
49 hb_vector_t<item_t> heap;
50
51 public:
52
53 void reset () { heap.resize (0); }
54
55 bool in_error () const { return heap.in_error (); }
56
57#ifndef HB_OPTIMIZE_SIZE
58 HB_ALWAYS_INLINE
59#endif
60 void insert (int64_t priority, unsigned value)
61 {
62 heap.push (item_t (priority, value));
63 if (unlikely (heap.in_error ())) return;
64 bubble_up (heap.length - 1);
65 }
66
67#ifndef HB_OPTIMIZE_SIZE
68 HB_ALWAYS_INLINE
69#endif
70 item_t pop_minimum ()
71 {
72 assert (!is_empty ());
73
74 item_t result = heap.arrayZ[0];
75
76 heap.arrayZ[0] = heap.arrayZ[heap.length - 1];
77 heap.resize (heap.length - 1);
78
79 if (!is_empty ())
80 bubble_down (0);
81
82 return result;
83 }
84
85 const item_t& minimum ()
86 {
87 return heap[0];
88 }
89
90 bool is_empty () const { return heap.length == 0; }
91 explicit operator bool () const { return !is_empty (); }
92 unsigned int get_population () const { return heap.length; }
93
94 /* Sink interface. */
95 hb_priority_queue_t& operator << (item_t item)
96 { insert (item.first, item.second); return *this; }
97
98 private:
99
100 static constexpr unsigned parent (unsigned index)
101 {
102 return (index - 1) / 2;
103 }
104
105 static constexpr unsigned left_child (unsigned index)
106 {
107 return 2 * index + 1;
108 }
109
110 static constexpr unsigned right_child (unsigned index)
111 {
112 return 2 * index + 2;
113 }
114
115 HB_ALWAYS_INLINE
116 void bubble_down (unsigned index)
117 {
118 repeat:
119 assert (index < heap.length);
120
121 unsigned left = left_child (index);
122 unsigned right = right_child (index);
123
124 bool has_left = left < heap.length;
125 if (!has_left)
126 // If there's no left, then there's also no right.
127 return;
128
129 bool has_right = right < heap.length;
130 if (heap.arrayZ[index].first <= heap.arrayZ[left].first
131 && (!has_right || heap.arrayZ[index].first <= heap.arrayZ[right].first))
132 return;
133
134 unsigned child;
135 if (!has_right || heap.arrayZ[left].first < heap.arrayZ[right].first)
136 child = left;
137 else
138 child = right;
139
140 swap (index, child);
141 index = child;
142 goto repeat;
143 }
144
145 HB_ALWAYS_INLINE
146 void bubble_up (unsigned index)
147 {
148 repeat:
149 assert (index < heap.length);
150
151 if (index == 0) return;
152
153 unsigned parent_index = parent (index);
154 if (heap.arrayZ[parent_index].first <= heap.arrayZ[index].first)
155 return;
156
157 swap (index, parent_index);
158 index = parent_index;
159 goto repeat;
160 }
161
162 void swap (unsigned a, unsigned b)
163 {
164 assert (a < heap.length);
165 assert (b < heap.length);
166 hb_swap (heap.arrayZ[a], heap.arrayZ[b]);
167 }
168};
169
170#endif /* HB_PRIORITY_QUEUE_HH */
171