| /* |
| * Copyright © 2020 Google, Inc. |
| * |
| * This is part of HarfBuzz, a text shaping library. |
| * |
| * Permission is hereby granted, without written agreement and without |
| * license or royalty fees, to use, copy, modify, and distribute this |
| * software and its documentation for any purpose, provided that the |
| * above copyright notice and the following two paragraphs appear in |
| * all copies of this software. |
| * |
| * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR |
| * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES |
| * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN |
| * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH |
| * DAMAGE. |
| * |
| * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, |
| * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND |
| * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS |
| * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO |
| * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. |
| * |
| * Google Author(s): Garret Rieger |
| */ |
| |
| #ifndef HB_PRIORITY_QUEUE_HH |
| #define HB_PRIORITY_QUEUE_HH |
| |
| #include "hb.hh" |
| #include "hb-vector.hh" |
| |
| /* |
| * hb_priority_queue_t |
| * |
| * Priority queue implemented as a binary heap. Supports extract minimum |
| * and insert operations. |
| * |
| * The priority queue is implemented as a binary heap, which is a complete |
| * binary tree. The root of the tree is the minimum element. The heap |
| * property is that the priority of a node is less than or equal to the |
| * priority of its children. The heap is stored in an array, with the |
| * children of node i stored at indices 2i + 1 and 2i + 2. |
| */ |
| template <typename K> |
| struct hb_priority_queue_t |
| { |
| private: |
| typedef hb_pair_t<K, unsigned> item_t; |
| hb_vector_t<item_t> heap; |
| |
| public: |
| |
| void reset () { heap.resize (0); } |
| |
| bool in_error () const { return heap.in_error (); } |
| |
| #ifndef HB_OPTIMIZE_SIZE |
| HB_ALWAYS_INLINE |
| #endif |
| void insert (K priority, unsigned value) |
| { |
| heap.push (item_t (priority, value)); |
| if (unlikely (heap.in_error ())) return; |
| bubble_up (heap.length - 1); |
| } |
| |
| #ifndef HB_OPTIMIZE_SIZE |
| HB_ALWAYS_INLINE |
| #endif |
| item_t pop_minimum () |
| { |
| assert (!is_empty ()); |
| |
| item_t result = heap.arrayZ[0]; |
| |
| heap.arrayZ[0] = heap.arrayZ[heap.length - 1]; |
| heap.resize (heap.length - 1); |
| |
| if (!is_empty ()) |
| bubble_down (0); |
| |
| return result; |
| } |
| |
| const item_t& minimum () |
| { |
| return heap[0]; |
| } |
| |
| bool is_empty () const { return heap.length == 0; } |
| explicit operator bool () const { return !is_empty (); } |
| unsigned int get_population () const { return heap.length; } |
| |
| /* Sink interface. */ |
| hb_priority_queue_t& operator << (item_t item) |
| { insert (item.first, item.second); return *this; } |
| |
| private: |
| |
| static constexpr unsigned parent (unsigned index) |
| { |
| return (index - 1) / 2; |
| } |
| |
| static constexpr unsigned left_child (unsigned index) |
| { |
| return 2 * index + 1; |
| } |
| |
| static constexpr unsigned right_child (unsigned index) |
| { |
| return 2 * index + 2; |
| } |
| |
| HB_ALWAYS_INLINE |
| void bubble_down (unsigned index) |
| { |
| repeat: |
| assert (index < heap.length); |
| |
| unsigned left = left_child (index); |
| unsigned right = right_child (index); |
| |
| bool has_left = left < heap.length; |
| if (!has_left) |
| // If there's no left, then there's also no right. |
| return; |
| |
| bool has_right = right < heap.length; |
| if (heap.arrayZ[index].first <= heap.arrayZ[left].first |
| && (!has_right || heap.arrayZ[index].first <= heap.arrayZ[right].first)) |
| return; |
| |
| unsigned child; |
| if (!has_right || heap.arrayZ[left].first < heap.arrayZ[right].first) |
| child = left; |
| else |
| child = right; |
| |
| swap (index, child); |
| index = child; |
| goto repeat; |
| } |
| |
| HB_ALWAYS_INLINE |
| void bubble_up (unsigned index) |
| { |
| repeat: |
| assert (index < heap.length); |
| |
| if (index == 0) return; |
| |
| unsigned parent_index = parent (index); |
| if (heap.arrayZ[parent_index].first <= heap.arrayZ[index].first) |
| return; |
| |
| swap (index, parent_index); |
| index = parent_index; |
| goto repeat; |
| } |
| |
| void swap (unsigned a, unsigned b) |
| { |
| assert (a < heap.length); |
| assert (b < heap.length); |
| hb_swap (heap.arrayZ[a], heap.arrayZ[b]); |
| } |
| }; |
| |
| #endif /* HB_PRIORITY_QUEUE_HH */ |