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    */
nsTPriorityQueue()28   nsTPriorityQueue() : mCompare(Compare()) {}
29 
30   /**
31    * Constructor to allow a specific instance of a comparator object to be
32    * used.
33    */
nsTPriorityQueue(const Compare & aComp)34   explicit nsTPriorityQueue(const Compare& aComp) : mCompare(aComp) {}
35 
36   /**
37    * Copy constructor
38    */
nsTPriorityQueue(const nsTPriorityQueue & aOther)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    */
IsEmpty()48   bool IsEmpty() const { return mElements.IsEmpty(); }
49 
50   /**
51    * @return The number of elements in the queue.
52    */
Length()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    */
Top()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    */
Push(const T & aElement)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    */
Pop()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    */
Clear()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    */
Elements()144   const T* Elements() const { return mElements.Elements(); }
145 
146 protected:
147   /**
148    * Swaps the elements at the specified indices.
149    */
Swap(size_type aIndexA,size_type aIndexB)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_
162