|
@@ -82,13 +82,13 @@ protected:
|
|
|
* is in order again.
|
|
|
*
|
|
|
* @param gap The position of the gap
|
|
|
* @param item The proposed item for filling the gap
|
|
|
* @return The (gap)position where the item fits
|
|
|
*/
|
|
|
FORCEINLINE uint HeapifyDown(uint gap, T *item)
|
|
|
inline uint HeapifyDown(uint gap, T *item)
|
|
|
{
|
|
|
assert(gap != 0);
|
|
|
|
|
|
/* The first child of the gap is at [parent * 2] */
|
|
|
uint child = gap * 2;
|
|
|
|
|
@@ -118,13 +118,13 @@ protected:
|
|
|
* is in order again.
|
|
|
*
|
|
|
* @param gap The position of the gap
|
|
|
* @param item The proposed item for filling the gap
|
|
|
* @return The (gap)position where the item fits
|
|
|
*/
|
|
|
FORCEINLINE uint HeapifyUp(uint gap, T *item)
|
|
|
inline uint HeapifyUp(uint gap, T *item)
|
|
|
{
|
|
|
assert(gap != 0);
|
|
|
|
|
|
uint parent;
|
|
|
|
|
|
while (gap > 1) {
|
|
@@ -139,13 +139,13 @@ protected:
|
|
|
}
|
|
|
return gap;
|
|
|
}
|
|
|
|
|
|
#if BINARYHEAP_CHECK
|
|
|
/** Verify the heap consistency */
|
|
|
FORCEINLINE void CheckConsistency()
|
|
|
inline void CheckConsistency()
|
|
|
{
|
|
|
for (uint child = 2; child <= this->items; child++) {
|
|
|
uint parent = child / 2;
|
|
|
assert(!(*this->data[child] < *this->data[parent]));
|
|
|
}
|
|
|
}
|
|
@@ -154,57 +154,57 @@ protected:
|
|
|
public:
|
|
|
/**
|
|
|
* Get the number of items stored in the priority queue.
|
|
|
*
|
|
|
* @return The number of items in the queue
|
|
|
*/
|
|
|
FORCEINLINE uint Length() const { return this->items; }
|
|
|
inline uint Length() const { return this->items; }
|
|
|
|
|
|
/**
|
|
|
* Test if the priority queue is empty.
|
|
|
*
|
|
|
* @return True if empty
|
|
|
*/
|
|
|
FORCEINLINE bool IsEmpty() const { return this->items == 0; }
|
|
|
inline bool IsEmpty() const { return this->items == 0; }
|
|
|
|
|
|
/**
|
|
|
* Test if the priority queue is full.
|
|
|
*
|
|
|
* @return True if full.
|
|
|
*/
|
|
|
FORCEINLINE bool IsFull() const { return this->items >= this->capacity; }
|
|
|
inline bool IsFull() const { return this->items >= this->capacity; }
|
|
|
|
|
|
/**
|
|
|
* Get the smallest item in the binary tree.
|
|
|
*
|
|
|
* @return The smallest item, or throw assert if empty.
|
|
|
*/
|
|
|
FORCEINLINE T *Begin()
|
|
|
inline T *Begin()
|
|
|
{
|
|
|
assert(!this->IsEmpty());
|
|
|
return this->data[1];
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Get the LAST item in the binary tree.
|
|
|
*
|
|
|
* @note The last item is not neccesary the biggest!
|
|
|
*
|
|
|
* @return The last item
|
|
|
*/
|
|
|
FORCEINLINE T *End()
|
|
|
inline T *End()
|
|
|
{
|
|
|
return this->data[1 + this->items];
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Insert new item into the priority queue, maintaining heap order.
|
|
|
*
|
|
|
* @param new_item The pointer to the new item
|
|
|
*/
|
|
|
FORCEINLINE void Include(T *new_item)
|
|
|
inline void Include(T *new_item)
|
|
|
{
|
|
|
if (this->IsFull()) {
|
|
|
assert(this->capacity < UINT_MAX / 2);
|
|
|
|
|
|
this->capacity *= 2;
|
|
|
this->data = ReallocT<T*>(this->data, this->capacity + 1);
|
|
@@ -219,13 +219,13 @@ public:
|
|
|
/**
|
|
|
* Remove and return the smallest (and also first) item
|
|
|
* from the priority queue.
|
|
|
*
|
|
|
* @return The pointer to the removed item
|
|
|
*/
|
|
|
FORCEINLINE T *Shift()
|
|
|
inline T *Shift()
|
|
|
{
|
|
|
assert(!this->IsEmpty());
|
|
|
|
|
|
T *first = this->Begin();
|
|
|
|
|
|
this->items--;
|
|
@@ -241,13 +241,13 @@ public:
|
|
|
|
|
|
/**
|
|
|
* Remove item at given index from the priority queue.
|
|
|
*
|
|
|
* @param index The position of the item in the heap
|
|
|
*/
|
|
|
FORCEINLINE void Remove(uint index)
|
|
|
inline void Remove(uint index)
|
|
|
{
|
|
|
if (index < this->items) {
|
|
|
assert(index != 0);
|
|
|
this->items--;
|
|
|
/* at position index we have a gap now */
|
|
|
|
|
@@ -269,13 +269,13 @@ public:
|
|
|
* Matching is done by comparing adress of the
|
|
|
* item.
|
|
|
*
|
|
|
* @param item The reference to the item
|
|
|
* @return The index of the item or zero if not found
|
|
|
*/
|
|
|
FORCEINLINE uint FindIndex(const T &item) const
|
|
|
inline uint FindIndex(const T &item) const
|
|
|
{
|
|
|
if (this->IsEmpty()) return 0;
|
|
|
for (T **ppI = this->data + 1, **ppLast = ppI + this->items; ppI <= ppLast; ppI++) {
|
|
|
if (*ppI == &item) {
|
|
|
return ppI - this->data;
|
|
|
}
|
|
@@ -284,10 +284,10 @@ public:
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Make the priority queue empty.
|
|
|
* All remaining items will remain untouched.
|
|
|
*/
|
|
|
FORCEINLINE void Clear() { this->items = 0; }
|
|
|
inline void Clear() { this->items = 0; }
|
|
|
};
|
|
|
|
|
|
#endif /* BINARYHEAP_HPP */
|