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