|
@@ -76,25 +76,25 @@ public:
|
|
|
}
|
|
|
|
|
|
protected:
|
|
|
/**
|
|
|
* Get position for fixing a gap (downwards).
|
|
|
* The gap is moved downwards in the binary tree until it
|
|
|
* 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;
|
|
|
|
|
|
/* while children are valid */
|
|
|
while (child <= this->items) {
|
|
|
/* choose the smaller child */
|
|
|
if (child < this->items && *this->data[child + 1] < *this->data[child]) {
|
|
|
child++;
|
|
|
}
|
|
@@ -112,148 +112,148 @@ protected:
|
|
|
return gap;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Get position for fixing a gap (upwards).
|
|
|
* The gap is moved upwards in the binary tree until the
|
|
|
* 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) {
|
|
|
/* compare [gap] with its parent */
|
|
|
parent = gap / 2;
|
|
|
if (!(*item < *this->data[parent])) {
|
|
|
/* we don't need to continue upstairs */
|
|
|
break;
|
|
|
}
|
|
|
this->data[gap] = this->data[parent];
|
|
|
gap = parent;
|
|
|
}
|
|
|
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]));
|
|
|
}
|
|
|
}
|
|
|
#endif
|
|
|
|
|
|
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);
|
|
|
}
|
|
|
|
|
|
/* Make place for new item. A gap is now at the end of the tree. */
|
|
|
uint gap = this->HeapifyUp(++items, new_item);
|
|
|
this->data[gap] = new_item;
|
|
|
CHECK_CONSISTY();
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* 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--;
|
|
|
/* at index 1 we have a gap now */
|
|
|
T *last = this->End();
|
|
|
uint gap = this->HeapifyDown(1, last);
|
|
|
/* move last item to the proper place */
|
|
|
if (!this->IsEmpty()) this->data[gap] = last;
|
|
|
|
|
|
CHECK_CONSISTY();
|
|
|
return first;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* 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 */
|
|
|
|
|
|
T *last = this->End();
|
|
|
/* Fix binary tree up and downwards */
|
|
|
uint gap = this->HeapifyUp(index, last);
|
|
|
gap = this->HeapifyDown(gap, last);
|
|
|
/* move last item to the proper place */
|
|
|
if (!this->IsEmpty()) this->data[gap] = last;
|
|
@@ -263,31 +263,31 @@ public:
|
|
|
}
|
|
|
CHECK_CONSISTY();
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Search for an item in the priority queue.
|
|
|
* 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;
|
|
|
}
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* 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 */
|