Ca a l'air bien...

3 files changed, 30 insertions, 35 deletions

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;
diff --git a/po/PriorityLists.pot b/po/PriorityLists.pot
index 424fc6a..95ea5ec 100644
--- a/po/PriorityLists.pot
+++ b/po/PriorityLists.pot
@@ -6,7 +6,7 @@
 msgid ""
 msgstr ""
 "Project-Id-Version: PACKAGE VERSION\n"
-"POT-Creation-Date: 2001-03-03 23:47+0100\n"
+"POT-Creation-Date: 2001-03-04 01:37+0100\n"
 "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
 "Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
 "Language-Team: LANGUAGE <LL@li.org>\n"
@@ -44,7 +44,7 @@ msgstr ""
 msgid " keys (real count). Expecting "
 msgstr ""
 
-#: src/test.cc:53 src/test.cc:125
+#: src/test.cc:53 src/test.cc:123
 msgid "Incorrect order."
 msgstr ""
 
@@ -80,45 +80,45 @@ msgstr ""
 msgid "Size of a BinHeap cell     : "
 msgstr ""
 
-#: src/test.cc:92
+#: src/test.cc:90
 msgid "Creating a priority list and adding keys:\n"
 msgstr ""
 
-#: src/test.cc:105 src/test.cc:112 src/test.cc:116
+#: src/test.cc:103 src/test.cc:110 src/test.cc:114
 msgid ""
 "Ok.\n"
 "List browsing...\n"
 msgstr ""
 
-#: src/test.cc:107
+#: src/test.cc:105
 msgid ""
 "Ok.\n"
 "Extract_Min + List browsing...\n"
 msgstr ""
 
-#: src/test.cc:110
+#: src/test.cc:108
 msgid ""
 "Ok.\n"
 "Lower_Key(-12) over 59...\n"
 msgstr ""
 
-#: src/test.cc:114
+#: src/test.cc:112
 msgid ""
 "Ok.\n"
 "Delete over 54...\n"
 msgstr ""
 
-#: src/test.cc:120
+#: src/test.cc:118
 msgid ""
 "Ok.\n"
 "Extracting datas...\n"
 msgstr ""
 
-#: src/test.cc:122
+#: src/test.cc:120
 msgid "Minimum #"
 msgstr ""
 
-#: src/test.cc:128
+#: src/test.cc:126
 msgid ""
 "Ok.\n"
 "\n"
@@ -147,11 +147,11 @@ msgid ""
 " |\n"
 msgstr ""
 
-#: lib/BinHeap.cc:120
+#: lib/BinHeap.cc:121
 msgid "Not enough memory"
 msgstr ""
 
-#: lib/BinHeap.cc:147
+#: lib/BinHeap.cc:148
 msgid "negative overflow"
 msgstr ""
 
diff --git a/src/test.cc b/src/test.cc
index 924cba3..5a1bce5 100644
--- a/src/test.cc
+++ b/src/test.cc
@@ -33,13 +33,11 @@ void DoCombTest(int number)
 	cerr << _("Creation of a priority list and adding ") << number << _(" random entrie(s)...");
 	T = newlist();
 	for (i = 1; i <= number; i++) {
-		T->Dump(cerr);
 		T->Insert(rand() % P_INFINITY, NULL);
 	}
 	cerr << _("Ok.\nDeleting the list...");
 	oK = P_INFINITY;
 	for (i = number; i >= 1; i--) {
-		T->Dump(cerr);
 		if (T->n() != i) {
 			cerr << _("List has ") << T->n() << _(" keys. Expecting ") << i << endl;
 			exception(1, _("List corrupted."));
@@ -75,13 +73,11 @@ void FullTest(void)
 	cerr << _("Size of a BinHeap header   : ") << sizeof(BinHeap) << endl;
 	cerr << _("Size of a BinHeap cell     : ") << sizeof(binheap_t) << endl;
 
-/*
 	DoCombTest(0);
 	DoCombTest(10);
 	DoCombTest(70);
-*/
-//  DoCombTest(1000);
-//  DoCombTest(10000);
+  DoCombTest(1000);
+  DoCombTest(10000);
 #ifdef BT
 	DoCombTest(100000);
 #ifdef VBT
@@ -92,8 +88,7 @@ void FullTest(void)
 	cerr << _("Creating a priority list and adding keys:\n");
 	T = newlist();
 	for (i = 0; i < 30; i++) {
-		T->Dump(cerr);
-		fprintf(stderr, "%i \n", N[i]);
+		fprintf(stderr, "%i ", N[i]);
 		T->Insert(N[i], NULL);
 	}