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 */ 45 template <typename K> 46 struct hb_priority_queue_t 47 { 48 private: 49 typedef hb_pair_t<K, unsigned> item_t; 50 hb_vector_t<item_t> heap; 51 52 public: 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 58 #ifndef HB_OPTIMIZE_SIZE 59 HB_ALWAYS_INLINE 60 #endif inserthb_priority_queue_t61 void insert (K priority, unsigned value) 62 { 63 heap.push (item_t (priority, value)); 64 if (unlikely (heap.in_error ())) return; 65 bubble_up (heap.length - 1); 66 } 67 68 #ifndef HB_OPTIMIZE_SIZE 69 HB_ALWAYS_INLINE 70 #endif pop_minimumhb_priority_queue_t71 item_t pop_minimum () 72 { 73 assert (!is_empty ()); 74 75 item_t result = heap.arrayZ[0]; 76 77 heap.arrayZ[0] = heap.arrayZ[heap.length - 1]; 78 heap.resize (heap.length - 1); 79 80 if (!is_empty ()) 81 bubble_down (0); 82 83 return result; 84 } 85 minimumhb_priority_queue_t86 const item_t& minimum () 87 { 88 return heap[0]; 89 } 90 is_emptyhb_priority_queue_t91 bool is_empty () const { return heap.length == 0; } operator boolhb_priority_queue_t92 explicit operator bool () const { return !is_empty (); } get_populationhb_priority_queue_t93 unsigned int get_population () const { return heap.length; } 94 95 /* Sink interface. */ operator <<hb_priority_queue_t96 hb_priority_queue_t& operator << (item_t item) 97 { insert (item.first, item.second); return *this; } 98 99 private: 100 parenthb_priority_queue_t101 static constexpr unsigned parent (unsigned index) 102 { 103 return (index - 1) / 2; 104 } 105 left_childhb_priority_queue_t106 static constexpr unsigned left_child (unsigned index) 107 { 108 return 2 * index + 1; 109 } 110 right_childhb_priority_queue_t111 static constexpr unsigned right_child (unsigned index) 112 { 113 return 2 * index + 2; 114 } 115 116 HB_ALWAYS_INLINE bubble_downhb_priority_queue_t117 void bubble_down (unsigned index) 118 { 119 repeat: 120 assert (index < heap.length); 121 122 unsigned left = left_child (index); 123 unsigned right = right_child (index); 124 125 bool has_left = left < heap.length; 126 if (!has_left) 127 // If there's no left, then there's also no right. 128 return; 129 130 bool has_right = right < heap.length; 131 if (heap.arrayZ[index].first <= heap.arrayZ[left].first 132 && (!has_right || heap.arrayZ[index].first <= heap.arrayZ[right].first)) 133 return; 134 135 unsigned child; 136 if (!has_right || heap.arrayZ[left].first < heap.arrayZ[right].first) 137 child = left; 138 else 139 child = right; 140 141 swap (index, child); 142 index = child; 143 goto repeat; 144 } 145 146 HB_ALWAYS_INLINE bubble_uphb_priority_queue_t147 void bubble_up (unsigned index) 148 { 149 repeat: 150 assert (index < heap.length); 151 152 if (index == 0) return; 153 154 unsigned parent_index = parent (index); 155 if (heap.arrayZ[parent_index].first <= heap.arrayZ[index].first) 156 return; 157 158 swap (index, parent_index); 159 index = parent_index; 160 goto repeat; 161 } 162 swaphb_priority_queue_t163 void swap (unsigned a, unsigned b) 164 { 165 assert (a < heap.length); 166 assert (b < heap.length); 167 hb_swap (heap.arrayZ[a], heap.arrayZ[b]); 168 } 169 }; 170 171 #endif /* HB_PRIORITY_QUEUE_HH */ 172