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