xpcom/ds/nsTPriorityQueue.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   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 NS_TPRIORITY_QUEUE_H_
   8 #define NS_TPRIORITY_QUEUE_H_
   9
  10 #include "nsTArray.h"
  11 #include "nsDebug.h"
  12
  13 /**
  14  * A templatized priority queue data structure that uses an nsTArray to serve as
  15  * a binary heap. The default comparator causes this to act like a min-heap.
  16  * Only the LessThan method of the comparator is used.
  17  */
  18 template<class T, class Compare = nsDefaultComparator<T, T>>
  19 class nsTPriorityQueue
  20 {
  21 public:
  22   typedef typename nsTArray<T>::size_type size_type;
  23
  24   /**
  25    * Default constructor also creates a comparator object using the default
  26    * constructor for type Compare.
  27    */
  28   nsTPriorityQueue() : mCompare(Compare()) {}
  29
  30   /**
  31    * Constructor to allow a specific instance of a comparator object to be
  32    * used.
  33    */
  34   explicit nsTPriorityQueue(const Compare& aComp) : mCompare(aComp) {}
  35
  36   /**
  37    * Copy constructor
  38    */
  39   nsTPriorityQueue(const nsTPriorityQueue& aOther)
  40     : mElements(aOther.mElements)
  41     , mCompare(aOther.mCompare)
  42   {
  43   }
  44
  45   /**
  46    * @return True if the queue is empty or false otherwise.
  47    */
  48   bool IsEmpty() const { return mElements.IsEmpty(); }
  49
  50   /**
  51    * @return The number of elements in the queue.
  52    */
  53   size_type Length() const { return mElements.Length(); }
  54
  55   /**
  56    * @return The topmost element in the queue without changing the queue. This
  57    * is the element 'a' such that there is no other element 'b' in the queue for
  58    * which Compare(b, a) returns true. (Since this container does not check
  59    * for duplicate entries there may exist 'b' for which Compare(a, b) returns
  60    * false.)
  61    */
  62   const T& Top() const
  63   {
  64     MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
  65     return mElements[0];
  66   }
  67
  68   /**
  69    * Adds an element to the queue
  70    * @param aElement The element to add
  71    * @return true on success, false on out of memory.
  72    */
  73   bool Push(const T& aElement)
  74   {
  75     T* elem = mElements.AppendElement(aElement);
  76     if (!elem) {
  77       return false;  // Out of memory
  78     }
  79
  80     // Sift up
  81     size_type i = mElements.Length() - 1;
  82     while (i) {
  83       size_type parent = (size_type)((i - 1) / 2);
  84       if (mCompare.LessThan(mElements[parent], mElements[i])) {
  85         break;
  86       }
  87       Swap(i, parent);
  88       i = parent;
  89     }
  90
  91     return true;
  92   }
  93
  94   /**
  95    * Removes and returns the top-most element from the queue.
  96    * @return The topmost element, that is, the element 'a' such that there is no
  97    * other element 'b' in the queue for which Compare(b, a) returns true.
  98    * @see Top()
  99    */
 100   T Pop()
 101   {
 102     MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
 103     T pop = mElements[0];
 104
 105     // Move last to front
 106     mElements[0] = mElements[mElements.Length() - 1];
 107     mElements.TruncateLength(mElements.Length() - 1);
 108
 109     // Sift down
 110     size_type i = 0;
 111     while (2 * i + 1 < mElements.Length()) {
 112       size_type swap = i;
 113       size_type l_child = 2 * i + 1;
 114       if (mCompare.LessThan(mElements[l_child], mElements[i])) {
 115         swap = l_child;
 116       }
 117       size_type r_child = l_child + 1;
 118       if (r_child < mElements.Length() &&
 119           mCompare.LessThan(mElements[r_child], mElements[swap])) {
 120         swap = r_child;
 121       }
 122       if (swap == i) {
 123         break;
 124       }
 125       Swap(i, swap);
 126       i = swap;
 127     }
 128
 129     return pop;
 130   }
 131
 132   /**
 133    * Removes all elements from the queue.
 134    */
 135   void Clear() { mElements.Clear(); }
 136
 137   /**
 138    * Provides readonly access to the queue elements as an array. Generally this
 139    * should be avoided but may be needed in some situations such as when the
 140    * elements contained in the queue need to be enumerated for cycle-collection.
 141    * @return A pointer to the first element of the array.  If the array is
 142    * empty, then this pointer must not be dereferenced.
 143    */
 144   const T* Elements() const { return mElements.Elements(); }
 145
 146 protected:
 147   /**
 148    * Swaps the elements at the specified indices.
 149    */
 150   void Swap(size_type aIndexA, size_type aIndexB)
 151   {
 152     T temp = mElements[aIndexA];
 153     mElements[aIndexA] = mElements[aIndexB];
 154     mElements[aIndexB] = temp;
 155   }
 156
 157   nsTArray<T> mElements;
 158   Compare mCompare; // Comparator object
 159 };
 160
 161 #endif // NS_TPRIORITY_QUEUE_H_