diff options
| -rw-r--r-- | include/BHeap.h | 20 | ||||
| -rw-r--r-- | include/BinHeap.h | 36 | ||||
| -rw-r--r-- | include/FHeap.h | 13 | ||||
| -rw-r--r-- | include/HTree.h | 18 | ||||
| -rw-r--r-- | include/Hash.h | 9 | ||||
| -rw-r--r-- | include/Makefile.am | 2 | ||||
| -rw-r--r-- | include/PTypes.h | 8 | ||||
| -rw-r--r-- | include/SList.h | 3 | ||||
| -rw-r--r-- | lib/BHeap.cc | 159 | ||||
| -rw-r--r-- | lib/BinHeap.cc | 180 | ||||
| -rw-r--r-- | lib/CList.cc | 14 | ||||
| -rw-r--r-- | lib/FHeap.cc | 10 | ||||
| -rw-r--r-- | lib/HTree.cc | 64 | ||||
| -rw-r--r-- | lib/Hash.cc | 3 | ||||
| -rw-r--r-- | lib/Makefile.am | 2 | ||||
| -rw-r--r-- | lib/PCommon.cc | 56 | ||||
| -rw-r--r-- | lib/PLList.cc | 44 | ||||
| -rw-r--r-- | lib/SList.cc | 14 | ||||
| -rw-r--r-- | po/POTFILES.in | 7 | ||||
| -rw-r--r-- | po/PriorityLists.pot | 72 | ||||
| -rw-r--r-- | po/cat-id-tbl.c | 37 | ||||
| -rw-r--r-- | src/test.cc | 30 |
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.")); |