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 resethb_priority_queue_t47 void reset () { heap.resize (0); } 48 in_errorhb_priority_queue_t49 bool in_error () const { return heap.in_error (); } 50 inserthb_priority_queue_t51 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 pop_minimumhb_priority_queue_t58 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 minimumhb_priority_queue_t73 const item_t& minimum () 74 { 75 return heap[0]; 76 } 77 is_emptyhb_priority_queue_t78 bool is_empty () const { return heap.length == 0; } operator boolhb_priority_queue_t79 explicit operator bool () const { return !is_empty (); } get_populationhb_priority_queue_t80 unsigned int get_population () const { return heap.length; } 81 82 /* Sink interface. */ operator <<hb_priority_queue_t83 hb_priority_queue_t& operator << (item_t item) 84 { insert (item.first, item.second); return *this; } 85 86 private: 87 parenthb_priority_queue_t88 static constexpr unsigned parent (unsigned index) 89 { 90 return (index - 1) / 2; 91 } 92 left_childhb_priority_queue_t93 static constexpr unsigned left_child (unsigned index) 94 { 95 return 2 * index + 1; 96 } 97 right_childhb_priority_queue_t98 static constexpr unsigned right_child (unsigned index) 99 { 100 return 2 * index + 2; 101 } 102 bubble_downhb_priority_queue_t103 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 bubble_uphb_priority_queue_t131 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 swaphb_priority_queue_t145 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 */ 154