Plein de changements

22 files changed, 642 insertions, 159 deletions

diff --git a/include/BHeap.h b/include/BHeap.h
index ab63852..d67ab29 100644
--- a/include/BHeap.h
+++ b/include/BHeap.h
@@ -10,10 +10,10 @@ class BHeap:public PriorityList {
 	BHeap *Father, *Child, *Brother;
 	CList *FP;
 
-	void Link(BHeap * z);	
-	void Merge(BHeap * H);	
+	void Link(BHeap * z);
+	void Merge(BHeap * H);
 	  BHeap(Key_t IKey, Datas_t const &IDatas);	// Insert 
-	Cell Insert(BHeap * x);	
+	Cell Insert(BHeap * x);
 
       public:
 	  BHeap(void);		// Constructor                         
@@ -22,15 +22,15 @@ class BHeap:public PriorityList {
 	virtual Key_t ReadKey(Cell C);
 	virtual Datas_t ReadDatas(Cell C);
 
-	virtual void Dump(ostream & os);	
+	virtual void Dump(ostream & os);
 	virtual bool IsEmpty(void);
 
-	virtual Cell Min(void);	
-	virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);	
-	virtual Key_t Extract_Min(Datas_t & Datas);	
-	virtual PriorityList *Union(PriorityList * P);	
-	virtual bool Lower_Key(Cell x, Key_t NKey);	
-	virtual Key_t Delete(Datas_t & Datas, Cell x);	
+	virtual Cell Min(void);
+	virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
+	virtual Key_t Extract_Min(Datas_t & Datas);
+	virtual PriorityList *Union(PriorityList * P);
+	virtual bool Lower_Key(Cell x, Key_t NKey);
+	virtual Key_t Delete(Datas_t & Datas, Cell x);
 };
 #else
 #error This librairy will only compile with a C++ compiler.
diff --git a/include/BinHeap.h b/include/BinHeap.h
new file mode 100644
index 0000000..8273365
--- /dev/null
+++ b/include/BinHeap.h
@@ -0,0 +1,36 @@
+#ifndef __BINHEAP_H__
+#define __BINHEAP_H__
+#include <PCommon.h>
+
+#define GRANUL 8
+
+struct binheap_t {
+	Key_t Key;
+	Datas_t Datas;
+};
+
+#ifdef __cplusplus
+typedef class BinHeap:public PriorityList { private:
+	void PackUp(int i);
+      public:
+	  BinHeap(void);	// Constructor                         
+	 ~BinHeap(void);	// Destructor
+
+	virtual int rn(void);
+
+	virtual void Dump(ostream & os);
+	virtual bool IsEmpty(void);
+	virtual Key_t ReadKey(Cell C);
+	virtual Datas_t ReadDatas(Cell C);
+
+	virtual Cell Min(void);
+	virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
+	virtual Key_t Extract_Min(Datas_t & Datas);
+	virtual PriorityList *Union(PriorityList * P);
+	virtual bool Lower_Key(Cell x, Key_t NKey);
+	virtual Key_t Delete(Datas_t & Datas, Cell x);
+} BinHeap;
+#else
+#error This librairy will only compile with a C++ compiler.
+#endif
+#endif
diff --git a/include/FHeap.h b/include/FHeap.h
index ac58a6d..65d9253 100644
--- a/include/FHeap.h
+++ b/include/FHeap.h
@@ -10,10 +10,10 @@ typedef class FHeap:public PriorityList {
 	int Degree;
 	bool Mark;
 
-	void Link(FHeap * x);	
-	void Rebuild(void);	
+	void Link(FHeap * x);
+	void Rebuild(void);
 	  FHeap(Key_t IKey, Datas_t const &IDatas);	// Insert 
-	FHeap *Insert(FHeap * x);	
+	FHeap *Insert(FHeap * x);
 	void Cut(FHeap * x, FHeap * y);
 	void CascadeCut(FHeap * y);
 
@@ -24,13 +24,12 @@ typedef class FHeap:public PriorityList {
 	virtual int rn(void);
 
 	virtual void Dump(ostream & os);
-	void RDump(ostream & os);
 	virtual bool IsEmpty(void);
 
-	virtual Cell Min(void);	
-	virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);	
+	virtual Cell Min(void);
+	virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
 	virtual Key_t Extract_Min(Datas_t & Datas);
-	virtual PriorityList *Union(PriorityList * P);	
+	virtual PriorityList *Union(PriorityList * P);
 	virtual bool Lower_Key(Cell x, Key_t NKey);
 	virtual Key_t Delete(Datas_t & Datas, Cell x);
 } FHeap;
diff --git a/include/HTree.h b/include/HTree.h
index 7a8dea0..18150b1 100644
--- a/include/HTree.h
+++ b/include/HTree.h
@@ -8,15 +8,15 @@
 #ifdef __cplusplus
 
 class HTree {
-private:
-    HTree * left, * right;
-    int freq;
-    Datas_t objet;
-public:
-    HTree(int n_freq, char * n_objet);
-    HTree(HTree * n_left, HTree * n_right);
-    ~HTree();
-    ostream & Trace(ostream & os, int d = 0);
+      private:
+	HTree * left, *right;
+	int freq;
+	Datas_t objet;
+      public:
+	  HTree(int n_freq, char *n_objet);
+	  HTree(HTree * n_left, HTree * n_right);
+	 ~HTree();
+	  ostream & Trace(ostream & os, int d = 0);
 };
 
 #else
diff --git a/include/Hash.h b/include/Hash.h
deleted file mode 100644
index a8d8c1e..0000000
--- a/include/Hash.h
+++ /dev/null
@@ -1,9 +0,0 @@
-#ifndef __HASH_H__
-#define __HASH_H__
-
-class Hash {
-      private:
-	void *table;
-};
-
-#endif
diff --git a/include/Makefile.am b/include/Makefile.am
index a2c74d9..c0518e5 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -1 +1 @@
-include_HEADERS = PCommon.h PLList.h FHeap.h BHeap.h Hash.h CList.h SList.h PTypes.h
+include_HEADERS = PCommon.h PLList.h FHeap.h BHeap.h BinHeap.h CList.h SList.h PTypes.h
diff --git a/include/PTypes.h b/include/PTypes.h
index 6e4e7b7..418eca5 100644
--- a/include/PTypes.h
+++ b/include/PTypes.h
@@ -12,10 +12,10 @@ typedef void *Datas_t;
 typedef void *Cell;
 
 enum {
-  T_PLLIST = 1,
-  T_BINHEAP,
-  T_BHEAP,
-  T_FHEAP
+	T_PLLIST = 1,
+	T_BINHEAP,
+	T_BHEAP,
+	T_FHEAP
 };
 
 #endif
diff --git a/include/SList.h b/include/SList.h
index 845d83a..4407b2b 100644
--- a/include/SList.h
+++ b/include/SList.h
@@ -6,7 +6,8 @@
 
 #ifdef __cplusplus
 
-class SList:public CList { public:
+class SList:public CList {
+      public:
 	virtual Cell Insert(Key_t IKey, Datas_t const &IDatas);
 };
 
diff --git a/lib/BHeap.cc b/lib/BHeap.cc
index 4d7cc9e..ef4bd04 100644
--- a/lib/BHeap.cc
+++ b/lib/BHeap.cc
@@ -3,8 +3,52 @@
 #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;
@@ -30,6 +74,12 @@ void BHeap::Dump(ostream & 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;
@@ -46,6 +96,11 @@ int BHeap::rn(void)
 	return n;
 }
 
+
+ /*
+  * Implémentation directe de la primitive LIEN-BINOMIAL(y, z) avec y = this.
+  */
+
 void BHeap::Link(BHeap * z)
 {
 	Father = z;
@@ -54,6 +109,15 @@ void BHeap::Link(BHeap * z)
 	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éé.
+  */
+
 void BHeap::Merge(BHeap * H)
 {
 	BHeap *P1, *P2, *T1, *T2;
@@ -78,21 +142,38 @@ void BHeap::Merge(BHeap * H)
 	H->Brother = NULL;
 }
 
-BHeap::BHeap(void):Degree(-1), Father(NULL), Child(NULL), Brother(NULL),
-FP(new CList)
+
+ /*
+  * Constructeur d'un tas binomial.
+  */
+
+BHeap::BHeap(void):Degree(-1), Father(NULL), Child(NULL), Brother(NULL), FP(new CList)
 {
-  type = T_BHEAP;
+	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;
+	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 (voir rapport).
+  */
+
 BHeap::~BHeap(void)
 {
 	if (Degree == -1)
@@ -109,6 +190,11 @@ BHeap::~BHeap(void)
 #endif
 }
 
+
+ /*
+  * Implémentation directe de l'algorithme MINIMUM-TAS-BINOMIAL(T) avec T = this.
+  */
+
 Cell BHeap::Min(void)
 {
 	BHeap *x = this, *y = NULL;
@@ -124,6 +210,12 @@ Cell BHeap::Min(void)
 	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;
@@ -139,6 +231,11 @@ Cell BHeap::Insert(BHeap * E)
 	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;
@@ -150,6 +247,15 @@ Cell BHeap::Insert(Key_t IKey, Datas_t const &IDatas)
 	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;
@@ -163,6 +269,8 @@ Key_t BHeap::Extract_Min(Datas_t & Datas)
 
 	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;
@@ -172,10 +280,14 @@ Key_t BHeap::Extract_Min(Datas_t & Datas)
 		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.
 	for (P = y->Child; P;) {
 		P2 = Before->Brother;
 		P3 = P->Brother;
@@ -184,9 +296,11 @@ Key_t BHeap::Extract_Min(Datas_t & Datas)
 		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));
@@ -196,6 +310,11 @@ Key_t BHeap::Extract_Min(Datas_t & Datas)
 	return k;
 }
 
+
+ /*
+  * Implémentation directe de l'algorithme UNION-TAS-BINOMIAUX(T1, T2) avec T1 = this.
+  */
+
 PriorityList *BHeap::Union(PriorityList * P)
 {
 	BHeap *x, *Before, *After;
@@ -231,6 +350,13 @@ PriorityList *BHeap::Union(PriorityList * P)
 	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);
@@ -239,8 +365,7 @@ bool BHeap::Lower_Key(Cell x, Key_t NKey)
 		return false;
 	tx->Key = NKey;
 
-	for (y = tx, z = tx->Father; z && (y->Key < z->Key);
-	     y = z, z = y->Father) {
+	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);
@@ -250,6 +375,13 @@ bool BHeap::Lower_Key(Cell x, Key_t NKey)
 	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;
@@ -262,16 +394,31 @@ Key_t BHeap::Delete(Datas_t & Datas, Cell x)
 	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;
diff --git a/lib/BinHeap.cc b/lib/BinHeap.cc
new file mode 100644
index 0000000..7080a97
--- /dev/null
+++ b/lib/BinHeap.cc
@@ -0,0 +1,180 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "config.h"
+#include "BinHeap.h"
+
+#define FATHER(i) (i >> 2)
+#define LEFT(i) (i << 2)
+#define RIGHT(i) ((i <<2) + 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;
+	
+	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;
+	if (min != i) {
+		SWAP(binheap[i - 1], binheap[min - 1]);
+		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);
+}
+
+
+ /*
+  * Comme pour l'Union, nous allons devoir utiliser une méthode lente pour
+  * effectuer le diminuer clef (voir rapport)
+  */
+
+bool BinHeap::Lower_Key(Cell x, Key_t NKey)
+{
+	Datas_t Datas;
+	Key_t Key;
+
+	Key = Delete(Datas, x);
+	Insert(Key, Datas);
+	return true;
+}
+
+BinHeap::BinHeap(void)
+{
+	Key = 0;
+	Datas = NULL;
+}
+
+BinHeap::~BinHeap(void)
+{
+	if (Datas)
+		free(Datas);
+}
+
+Key_t BinHeap::ReadKey(Cell C)
+{
+	return ((binheap_t *) C)->Key;
+}
+
+Datas_t BinHeap::ReadDatas(Cell C)
+{
+	return ((binheap_t *) 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 Datas;
+}
+
+Cell BinHeap::Insert(Key_t IKey, Datas_t const &IDatas)
+{
+	binheap_t newcell = { IKey, IDatas }, *binheap;
+	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"));
+		}
+	}
+	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);
+	}
+	binheap[i - 1] = newcell;
+
+	return &(binheap[i - 1]);
+}
+
+
+ /*
+  * 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 *) Datas;
+	Key_t ret;
+
+	if (Key < 1)
+		exception(5, _("negative overflow"));
+
+
+	ret = binheap[0].Key;
+	Datas = binheap[0].Datas;
+	binheap[0] = binheap[Key - 1];
+
+	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));
+	}
+	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;
+}
diff --git a/lib/CList.cc b/lib/CList.cc
index c54e6e1..7e1f39a 100644
--- a/lib/CList.cc
+++ b/lib/CList.cc
@@ -2,6 +2,20 @@
 #include "config.h"
 #include "CList.h"
 
+/*************************\
+*                         *
+*     Liste chaînée.      *
+*                         *
+\*************************/
+
+ /*
+
+  * Toutes les fonctions écrites dans ce modules servent à la construction
+  * de liste doublement chaînées, non triées. Ces fonctions étant connues
+  * depuis quelques temps déjà, il me semble inutile de les commenter en détail.
+  *
+  */
+
 CList::CList(CList * IPoint, Datas_t IDatas, Key_t IKey):Left(IPoint), Right(IPoint->Right), Key(IKey), Datas(IDatas)
 {
 	Left->Right = this;
diff --git a/lib/FHeap.cc b/lib/FHeap.cc
index f8a206f..9f3dc24 100644
--- a/lib/FHeap.cc
+++ b/lib/FHeap.cc
@@ -82,8 +82,7 @@ void FHeap::Dump(ostream & os)
 	} else {
 		for (i = 1; i <= d; i++)
 			os << " |";
-		os << (Child ? "_  " : "__ ") << Key << " (" << Degree <<
-			")\n";
+		os << (Child ? "_  " : "__ ") << Key << " (" << Degree << ")\n";
 	}
 	if (Child) {
 		d++;
@@ -121,16 +120,15 @@ int FHeap::rn(void)
 	return n;
 }
 
-FHeap::FHeap(void):Father(NULL), Child(NULL), Left(this), Right(this),
-Degree(-1), Mark(false)
+FHeap::FHeap(void):Father(NULL), Child(NULL), Left(this), Right(this), Degree(-1), Mark(false)
 {
-  type = T_FHEAP;
+	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;
+	type = T_FHEAP;
 #ifdef DEBUG
 	nc++;
 #endif
diff --git a/lib/HTree.cc b/lib/HTree.cc
index c651f48..b8731e4 100644
--- a/lib/HTree.cc
+++ b/lib/HTree.cc
@@ -3,38 +3,46 @@
 #include "config.h"
 #include "HTree.h"
 
-HTree::HTree(int n_freq, char * n_objet) {
-  freq = n_freq;
-  objet = n_objet;
-  left = right = NULL;
+HTree::HTree(int n_freq, char *n_objet)
+{
+	freq = n_freq;
+	objet = n_objet;
+	left = right = NULL;
 }
 
-HTree::HTree(HTree * n_left, HTree * n_right) {
-  left = n_left;
-  right = n_right;
-  freq = n_left->freq + n_right->freq;
-  objet = NULL;
+HTree::HTree(HTree * n_left, HTree * n_right)
+{
+	left = n_left;
+	right = n_right;
+	freq = n_left->freq + n_right->freq;
+	objet = NULL;
 }
 
-HTree::~HTree() {
-  if (left) delete left;
-  if (right) delete right;
+HTree::~HTree()
+{
+	if (left)
+		delete left;
+
+	if (right)
+		delete right;
 }
 
-ostream & HTree::Trace(ostream & os, int d) {
-  static char cmpr[MAX_HDEPTH + 1];
-  if (objet) {
-    cmpr[d] = '\0';
-    os << objet << " = " << cmpr << endl;
-  } else {
-    if (left) {
-      cmpr[d] = '0';
-      left->Trace(os, d + 1);
-    }
-    if (right) {
-      cmpr[d] = '1';
-      right->Trace(os, d + 1);
-    }
-  }
-  return os;
+ostream & HTree::Trace(ostream & os, int d)
+{
+	static char cmpr[MAX_HDEPTH + 1];
+
+	if (objet) {
+		cmpr[d] = '\0';
+		os << objet << " = " << cmpr << endl;
+	} else {
+		if (left) {
+			cmpr[d] = '0';
+			left->Trace(os, d + 1);
+		}
+		if (right) {
+			cmpr[d] = '1';
+			right->Trace(os, d + 1);
+		}
+	}
+	return os;
 }
diff --git a/lib/Hash.cc b/lib/Hash.cc
deleted file mode 100644
index 146f061..0000000
--- a/lib/Hash.cc
+++ /dev/null
@@ -1,3 +0,0 @@
-#include <stdio.h>
-#include "config.h"
-#include "Hash.h"
diff --git a/lib/Makefile.am b/lib/Makefile.am
index 9e99421..71b12e7 100644
--- a/lib/Makefile.am
+++ b/lib/Makefile.am
@@ -4,7 +4,7 @@ AM_CFLAGS = -O3 -Wall -Wstrict-prototypes $(CFLAGS)
 INCLUDES = -I. -I.. -I$(includedir) -I../include
 lib_LTLIBRARIES = libPriorityLists.la
 
-libPriorityLists_la_SOURCES = PCommon.cc BHeap.cc FHeap.cc Hash.cc PLList.cc CList.cc SList.cc HTree.cc
+libPriorityLists_la_SOURCES = PCommon.cc BHeap.cc FHeap.cc BinHeap.cc PLList.cc CList.cc SList.cc HTree.cc
 
 libPriorityLists_la_LDFLAGS = -version-info $(PriorityLists_VERSION_INFO)
 
diff --git a/lib/PCommon.cc b/lib/PCommon.cc
index 20299ba..b833a10 100644
--- a/lib/PCommon.cc
+++ b/lib/PCommon.cc
@@ -2,8 +2,17 @@
 #include "config.h"
 #include "PCommon.h"
 
-PriorityList::PriorityList(Key_t IKey, Datas_t const &IDatas):Key(IKey),
-Datas(IDatas)
+ /*
+
+  * Toutes les méthodes écrites dans ce module sont communes à toutes
+  * les files de priorités. Il s'agit de la classe "Père" dont héritent
+  * toutes les autres files de priorités. Nous ne trouverons ici que
+  * les constructeurs nécessaires pour la bonne opération sur les files,
+  * ainsi que les deux routines génériques n est GenericUnion.
+  *
+  */
+
+PriorityList::PriorityList(Key_t IKey, Datas_t const &IDatas):Key(IKey), Datas(IDatas)
 {
 }
 
@@ -11,23 +20,27 @@ PriorityList::PriorityList(void):Key(0), Datas(NULL)
 {
 }
 
-PriorityList::~PriorityList(void){}
-
-Key_t PriorityList::ReadKey(Cell C)
+PriorityList::~PriorityList(void)
 {
-	return ((PriorityList *) C)->Key;
 }
 
-Datas_t PriorityList::ReadDatas(Cell C)
-{
-	return ((PriorityList *) C)->Datas;
-}
+
+ /*
+  * Renvoie le nombre d'éléments dans la file.
+  */
 
 int PriorityList::n(void)
 {
 	return Key;
 }
 
+
+ /*
+  * Effectue un union générique entre deux files de type différents.
+  * Cette fonction va dépiler la deuxième file élément par éléments
+  * et va les insérer dans la première.
+  */
+
 PriorityList *PriorityList::GenericUnion(PriorityList * P)
 {
 	Key_t IKey;
@@ -39,6 +52,25 @@ PriorityList *PriorityList::GenericUnion(PriorityList * P)
 	}
 }
 
-int PriorityList::GetType(void) {
-  return type;
+
+ /*
+  * Renvoie une constante sur le type de la file. Ce type est initialisé
+  * par le constructeur des files.
+  */
+
+int PriorityList::GetType(void)
+{
+	return type;
+}
+
+
+
+Key_t PriorityList::ReadKey(Cell C)
+{
+	return ((PriorityList *) C)->Key;
+}
+
+Datas_t PriorityList::ReadDatas(Cell C)
+{
+	return ((PriorityList *) C)->Datas;
 }
diff --git a/lib/PLList.cc b/lib/PLList.cc
index 5234b91..48d294c 100644
--- a/lib/PLList.cc
+++ b/lib/PLList.cc
@@ -2,6 +2,23 @@
 #include "config.h"
 #include "PLList.h"
 
+/*****************************************************\
+*                                                     *
+* File de priorité basée sur une liste chaînée triée. *
+*                                                     *
+\*****************************************************/
+
+ /*
+
+  * Cette file de priorité a une structure non récursive. Elle se base sur
+  * une SList pour fonctionner. 
+  *
+  */
+
+
+ /*
+  * La méthode "Union" est en fait l'algorithme "Fusion" du tri-fusion.
+  */
 
 PriorityList *PLList::Union(PriorityList * P)
 {
@@ -37,6 +54,13 @@ PriorityList *PLList::Union(PriorityList * P)
 	return this;
 }
 
+
+ /*
+  * Cette méthode va "décrocher" l'élément de la liste
+  * et va tenter de trouver sa nouvelle place, en se déplaçant
+  * depuis son ancienne place vers la "gauche".
+  */
+
 bool PLList::Lower_Key(Cell x, Key_t NKey)
 {
 	CList *T = ((CList *) x), *t;
@@ -51,8 +75,7 @@ bool PLList::Lower_Key(Cell x, Key_t NKey)
 	if (T->Right)
 		T->Right->Left = T->Left;
 
-	for (t = T->Left; ((t->Left->Left) && (NKey < t->Left->Key));
-	     t = t->Left) ;
+	for (t = T->Left; ((t->Left->Left) && (NKey < t->Left->Key)); t = t->Left) ;
 
 	T->Left = t->Left;
 	T->Right = t;
@@ -61,25 +84,34 @@ bool PLList::Lower_Key(Cell x, Key_t NKey)
 }
 
 
+ /*
+  * Toutes les autres méthodes sont "simples" (c'est à dire une lignes ou deux)
+  * et parlent d'elles-même. Nul besoin de commentaires pour elles. Elles se
+  * basent en grande partie sur la SList présente dans la structure.
+  */
+
 PLList::PLList(void)
 {
 	type = T_PLLIST;
 	Key = 0;
 	Datas = NULL;
-};
+}
+
 PLList::~PLList(void)
 {
 	delete Head.Right;
-};
+}
 
 Key_t PLList::ReadKey(Cell C)
 {
 	return Head.ReadKey(C);
-};
+}
+
 Datas_t PLList::ReadDatas(Cell C)
 {
 	return Head.ReadDatas(C);
-};
+}
+
 int PLList::rn(void)
 {
 	int n = 0;
diff --git a/lib/SList.cc b/lib/SList.cc
index fef50e9..c65d299 100644
--- a/lib/SList.cc
+++ b/lib/SList.cc
@@ -1,6 +1,20 @@
 #include <stdio.h>
 #include "SList.h"
 
+/**********************\
+*                      *
+*  Liste chaînée triée *
+*                      *
+\**********************/
+
+ /*
+
+  * Nous faisons une classe dérivée de la classe CList. La seule méthode qui
+  * va changer pour créer une liste chaînée triée est l'Insertion. Elle va
+  * placer directement l'élément à insérer à la bonne place.
+  *
+  */
+
 Cell SList::Insert(Key_t IKey, Datas_t const &IDatas)
 {
 	CList *I = this, *x;
diff --git a/po/POTFILES.in b/po/POTFILES.in
index 4a2746b..196d40a 100644
--- a/po/POTFILES.in
+++ b/po/POTFILES.in
@@ -1,4 +1,9 @@
 src/test.cc
 lib/FHeap.cc
 lib/BHeap.cc
-lib/Hash.cc
\ No newline at end of file
+lib/BinHeap.cc
+lib/CList.cc
+lib/SList.cc
+lib/PLList.cc
+lib/PCommon.cc
+lib/HTree.cc
diff --git a/po/PriorityLists.pot b/po/PriorityLists.pot
index 7446747..424fc6a 100644
--- a/po/PriorityLists.pot
+++ b/po/PriorityLists.pot
@@ -6,7 +6,7 @@
 msgid ""
 msgstr ""
 "Project-Id-Version: PACKAGE VERSION\n"
-"POT-Creation-Date: 2001-01-13 22:41+0100\n"
+"POT-Creation-Date: 2001-03-03 23:47+0100\n"
 "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
 "Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
 "Language-Team: LANGUAGE <LL@li.org>\n"
@@ -14,7 +14,7 @@ msgstr ""
 "Content-Type: text/plain; charset=CHARSET\n"
 "Content-Transfer-Encoding: ENCODING\n"
 
-#: src/test.cc:32
+#: src/test.cc:33
 msgid "Creation of a priority list and adding "
 msgstr ""
 
@@ -22,13 +22,13 @@ msgstr ""
 msgid " random entrie(s)..."
 msgstr ""
 
-#: src/test.cc:38
+#: src/test.cc:39
 msgid ""
 "Ok.\n"
 "Deleting the list..."
 msgstr ""
 
-#: src/test.cc:43 src/test.cc:48
+#: src/test.cc:44 src/test.cc:48
 msgid "List has "
 msgstr ""
 
@@ -36,77 +36,85 @@ msgstr ""
 msgid " keys. Expecting "
 msgstr ""
 
-#: src/test.cc:45 src/test.cc:51
+#: src/test.cc:45 src/test.cc:49
 msgid "List corrupted."
 msgstr ""
 
-#: src/test.cc:49
+#: src/test.cc:48
 msgid " keys (real count). Expecting "
 msgstr ""
 
-#: src/test.cc:55 src/test.cc:125
+#: src/test.cc:53 src/test.cc:125
 msgid "Incorrect order."
 msgstr ""
 
-#: src/test.cc:71
+#: src/test.cc:69
 msgid "Size of a PriorityList cell: "
 msgstr ""
 
-#: src/test.cc:73
+#: src/test.cc:70
 msgid "Size of a BHeap cell       : "
 msgstr ""
 
-#: src/test.cc:74
+#: src/test.cc:71
 msgid "Size of a FHeap cell       : "
 msgstr ""
 
-#: src/test.cc:75
-msgid "Size of a PList header     : "
+#: src/test.cc:72
+msgid "Size of a PLList header    : "
 msgstr ""
 
-#: src/test.cc:76
+#: src/test.cc:73
 msgid "Size of a CList cell       : "
 msgstr ""
 
-#: src/test.cc:77
+#: src/test.cc:74
 msgid "Size of a SList cell       : "
 msgstr ""
 
-#: src/test.cc:91
+#: src/test.cc:75
+msgid "Size of a BinHeap header   : "
+msgstr ""
+
+#: src/test.cc:76
+msgid "Size of a BinHeap cell     : "
+msgstr ""
+
+#: src/test.cc:92
 msgid "Creating a priority list and adding keys:\n"
 msgstr ""
 
-#: src/test.cc:103 src/test.cc:110 src/test.cc:114
+#: src/test.cc:105 src/test.cc:112 src/test.cc:116
 msgid ""
 "Ok.\n"
 "List browsing...\n"
 msgstr ""
 
-#: src/test.cc:105
+#: src/test.cc:107
 msgid ""
 "Ok.\n"
 "Extract_Min + List browsing...\n"
 msgstr ""
 
-#: src/test.cc:108
+#: src/test.cc:110
 msgid ""
 "Ok.\n"
 "Lower_Key(-12) over 59...\n"
 msgstr ""
 
-#: src/test.cc:112
+#: src/test.cc:114
 msgid ""
 "Ok.\n"
 "Delete over 54...\n"
 msgstr ""
 
-#: src/test.cc:118
+#: src/test.cc:120
 msgid ""
 "Ok.\n"
 "Extracting datas...\n"
 msgstr ""
 
-#: src/test.cc:120
+#: src/test.cc:122
 msgid "Minimum #"
 msgstr ""
 
@@ -121,20 +129,34 @@ msgstr ""
 msgid " * Head cell. ("
 msgstr ""
 
-#: lib/BHeap.cc:130 lib/FHeap.cc:162
+#: lib/BHeap.cc:224 lib/FHeap.cc:162
 msgid "Insert: not over Head."
 msgstr ""
 
-#: lib/BHeap.cc:132 lib/BHeap.cc:147 lib/FHeap.cc:184
+#: lib/BHeap.cc:226 lib/BHeap.cc:246 lib/FHeap.cc:184
 msgid "Insert: No more memory."
 msgstr ""
 
-#: lib/BHeap.cc:160 lib/FHeap.cc:194
+#: lib/BHeap.cc:268 lib/FHeap.cc:194 lib/PLList.cc:150
 msgid "Extract_Min: Priority List is empty."
 msgstr ""
 
-#: lib/BHeap.cc:13
+#: lib/BHeap.cc:57
 msgid ""
 " * Head cell.\n"
 " |\n"
 msgstr ""
+
+#: lib/BinHeap.cc:120
+msgid "Not enough memory"
+msgstr ""
+
+#: lib/BinHeap.cc:147
+msgid "negative overflow"
+msgstr ""
+
+#: lib/PLList.cc:126
+msgid ""
+" * Head cell\n"
+" |\n"
+msgstr ""
diff --git a/po/cat-id-tbl.c b/po/cat-id-tbl.c
index 395b400..b7c079f 100644
--- a/po/cat-id-tbl.c
+++ b/po/cat-id-tbl.c
@@ -21,37 +21,44 @@ Deleting the list...", 4},
   {"Size of a PriorityList cell: ", 10},
   {"Size of a BHeap cell       : ", 11},
   {"Size of a FHeap cell       : ", 12},
-  {"Size of a PList header     : ", 13},
+  {"Size of a PLList header    : ", 13},
   {"Size of a CList cell       : ", 14},
   {"Size of a SList cell       : ", 15},
-  {"Creating a priority list and adding keys:\n", 16},
+  {"Size of a BinHeap header   : ", 16},
+  {"Size of a BinHeap cell     : ", 17},
+  {"Creating a priority list and adding keys:\n", 18},
   {"\
 Ok.\n\
-List browsing...\n", 17},
+List browsing...\n", 19},
   {"\
 Ok.\n\
-Extract_Min + List browsing...\n", 18},
+Extract_Min + List browsing...\n", 20},
   {"\
 Ok.\n\
-Lower_Key(-12) over 59...\n", 19},
+Lower_Key(-12) over 59...\n", 21},
   {"\
 Ok.\n\
-Delete over 54...\n", 20},
+Delete over 54...\n", 22},
   {"\
 Ok.\n\
-Extracting datas...\n", 21},
-  {"Minimum #", 22},
+Extracting datas...\n", 23},
+  {"Minimum #", 24},
   {"\
 Ok.\n\
 \n\
-All the tests were successfull\n", 23},
-  {" * Head cell. (", 24},
-  {"Insert: not over Head.", 25},
-  {"Insert: No more memory.", 26},
-  {"Extract_Min: Priority List is empty.", 27},
+All the tests were successfull\n", 25},
+  {" * Head cell. (", 26},
+  {"Insert: not over Head.", 27},
+  {"Insert: No more memory.", 28},
+  {"Extract_Min: Priority List is empty.", 29},
   {"\
  * Head cell.\n\
- |\n", 28},
+ |\n", 30},
+  {"Not enough memory", 31},
+  {"negative overflow", 32},
+  {"\
+ * Head cell\n\
+ |\n", 33},
 };
 
-int _msg_tbl_length = 28;
+int _msg_tbl_length = 33;
diff --git a/src/test.cc b/src/test.cc
index 9dbc455..924cba3 100644
--- a/src/test.cc
+++ b/src/test.cc
@@ -3,6 +3,7 @@
 #include "config.h"
 #include "BHeap.h"
 #include "FHeap.h"
+#include "BinHeap.h"
 #include "PLList.h"
 
 char N[] = {
@@ -19,7 +20,7 @@ void exception(int e, char *msg)
 
 PriorityList *newlist(void)
 {
-	return new FHeap;
+	return new BinHeap;
 }
 
 void DoCombTest(int number)
@@ -29,10 +30,10 @@ void DoCombTest(int number)
 	Datas_t Datas;
 	PriorityList *T;
 
-	cerr << _("Creation of a priority list and adding ") << number <<
-		_(" random entrie(s)...");
+	cerr << _("Creation of a priority list and adding ") << number << _(" random entrie(s)...");
 	T = newlist();
 	for (i = 1; i <= number; i++) {
+		T->Dump(cerr);
 		T->Insert(rand() % P_INFINITY, NULL);
 	}
 	cerr << _("Ok.\nDeleting the list...");
@@ -40,14 +41,11 @@ void DoCombTest(int number)
 	for (i = number; i >= 1; i--) {
 		T->Dump(cerr);
 		if (T->n() != i) {
-			cerr << _("List has ") << T->
-				n() << _(" keys. Expecting ") << i << endl;
+			cerr << _("List has ") << T->n() << _(" keys. Expecting ") << i << endl;
 			exception(1, _("List corrupted."));
 		}
 		if ((n = T->rn()) != i) {
-			cerr << _("List has ") << T->
-				rn() << _(" keys (real count). Expecting ") <<
-				i << endl;
+			cerr << _("List has ") << T->rn() << _(" keys (real count). Expecting ") << i << endl;
 			exception(1, _("List corrupted."));
 		}
 		K = T->Extract_Min(Datas);
@@ -68,17 +66,20 @@ void FullTest(void)
 	Key_t K;
 	int i;
 
-	cerr << _("Size of a PriorityList cell: ") << sizeof(PriorityList) <<
-		endl;
+	cerr << _("Size of a PriorityList cell: ") << sizeof(PriorityList) << endl;
 	cerr << _("Size of a BHeap cell       : ") << sizeof(BHeap) << endl;
 	cerr << _("Size of a FHeap cell       : ") << sizeof(FHeap) << endl;
-	cerr << _("Size of a PList header     : ") << sizeof(PLList) << endl;
+	cerr << _("Size of a PLList header    : ") << sizeof(PLList) << endl;
 	cerr << _("Size of a CList cell       : ") << sizeof(CList) << endl;
 	cerr << _("Size of a SList cell       : ") << sizeof(SList) << endl;
+	cerr << _("Size of a BinHeap header   : ") << sizeof(BinHeap) << endl;
+	cerr << _("Size of a BinHeap cell     : ") << sizeof(binheap_t) << endl;
 
+/*
 	DoCombTest(0);
 	DoCombTest(10);
 	DoCombTest(70);
+*/
 //  DoCombTest(1000);
 //  DoCombTest(10000);
 #ifdef BT
@@ -91,7 +92,8 @@ void FullTest(void)
 	cerr << _("Creating a priority list and adding keys:\n");
 	T = newlist();
 	for (i = 0; i < 30; i++) {
-		fprintf(stderr, "%i ", N[i]);
+		T->Dump(cerr);
+		fprintf(stderr, "%i \n", N[i]);
 		T->Insert(N[i], NULL);
 	}
 
@@ -117,9 +119,7 @@ void FullTest(void)
 	cerr << T->Extract_Min(Datas) << endl;
 	cerr << _("Ok.\nExtracting datas...\n");
 	for (i = 1; i <= 30; i++) {
-		cerr << _("Minimum #") << i << " = " << (K =
-							 (T->
-							  Extract_Min(Datas)))
+		cerr << _("Minimum #") << i << " = " << (K = (T->Extract_Min(Datas)))
 			<< endl;
 		if (K != i)
 			exception(1, _("Incorrect order."));