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   HB_DELETE_COPY_ASSIGN (hb_priority_queue_t);
hb_priority_queue_thb_priority_queue_t42   hb_priority_queue_t ()  { init (); }
~hb_priority_queue_thb_priority_queue_t43   ~hb_priority_queue_t () { fini (); }
44 
45  private:
46   typedef hb_pair_t<int64_t, unsigned> item_t;
47   hb_vector_t<item_t> heap;
48 
49  public:
inithb_priority_queue_t50   void init () { heap.init (); }
51 
finihb_priority_queue_t52   void fini () { heap.fini (); }
53 
resethb_priority_queue_t54   void reset () { heap.resize (0); }
55 
in_errorhb_priority_queue_t56   bool in_error () const { return heap.in_error (); }
57 
inserthb_priority_queue_t58   void insert (int64_t priority, unsigned value)
59   {
60     heap.push (item_t (priority, value));
61     bubble_up (heap.length - 1);
62   }
63 
pop_minimumhb_priority_queue_t64   item_t pop_minimum ()
65   {
66     item_t result = heap[0];
67 
68     heap[0] = heap[heap.length - 1];
69     heap.shrink (heap.length - 1);
70     bubble_down (0);
71 
72     return result;
73   }
74 
minimumhb_priority_queue_t75   const item_t& minimum ()
76   {
77     return heap[0];
78   }
79 
is_emptyhb_priority_queue_t80   bool is_empty () const { return heap.length == 0; }
operator boolhb_priority_queue_t81   explicit operator bool () const { return !is_empty (); }
get_populationhb_priority_queue_t82   unsigned int get_population () const { return heap.length; }
83 
84   /* Sink interface. */
operator <<hb_priority_queue_t85   hb_priority_queue_t& operator << (item_t item)
86   { insert (item.first, item.second); return *this; }
87 
88  private:
89 
parenthb_priority_queue_t90   static constexpr unsigned parent (unsigned index)
91   {
92     return (index - 1) / 2;
93   }
94 
left_childhb_priority_queue_t95   static constexpr unsigned left_child (unsigned index)
96   {
97     return 2 * index + 1;
98   }
99 
right_childhb_priority_queue_t100   static constexpr unsigned right_child (unsigned index)
101   {
102     return 2 * index + 2;
103   }
104 
bubble_downhb_priority_queue_t105   void bubble_down (unsigned index)
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[index].first <= heap[left].first
117         && (!has_right || heap[index].first <= heap[right].first))
118       return;
119 
120     if (!has_right || heap[left].first < heap[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 
bubble_uphb_priority_queue_t131   void bubble_up (unsigned index)
132   {
133     if (index == 0) return;
134 
135     unsigned parent_index = parent (index);
136     if (heap[parent_index].first <= heap[index].first)
137       return;
138 
139     swap (index, parent_index);
140     bubble_up (parent_index);
141   }
142 
swaphb_priority_queue_t143   void swap (unsigned a, unsigned b)
144   {
145     item_t temp = heap[a];
146     heap[a] = heap[b];
147     heap[b] = temp;
148   }
149 };
150 
151 #endif /* HB_PRIORITY_QUEUE_HH */
152