1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/ds/PriorityQueue.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,135 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef ds_PriorityQueue_h
1.11 +#define ds_PriorityQueue_h
1.12 +
1.13 +#include "js/Vector.h"
1.14 +
1.15 +namespace js {
1.16 +
1.17 +/*
1.18 + * Class which represents a heap based priority queue using a vector.
1.19 + * Inserting elements and removing the highest priority one are both O(log n).
1.20 + *
1.21 + * Template parameters are the same as for Vector, with the addition that P
1.22 + * must have a static priority(const T&) method which returns higher numbers
1.23 + * for higher priority elements.
1.24 + */
1.25 +template <class T, class P,
1.26 + size_t MinInlineCapacity = 0,
1.27 + class AllocPolicy = TempAllocPolicy>
1.28 +class PriorityQueue
1.29 +{
1.30 + Vector<T, MinInlineCapacity, AllocPolicy> heap;
1.31 +
1.32 + PriorityQueue(const PriorityQueue &) MOZ_DELETE;
1.33 + PriorityQueue &operator=(const PriorityQueue &) MOZ_DELETE;
1.34 +
1.35 + public:
1.36 +
1.37 + PriorityQueue(AllocPolicy ap = AllocPolicy())
1.38 + : heap(ap)
1.39 + {}
1.40 +
1.41 + bool reserve(size_t capacity) {
1.42 + return heap.reserve(capacity);
1.43 + }
1.44 +
1.45 + size_t length() const {
1.46 + return heap.length();
1.47 + }
1.48 +
1.49 + bool empty() const {
1.50 + return heap.empty();
1.51 + }
1.52 +
1.53 + T removeHighest() {
1.54 + T highest = heap[0];
1.55 + T last = heap.popCopy();
1.56 + if (!heap.empty()) {
1.57 + heap[0] = last;
1.58 + siftDown(0);
1.59 + }
1.60 + return highest;
1.61 + }
1.62 +
1.63 + bool insert(const T &v) {
1.64 + if (!heap.append(v))
1.65 + return false;
1.66 + siftUp(heap.length() - 1);
1.67 + return true;
1.68 + }
1.69 +
1.70 + void infallibleInsert(const T &v) {
1.71 + heap.infallibleAppend(v);
1.72 + siftUp(heap.length() - 1);
1.73 + }
1.74 +
1.75 + private:
1.76 +
1.77 + /*
1.78 + * Elements of the vector encode a binary tree:
1.79 + *
1.80 + * 0
1.81 + * 1 2
1.82 + * 3 4 5 6
1.83 + *
1.84 + * The children of element N are (2N + 1) and (2N + 2).
1.85 + * The parent of element N is (N - 1) / 2.
1.86 + *
1.87 + * Each element has higher priority than its children.
1.88 + */
1.89 +
1.90 + void siftDown(size_t n) {
1.91 + while (true) {
1.92 + size_t left = n * 2 + 1;
1.93 + size_t right = n * 2 + 2;
1.94 +
1.95 + if (left < heap.length()) {
1.96 + if (right < heap.length()) {
1.97 + if (P::priority(heap[n]) < P::priority(heap[right]) &&
1.98 + P::priority(heap[left]) < P::priority(heap[right]))
1.99 + {
1.100 + swap(n, right);
1.101 + n = right;
1.102 + continue;
1.103 + }
1.104 + }
1.105 +
1.106 + if (P::priority(heap[n]) < P::priority(heap[left])) {
1.107 + swap(n, left);
1.108 + n = left;
1.109 + continue;
1.110 + }
1.111 + }
1.112 +
1.113 + break;
1.114 + }
1.115 + }
1.116 +
1.117 + void siftUp(size_t n) {
1.118 + while (n > 0) {
1.119 + size_t parent = (n - 1) / 2;
1.120 +
1.121 + if (P::priority(heap[parent]) > P::priority(heap[n]))
1.122 + break;
1.123 +
1.124 + swap(n, parent);
1.125 + n = parent;
1.126 + }
1.127 + }
1.128 +
1.129 + void swap(size_t a, size_t b) {
1.130 + T tmp = heap[a];
1.131 + heap[a] = heap[b];
1.132 + heap[b] = tmp;
1.133 + }
1.134 +};
1.135 +
1.136 +} /* namespace js */
1.137 +
1.138 +#endif /* ds_PriorityQueue_h */
