summaryrefslogtreecommitdiffstats
path: root/js/src/ds/PriorityQueue.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--js/src/ds/PriorityQueue.h125
1 files changed, 125 insertions, 0 deletions
diff --git a/js/src/ds/PriorityQueue.h b/js/src/ds/PriorityQueue.h
new file mode 100644
index 0000000000..439c2075a4
--- /dev/null
+++ b/js/src/ds/PriorityQueue.h
@@ -0,0 +1,125 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef ds_PriorityQueue_h
+#define ds_PriorityQueue_h
+
+#include "js/Vector.h"
+
+namespace js {
+
+/*
+ * Class which represents a heap based priority queue using a vector.
+ * Inserting elements and removing the highest priority one are both O(log n).
+ *
+ * Template parameters are the same as for Vector, with the addition that P
+ * must have a static priority(const T&) method which returns higher numbers
+ * for higher priority elements.
+ */
+template <class T, class P, size_t MinInlineCapacity = 0,
+ class AllocPolicy = TempAllocPolicy>
+class PriorityQueue {
+ Vector<T, MinInlineCapacity, AllocPolicy> heap;
+
+ PriorityQueue(const PriorityQueue&) = delete;
+ PriorityQueue& operator=(const PriorityQueue&) = delete;
+
+ public:
+ explicit PriorityQueue(AllocPolicy ap = AllocPolicy())
+ : heap(std::move(ap)) {}
+
+ MOZ_MUST_USE bool reserve(size_t capacity) { return heap.reserve(capacity); }
+
+ size_t length() const { return heap.length(); }
+
+ bool empty() const { return heap.empty(); }
+
+ T removeHighest() {
+ T highest = heap[0];
+ T last = heap.popCopy();
+ if (!heap.empty()) {
+ heap[0] = last;
+ siftDown(0);
+ }
+ return highest;
+ }
+
+ MOZ_MUST_USE bool insert(const T& v) {
+ if (!heap.append(v)) {
+ return false;
+ }
+ siftUp(heap.length() - 1);
+ return true;
+ }
+
+ void infallibleInsert(const T& v) {
+ heap.infallibleAppend(v);
+ siftUp(heap.length() - 1);
+ }
+
+ private:
+ /*
+ * Elements of the vector encode a binary tree:
+ *
+ * 0
+ * 1 2
+ * 3 4 5 6
+ *
+ * The children of element N are (2N + 1) and (2N + 2).
+ * The parent of element N is (N - 1) / 2.
+ *
+ * Each element has higher priority than its children.
+ */
+
+ void siftDown(size_t n) {
+ while (true) {
+ size_t left = n * 2 + 1;
+ size_t right = n * 2 + 2;
+
+ if (left < heap.length()) {
+ if (right < heap.length()) {
+ if (P::priority(heap[n]) < P::priority(heap[right]) &&
+ P::priority(heap[left]) < P::priority(heap[right])) {
+ swap(n, right);
+ n = right;
+ continue;
+ }
+ }
+
+ if (P::priority(heap[n]) < P::priority(heap[left])) {
+ swap(n, left);
+ n = left;
+ continue;
+ }
+ }
+
+ break;
+ }
+ }
+
+ void siftUp(size_t n) {
+ while (n > 0) {
+ size_t parent = (n - 1) / 2;
+
+ if (P::priority(heap[parent]) > P::priority(heap[n])) {
+ break;
+ }
+
+ swap(n, parent);
+ n = parent;
+ }
+ }
+
+ void swap(size_t a, size_t b) {
+ T tmp = heap[a];
+ heap[a] = heap[b];
+ heap[b] = tmp;
+ }
+};
+
+} /* namespace js */
+
+#endif /* ds_PriorityQueue_h */