summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/BHeap.cc4
-rw-r--r--lib/BinHeap.cc27
-rw-r--r--lib/FHeap.cc10
-rw-r--r--lib/HTree.cc28
-rw-r--r--lib/PLList.cc1
-rw-r--r--lib/numbers.c8
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;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 14:10:17 +0000