From 5c9f12580ae4e515ef48d0891c7d85a3d7eb2b04 Mon Sep 17 00:00:00 2001
From: Francois Fleuret <francois@fleuret.org>
Date: Sun, 30 Dec 2012 23:05:27 +0100
Subject: [PATCH] Scrapping as much as possible from the heap operations.
 Gained ~10% for tracking time!

---
 mtp_graph.cc | 44 ++++++++++++++++++++++++--------------------
 1 file changed, 24 insertions(+), 20 deletions(-)

diff --git a/mtp_graph.cc b/mtp_graph.cc
index c17917e..5b42781 100644
--- a/mtp_graph.cc
+++ b/mtp_graph.cc
@@ -97,36 +97,40 @@ void Vertex::del_leaving_edge(Edge *e) {
 
 void Vertex::decrease_distance_in_heap(Vertex **heap) {
   Vertex **p, **h;
-  // There is some beauty in that
   h = heap_slot;
-  while(h > heap &&
-        (p = heap + (h - heap + 1) / 2 - 1,
-         (*p)->distance_from_source > (*h)->distance_from_source)) {
+  while(1) {
+    if(h <= heap) break;
+    p = heap + ((h - heap + 1) >> 1) - 1;
+    if((*p)->distance_from_source <= distance_from_source) break;
+    swap((*p)->heap_slot, heap_slot);
     swap(*p, *h);
-    swap((*p)->heap_slot, (*h)->heap_slot);
     h = p;
   }
 }
 
 void Vertex::increase_distance_in_heap(Vertex **heap, Vertex **heap_bottom) {
   Vertex **c1, **c2, **h;
-  // omg, that's beautiful
   h = heap_slot;
-  while(c1 = heap + 2 * (h - heap) + 1,
-        c1 < heap_bottom &&
-        (c2 = c1 + 1,
-         (*c1)->distance_from_source < (*h)->distance_from_source
-         ||
-         (c2 < heap_bottom && (*c2)->distance_from_source < (*h)->distance_from_source)
-         )) {
-    if(c2 < heap_bottom && (*c2)->distance_from_source <= (*c1)->distance_from_source) {
-      swap(*c2, *h);
-      swap((*c2)->heap_slot, (*h)->heap_slot);
-      h = c2;
+  while(1) {
+    c1 = heap + 2 * (h - heap) + 1;
+    if(c1 >= heap_bottom) break;
+    c2 = c1 + 1;
+    if((*c1)->distance_from_source < distance_from_source) {
+      if(c2 < heap_bottom && (*c2)->distance_from_source < (*c1)->distance_from_source) {
+        swap((*c2)->heap_slot, heap_slot);
+        swap(*c2, *h);
+        h = c2;
+      } else {
+        swap((*c1)->heap_slot, heap_slot);
+        swap(*c1, *h);
+        h = c1;
+      }
     } else {
-      swap(*c1, *h);
-      swap((*c1)->heap_slot, (*h)->heap_slot);
-      h = c1;
+      if(c2 < heap_bottom && (*c2)->distance_from_source < distance_from_source) {
+        swap((*c2)->heap_slot, heap_slot);
+        swap(*c2, *h);
+        h = c2;
+      } else break;
     }
   }
 }
-- 
2.39.5