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/. */
7 #ifndef NS_TPRIORITY_QUEUE_H_
8 #define NS_TPRIORITY_QUEUE_H_
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.
18 template<class T
, class Compare
= nsDefaultComparator
<T
, T
>>
19 class nsTPriorityQueue
22 typedef typename nsTArray
<T
>::size_type size_type
;
25 * Default constructor also creates a comparator object using the default
26 * constructor for type Compare.
28 nsTPriorityQueue() : mCompare(Compare()) {}
31 * Constructor to allow a specific instance of a comparator object to be
34 explicit nsTPriorityQueue(const Compare
& aComp
) : mCompare(aComp
) {}
39 nsTPriorityQueue(const nsTPriorityQueue
& aOther
)
40 : mElements(aOther
.mElements
)
41 , mCompare(aOther
.mCompare
)
46 * @return True if the queue is empty or false otherwise.
48 bool IsEmpty() const { return mElements
.IsEmpty(); }
51 * @return The number of elements in the queue.
53 size_type
Length() const { return mElements
.Length(); }
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
64 NS_ABORT_IF_FALSE(!mElements
.IsEmpty(), "Empty queue");
69 * Adds an element to the queue
70 * @param aElement The element to add
71 * @return true on success, false on out of memory.
73 bool Push(const T
& aElement
)
75 T
* elem
= mElements
.AppendElement(aElement
);
77 return false; // Out of memory
81 size_type i
= mElements
.Length() - 1;
83 size_type parent
= (size_type
)((i
- 1) / 2);
84 if (mCompare
.LessThan(mElements
[parent
], mElements
[i
])) {
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.
102 NS_ABORT_IF_FALSE(!mElements
.IsEmpty(), "Empty queue");
103 T pop
= mElements
[0];
105 // Move last to front
106 mElements
[0] = mElements
[mElements
.Length() - 1];
107 mElements
.TruncateLength(mElements
.Length() - 1);
111 while (2 * i
+ 1 < mElements
.Length()) {
113 size_type l_child
= 2 * i
+ 1;
114 if (mCompare
.LessThan(mElements
[l_child
], mElements
[i
])) {
117 size_type r_child
= l_child
+ 1;
118 if (r_child
< mElements
.Length() &&
119 mCompare
.LessThan(mElements
[r_child
], mElements
[swap
])) {
133 * Removes all elements from the queue.
135 void Clear() { mElements
.Clear(); }
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.
144 const T
* Elements() const { return mElements
.Elements(); }
148 * Swaps the elements at the specified indices.
150 void Swap(size_type aIndexA
, size_type aIndexB
)
152 T temp
= mElements
[aIndexA
];
153 mElements
[aIndexA
] = mElements
[aIndexB
];
154 mElements
[aIndexB
] = temp
;
157 nsTArray
<T
> mElements
;
158 Compare mCompare
; // Comparator object
161 #endif // NS_TPRIORITY_QUEUE_H_