From 3aff7aaa9de61a5f3430bd86960c4f9c4b958786 Mon Sep 17 00:00:00 2001 From: Pixel <> Date: Wed, 7 Mar 2001 00:41:50 +0000 Subject: Version finale pour les algos. --- doc/BHeap.doc.fr | 89 ------------------------------- doc/README.en | 0 doc/README.fr | 0 include/BinHeap.h | 6 ++- include/CList.h | 1 + include/FHeap.h | 3 +- include/PLList.h | 3 +- include/numbers.h | 5 +- lib/BHeap.cc | 4 +- lib/BinHeap.cc | 27 ++++++---- lib/FHeap.cc | 10 ++-- lib/HTree.cc | 28 +++++++++- lib/PLList.cc | 1 - lib/numbers.c | 8 +-- po/PriorityLists.pot | 148 ++++++++++++++++++++++++++++----------------------- po/cat-id-tbl.c | 80 +++++++++++++++------------- src/Makefile.am | 2 + src/dict.sample | 6 +++ src/main.cc | 117 +++++++++++++++++++++++----------------- src/test.cc | 16 +++--- 20 files changed, 277 insertions(+), 277 deletions(-) delete mode 100644 doc/BHeap.doc.fr create mode 100644 doc/README.en create mode 100644 doc/README.fr create mode 100644 src/dict.sample diff --git a/doc/BHeap.doc.fr b/doc/BHeap.doc.fr deleted file mode 100644 index 753ceee..0000000 --- a/doc/BHeap.doc.fr +++ /dev/null @@ -1,89 +0,0 @@ -BHeap: (tas binomial) ------ - - Implémentation: - ~~~~~~~~~~~~~~ -Ce code utilisant les classes, il ne peut marcher qu'en C++. -Le tas binomial est une classe dérivée de la classe 'PriorityList'. -Toutes les méthodes étant virtuelles, vous pouvez sans problème assigner -un BHeap à une PriorityList et appeler les méthodes classiques de la liste -de priorité. - - - Utilisation: - ~~~~~~~~~~~ -Pour creer un tas binomial vide, il suffit de faire: - -BHeap * Tas = new BHeap; - -Il n'y a aucune variable de la structure BHeap lisible directement. Tout -s'effectue par des appels aux méthodes de la classe. - -Les données satellites sont disposées dans la structure sous la forme d'un -pointeur du type void. Le type des données est définit par le typedef 'Datas_t'. -Le type des clefs est définit par le typedef 'Key_t'. Par défaut, ceux-ci sont: - -typedef Datas_t void * -typedef Key_t int - -Vous pouvez changer ces typedefs avant de faire un #include . Le type -changera alors automatiquement dans la compilation de la librairie. Attention: -cela ne marchera bien évidemment qu'en compilation statique (c'est à dire avec -le package PriorityList dans votre arbre de développement) et le type Key_t doit -être un type 'comparable' (afin de faire les tests sur les clefs). Il est néanmoins -vivement conseillé de conserver les types de bases. - -Il n'y a aucun moyen direct de 'renverser' l'ordre de la liste (c'est à dire -faire du plus grand au plus petit). Il vous suffit de faire des insertions sur -les valeurs négatives des clefs réelles à insérer. - -Voici les méthodes disponibles: - - BHeap::BHeap(void); - BHeap::~BHeap(void); - - Key_t PriorityList::ReadKey(void); - Datas_t PriorityList::ReadDatas(void); - - void BHeap::Dump(void); - - BHeap * BHeap::Min(void); - BHeap * BHeap::Insert(Key_t IKey, Datas_t IDatas); - Key_t BHeap::Extract_Min(Datas_t & Datas); - BHeap * BHeap::Union(PriorityList * H); - int BHeap::Lower_Key(Key_t NKey); - Key_t BHeap::Delete(Datas_t & Datas, PriorityList * x); - -Le constructeur est le constructeur 'tas vide'. Le -destructeur ne peut que servir a détruire un tas complet. - -Les deux méthodes PriorityList::ReadKey et PriorityList::ReadDatas servent a lire -les données de la structure. Elles sont directement dérivées de PriorityList. - -La méthode BHeap::Min recherche la clef minimum de la structure et en renvoie -le pointeur correspondant. Elle s'utilise sur le tas dans lequel on recherche. - -La méthode BHeap::Insert va inserer une nouvelle clef dans le tas sur lequel -on a appelé la méthode. - -La méthode BHeap:Extract_Min va rechercher et supprimer le minimum dans le tas -sur lequel elle a été appelée. Elle renvoie la clef minimum. Les -données satellite sont écrites dans la variable Datas passée en paramètre. - -La méthode BHeap::Union va vider complètement le tas passé en paramètre pour -effectuer l'opération Union avec le tas sur lequel la méthode a été appelée. - -La méthode BHeap::Lower_Key va diminuer la valeur de la clef de la cellule sur -laquelle la méthode a été appelée. - -Enfin la méthode BHeap::Delete va effacer la clef passée en paramètre depuis le -tas sur lequel la méthode a été appelée. Elle va renvoyer la valeur de la clef -supprimée et les données satellites sont écrites dans la variable Datas. - - - Précautions: - ~~~~~~~~~~~ -Il ne faut *jamais* supprimer une clef directement avec la fonction C++ -delete. Il faut toujours utiliser la méthode BHeap::Delete(). Par contre -pour effacer l'intégralité d'un tas, il suffit de faire delete Tas, et -l'ensemble des clefs seront effacées très rapidement. diff --git a/doc/README.en b/doc/README.en new file mode 100644 index 0000000..e69de29 diff --git a/doc/README.fr b/doc/README.fr new file mode 100644 index 0000000..e69de29 diff --git a/include/BinHeap.h b/include/BinHeap.h index c67239c..879267a 100644 --- a/include/BinHeap.h +++ b/include/BinHeap.h @@ -1,18 +1,20 @@ #ifndef __BINHEAP_H__ #define __BINHEAP_H__ #include +#include #define GRANUL 8 struct binheap_t { Key_t Key; Datas_t Datas; + Cell FP; }; #ifdef __cplusplus -typedef class BinHeap:public PriorityList { - private: +typedef class BinHeap:public PriorityList { private: void PackUp(int i); + CList *FP; public: BinHeap(void); // Constructor virtual ~ BinHeap(void); // Destructor diff --git a/include/CList.h b/include/CList.h index 71f2f37..c18fa9a 100644 --- a/include/CList.h +++ b/include/CList.h @@ -15,6 +15,7 @@ class CList { friend class PLList; friend class SList; friend class BHeap; + friend class BinHeap; public: CList(void); diff --git a/include/FHeap.h b/include/FHeap.h index 292540c..4b8b8fa 100644 --- a/include/FHeap.h +++ b/include/FHeap.h @@ -4,7 +4,8 @@ #define DFMAX 128 #ifdef __cplusplus -typedef class FHeap:public PriorityList { private: +typedef class FHeap:public PriorityList { + private: FHeap * Father, *Child, *Left, *Right; int Degree; bool Mark; diff --git a/include/PLList.h b/include/PLList.h index f729ffe..1b00f33 100644 --- a/include/PLList.h +++ b/include/PLList.h @@ -5,8 +5,7 @@ #include #ifdef __cplusplus -class PLList:public PriorityList { - private: +class PLList:public PriorityList { private: SList Head; public: diff --git a/include/numbers.h b/include/numbers.h index 6eba30d..692a5bb 100644 --- a/include/numbers.h +++ b/include/numbers.h @@ -4,9 +4,8 @@ #ifdef __cplusplus extern "C" { #endif -int char_to_number(char * st, int * valid); + int char_to_number(char *st, int *valid); #ifdef __cplusplus } #endif - -#endif \ No newline at end of file +#endif 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 #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 #include +#include +#include #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; } diff --git a/po/PriorityLists.pot b/po/PriorityLists.pot index 14a3e97..4f5f857 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-03-05 15:46+0100\n" +"POT-Creation-Date: 2001-03-07 01:38+0100\n" "PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n" "Last-Translator: FULL NAME \n" "Language-Team: LANGUAGE \n" @@ -22,234 +22,250 @@ msgstr "" msgid " random entrie(s)..." msgstr "" -#: src/test.cc:38 +#: src/test.cc:40 msgid "" "Ok.\n" "Deleting the list..." msgstr "" -#: src/test.cc:42 src/test.cc:46 +#: src/test.cc:44 src/test.cc:48 msgid "List has " msgstr "" -#: src/test.cc:42 +#: src/test.cc:44 msgid " keys. Expecting " msgstr "" -#: src/test.cc:43 src/test.cc:47 +#: src/test.cc:45 src/test.cc:49 msgid "List corrupted." msgstr "" -#: src/test.cc:46 +#: src/test.cc:48 msgid " keys (real count). Expecting " msgstr "" -#: src/test.cc:51 src/test.cc:126 +#: src/test.cc:53 src/test.cc:128 msgid "Incorrect order." msgstr "" -#: src/test.cc:66 +#: src/test.cc:68 msgid "Size of a PriorityList cell: " msgstr "" -#: src/test.cc:67 +#: src/test.cc:69 msgid "Size of a BHeap cell : " msgstr "" -#: src/test.cc:68 +#: src/test.cc:70 msgid "Size of a FHeap cell : " msgstr "" -#: src/test.cc:69 +#: src/test.cc:71 msgid "Size of a PLList header : " msgstr "" -#: src/test.cc:70 +#: src/test.cc:72 msgid "Size of a CList cell : " msgstr "" -#: src/test.cc:71 +#: src/test.cc:73 msgid "Size of a SList cell : " msgstr "" -#: src/test.cc:72 +#: src/test.cc:74 msgid "Size of a BinHeap header : " msgstr "" -#: src/test.cc:73 +#: src/test.cc:75 msgid "Size of a BinHeap cell : " msgstr "" -#: src/test.cc:87 +#: src/test.cc:89 msgid "Creating a priority list and adding keys:\n" msgstr "" -#: src/test.cc:102 src/test.cc:109 src/test.cc:113 src/test.cc:117 +#: src/test.cc:104 src/test.cc:111 src/test.cc:115 src/test.cc:119 msgid "" "Ok.\n" "List browsing...\n" msgstr "" -#: src/test.cc:104 +#: src/test.cc:106 msgid "" "Ok.\n" "Extract_Min + List browsing...\n" msgstr "" -#: src/test.cc:107 +#: src/test.cc:109 msgid "" "Ok.\n" "Lower_Key(0) over 59...\n" msgstr "" -#: src/test.cc:111 +#: src/test.cc:113 msgid "" "Ok.\n" "Delete over 54...\n" msgstr "" -#: src/test.cc:115 +#: src/test.cc:117 msgid "" "Ok.\n" "Lower_Key(-12) over 30...\n" msgstr "" -#: src/test.cc:119 +#: src/test.cc:121 msgid "" "Ok.\n" "Extract_Min...\n" msgstr "" -#: src/test.cc:121 +#: src/test.cc:123 msgid "" "Ok.\n" "Extracting datas...\n" msgstr "" -#: src/test.cc:123 +#: src/test.cc:125 msgid "Minimum #" msgstr "" -#: src/test.cc:129 +#: src/test.cc:131 msgid "" "Ok.\n" "\n" "All the tests were successfull\n" msgstr "" -#: src/main.cc:34 src/main.cc:166 +#: src/main.cc:35 src/main.cc:174 msgid "Unknow priority list type: " msgstr "" -#: src/main.cc:45 src/main.cc:71 +#: src/main.cc:46 src/main.cc:72 msgid "Error opening file (" msgstr "" -#: src/main.cc:77 +#: src/main.cc:78 msgid "Bad dictionnary structure. See doc/README.en (missing : separator)" msgstr "" -#: src/main.cc:90 +#: src/main.cc:91 msgid "Bad dictionnary structure. See doc/README.en (missing word)" msgstr "" -#: src/main.cc:101 +#: src/main.cc:102 msgid "Bad dictionnary structure. See doc/README.en (missing frequency)" msgstr "" -#: src/main.cc:109 +#: src/main.cc:107 +msgid "Error: \"" +msgstr "" + +#: src/main.cc:107 +msgid "\" is not a valid number." +msgstr "" + +#: src/main.cc:116 msgid "Huffman [{-f|-i} file] {type}" msgstr "" -#: src/main.cc:110 +#: src/main.cc:117 msgid "Huffman -h" msgstr "" -#: src/main.cc:111 +#: src/main.cc:118 msgid "By Nicolas Noble (nicolas@nobis-crew.org)." msgstr "" -#: src/main.cc:112 +#: src/main.cc:119 msgid "This will encode the input file with the Huffman code" msgstr "" -#: src/main.cc:113 +#: src/main.cc:120 msgid "using the priority list defined by type." msgstr "" -#: src/main.cc:114 +#: src/main.cc:121 msgid "Type is a number taken from this list:" msgstr "" -#: src/main.cc:115 +#: src/main.cc:122 msgid " 0 : Binary Heap (default)" msgstr "" -#: src/main.cc:116 +#: src/main.cc:123 msgid " 1 : Binomial Heap" msgstr "" -#: src/main.cc:117 +#: src/main.cc:124 msgid " 2 : Fibbonacci Heap (bugged)" msgstr "" -#: src/main.cc:118 +#: src/main.cc:125 msgid " 3 : Sorted chained list" msgstr "" -#: src/main.cc:119 +#: src/main.cc:126 msgid "-f file means that you specify a dictionnary file which is" msgstr "" -#: src/main.cc:120 +#: src/main.cc:127 msgid " structured as described into the README file." msgstr "" -#: src/main.cc:121 +#: src/main.cc:128 msgid "-i file means that you specify a file to encode. It will" msgstr "" -#: src/main.cc:122 +#: src/main.cc:129 msgid " built a quiet dumb dictionnary." msgstr "" -#: src/main.cc:123 +#: src/main.cc:130 msgid "By default, a dictionnary will be built from stdin." msgstr "" -#: src/main.cc:124 +#: src/main.cc:131 msgid "-h prints this help and exit." msgstr "" -#: src/main.cc:140 +#: src/main.cc:146 msgid "Unknow option: " msgstr "" -#: src/main.cc:149 src/main.cc:157 +#: src/main.cc:155 src/main.cc:164 msgid "-i and -f options are exclusive" msgstr "" -#: src/main.cc:170 +#: src/main.cc:178 msgid "Extra command: " msgstr "" -#: src/main.cc:189 +#: src/main.cc:193 +msgid "-i needs a filename" +msgstr "" + +#: src/main.cc:198 +msgid "-f needs a filename" +msgstr "" + +#: src/main.cc:202 msgid "Internal error." msgstr "" -#: lib/FHeap.cc:80 +#: lib/FHeap.cc:84 msgid " * Head cell. (" msgstr "" -#: lib/BHeap.cc:224 lib/FHeap.cc:160 +#: lib/BHeap.cc:224 lib/FHeap.cc:164 msgid "Insert: not over Head." msgstr "" -#: lib/BHeap.cc:226 lib/BHeap.cc:246 lib/FHeap.cc:182 +#: lib/BHeap.cc:226 lib/BHeap.cc:246 lib/FHeap.cc:186 msgid "Insert: No more memory." msgstr "" -#: lib/BHeap.cc:268 lib/FHeap.cc:192 lib/PLList.cc:150 +#: lib/BHeap.cc:268 lib/FHeap.cc:196 lib/PLList.cc:149 msgid "Extract_Min: Priority List is empty." msgstr "" @@ -259,52 +275,52 @@ msgid "" " |\n" msgstr "" -#: lib/BinHeap.cc:122 +#: lib/BinHeap.cc:129 msgid "Not enough memory" msgstr "" -#: lib/BinHeap.cc:149 +#: lib/BinHeap.cc:157 msgid "negative overflow" msgstr "" -#: lib/PLList.cc:126 +#: lib/PLList.cc:125 msgid "" " * Head cell\n" " |\n" msgstr "" -#: lib/HTree.cc:58 +#: lib/HTree.cc:79 msgid "Bitstream length : " msgstr "" -#: lib/HTree.cc:58 lib/HTree.cc:61 lib/HTree.cc:63 lib/HTree.cc:64 +#: lib/HTree.cc:79 lib/HTree.cc:82 lib/HTree.cc:84 lib/HTree.cc:85 msgid " bits (= " msgstr "" -#: lib/HTree.cc:60 lib/HTree.cc:61 lib/HTree.cc:63 lib/HTree.cc:68 +#: lib/HTree.cc:81 lib/HTree.cc:82 lib/HTree.cc:84 lib/HTree.cc:89 msgid " bytes)\n" msgstr "" -#: lib/HTree.cc:61 +#: lib/HTree.cc:82 msgid "Real size input : " msgstr "" -#: lib/HTree.cc:62 +#: lib/HTree.cc:83 msgid "Size squeezed by : " msgstr "" -#: lib/HTree.cc:62 lib/HTree.cc:70 +#: lib/HTree.cc:83 lib/HTree.cc:91 msgid " percents\n" msgstr "" -#: lib/HTree.cc:63 +#: lib/HTree.cc:84 msgid "Dictionnary size : " msgstr "" -#: lib/HTree.cc:64 +#: lib/HTree.cc:85 msgid "Total bitstream length : " msgstr "" -#: lib/HTree.cc:69 +#: lib/HTree.cc:90 msgid "Real gain (4 bytes header) : " msgstr "" diff --git a/po/cat-id-tbl.c b/po/cat-id-tbl.c index 7c2abcb..98d3bf4 100644 --- a/po/cat-id-tbl.c +++ b/po/cat-id-tbl.c @@ -58,47 +58,51 @@ All the tests were successfull\n", 27}, {"Bad dictionnary structure. See doc/README.en (missing : separator)", 30}, {"Bad dictionnary structure. See doc/README.en (missing word)", 31}, {"Bad dictionnary structure. See doc/README.en (missing frequency)", 32}, - {"Huffman [{-f|-i} file] {type}", 33}, - {"Huffman -h", 34}, - {"By Nicolas Noble (nicolas@nobis-crew.org).", 35}, - {"This will encode the input file with the Huffman code", 36}, - {"using the priority list defined by type.", 37}, - {"Type is a number taken from this list:", 38}, - {" 0 : Binary Heap (default)", 39}, - {" 1 : Binomial Heap", 40}, - {" 2 : Fibbonacci Heap (bugged)", 41}, - {" 3 : Sorted chained list", 42}, - {"-f file means that you specify a dictionnary file which is", 43}, - {" structured as described into the README file.", 44}, - {"-i file means that you specify a file to encode. It will", 45}, - {" built a quiet dumb dictionnary.", 46}, - {"By default, a dictionnary will be built from stdin.", 47}, - {"-h prints this help and exit.", 48}, - {"Unknow option: ", 49}, - {"-i and -f options are exclusive", 50}, - {"Extra command: ", 51}, - {"Internal error.", 52}, - {" * Head cell. (", 53}, - {"Insert: not over Head.", 54}, - {"Insert: No more memory.", 55}, - {"Extract_Min: Priority List is empty.", 56}, + {"Error: \"", 33}, + {"\" is not a valid number.", 34}, + {"Huffman [{-f|-i} file] {type}", 35}, + {"Huffman -h", 36}, + {"By Nicolas Noble (nicolas@nobis-crew.org).", 37}, + {"This will encode the input file with the Huffman code", 38}, + {"using the priority list defined by type.", 39}, + {"Type is a number taken from this list:", 40}, + {" 0 : Binary Heap (default)", 41}, + {" 1 : Binomial Heap", 42}, + {" 2 : Fibbonacci Heap (bugged)", 43}, + {" 3 : Sorted chained list", 44}, + {"-f file means that you specify a dictionnary file which is", 45}, + {" structured as described into the README file.", 46}, + {"-i file means that you specify a file to encode. It will", 47}, + {" built a quiet dumb dictionnary.", 48}, + {"By default, a dictionnary will be built from stdin.", 49}, + {"-h prints this help and exit.", 50}, + {"Unknow option: ", 51}, + {"-i and -f options are exclusive", 52}, + {"Extra command: ", 53}, + {"-i needs a filename", 54}, + {"-f needs a filename", 55}, + {"Internal error.", 56}, + {" * Head cell. (", 57}, + {"Insert: not over Head.", 58}, + {"Insert: No more memory.", 59}, + {"Extract_Min: Priority List is empty.", 60}, {"\ * Head cell.\n\ - |\n", 57}, - {"Not enough memory", 58}, - {"negative overflow", 59}, + |\n", 61}, + {"Not enough memory", 62}, + {"negative overflow", 63}, {"\ * Head cell\n\ - |\n", 60}, - {"Bitstream length : ", 61}, - {" bits (= ", 62}, - {" bytes)\n", 63}, - {"Real size input : ", 64}, - {"Size squeezed by : ", 65}, - {" percents\n", 66}, - {"Dictionnary size : ", 67}, - {"Total bitstream length : ", 68}, - {"Real gain (4 bytes header) : ", 69}, + |\n", 64}, + {"Bitstream length : ", 65}, + {" bits (= ", 66}, + {" bytes)\n", 67}, + {"Real size input : ", 68}, + {"Size squeezed by : ", 69}, + {" percents\n", 70}, + {"Dictionnary size : ", 71}, + {"Total bitstream length : ", 72}, + {"Real gain (4 bytes header) : ", 73}, }; -int _msg_tbl_length = 69; +int _msg_tbl_length = 73; diff --git a/src/Makefile.am b/src/Makefile.am index c8a43f6..fb784dd 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -13,3 +13,5 @@ LDADD = ../lib/libPriorityLists.la testTas_LDADD = $(LDADD) Huffman_LDADD = $(LDADD) ../lib/libHuffman.la + +EXTRA_DIST = dict.sample \ No newline at end of file diff --git a/src/dict.sample b/src/dict.sample new file mode 100644 index 0000000..6a46bb0 --- /dev/null +++ b/src/dict.sample @@ -0,0 +1,6 @@ +MOT1 : 2000 +MOT2 : 1234 +MOT3 : 15987 +MOT4 : 1203 +MOT5 : 192837 +MOT6 : 12987 diff --git a/src/main.cc b/src/main.cc index 9cc96d5..16e9985 100644 --- a/src/main.cc +++ b/src/main.cc @@ -8,6 +8,7 @@ #include "BinHeap.h" #include "PLList.h" #include "Huffman.h" +#include "numbers.h" void exception(int e, char *msg) { @@ -18,8 +19,8 @@ void exception(int e, char *msg) PriorityList *newlist(int method) { switch (method) { - case 0: - return new BinHeap; + case 0: + return new BinHeap; break; case 1: return new BHeap; @@ -33,13 +34,13 @@ PriorityList *newlist(int method) default: cerr << _("Unknow priority list type: ") << method << endl; exit(-1); - } + } } void Count(FILE * strm, PriorityList * P) { - int tab[256], i, valid; - char *t; + int tab[256], i; + char t[2]; if (!strm) { cerr << _("Error opening file (") << strerror(errno) << ")\n"; @@ -56,7 +57,6 @@ void Count(FILE * strm, PriorityList * P) for (i = 0; i < 256; i++) { if (tab[i]) { - t = (char *) malloc(2); t[0] = i; t[1] = 0; HInsert(P, tab[i], t); @@ -64,18 +64,20 @@ void Count(FILE * strm, PriorityList * P) } } -void ReadDic(FILE * strm, PriorityList * P) { +void ReadDic(FILE * strm, PriorityList * P) +{ char t[1024], *f, *word, *p; + int valid, freq; if (!strm) { cerr << _("Error opening file (") << strerror(errno) << ")\n"; exit(-1); } - - while(gets(t)) { + + while (fgets(t, 1024, strm)) { if (!(f = strchr(t, ':'))) { cerr << _("Bad dictionnary structure. See doc/README.en (missing : separator)") << endl; - exit (-1); + exit(-1); } *(f++) = '\0'; word = t; @@ -88,19 +90,25 @@ void ReadDic(FILE * strm, PriorityList * P) { } if (!strlen(word)) { cerr << _("Bad dictionnary structure. See doc/README.en (missing word)") << endl; - exit (-1); + exit(-1); } while (*f == ' ') { f++; } p = f + strlen(f) - 1; - while (*p == ' ') { + while ((*p == ' ') || (*p == '\n')) { *(p--) = '\0'; } if (!strlen(f)) { cerr << _("Bad dictionnary structure. See doc/README.en (missing frequency)") << endl; - exit (-1); + exit(-1); + } + freq = char_to_number(f, &valid); + if (!valid) { + cerr << _("Error: \"") << f << _("\" is not a valid number.") << endl; + exit(-1); } + HInsert(P, freq, word); } } @@ -129,68 +137,77 @@ int main(int argc, char **argv) { PriorityList *P; HTree *H; - FILE * f; int method = -1, readm = -1; char *filename = NULL; while (--argc) { argv++; - if (*argv[0] == '-') { + if ((*argv)[0] == '-') { if (strlen(*argv) != 2) { cerr << _("Unknow option: ") << *argv << endl; Usage(); } - switch (*argv[1]) { - case 'h': + switch ((*argv)[1]) { + case 'h': + Usage(); + break; + case 'i': + if (readm != -1) { + cerr << _("-i and -f options are exclusive") << endl; + Usage(); + } + readm = 1; + filename = *(++argv); + argc--; + break; + case 'f': + if (readm != -1) { + cerr << _("-i and -f options are exclusive") << endl; Usage(); - break; - case 'i': - if (readm != -1) { - cerr << _("-i and -f options are exclusive") << endl; - Usage(); - } - readm = 1; - filename = *(++argv); - break; - case 'f': - if (readm != -1) { - cerr << _("-i and -f options are exclusive") << endl; - Usage(); - } - readm = 2; - filename = *(++argv); - break; + } + readm = 2; + filename = *(++argv); + argc--; + break; } } else { - if ((strlen(*argv) != 1) || ((*argv[0] < '0' || *argv[0] > '3'))) { + if ((strlen(*argv) != 1) || (((*argv)[0] < '0' || (*argv)[0] > '3'))) { cerr << _("Unknow priority list type: ") << *argv << endl; Usage(); } if (method != -1) { cerr << _("Extra command: ") << *argv << endl; } - method = *argv[0] - '0'; + method = (*argv)[0] - '0'; } } - + + if (method == -1) + method = 0; P = newlist(method); - + switch (readm) { - case -1: - Count(stdin, P); - break; - case 1: - Count(fopen(filename, "r"), P); - break; - case 2: - ReadDic(fopen(filename, "r"), P); - break; - default: - cerr << _("Internal error.") << endl; - exit(-1); + case -1: + Count(stdin, P); + break; + case 1: + if (!filename) + cerr << _("-i needs a filename") << endl; + Count(fopen(filename, "r"), P); + break; + case 2: + if (!filename) + cerr << _("-f needs a filename") << endl; + ReadDic(fopen(filename, "r"), P); + break; + default: + cerr << _("Internal error.") << endl; + exit(-1); } H = Coder(P); + delete P; + H->Trace(cout); return 0; } diff --git a/src/test.cc b/src/test.cc index fec7131..c5be9b8 100644 --- a/src/test.cc +++ b/src/test.cc @@ -20,7 +20,7 @@ void exception(int e, char *msg) PriorityList *newlist(void) { - return new BHeap; + return new FHeap; } void DoCombTest(int number) @@ -33,7 +33,9 @@ void DoCombTest(int number) cerr << _("Creation of a priority list and adding ") << number << _(" random entrie(s)..."); T = newlist(); for (i = 1; i <= number; i++) { - T->Insert(rand() % P_INFINITY, NULL); +// T->Insert(rand() % P_INFINITY, NULL); +// T->Insert(rand() % 100, NULL); + T->Insert(1, NULL); } cerr << _("Ok.\nDeleting the list..."); oK = P_INFINITY; @@ -73,7 +75,7 @@ void FullTest(void) cerr << _("Size of a BinHeap cell : ") << sizeof(binheap_t) << endl; DoCombTest(0); - DoCombTest(10); + DoCombTest(30); DoCombTest(70); DoCombTest(1000); // DoCombTest(10000); @@ -89,10 +91,12 @@ void FullTest(void) for (i = 0; i < 30; i++) { fprintf(stderr, "%i ", N[i]); C1 = T->Insert(N[i], NULL); - if (N[i] == 30) C3 = C1; + if (N[i] == 30) + C3 = C1; } - - if (!C3) exit(-1); + + if (!C3) + exit(-1); fprintf(stderr, "59 54 -10\n"); C1 = T->Insert(59, NULL); -- cgit v1.2.3