blob: baac7e1e69576269e9f8363eb66e60da059126f1 [file] [log] [blame]
/*
* 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.
*/
struct hb_priority_queue_t
{
private:
typedef hb_pair_t<int64_t, 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 (int64_t 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 */