1/*
2 * Copyright (C) 2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/MathExtras.h>
29#include <wtf/Vector.h>
30
31namespace WTF {
32
33// This class implements a basic priority queue. The class is backed as a binary heap, like std::priority_queue.
34// PriorityQueue has a couple of advantages over std::priority_queue:
35//
36// 1) The backing vector is fastMalloced.
37// 2) You can iterate the elements.
38// 3) It has in-place decrease/increaseKey methods, although they are still O(n) rather than O(log(n)).
39
40template<typename T, bool (*isHigherPriority)(const T&, const T&) = &isLessThan<T>, size_t inlineCapacity = 0>
41class PriorityQueue {
42 using BufferType = Vector<T, inlineCapacity>;
43 using const_iterator = typename BufferType::const_iterator;
44public:
45 size_t size() const { return m_buffer.size(); }
46 bool isEmpty() const { return m_buffer.isEmpty(); }
47
48 void enqueue(T element)
49 {
50 size_t location = m_buffer.size();
51 m_buffer.append(std::forward<T>(element));
52 siftUp(location);
53 }
54
55 const T& peek() const { return m_buffer[0]; }
56 T dequeue()
57 {
58 std::swap(m_buffer[0], m_buffer.last());
59 T result = m_buffer.takeLast();
60 siftDown(0);
61 return result;
62 }
63
64 template<typename Functor>
65 void decreaseKey(const Functor& desiredElement)
66 {
67 for (size_t i = 0; i < m_buffer.size(); ++i) {
68 if (desiredElement(m_buffer[i])) {
69 siftDown(i);
70 return;
71 }
72 }
73 ASSERT(isValidHeap());
74 }
75
76 template<typename Functor>
77 void increaseKey(const Functor& desiredElement)
78 {
79 for (size_t i = 0; i < m_buffer.size(); ++i) {
80 if (desiredElement(m_buffer[i])) {
81 siftUp(i);
82 return;
83 }
84 }
85 ASSERT(isValidHeap());
86 }
87
88 const_iterator begin() const { return m_buffer.begin(); };
89 const_iterator end() const { return m_buffer.end(); };
90
91 bool isValidHeap() const
92 {
93 for (size_t i = 0; i < m_buffer.size(); ++i) {
94 if (leftChildOf(i) < m_buffer.size() && !isHigherPriority(m_buffer[i], m_buffer[leftChildOf(i)]))
95 return false;
96 if (rightChildOf(i) < m_buffer.size() && !isHigherPriority(m_buffer[i], m_buffer[rightChildOf(i)]))
97 return false;
98 }
99 return true;
100 }
101
102protected:
103 static inline size_t parentOf(size_t location) { ASSERT(location); return (location - 1) / 2; }
104 static constexpr size_t leftChildOf(size_t location) { return location * 2 + 1; }
105 static constexpr size_t rightChildOf(size_t location) { return leftChildOf(location) + 1; }
106
107 void siftUp(size_t location)
108 {
109 while (location) {
110 auto parent = parentOf(location);
111 if (isHigherPriority(m_buffer[parent], m_buffer[location]))
112 return;
113
114 std::swap(m_buffer[parent], m_buffer[location]);
115 location = parent;
116 }
117 }
118
119 void siftDown(size_t location)
120 {
121 while (leftChildOf(location) < m_buffer.size()) {
122 size_t higherPriorityChild;
123 if (LIKELY(rightChildOf(location) < m_buffer.size()))
124 higherPriorityChild = isHigherPriority(m_buffer[leftChildOf(location)], m_buffer[rightChildOf(location)]) ? leftChildOf(location) : rightChildOf(location);
125 else
126 higherPriorityChild = leftChildOf(location);
127
128 if (isHigherPriority(m_buffer[location], m_buffer[higherPriorityChild]))
129 return;
130
131 std::swap(m_buffer[location], m_buffer[higherPriorityChild]);
132 location = higherPriorityChild;
133 }
134 }
135
136 Vector<T, inlineCapacity> m_buffer;
137};
138
139} // namespace WTF
140
141using WTF::PriorityQueue;
142