Premier jetstart

1 files changed, 340 insertions, 0 deletions

diff --git a/lib/FHeap.cc b/lib/FHeap.cc
new file mode 100644
index 0000000..f8a206f
--- /dev/null
+++ b/lib/FHeap.cc
@@ -0,0 +1,340 @@
+#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);
+			}
+			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)
+{
+	FHeap *T;
+
+	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 ((P->GetType()) != (((PriorityList *) 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;
+}
+
+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 = Left;
+	x->Left->Right = 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));
+}