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 "mozilla/Assertions.h"
  11 #include "nsTArray.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  public:
  21   typedef typename nsTArray<T>::size_type size_type;
  22
  23   /**
  24    * Default constructor also creates a comparator object using the default
  25    * constructor for type Compare.
  26    */
  27   nsTPriorityQueue() : mCompare(Compare()) {}
  28
  29   /**
  30    * Constructor to allow a specific instance of a comparator object to be
  31    * used.
  32    */
  33   explicit nsTPriorityQueue(const Compare& aComp) : mCompare(aComp) {}
  34
  35   nsTPriorityQueue(nsTPriorityQueue&&) = default;
  36   nsTPriorityQueue& operator=(nsTPriorityQueue&&) = default;
  37
  38   /**
  39    * @return True if the queue is empty or false otherwise.
  40    */
  41   bool IsEmpty() const { return mElements.IsEmpty(); }
  42
  43   /**
  44    * @return The number of elements in the queue.
  45    */
  46   size_type Length() const { return mElements.Length(); }
  47
  48   /**
  49    * @return The topmost element in the queue without changing the queue. This
  50    * is the element 'a' such that there is no other element 'b' in the queue for
  51    * which Compare(b, a) returns true. (Since this container does not check
  52    * for duplicate entries there may exist 'b' for which Compare(a, b) returns
  53    * false.)
  54    */
  55   const T& Top() const {
  56     MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
  57     return mElements[0];
  58   }
  59
  60   /**
  61    * Adds an element to the queue
  62    * @param aElement The element to add
  63    * @return true on success, false on out of memory.
  64    */
  65   void Push(T&& aElement) {
  66     mElements.AppendElement(std::move(aElement));
  67
  68     // Sift up
  69     size_type i = mElements.Length() - 1;
  70     while (i) {
  71       size_type parent = (size_type)((i - 1) / 2);
  72       if (mCompare.LessThan(mElements[parent], mElements[i])) {
  73         break;
  74       }
  75       std::swap(mElements[i], mElements[parent]);
  76       i = parent;
  77     }
  78   }
  79
  80   /**
  81    * Removes and returns the top-most element from the queue.
  82    * @return The topmost element, that is, the element 'a' such that there is no
  83    * other element 'b' in the queue for which Compare(b, a) returns true.
  84    * @see Top()
  85    */
  86   T Pop() {
  87     MOZ_ASSERT(!mElements.IsEmpty(), "Empty queue");
  88     T pop = std::move(mElements[0]);
  89
  90     const size_type newLength = mElements.Length() - 1;
  91     if (newLength == 0) {
  92       mElements.Clear();
  93       return pop;
  94     }
  95
  96     // Move last to front
  97     mElements[0] = mElements.PopLastElement();
  98
  99     // Sift down
 100     size_type i = 0;
 101     while (2 * i + 1 < newLength) {
 102       size_type swap = i;
 103       size_type l_child = 2 * i + 1;
 104       if (mCompare.LessThan(mElements[l_child], mElements[i])) {
 105         swap = l_child;
 106       }
 107       size_type r_child = l_child + 1;
 108       if (r_child < newLength &&
 109           mCompare.LessThan(mElements[r_child], mElements[swap])) {
 110         swap = r_child;
 111       }
 112       if (swap == i) {
 113         break;
 114       }
 115       std::swap(mElements[i], mElements[swap]);
 116       i = swap;
 117     }
 118
 119     return pop;
 120   }
 121
 122   /**
 123    * Removes all elements from the queue.
 124    */
 125   void Clear() { mElements.Clear(); }
 126
 127   /**
 128    * Provides readonly access to the queue elements as an array. Generally this
 129    * should be avoided but may be needed in some situations such as when the
 130    * elements contained in the queue need to be enumerated for cycle-collection.
 131    * @return A pointer to the first element of the array.  If the array is
 132    * empty, then this pointer must not be dereferenced.
 133    */
 134   const T* Elements() const { return mElements.Elements(); }
 135
 136   nsTPriorityQueue Clone() const {
 137     auto res = nsTPriorityQueue{mCompare};
 138     res.mElements = mElements.Clone();
 139     return res;
 140   }
 141
 142  protected:
 143   nsTArray<T> mElements;
 144   Compare mCompare;  // Comparator object
 145 };
 146
 147 #endif  // NS_TPRIORITY_QUEUE_H_