summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/BinHeap.cc30
-rw-r--r--po/PriorityLists.pot24
-rw-r--r--src/test.cc11
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);
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 14:59:41 +0000