From dc2ce18ea8e1686e61dce2b924e3607df69a2dcf Mon Sep 17 00:00:00 2001 From: Pixel <> Date: Sat, 3 Mar 2001 22:53:41 +0000 Subject: Plein de changements --- lib/BHeap.cc | 159 +++++++++++++++++++++++++++++++++++++++++++++++-- lib/BinHeap.cc | 180 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/CList.cc | 14 +++++ lib/FHeap.cc | 10 ++-- lib/HTree.cc | 64 +++++++++++--------- lib/Hash.cc | 3 - lib/Makefile.am | 2 +- lib/PCommon.cc | 56 ++++++++++++++---- lib/PLList.cc | 44 ++++++++++++-- lib/SList.cc | 14 +++++ 10 files changed, 484 insertions(+), 62 deletions(-) create mode 100644 lib/BinHeap.cc delete mode 100644 lib/Hash.cc (limited to 'lib') 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 +#include +#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 -#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 #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; -- cgit v1.2.3