The Tor Browser / file comparison
comparison: xpcom/glue/nsTPriorityQueue.h
xpcom/glue/nsTPriorityQueue.h
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:0bd9e8a70e94 |
|---|---|
| 1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ | |
| 2 /* vim:set ts=2 sw=2 sts=2 et cindent: */ | |
| 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 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 * @return True if the queue is empty or false otherwise. | |
| 46 */ | |
| 47 bool IsEmpty() const | |
| 48 { | |
| 49 return mElements.IsEmpty(); | |
| 50 } | |
| 51 | |
| 52 /** | |
| 53 * @return The number of elements in the queue. | |
| 54 */ | |
| 55 size_type Length() const | |
| 56 { | |
| 57 return mElements.Length(); | |
| 58 } | |
| 59 | |
| 60 /** | |
| 61 * @return The topmost element in the queue without changing the queue. This | |
| 62 * is the element 'a' such that there is no other element 'b' in the queue for | |
| 63 * which Compare(b, a) returns true. (Since this container does not check | |
| 64 * for duplicate entries there may exist 'b' for which Compare(a, b) returns | |
| 65 * false.) | |
| 66 */ | |
| 67 const T& Top() const | |
| 68 { | |
| 69 NS_ABORT_IF_FALSE(!mElements.IsEmpty(), "Empty queue"); | |
| 70 return mElements[0]; | |
| 71 } | |
| 72 | |
| 73 /** | |
| 74 * Adds an element to the queue | |
| 75 * @param aElement The element to add | |
| 76 * @return true on success, false on out of memory. | |
| 77 */ | |
| 78 bool Push(const T& aElement) | |
| 79 { | |
| 80 T* elem = mElements.AppendElement(aElement); | |
| 81 if (!elem) | |
| 82 return false; // Out of memory | |
| 83 | |
| 84 // Sift up | |
| 85 size_type i = mElements.Length() - 1; | |
| 86 while (i) { | |
| 87 size_type parent = (size_type)((i - 1) / 2); | |
| 88 if (mCompare.LessThan(mElements[parent], mElements[i])) { | |
| 89 break; | |
| 90 } | |
| 91 Swap(i, parent); | |
| 92 i = parent; | |
| 93 } | |
| 94 | |
| 95 return true; | |
| 96 } | |
| 97 | |
| 98 /** | |
| 99 * Removes and returns the top-most element from the queue. | |
| 100 * @return The topmost element, that is, the element 'a' such that there is no | |
| 101 * other element 'b' in the queue for which Compare(b, a) returns true. | |
| 102 * @see Top() | |
| 103 */ | |
| 104 T Pop() | |
| 105 { | |
| 106 NS_ABORT_IF_FALSE(!mElements.IsEmpty(), "Empty queue"); | |
| 107 T pop = mElements[0]; | |
| 108 | |
| 109 // Move last to front | |
| 110 mElements[0] = mElements[mElements.Length() - 1]; | |
| 111 mElements.TruncateLength(mElements.Length() - 1); | |
| 112 | |
| 113 // Sift down | |
| 114 size_type i = 0; | |
| 115 while (2*i + 1 < mElements.Length()) { | |
| 116 size_type swap = i; | |
| 117 size_type l_child = 2*i + 1; | |
| 118 if (mCompare.LessThan(mElements[l_child], mElements[i])) { | |
| 119 swap = l_child; | |
| 120 } | |
| 121 size_type r_child = l_child + 1; | |
| 122 if (r_child < mElements.Length() && | |
| 123 mCompare.LessThan(mElements[r_child], mElements[swap])) { | |
| 124 swap = r_child; | |
| 125 } | |
| 126 if (swap == i) { | |
| 127 break; | |
| 128 } | |
| 129 Swap(i, swap); | |
| 130 i = swap; | |
| 131 } | |
| 132 | |
| 133 return pop; | |
| 134 } | |
| 135 | |
| 136 /** | |
| 137 * Removes all elements from the queue. | |
| 138 */ | |
| 139 void Clear() | |
| 140 { | |
| 141 mElements.Clear(); | |
| 142 } | |
| 143 | |
| 144 /** | |
| 145 * Provides readonly access to the queue elements as an array. Generally this | |
| 146 * should be avoided but may be needed in some situations such as when the | |
| 147 * elements contained in the queue need to be enumerated for cycle-collection. | |
| 148 * @return A pointer to the first element of the array. If the array is | |
| 149 * empty, then this pointer must not be dereferenced. | |
| 150 */ | |
| 151 const T* Elements() const | |
| 152 { | |
| 153 return mElements.Elements(); | |
| 154 } | |
| 155 | |
| 156 protected: | |
| 157 /** | |
| 158 * Swaps the elements at the specified indices. | |
| 159 */ | |
| 160 void Swap(size_type aIndexA, size_type aIndexB) | |
| 161 { | |
| 162 T temp = mElements[aIndexA]; | |
| 163 mElements[aIndexA] = mElements[aIndexB]; | |
| 164 mElements[aIndexB] = temp; | |
| 165 } | |
| 166 | |
| 167 nsTArray<T> mElements; | |
| 168 Compare mCompare; // Comparator object | |
| 169 }; | |
| 170 | |
| 171 #endif // NS_TPRIORITY_QUEUE_H_ |
