#include <stdio.h> #include "config.h" #include "PCommon.h" #include "FHeap.h" /* The Child of the Head of a FHeap is the min. The Key of the Head of a FHeap is the number of cells. The Degree of the Head is -1. */ static int d; void FHeap::Link(FHeap * x) { Right->Left = Left; Left->Right = Right; Father = x; if (x->Degree++) { Left = x->Child->Left; Right = x->Child; Left->Right = Right->Left = this; } else { x->Child = this; Left = Right = this; } Mark = false; } void FHeap::Rebuild(void) { FHeap *A[DFMAX], *w, *x, *y; int i, d; for (i = 0; i < DFMAX; i++) A[i] = NULL; /* L'impl�mentation de la phrase du Cormen 'pour chaque noeud w de la liste des racines de T' se fait de cette mani�re: comme chaque noeud de la liste des racines se retrouvera dans le tableau A, si nous voulons effectuer le travail sur un noeud w et qu'il se trouve d�j� dans le tableau A � l'emplacement de son propre degr�, c'est que nous avons fait le tour de la liste des racines. */ for (w = Child; A[w->Degree] != w; w = w->Right) { x = w; d = x->Degree; while (A[d]) { y = A[d]; if (x->Key > y->Key) { /* Attention, w va passer EN DESSOUS de la liste des racines. Nous devons pr�server w, puisque x == y. Donc comme x va dispara�tre de la liste des racines, le prochain �l�ment sur lequel nous travaillerons sera x->Right. Et son pr�desseur est x->Right->Left->Left, c'est � dire x->Left. C'est pourquoi nous faisons w = x->Left maintenant. */ w = x->Left; SWAP(x, y); } if (y == Child) { Child = x; } y->Link(x); A[d++] = NULL; } A[d] = x; /* Nous recalculons l'�ventuelle nouvelle valeur de max[T]. */ if (ReadKey(Child) > ReadKey(w)) { Child = w; } } /* Contrairement au Cormen, nous n'avons pas besoin de reconstruire ici la liste des racines de T. */ } void FHeap::Dump(ostream & os) { int i; FHeap *l; if (Degree == -1) { os << _(" * Head cell. (") << Key << ")\n |\n"; d = 0; } else { for (i = 1; i <= d; i++) os << " |"; os << (Child ? "_ " : "__ ") << Key << " (" << Degree << ")\n"; } if (Child) { d++; Child->Dump(os); d--; } l = Left->Right; Left->Right = NULL; if (Right) { Right->Dump(os); } Left->Right = l; } int FHeap::rn(void) { int n = 0; FHeap *l; if (Degree != -1) { n++; } if (Child) { n += Child->rn(); } l = Left->Right; Left->Right = NULL; if (Right) { n += Right->rn(); } Left->Right = l; return n; } FHeap::FHeap(void):Father(NULL), Child(NULL), Left(this), Right(this), Degree(-1), Mark(false) { type = T_FHEAP; } FHeap::FHeap(Key_t IKey, Datas_t const &IDatas):PriorityList(IKey, IDatas), Father(NULL), Child(NULL), Left(this), Right(this), Degree(0), Mark(false) { type = T_FHEAP; #ifdef DEBUG nc++; #endif } FHeap::~FHeap(void) { if (Child) { delete Child; } if (Right != this) { Left->Right = Right; Right->Left = Left; delete Right; } #ifdef DEBUG nd++; #endif } Cell FHeap::Min(void) { return Child; } FHeap *FHeap::Insert(FHeap * E) { if (Degree != -1) exception(2, _("Insert: not over Head.")); if (Child) { ((FHeap *) E)->Father = NULL; ((FHeap *) E)->Left = Child; ((FHeap *) E)->Right = Child->Right; Child->Right->Left = ((FHeap *) E); Child->Right = ((FHeap *) E); if (ReadKey(E) < (Child->Key)) { Child = ((FHeap *) E); } } else { Child = ((FHeap *) E); } Key++; return E; } Cell FHeap::Insert(Key_t IKey, Datas_t const &IDatas) { FHeap *P; if (!(P = new FHeap(IKey, IDatas))) exception(5, _("Insert: No more memory.")); return Insert(P); } Key_t FHeap::Extract_Min(Datas_t & Datas) { FHeap *z, *w; Key_t k; if (!(z = Child)) exception(4, _("Extract_Min: Priority List is empty.")); Datas = z->Datas; k = z->Key; /* Nous inversons ici l'id�e du Cormen... Au lieu de proc�der cas par cas, nous mettons d'abord en globalit� les p�res de tous les fils de z � NULL (ce qui nous permet de faire facilement la boucle, puisque, lorsque nous retombons sur une cellule dont le p�re est NULL, cela signifie que nous avons fait le tour) et � ce moment-l�, la liste des fils de z, index�e par z fait un superbe tas de Fibonacci que nous allons imm�diatement fusionner avec le tas en cours. De plus, nous supprimons z de la liste des racines maintenant. */ z->Right->Left = z->Left; z->Left->Right = z->Right; if ((Child = z->Right) == z) Child = NULL; z->Father = NULL; z->Left = z->Right = z; if (z->Child) { for (w = z->Child; w->Father; w = w->Left) w->Father = NULL; z->Degree = -1; z->Key = Child ? 0 : Key; // Pour conserver n[T] � jour. Union(z); } if (!(--Key)) { Child = NULL; } else { Rebuild(); } z->Child = NULL; delete z; return k; } PriorityList *FHeap::Union(PriorityList * P) { FHeap *Temp, *T = ((FHeap *) P); if (GetType() != (P->GetType())) return GenericUnion(P); /* Cette fonction ne suit pas du tout l'id�e du Cormen. Elle va fusionner directement T dans le tas en cours, sans cr�er d'interm�diaires. Les donn�es internes du tas sont mises � jour. */ if (!Child) { Child = T->Child; Key = T->Key; } else if (T->Child) { Child->Right->Left = T->Child; T->Child->Right->Left = Child; Temp = Child->Right; Child->Right = T->Child->Right; T->Child->Right = Temp; if (T->Child->Key < Child->Key) Child = T->Child; Key += T->Key; } T->Child = NULL; return this; } bool FHeap::Lower_Key(Cell x, Key_t NKey) { FHeap *y, *tx = ((FHeap *) x); if (NKey > tx->Key) return false; tx->Key = NKey; y = tx->Father; if ((y) && (tx->Key < y->Key)) { Cut(tx, y); CascadeCut(y); } if (NKey < Child->Key) Child = tx; return true; } Key_t FHeap::Delete(Datas_t & Datas, Cell x) { Key_t K; K = ReadKey(x); Lower_Key(x, M_INFINITY); Extract_Min(Datas); return K; } void FHeap::Cut(FHeap * x, FHeap * y) { /* Le fait de rajouter la cellule en cours � la liste des racines de T ne modifie en rien le comportement de min[T]. Sinon, cela voudrait dire que le minimum est la cellule que nous d�pla�ons et cela est impossible car le minimum est obligatoirement une racine. */ y->Degree--; x->Right->Left = x->Left; x->Left->Right = x->Right; if (y->Child == x) { y->Child = y->Degree ? x->Right : NULL; } x->Right = Child->Right; x->Left = Child; Child->Right->Left = x; Child->Right = x; x->Father = NULL; x->Mark = false; } void FHeap::CascadeCut(FHeap * y) { FHeap *z = y->Father; if (z) { if (!(y->Mark)) { y->Mark = true; } else { Cut(y, z); CascadeCut(z); } } } bool FHeap::IsEmpty(void) { return (!(Child)); }