summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authoryexo <yexo@openttd.org>2010-02-25 11:47:44 +0000
committeryexo <yexo@openttd.org>2010-02-25 11:47:44 +0000
commiteeb81897450aae2808f4b38726b4026b8a58f3a7 (patch)
treefc41cb1f451fe8ad4142a96dafa1015ff9285dec
parentb4c51f2ccd22d138f9821cd80e5a244cbe3baf92 (diff)
downloadopenttd-eeb81897450aae2808f4b38726b4026b8a58f3a7.tar.xz
(svn r19240) -Codechange: Unify HeapifyUp code (skidd13)
-rw-r--r--src/misc/binaryheap.hpp13
1 files changed, 11 insertions, 2 deletions
diff --git a/src/misc/binaryheap.hpp b/src/misc/binaryheap.hpp
index a50ee086a..04343af41 100644
--- a/src/misc/binaryheap.hpp
+++ b/src/misc/binaryheap.hpp
@@ -117,8 +117,17 @@ public:
/* make place for new item */
uint gap = ++m_size;
/* Heapify up */
- for (uint parent = gap / 2; (parent > 0) && (new_item < *m_items[parent]); gap = parent, parent /= 2)
- m_items[gap] = m_items[parent];
+ 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;
+ }
+ }
m_items[gap] = &new_item;
CheckConsistency();
}