1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/xpcom/glue/nsTPriorityQueue.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,171 @@
1.4 +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
1.5 +/* vim:set ts=2 sw=2 sts=2 et cindent: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef NS_TPRIORITY_QUEUE_H_
1.11 +#define NS_TPRIORITY_QUEUE_H_
1.12 +
1.13 +#include "nsTArray.h"
1.14 +#include "nsDebug.h"
1.15 +
1.16 +/**
1.17 + * A templatized priority queue data structure that uses an nsTArray to serve as
1.18 + * a binary heap. The default comparator causes this to act like a min-heap.
1.19 + * Only the LessThan method of the comparator is used.
1.20 + */
1.21 +template<class T, class Compare = nsDefaultComparator<T, T> >
1.22 +class nsTPriorityQueue
1.23 +{
1.24 +public:
1.25 + typedef typename nsTArray<T>::size_type size_type;
1.26 +
1.27 + /**
1.28 + * Default constructor also creates a comparator object using the default
1.29 + * constructor for type Compare.
1.30 + */
1.31 + nsTPriorityQueue() : mCompare(Compare()) { }
1.32 +
1.33 + /**
1.34 + * Constructor to allow a specific instance of a comparator object to be
1.35 + * used.
1.36 + */
1.37 + nsTPriorityQueue(const Compare& aComp) : mCompare(aComp) { }
1.38 +
1.39 + /**
1.40 + * Copy constructor
1.41 + */
1.42 + nsTPriorityQueue(const nsTPriorityQueue& aOther)
1.43 + : mElements(aOther.mElements),
1.44 + mCompare(aOther.mCompare)
1.45 + { }
1.46 +
1.47 + /**
1.48 + * @return True if the queue is empty or false otherwise.
1.49 + */
1.50 + bool IsEmpty() const
1.51 + {
1.52 + return mElements.IsEmpty();
1.53 + }
1.54 +
1.55 + /**
1.56 + * @return The number of elements in the queue.
1.57 + */
1.58 + size_type Length() const
1.59 + {
1.60 + return mElements.Length();
1.61 + }
1.62 +
1.63 + /**
1.64 + * @return The topmost element in the queue without changing the queue. This
1.65 + * is the element 'a' such that there is no other element 'b' in the queue for
1.66 + * which Compare(b, a) returns true. (Since this container does not check
1.67 + * for duplicate entries there may exist 'b' for which Compare(a, b) returns
1.68 + * false.)
1.69 + */
1.70 + const T& Top() const
1.71 + {
1.72 + NS_ABORT_IF_FALSE(!mElements.IsEmpty(), "Empty queue");
1.73 + return mElements[0];
1.74 + }
1.75 +
1.76 + /**
1.77 + * Adds an element to the queue
1.78 + * @param aElement The element to add
1.79 + * @return true on success, false on out of memory.
1.80 + */
1.81 + bool Push(const T& aElement)
1.82 + {
1.83 + T* elem = mElements.AppendElement(aElement);
1.84 + if (!elem)
1.85 + return false; // Out of memory
1.86 +
1.87 + // Sift up
1.88 + size_type i = mElements.Length() - 1;
1.89 + while (i) {
1.90 + size_type parent = (size_type)((i - 1) / 2);
1.91 + if (mCompare.LessThan(mElements[parent], mElements[i])) {
1.92 + break;
1.93 + }
1.94 + Swap(i, parent);
1.95 + i = parent;
1.96 + }
1.97 +
1.98 + return true;
1.99 + }
1.100 +
1.101 + /**
1.102 + * Removes and returns the top-most element from the queue.
1.103 + * @return The topmost element, that is, the element 'a' such that there is no
1.104 + * other element 'b' in the queue for which Compare(b, a) returns true.
1.105 + * @see Top()
1.106 + */
1.107 + T Pop()
1.108 + {
1.109 + NS_ABORT_IF_FALSE(!mElements.IsEmpty(), "Empty queue");
1.110 + T pop = mElements[0];
1.111 +
1.112 + // Move last to front
1.113 + mElements[0] = mElements[mElements.Length() - 1];
1.114 + mElements.TruncateLength(mElements.Length() - 1);
1.115 +
1.116 + // Sift down
1.117 + size_type i = 0;
1.118 + while (2*i + 1 < mElements.Length()) {
1.119 + size_type swap = i;
1.120 + size_type l_child = 2*i + 1;
1.121 + if (mCompare.LessThan(mElements[l_child], mElements[i])) {
1.122 + swap = l_child;
1.123 + }
1.124 + size_type r_child = l_child + 1;
1.125 + if (r_child < mElements.Length() &&
1.126 + mCompare.LessThan(mElements[r_child], mElements[swap])) {
1.127 + swap = r_child;
1.128 + }
1.129 + if (swap == i) {
1.130 + break;
1.131 + }
1.132 + Swap(i, swap);
1.133 + i = swap;
1.134 + }
1.135 +
1.136 + return pop;
1.137 + }
1.138 +
1.139 + /**
1.140 + * Removes all elements from the queue.
1.141 + */
1.142 + void Clear()
1.143 + {
1.144 + mElements.Clear();
1.145 + }
1.146 +
1.147 + /**
1.148 + * Provides readonly access to the queue elements as an array. Generally this
1.149 + * should be avoided but may be needed in some situations such as when the
1.150 + * elements contained in the queue need to be enumerated for cycle-collection.
1.151 + * @return A pointer to the first element of the array. If the array is
1.152 + * empty, then this pointer must not be dereferenced.
1.153 + */
1.154 + const T* Elements() const
1.155 + {
1.156 + return mElements.Elements();
1.157 + }
1.158 +
1.159 +protected:
1.160 + /**
1.161 + * Swaps the elements at the specified indices.
1.162 + */
1.163 + void Swap(size_type aIndexA, size_type aIndexB)
1.164 + {
1.165 + T temp = mElements[aIndexA];
1.166 + mElements[aIndexA] = mElements[aIndexB];
1.167 + mElements[aIndexB] = temp;
1.168 + }
1.169 +
1.170 + nsTArray<T> mElements;
1.171 + Compare mCompare; // Comparator object
1.172 +};
1.173 +
1.174 +#endif // NS_TPRIORITY_QUEUE_H_
