Version finale pour les algos.

6 files changed, 58 insertions, 20 deletions

diff --git a/lib/BHeap.cc b/lib/BHeap.cc
index 1dfe6de..aaec87a 100644
--- a/lib/BHeap.cc
+++ b/lib/BHeap.cc
@@ -115,7 +115,7 @@ void BHeap::Link(BHeap * z)
   * 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éé.
+  * APRES T1, et aucun tas binaire nouveau ne sera créé. (voir rapport)
   */
 
 void BHeap::Merge(BHeap * H)
@@ -288,6 +288,8 @@ Key_t BHeap::Extract_Min(Datas_t & Datas)
 
 	// 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;
diff --git a/lib/BinHeap.cc b/lib/BinHeap.cc
index 45f77e6..450ff4a 100644
--- a/lib/BinHeap.cc
+++ b/lib/BinHeap.cc
@@ -2,6 +2,7 @@
 #include <stdlib.h>
 #include "config.h"
 #include "BinHeap.h"
+#include "CList.h"
 
 #define FATHER(i) (i >> 1)
 #define LEFT(i) (i << 1)
@@ -29,6 +30,7 @@ void BinHeap::PackUp(int i)
 		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);
 	}
 }
@@ -45,26 +47,26 @@ PriorityList *BinHeap::Union(PriorityList * P)
 
 
  /*
-  * Comme pour l'Union, nous allons devoir utiliser une méthode lente pour
-  * effectuer le diminuer clef (voir rapport)
+  * L'algorithme "Diminuer Clef" ressemble à l'algorithme "Inserer"
   */
 
 bool BinHeap::Lower_Key(Cell x, Key_t NKey)
 {
-	int i = ((binheap_t *) x) - ((binheap_t *) Datas) + 1;
+	int i = ((binheap_t *) (FP->ReadDatas(x))) - ((binheap_t *) Datas) + 1;
 	binheap_t *binheap = (binheap_t *) Datas;
 
-	if (((binheap_t *) x)->Key < NKey)
+	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)
+BinHeap::BinHeap(void):FP(new CList)
 {
 	Key = 0;
 	Datas = NULL;
@@ -78,12 +80,12 @@ BinHeap::~BinHeap(void)
 
 Key_t BinHeap::ReadKey(Cell C)
 {
-	return ((binheap_t *) C)->Key;
+	return ((binheap_t *) FP->ReadDatas(C))->Key;
 }
 
 Datas_t BinHeap::ReadDatas(Cell C)
 {
-	return ((binheap_t *) C)->Datas;
+	return ((binheap_t *) FP->ReadDatas(C))->Datas;
 }
 
 int BinHeap::rn(void)
@@ -109,9 +111,14 @@ bool BinHeap::IsEmpty(void)
 
 Cell BinHeap::Min(void)
 {
-	return Datas;
+	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;
@@ -132,7 +139,7 @@ Cell BinHeap::Insert(Key_t IKey, Datas_t const &IDatas)
 	}
 	binheap[i - 1] = newcell;
 
-	return &(binheap[i - 1]);
+	return (binheap[i - 1].FP = FP->Insert(0, &(binheap[i - 1])));
 }
 
 
@@ -144,6 +151,7 @@ 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"));
@@ -151,6 +159,7 @@ Key_t BinHeap::Extract_Min(Datas_t & Datas)
 
 	ret = binheap[0].Key;
 	Datas = binheap[0].Datas;
+	FP->Delete(Dumb, binheap[0].FP);
 	binheap[0] = binheap[Key - 1];
 
 	int i = Key--;
diff --git a/lib/FHeap.cc b/lib/FHeap.cc
index 158a1e5..a10e089 100644
--- a/lib/FHeap.cc
+++ b/lib/FHeap.cc
@@ -58,13 +58,17 @@ void FHeap::Rebuild(void)
 				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))
+		if (ReadKey(Child) > ReadKey(w)) {
 			Child = w;
+		}
 	}
 
 	/* Contrairement au Cormen, nous n'avons pas besoin de reconstruire ici
@@ -299,8 +303,8 @@ void FHeap::Cut(FHeap * x, FHeap * y)
 
 	y->Degree--;
 
-	x->Right->Left = Left;
-	x->Left->Right = Right;
+	x->Right->Left = x->Left;
+	x->Left->Right = x->Right;
 
 	if (y->Child == x) {
 		y->Child = y->Degree ? x->Right : NULL;
diff --git a/lib/HTree.cc b/lib/HTree.cc
index 3910ce3..985d687 100644
--- a/lib/HTree.cc
+++ b/lib/HTree.cc
@@ -1,12 +1,32 @@
 #include <stdio.h>
 #include <iostream.h>
+#include <stdlib.h>
+#include <string.h>
 #include "config.h"
 #include "HTree.h"
 
+ostream & PrintString(ostream & os, char *str)
+{
+	char t[2];
+
+	t[1] = '\0';
+	while (*str) {
+		if (*str >= 33) {
+			t[0] = *str;
+			os << t;
+		} else {
+			os << "\\" << ((unsigned int) (((unsigned char) *str)));
+		}
+		str++;
+	}
+
+	return os;
+}
+
 HTree::HTree(int n_freq, char *n_objet)
 {
 	freq = n_freq;
-	objet = n_objet;
+	objet = strdup(n_objet);
 	left = right = NULL;
 }
 
@@ -25,6 +45,9 @@ HTree::~HTree()
 
 	if (right)
 		delete right;
+
+	if (objet)
+		free(objet);
 }
 
 ostream & HTree::Trace(ostream & os, int d)
@@ -39,7 +62,8 @@ ostream & HTree::Trace(ostream & os, int d)
 
 	if (objet) {
 		cmpr[d] = '\0';
-		os << objet << " (" << freq << ") = " << cmpr << endl;
+		PrintString(os, objet);
+		os << " (" << freq << ") = " << cmpr << endl;
 		tsize += freq * strlen(cmpr);
 		rsize += freq * strlen(objet);
 		dsize += ((strlen(cmpr) >> 3) + (strlen(cmpr) & 7 ? 1 : 0)) + strlen(objet) + 2;
diff --git a/lib/PLList.cc b/lib/PLList.cc
index 48d294c..77bf2e7 100644
--- a/lib/PLList.cc
+++ b/lib/PLList.cc
@@ -99,7 +99,6 @@ PLList::PLList(void)
 
 PLList::~PLList(void)
 {
-	delete Head.Right;
 }
 
 Key_t PLList::ReadKey(Cell C)
diff --git a/lib/numbers.c b/lib/numbers.c
index 8334dd4..eb56f2c 100644
--- a/lib/numbers.c
+++ b/lib/numbers.c
@@ -3,9 +3,9 @@
 int char_to_number(char *st, int *valid)
 {
 	int whattype = 0, result = 0;
-	
+
 	*valid = 0;
-	
+
 	if (*st == '0') {
 		st++;
 		if (*st == 'x') {
@@ -18,7 +18,7 @@ int char_to_number(char *st, int *valid)
 			return 0;
 		}
 	}
-	
+
 	while (*st) {
 		switch (whattype) {
 		case 0:
@@ -52,7 +52,7 @@ int char_to_number(char *st, int *valid)
 		}
 		st++;
 	}
-	
+
 	*valid = 1;
 	return result;
 }