Line data    Source code

       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           8 : class PriorityQueue
      26             : {
      27             :     Vector<T, MinInlineCapacity, AllocPolicy> heap;
      28             : 
      29             :     PriorityQueue(const PriorityQueue&) = delete;
      30             :     PriorityQueue& operator=(const PriorityQueue&) = delete;
      31             : 
      32             :   public:
      33             : 
      34           8 :     explicit PriorityQueue(AllocPolicy ap = AllocPolicy())
      35           8 :       : heap(ap)
      36           8 :     {}
      37             : 
      38           8 :     MOZ_MUST_USE bool reserve(size_t capacity) {
      39           8 :         return heap.reserve(capacity);
      40             :     }
      41             : 
      42             :     size_t length() const {
      43             :         return heap.length();
      44             :     }
      45             : 
      46        1446 :     bool empty() const {
      47        1446 :         return heap.empty();
      48             :     }
      49             : 
      50        1438 :     T removeHighest() {
      51        1438 :         T highest = heap[0];
      52        1438 :         T last = heap.popCopy();
      53        1438 :         if (!heap.empty()) {
      54        1430 :             heap[0] = last;
      55        1430 :             siftDown(0);
      56             :         }
      57        1438 :         return highest;
      58             :     }
      59             : 
      60        1438 :     MOZ_MUST_USE bool insert(const T& v) {
      61        1438 :         if (!heap.append(v))
      62           0 :             return false;
      63        1438 :         siftUp(heap.length() - 1);
      64        1438 :         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        7521 :     void siftDown(size_t n) {
      88        6091 :         while (true) {
      89        7521 :             size_t left = n * 2 + 1;
      90        7521 :             size_t right = n * 2 + 2;
      91             : 
      92        7521 :             if (left < heap.length()) {
      93        6928 :                 if (right < heap.length()) {
      94       12655 :                     if (P::priority(heap[n]) < P::priority(heap[right]) &&
      95        5840 :                         P::priority(heap[left]) < P::priority(heap[right]))
      96             :                     {
      97        2807 :                         swap(n, right);
      98        2807 :                         n = right;
      99        2807 :                         continue;
     100             :                     }
     101             :                 }
     102             : 
     103        4121 :                 if (P::priority(heap[n]) < P::priority(heap[left])) {
     104        3284 :                     swap(n, left);
     105        3284 :                     n = left;
     106        3284 :                     continue;
     107             :                 }
     108             :             }
     109             : 
     110        1430 :             break;
     111             :         }
     112        1430 :     }
     113             : 
     114        4270 :     void siftUp(size_t n) {
     115        7102 :         while (n > 0) {
     116        4041 :             size_t parent = (n - 1) / 2;
     117             : 
     118        4041 :             if (P::priority(heap[parent]) > P::priority(heap[n]))
     119        1209 :                 break;
     120             : 
     121        2832 :             swap(n, parent);
     122        2832 :             n = parent;
     123             :         }
     124        1438 :     }
     125             : 
     126        8923 :     void swap(size_t a, size_t b) {
     127        8923 :         T tmp = heap[a];
     128        8923 :         heap[a] = heap[b];
     129        8923 :         heap[b] = tmp;
     130        8923 :     }
     131             : };
     132             : 
     133             : }  /* namespace js */
     134             : 
     135             : #endif /* ds_PriorityQueue_h */