#include #include #include "config.h" #include "BinHeap.h" #include "CList.h" #define FATHER(i) (i >> 1) #define LEFT(i) (i << 1) #define RIGHT(i) ((i << 1) + 1) /**********************************\ * * * Tas binaires * * * \**********************************/ /* * Implémentation quasi directe de l'algorithme Entasser(A, i) avec A = this. * Seul le test de condition est inversé. */ void BinHeap::PackUp(int i) { int l = LEFT(i), r = RIGHT(i), min; binheap_t *binheap = (binheap_t *) Datas; 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; if (min != i) { SWAP(binheap[i - 1], binheap[min - 1]); SWAP(((CList *) binheap[i - 1].FP)->Datas, ((CList *) binheap[min - 1].FP)->Datas); PackUp(min); } } /* * Il n'y a aucune méthode "rapide" pour effectuer l'union de deux tas * binaires. Nous utiliserons donc l'union générique. */ PriorityList *BinHeap::Union(PriorityList * P) { return GenericUnion(P); } /* * L'algorithme "Diminuer Clef" ressemble à l'algorithme "Inserer" */ bool BinHeap::Lower_Key(Cell x, Key_t NKey) { int i = ((binheap_t *) (FP->ReadDatas(x))) - ((binheap_t *) Datas) + 1; binheap_t *binheap = (binheap_t *) Datas; if (((binheap_t *) (FP->ReadDatas(x)))->Key < NKey) return false; while ((i > 1) && (binheap[FATHER(i) - 1].Key > NKey)) { SWAP(binheap[i - 1], binheap[FATHER(i) - 1]); SWAP(((CList *) binheap[i - 1].FP)->Datas, ((CList *) binheap[FATHER(i) - 1].FP)->Datas); i = FATHER(i); } binheap[i - 1].Key = NKey; return true; } BinHeap::BinHeap(void):FP(new CList) { Key = 0; Datas = NULL; } BinHeap::~BinHeap(void) { if (Datas) free(Datas); } Key_t BinHeap::ReadKey(Cell C) { cerr << "Lecture de " << C << endl; return ((binheap_t *) FP->ReadDatas(C))->Key; } Datas_t BinHeap::ReadDatas(Cell C) { return ((binheap_t *) FP->ReadDatas(C))->Datas; } int BinHeap::rn(void) { return n(); } void BinHeap::Dump(ostream & os) { int i; binheap_t *binheap = (binheap_t *) Datas; for (i = 0; i < Key; i++) { os << binheap[i].Key << " "; } os << endl; } bool BinHeap::IsEmpty(void) { return (Key == 0); } Cell BinHeap::Min(void) { return ((binheap_t *) Datas)->FP; } /* * L'algorithme INSERER des tas binaires. Comme pour le tas binomial, nous * sommes obligés d'utiliser une liste auxiliaire. */ Cell BinHeap::Insert(Key_t IKey, Datas_t const &IDatas) { binheap_t newcell = { IKey, IDatas }, *binheap; int i = Key++; Cell r; if (!Datas || ((((Key >> GRANUL) + 1) << GRANUL) != (((i >> GRANUL) + 1) << GRANUL))) { if (!(Datas = realloc(Datas, (((Key >> GRANUL) + 1) << GRANUL) * sizeof(binheap_t)))) { exception(5, _("Not enough memory")); } } i = Key; binheap = (binheap_t *) Datas; while ((i > 1) && (binheap[FATHER(i) - 1].Key > IKey)) { binheap[i - 1] = binheap[FATHER(i) - 1]; ((CList *) binheap[FATHER(i) - 1].FP)->Datas = &binheap[i - 1]; i = FATHER(i); } binheap[i - 1] = newcell; r = binheap[i - 1].FP = FP->Insert(0, &(binheap[i - 1])); cerr << "Ajout de " << r << endl; return r; } /* * Implémentation directe de l'algorithme EXTRAIRE-MIN-TAS(A) avec A = this. */ Key_t BinHeap::Extract_Min(Datas_t & Datas) { binheap_t *binheap = (binheap_t *) this->Datas; Key_t ret; Datas_t Dumb; if (Key < 1) exception(5, _("negative overflow")); ret = binheap[0].Key; Datas = binheap[0].Datas; FP->Delete(Dumb, binheap[0].FP); binheap[0] = binheap[Key - 1]; int i = Key--; 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; } /* * Implémentation directe de l'algorithme TAS-BINOMIAL-SUPPRIMER(T,x) avec T = this. * La valeur de la clef supprimée est renvoyée par la routine et les données satellites * sont écrites dans la variable Datas. */ Key_t BinHeap::Delete(Datas_t & Datas, Cell x) { Key_t K; K = ReadKey(x); Lower_Key(x, M_INFINITY); Extract_Min(Datas); return K; }