summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authoryexo <yexo@openttd.org>2010-02-25 11:48:09 +0000
committeryexo <yexo@openttd.org>2010-02-25 11:48:09 +0000
commit7537fb18bcd1845d24b3fa3a71b36487edd3f1b7 (patch)
tree8ee2e9515ba5d047efafe27e8d3950f5a108de4f
parenteeb81897450aae2808f4b38726b4026b8a58f3a7 (diff)
downloadopenttd-7537fb18bcd1845d24b3fa3a71b36487edd3f1b7.tar.xz
(svn r19241) -Cleanup: Move the HeapifyUp code into its own method (skidd13)
-rw-r--r--src/misc/binaryheap.hpp59
1 files changed, 28 insertions, 31 deletions
diff --git a/src/misc/binaryheap.hpp b/src/misc/binaryheap.hpp
index 04343af41..c95255e10 100644
--- a/src/misc/binaryheap.hpp
+++ b/src/misc/binaryheap.hpp
@@ -79,6 +79,28 @@ protected:
return gap;
}
+ /** Heapify (move gap) up */
+ FORCEINLINE uint HeapifyUp(uint gap, T *item)
+ {
+ assert(gap != 0);
+
+ uint parent;
+
+ while (gap > 1) {
+ /* compare [gap] with its parent */
+ parent = gap / 2;
+
+ if (!(*item <*m_items[parent])) {
+ /* we don't need to continue upstairs */
+ break;
+ }
+
+ m_items[gap] = m_items[parent];
+ gap = parent;
+ }
+ return gap;
+ }
+
public:
/** Return the number of items stored in the priority queue.
* @return number of items in the queue */
@@ -115,19 +137,7 @@ public:
}
/* make place for new item */
- uint gap = ++m_size;
- /* Heapify up */
- while (gap > 1) {
- /* compare [gap] with its parent */
- uint parent = gap / 2;
- if (new_item < *m_items[parent]) {
- m_items[gap] = m_items[parent];
- gap = parent;
- } else {
- /* we don't need to continue upstairs */
- break;
- }
- }
+ uint gap = HeapifyUp(++m_size, &new_item);
m_items[gap] = &new_item;
CheckConsistency();
}
@@ -157,27 +167,14 @@ public:
/** Remove item specified by index */
FORCEINLINE void RemoveByIdx(uint idx)
{
- /* at position idx we have a gap now */
- uint gap = idx;
if (idx < m_size) {
- assert(idx >= 1);
+ assert(idx != 0);
m_size--;
- T *last = End();
- /* and the candidate item for fixing this gap is our last item 'last'
- * Move gap / last item up: */
- while (gap > 1)
- {
- /* compare [gap] with its parent */
- uint parent = gap / 2;
- if (*last < *m_items[parent]) {
- m_items[gap] = m_items[parent];
- gap = parent;
- } else {
- /* we don't need to continue upstairs */
- break;
- }
- }
+ /* at position idx we have a gap now */
+ T *last = End();
+ /* Fix binary tree up and downwards */
+ uint gap = HeapifyUp(idx, last);
gap = HeapifyDown(gap, last);
/* move last item to the proper place */
if (!IsEmpty()) m_items[gap] = last;