js/src/ds/PriorityQueue.h@6474c204b198
js/src/ds/PriorityQueue.h
Wed, 31 Dec 2014 06:09:35 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Wed, 31 Dec 2014 06:09:35 +0100
- changeset 0
- 6474c204b198
- permissions
- -rw-r--r--
Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
7 #ifndef ds_PriorityQueue_h
8 #define ds_PriorityQueue_h
10 #include "js/Vector.h"
12 namespace js {
14 /*
15 * Class which represents a heap based priority queue using a vector.
16 * Inserting elements and removing the highest priority one are both O(log n).
17 *
18 * Template parameters are the same as for Vector, with the addition that P
19 * must have a static priority(const T&) method which returns higher numbers
20 * for higher priority elements.
21 */
22 template <class T, class P,
23 size_t MinInlineCapacity = 0,
24 class AllocPolicy = TempAllocPolicy>
25 class PriorityQueue
26 {
27 Vector<T, MinInlineCapacity, AllocPolicy> heap;
29 PriorityQueue(const PriorityQueue &) MOZ_DELETE;
30 PriorityQueue &operator=(const PriorityQueue &) MOZ_DELETE;
32 public:
34 PriorityQueue(AllocPolicy ap = AllocPolicy())
35 : heap(ap)
36 {}
38 bool reserve(size_t capacity) {
39 return heap.reserve(capacity);
40 }
42 size_t length() const {
43 return heap.length();
44 }
46 bool empty() const {
47 return heap.empty();
48 }
50 T removeHighest() {
51 T highest = heap[0];
52 T last = heap.popCopy();
53 if (!heap.empty()) {
54 heap[0] = last;
55 siftDown(0);
56 }
57 return highest;
58 }
60 bool insert(const T &v) {
61 if (!heap.append(v))
62 return false;
63 siftUp(heap.length() - 1);
64 return true;
65 }
67 void infallibleInsert(const T &v) {
68 heap.infallibleAppend(v);
69 siftUp(heap.length() - 1);
70 }
72 private:
74 /*
75 * Elements of the vector encode a binary tree:
76 *
77 * 0
78 * 1 2
79 * 3 4 5 6
80 *
81 * The children of element N are (2N + 1) and (2N + 2).
82 * The parent of element N is (N - 1) / 2.
83 *
84 * Each element has higher priority than its children.
85 */
87 void siftDown(size_t n) {
88 while (true) {
89 size_t left = n * 2 + 1;
90 size_t right = n * 2 + 2;
92 if (left < heap.length()) {
93 if (right < heap.length()) {
94 if (P::priority(heap[n]) < P::priority(heap[right]) &&
95 P::priority(heap[left]) < P::priority(heap[right]))
96 {
97 swap(n, right);
98 n = right;
99 continue;
100 }
101 }
103 if (P::priority(heap[n]) < P::priority(heap[left])) {
104 swap(n, left);
105 n = left;
106 continue;
107 }
108 }
110 break;
111 }
112 }
114 void siftUp(size_t n) {
115 while (n > 0) {
116 size_t parent = (n - 1) / 2;
118 if (P::priority(heap[parent]) > P::priority(heap[n]))
119 break;
121 swap(n, parent);
122 n = parent;
123 }
124 }
126 void swap(size_t a, size_t b) {
127 T tmp = heap[a];
128 heap[a] = heap[b];
129 heap[b] = tmp;
130 }
131 };
133 } /* namespace js */
135 #endif /* ds_PriorityQueue_h */
