diff options
Diffstat (limited to 'lib/BinHeap.cc')
| -rw-r--r-- | lib/BinHeap.cc | 30 |
1 files changed, 15 insertions, 15 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; |