The Tor Browser / file comparison
comparison: js/src/ds/PriorityQueue.h
js/src/ds/PriorityQueue.h
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
equal
deleted
inserted
replaced
| -1:000000000000 | 0:73f91b680ed3 |
|---|---|
| 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/. */ | |
| 6 | |
| 7 #ifndef ds_PriorityQueue_h | |
| 8 #define ds_PriorityQueue_h | |
| 9 | |
| 10 #include "js/Vector.h" | |
| 11 | |
| 12 namespace js { | |
| 13 | |
| 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; | |
| 28 | |
| 29 PriorityQueue(const PriorityQueue &) MOZ_DELETE; | |
| 30 PriorityQueue &operator=(const PriorityQueue &) MOZ_DELETE; | |
| 31 | |
| 32 public: | |
| 33 | |
| 34 PriorityQueue(AllocPolicy ap = AllocPolicy()) | |
| 35 : heap(ap) | |
| 36 {} | |
| 37 | |
| 38 bool reserve(size_t capacity) { | |
| 39 return heap.reserve(capacity); | |
| 40 } | |
| 41 | |
| 42 size_t length() const { | |
| 43 return heap.length(); | |
| 44 } | |
| 45 | |
| 46 bool empty() const { | |
| 47 return heap.empty(); | |
| 48 } | |
| 49 | |
| 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 } | |
| 59 | |
| 60 bool insert(const T &v) { | |
| 61 if (!heap.append(v)) | |
| 62 return false; | |
| 63 siftUp(heap.length() - 1); | |
| 64 return true; | |
| 65 } | |
| 66 | |
| 67 void infallibleInsert(const T &v) { | |
| 68 heap.infallibleAppend(v); | |
| 69 siftUp(heap.length() - 1); | |
| 70 } | |
| 71 | |
| 72 private: | |
| 73 | |
| 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 */ | |
| 86 | |
| 87 void siftDown(size_t n) { | |
| 88 while (true) { | |
| 89 size_t left = n * 2 + 1; | |
| 90 size_t right = n * 2 + 2; | |
| 91 | |
| 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 } | |
| 102 | |
| 103 if (P::priority(heap[n]) < P::priority(heap[left])) { | |
| 104 swap(n, left); | |
| 105 n = left; | |
| 106 continue; | |
| 107 } | |
| 108 } | |
| 109 | |
| 110 break; | |
| 111 } | |
| 112 } | |
| 113 | |
| 114 void siftUp(size_t n) { | |
| 115 while (n > 0) { | |
| 116 size_t parent = (n - 1) / 2; | |
| 117 | |
| 118 if (P::priority(heap[parent]) > P::priority(heap[n])) | |
| 119 break; | |
| 120 | |
| 121 swap(n, parent); | |
| 122 n = parent; | |
| 123 } | |
| 124 } | |
| 125 | |
| 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 }; | |
| 132 | |
| 133 } /* namespace js */ | |
| 134 | |
| 135 #endif /* ds_PriorityQueue_h */ |
