#include <stdio.h> #include "config.h" #include "BHeap.h" #include "CList.h" /**********************************\ * * * Tas binomial * * * \**********************************/ /* * * Le tas binomial impl�ment� suit exactement les algorithmes pr�sent�s dans * le livre "Introduction � l'algorithmique". La structure est r�cursive et * les donn�es de l'ent�te sont r�parties comme suit: * - Degree = -1 (pour signaler que nous somme dans l'ent�te) * - Key contient le nombre d'�l�ments enregistr�s * - Brother est le pointeur sur le premier �l�ment du tas * */ static int d, Depths[65536]; /* * Cette fonction sert � afficher le contenu du tas binomial sur le stream * pass� en argument. L'affichage sera structur� de sorte � ressembler aux * diagrammes pr�sent�s dans le livre "Introduction � l'algorithmique", � * ceci pr�s qu'ils sont pr�sent�s � la verticale. Exemple: * * * Head cell. * | * |__ 6 * |_ 15 * | |__ 18 * |_ 5 * | |_ 10 * | | |__ 29 * | |__ 9 * |_ 2 * |_ 3 * | |_ 16 * | | |__ 23 * | |__ 17 * |_ 11 * | |__ 25 * |__ 14 * */ void BHeap::Dump(ostream & os) { int i; if (Degree == -1) { os << _(" * Head cell.\n |\n"); for (i = 0; i < 65535; i++) Depths[i] = 1; d = 1; } else { for (i = 1; i <= d; i++) os << (Depths[i] ? " |" : " "); os << (Child ? "_ " : "__ ") << Key << endl; } if (Child) { Depths[d] = (Brother != NULL); d++; Child->Dump(os); d--; } if (Brother) { Brother->Dump(os); } } /* * Cette fonction est utilis�e dans les tests "parano�aques" pour compter * le nombre v�ritable de cellules lors d'un parcours r�cursif. */ int BHeap::rn(void) { int n = 0; if (Degree != -1) { n++; } if (Child) { n += Child->rn(); } if (Brother) { n += Brother->rn(); } return n; } /* * Impl�mentation directe de la primitive LIEN-BINOMIAL(y, z) avec y = this. */ void BHeap::Link(BHeap * z) { Father = z; Brother = z->Child; z->Child = this; z->Degree = z->Degree + 1; } /* * Impl�mentation de la primitive FUSIONNER-TAS-BINOMIAUX(T1, T2) avec T1 = this. * L'algorithme a du �tre inventer car il n'est pas pr�sent� dans le livre. * Par contre, il s'inspire fortement de l'algorithme "Fusion" pour le * tri-fusion. De plus, contrairement aux indication du livre, T2 sera rajout� * APRES T1, et aucun tas binaire nouveau ne sera cr��. (voir rapport) */ void BHeap::Merge(BHeap * H) { BHeap *P1, *P2, *T1, *T2; Key += H->Key; H->Key = 0; for (P1 = this, P2 = H->Brother; P1->Brother && P2;) { if (P1->Brother->Degree < P2->Degree) { // P1 < P2, jump over P1. P1 = P1->Brother; } else { // P1 >= P2. We will insert P2 after P1. T1 = P1->Brother; T2 = P2->Brother; P1->Brother = P2; P2->Brother = T1; P1 = P2; P2 = T2; } } if (!(P1->Brother)) P1->Brother = P2; H->Brother = NULL; } /* * Constructeur d'un tas binomial. */ BHeap::BHeap(void):Degree(-1), Father(NULL), Child(NULL), Brother(NULL), FP(new CList) { type = T_BHEAP; } /* * Constructeur interne. La structure est r�cursive, donc nous impl�mentons * un constructeur priv�. */ BHeap::BHeap(Key_t IKey, Datas_t const &IDatas):PriorityList(IKey, IDatas), Degree(0), Father(NULL), Child(NULL), Brother(NULL) { type = T_BHEAP; #ifdef DEBUG nc++; #endif } /* * Le destructeur. S'il est appel� sur l'ent�te, nous effacons r�cursivement * la liste des pointeurs interm�diaires, ainsi que tout le tas * r�cursivement. */ BHeap::~BHeap(void) { if (Degree == -1) delete FP; if (Child) { delete Child; } if (Brother) { delete Brother; } #ifdef DEBUG nd++; #endif } /* * Impl�mentation directe de l'algorithme MINIMUM-TAS-BINOMIAL(T) avec T = this. */ Cell BHeap::Min(void) { BHeap *x = this, *y = NULL; int min = P_INFINITY; for (; x; x = x->Brother) { if ((x->Key < min)) { min = x->Key; y = x; } } return y->FP; } /* * Insertion d'une cellule d�j� cr�� dans le tas. * La routine fonctionne comme dans l'algorithme conseill�. */ Cell BHeap::Insert(BHeap * E) { BHeap *H; if (Degree != -1) exception(2, _("Insert: not over Head.")); if (!(H = new BHeap)) exception(5, _("Insert: No more memory.")); H->Brother = E; Union(H); delete H; return ((E->FP = ((CList *) (FP->Insert(Key, E))))); } /* * Insertion d'un couple (Clef, Donn�es) dans le tas. */ Cell BHeap::Insert(Key_t IKey, Datas_t const &IDatas) { BHeap *P; Key++; if (!(P = new BHeap(IKey, IDatas))) exception(5, _("Insert: No more memory.")); return (Insert(P)); } /* * Impl�mentation de l'algorithme TAS-BINOMIAL-EXTRAIRE-MIN(T) avec T = this. * La clef extraite sera renvoy�e et les donn�es satellites seront �crites dans * la variable Datas. L'impl�mentation est beaucoup plus longue que * l'algorithme de quatre lignes pr�sent� dans le livre mais il s'agit de la * traduction entre les phrases en fran�ais pr�sent�es et le langage C. */ Key_t BHeap::Extract_Min(Datas_t & Datas) { BHeap *x, *y = NULL, *P, *P2, *P3, *Before; Key_t k; int min = P_INFINITY; P = Before = this; if (!Brother) exception(4, _("Extract_Min: Priority List is empty.")); Key--; // 1. Trouver la racine x de cl� minimum dans la liste des racines de T... for (x = Brother; x; x = x->Brother) { if ((x->Key < min)) { min = x->Key; y = x; Before = P; } P = x; } // ... et supprimer x. Before->Brother = y->Brother; // 2. T' <- CREER-TAS-BINOMIAL Before = new BHeap; // 3. inverser l'ordre de la liste cha�n�e des fils de x, // et faire pointer t�te[T'] sur la t�te de la liste r�sultante. // Comme pour fusionner, nous effectuons le travail "sur place", // pour �viter les probl�mes dues aux recopies. (voir rapport) for (P = y->Child; P;) { P->Father = NULL; P2 = Before->Brother; P3 = P->Brother; Before->Brother = P; P->Brother = P2; P = P3; } // 4. T <- UNION-TAS-BINOMIAUX(T, T') Before->Key = 0; Union(Before); // 5. retourner x (et l'effacer) k = y->Key; y->Brother = y->Child = NULL; FP->Delete(Datas, ((Cell) y->FP)); Datas = y->Datas; delete y; return k; } /* * Impl�mentation de l'algorithme UNION-TAS-BINOMIAUX(T1, T2) avec T1 = this. * Il y a quelques changements par rapport a l'algorithme du cormen (voir rapport) */ PriorityList *BHeap::Union(PriorityList * P) { BHeap *x, *Before, *After; if ((P->GetType()) != GetType()) return GenericUnion(P); Merge((BHeap *) P); if (!(Brother)) { return this; } Before = this; x = Brother; After = x->Brother; while (After) { if ((x->Degree != After->Degree) || ((After->Brother) && (After->Brother->Degree == x->Degree))) { Before = x; x = After; } else { if (x->Key <= After->Key) { x->Brother = After->Brother; After->Link(x); } else { Before->Brother = After; x->Link(After); x = After; } } After = x->Brother; } return this; } /* * Impl�mentation de l'algorithme TAS-BINOMIAL-DIMINUER-CLE(T,x,k) avec T = this. * L'impl�mentation de cette routine a n�cessit� le rajout d'une table de pointeurs * pour conserver une structure correcte (voir rapport) */ bool BHeap::Lower_Key(Cell x, Key_t NKey) { BHeap *y, *z, *tx = ((BHeap *) ((CList *) x)->Datas); if (NKey > tx->Key) return false; tx->Key = NKey; for (y = tx, z = tx->Father; z && (y->Key < z->Key); y = z, z = y->Father) { SWAP(y->Datas, z->Datas); SWAP(y->Key, z->Key); SWAP(y->FP, z->FP); SWAP(((CList *) (y->FP))->Datas, ((CList *) (z->FP))->Datas); } return true; } /* * 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 BHeap::Delete(Datas_t & Datas, Cell x) { Key_t K; K = ReadKey(x); Lower_Key(x, M_INFINITY); Extract_Min(Datas); return K; } /* * Bool�en qui d�termine si le tas est vide ou pas. */ bool BHeap::IsEmpty(void) { return (!(Brother)); } /* * Lit la clef d'une cellule d'un tas. */ Key_t BHeap::ReadKey(Cell C) { return ((BHeap *) ((CList *) C)->Datas)->Key; } /* * Lit les donn�es d'une cellule d'un tas. */ Datas_t BHeap::ReadDatas(Cell C) { return ((BHeap *) ((CList *) C)->Datas)->Datas; }