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