/* -*- 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 */