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