#pragma once
#include <wtf/MathExtras.h>
#include <wtf/Vector.h>
namespace WTF {
template<typename T, bool (*isHigherPriority)(const T&, const T&) = &isLessThan<T>, size_t inlineCapacity = 0>
class PriorityQueue final {
WTF_MAKE_FAST_ALLOCATED;
using BufferType = Vector<T, inlineCapacity>;
using const_iterator = typename BufferType::const_iterator;
public:
size_t size() const { return m_buffer.size(); }
bool isEmpty() const { return m_buffer.isEmpty(); }
void enqueue(T element)
{
size_t location = m_buffer.size();
m_buffer.append(std::forward<T>(element));
siftUp(location);
}
const T& peek() const { return m_buffer[0]; }
T dequeue()
{
std::swap(m_buffer[0], m_buffer.last());
T result = m_buffer.takeLast();
siftDown(0);
return result;
}
template<typename Functor>
void decreaseKey(const Functor& desiredElement)
{
for (size_t i = 0; i < m_buffer.size(); ++i) {
if (desiredElement(m_buffer[i])) {
siftDown(i);
return;
}
}
ASSERT(isValidHeap());
}
template<typename Functor>
void increaseKey(const Functor& desiredElement)
{
for (size_t i = 0; i < m_buffer.size(); ++i) {
if (desiredElement(m_buffer[i])) {
siftUp(i);
return;
}
}
ASSERT(isValidHeap());
}
const_iterator begin() const { return m_buffer.begin(); };
const_iterator end() const { return m_buffer.end(); };
bool isValidHeap() const
{
for (size_t i = 0; i < m_buffer.size(); ++i) {
if (leftChildOf(i) < m_buffer.size() && !isHigherPriority(m_buffer[i], m_buffer[leftChildOf(i)]))
return false;
if (rightChildOf(i) < m_buffer.size() && !isHigherPriority(m_buffer[i], m_buffer[rightChildOf(i)]))
return false;
}
return true;
}
protected:
static inline size_t parentOf(size_t location) { ASSERT(location); return (location - 1) / 2; }
static constexpr size_t leftChildOf(size_t location) { return location * 2 + 1; }
static constexpr size_t rightChildOf(size_t location) { return leftChildOf(location) + 1; }
void siftUp(size_t location)
{
while (location) {
auto parent = parentOf(location);
if (isHigherPriority(m_buffer[parent], m_buffer[location]))
return;
std::swap(m_buffer[parent], m_buffer[location]);
location = parent;
}
}
void siftDown(size_t location)
{
while (leftChildOf(location) < m_buffer.size()) {
size_t higherPriorityChild;
if (LIKELY(rightChildOf(location) < m_buffer.size()))
higherPriorityChild = isHigherPriority(m_buffer[leftChildOf(location)], m_buffer[rightChildOf(location)]) ? leftChildOf(location) : rightChildOf(location);
else
higherPriorityChild = leftChildOf(location);
if (isHigherPriority(m_buffer[location], m_buffer[higherPriorityChild]))
return;
std::swap(m_buffer[location], m_buffer[higherPriorityChild]);
location = higherPriorityChild;
}
}
Vector<T, inlineCapacity> m_buffer;
};
}
using WTF::PriorityQueue;