From 9f7df14e416d678943e6abfe314d312b9cc7113c Mon Sep 17 00:00:00 2001
From: Pixel <>
Date: Sun, 4 Mar 2001 00:42:54 +0000
Subject: Ca a l'air bien...

---
 lib/BinHeap.cc | 30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

(limited to 'lib')

diff --git a/lib/BinHeap.cc b/lib/BinHeap.cc
index 7080a97..89dd0be 100644
--- a/lib/BinHeap.cc
+++ b/lib/BinHeap.cc
@@ -3,9 +3,9 @@
 #include "config.h"
 #include "BinHeap.h"
 
-#define FATHER(i) (i >> 2)
-#define LEFT(i) (i << 2)
-#define RIGHT(i) ((i <<2) + 1)
+#define FATHER(i) (i >> 1)
+#define LEFT(i) (i << 1)
+#define RIGHT(i) ((i << 1) + 1)
 
 /**********************************\
 *                                  *
@@ -24,8 +24,6 @@ void BinHeap::PackUp(int i)
 	int l = LEFT(i), r = RIGHT(i), min;
 	binheap_t *binheap = (binheap_t *) Datas;
 	
-	cerr << "Appel à PackUp(" << i << ")" << endl;
-
 	min = ((l <= Key) && (binheap[l - 1].Key < binheap[i - 1].Key)) ? l : i;
 	if ((r <= Key) && (binheap[r - 1].Key < binheap[min - 1].Key))
 		min = r;
@@ -53,11 +51,15 @@ PriorityList *BinHeap::Union(PriorityList * P)
 
 bool BinHeap::Lower_Key(Cell x, Key_t NKey)
 {
-	Datas_t Datas;
-	Key_t Key;
+	int i = ((binheap_t *)x) - ((binheap_t*)Datas) + 1;
+	binheap_t * binheap = (binheap_t*) Datas;
 
-	Key = Delete(Datas, x);
-	Insert(Key, Datas);
+	if (((binheap_t*)x)->Key < NKey) return false;
+	while ((i > 1) && (binheap[FATHER(i) - 1].Key > NKey)) {
+		SWAP(binheap[i - 1], binheap[FATHER(i) - 1]);
+		i = FATHER(i);
+	}
+	binheap[i - 1].Key = NKey;
 	return true;
 }
 
@@ -115,7 +117,6 @@ Cell BinHeap::Insert(Key_t IKey, Datas_t const &IDatas)
 	int i = Key++;
 
 	if (!Datas || ((((Key >> GRANUL) + 1) << GRANUL) != (((i >> GRANUL) + 1) << GRANUL))) {
-		cerr << "Reallocating " << (((Key >> GRANUL) + 1) << GRANUL) << " entries" << endl;
 		if (!(Datas = realloc(Datas, (((Key >> GRANUL) + 1) << GRANUL) * sizeof(binheap_t)))) {
 			exception(5, _("Not enough memory"));
 		}
@@ -123,7 +124,7 @@ Cell BinHeap::Insert(Key_t IKey, Datas_t const &IDatas)
 	i = Key;
 
 	binheap = (binheap_t *) Datas;
-
+	
 	while ((i > 1) && (binheap[FATHER(i) - 1].Key > IKey)) {
 		binheap[i - 1] = binheap[FATHER(i) - 1];
 		i = FATHER(i);
@@ -140,7 +141,7 @@ Cell BinHeap::Insert(Key_t IKey, Datas_t const &IDatas)
 
 Key_t BinHeap::Extract_Min(Datas_t & Datas)
 {
-	binheap_t *binheap = (binheap_t *) Datas;
+	binheap_t *binheap = (binheap_t *) this->Datas;
 	Key_t ret;
 
 	if (Key < 1)
@@ -153,9 +154,8 @@ Key_t BinHeap::Extract_Min(Datas_t & Datas)
 
 	int i = Key--;
 
-	if (!Datas || ((((Key >> GRANUL) + 1) << GRANUL) != (((i >> GRANUL) + 1) << GRANUL))) {
-		cerr << "Reallocating " << (((Key >> GRANUL) + 1) << GRANUL) << " entries" << endl;
-		Datas = realloc(Datas, (((Key >> GRANUL) + 1) << GRANUL) * sizeof(binheap_t));
+	if (!this->Datas || ((((Key >> GRANUL) + 1) << GRANUL) != (((i >> GRANUL) + 1) << GRANUL))) {
+		this->Datas = realloc(this->Datas, (((Key >> GRANUL) + 1) << GRANUL) * sizeof(binheap_t));
 	}
 	PackUp(1);
 	return ret;
-- 
cgit v1.2.3