DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (31ec81b5d7bb)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef ds_PriorityQueue_h
#define ds_PriorityQueue_h

#include "js/Vector.h"

namespace js {

/*
 * Class which represents a heap based priority queue using a vector.
 * Inserting elements and removing the highest priority one are both O(log n).
 *
 * Template parameters are the same as for Vector, with the addition that P
 * must have a static priority(const T&) method which returns higher numbers
 * for higher priority elements.
 */
template <class T, class P,
          size_t MinInlineCapacity = 0,
          class AllocPolicy = TempAllocPolicy>
class PriorityQueue
{
    Vector<T, MinInlineCapacity, AllocPolicy> heap;

    PriorityQueue(const PriorityQueue &) MOZ_DELETE;
    PriorityQueue &operator=(const PriorityQueue &) MOZ_DELETE;

  public:

    PriorityQueue(AllocPolicy ap = AllocPolicy())
      : heap(ap)
    {}

    bool reserve(size_t capacity) {
        return heap.reserve(capacity);
    }

    size_t length() const {
        return heap.length();
    }

    bool empty() const {
        return heap.empty();
    }

    T removeHighest() {
        T highest = heap[0];
        T last = heap.popCopy();
        if (!heap.empty()) {
            heap[0] = last;
            siftDown(0);
        }
        return highest;
    }

    bool insert(const T &v) {
        if (!heap.append(v))
            return false;
        siftUp(heap.length() - 1);
        return true;
    }

    void infallibleInsert(const T &v) {
        heap.infallibleAppend(v);
        siftUp(heap.length() - 1);
    }

  private:

    /*
     * Elements of the vector encode a binary tree:
     *
     *      0
     *    1   2
     *   3 4 5 6
     *
     * The children of element N are (2N + 1) and (2N + 2).
     * The parent of element N is (N - 1) / 2.
     *
     * Each element has higher priority than its children.
     */

    void siftDown(size_t n) {
        while (true) {
            size_t left = n * 2 + 1;
            size_t right = n * 2 + 2;

            if (left < heap.length()) {
                if (right < heap.length()) {
                    if (P::priority(heap[n]) < P::priority(heap[right]) &&
                        P::priority(heap[left]) < P::priority(heap[right]))
                    {
                        swap(n, right);
                        n = right;
                        continue;
                    }
                }

                if (P::priority(heap[n]) < P::priority(heap[left])) {
                    swap(n, left);
                    n = left;
                    continue;
                }
            }

            break;
        }
    }

    void siftUp(size_t n) {
        while (n > 0) {
            size_t parent = (n - 1) / 2;

            if (P::priority(heap[parent]) > P::priority(heap[n]))
                break;

            swap(n, parent);
            n = parent;
        }
    }

    void swap(size_t a, size_t b) {
        T tmp = heap[a];
        heap[a] = heap[b];
        heap[b] = tmp;
    }
};

}  /* namespace js */

#endif /* ds_PriorityQueue_h */