Plop

11 files changed, 316 insertions, 3 deletions

diff --git a/doc/Dumb.doc.fr b/doc/Dumb.doc.fr
deleted file mode 100644
index e69de29..0000000
--- a/doc/Dumb.doc.fr
+++ /dev/null
diff --git a/doc/Makefile.am b/doc/Makefile.am
index 54d0db0..c894a53 100644
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -1 +1,10 @@
-EXTRA_DIST = Dumb.doc.fr
+ps:
+	make -f Makefile.doc ps
+
+clean:
+	make -f Makefile.doc clean
+
+distclean:
+	make -f Makefile.doc clean
+
+EXTRA_DIST = bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex polynom.tex
diff --git a/doc/Makefile.doc b/doc/Makefile.doc
new file mode 100644
index 0000000..f71be85
--- /dev/null
+++ b/doc/Makefile.doc
@@ -0,0 +1,30 @@
+PROJET=polynom
+
+all: $(PROJET).dvi
+
+$(PROJET).dvi: bib.tex conclusion.tex description.tex intro.tex manuel.tex outils.tex polynom.tex source.tex
+	echo 
+	echo pass1
+	echo
+	latex $(PROJET)
+	echo
+	echo pass2
+	echo
+	latex $(PROJET)
+
+source.tex:
+	echo '\section{Includes}' > source.tex
+	for i in `find ../include -name *.h` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex
+	echo '\section{Sources de la librairie}' >> source.tex
+	for i in `find ../lib -name *.c` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex
+	echo '\section{Sources du frontend}' >> source.tex
+	for i in `find ../src -name *.c` ; do echo "\subsection{`basename $$i`}"; echo "\lstinputlisting{$$i}"; done >> source.tex
+
+ps: $(PROJET).ps
+
+$(PROJET).ps: $(PROJET).dvi
+	dvips $(PROJET)
+
+clean:
+	rm -f  *.dvi *.aux *.toc *.ps *.log source.tex
+
diff --git a/doc/bib.tex b/doc/bib.tex
new file mode 100644
index 0000000..1203fbb
--- /dev/null
+++ b/doc/bib.tex
@@ -0,0 +1,7 @@
+\begin{thebibliography}{WWW99}
+% pour citer le Tanenbaum : \cite{Tanenbaum}
+% pour citer le Tanenbaum page 238 : \cite[page 238]{Tanenbaum} 
+
+\bibitem[COR]{Cormen} T. Cormen, C. Leiserson, R. Rivest \textit{Introduction à l'algorithmique}, Dunod.
+
+\end{thebibliography}
diff --git a/doc/conclusion.tex b/doc/conclusion.tex
new file mode 100644
index 0000000..e5d9edf
--- /dev/null
+++ b/doc/conclusion.tex
@@ -0,0 +1,9 @@
+\chapter*{Conclusion}
+\addcontentsline{toc}{chapter}{Conclusion}
+\markboth{CONCLUSION}{CONCLUSION}
+
+Ce projet a été mené à terme, et l'ensemble des conditions du sujet ont été respectées.
+L'effort de recherche mené sur la manière d'implémenter les algorithmes en C++ a
+sans aucun doute été profitable pour notre connaissance personnelle. De plus, les algorithmes
+implémentés sont "durables": ils peuvent nous resservir dans n'importe quel autre projet nécessitant
+des structures de files de priorités, ce qui porte un intérêt quant au développement de ce projet.
diff --git a/doc/description.tex b/doc/description.tex
new file mode 100644
index 0000000..e86c698
--- /dev/null
+++ b/doc/description.tex
@@ -0,0 +1,19 @@
+\chapter{Description}
+\paragraph{}
+Nous allons décrire dans cette première partie tous ce que nous avons effectué comme travail de réflexion afin de
+programme ce projet. Il y a beaucoup de détails relatifs à l'implémentation dont nous ne parlerons pas, comme les structures
+sur les listes chaînées, ou l'initialisation du terminal pour gérer le menu du programme de test. En revanche, nous appuyerons
+sur les détails d'implémentation purement algorithmiques qui nous ont posé problème.
+\paragraph{}
+En ce qui concerne le langage de programmation, nous avons choisi le C++, car c'est le langage qui nous semblait le plus
+adapté pour créer les structures de données nécessaire à la programmation de ce projet.
+\paragraph{}
+Nous avons implémenté les algorithmes de files de priorités suivants:
+\begin{itemize}
+\item Tas Binaire
+\item Tas Binomial
+\item Tas de Fibonacci
+\item Liste chaînée triée
+\end{itemize}
+\paragraph{}
+L'algorithme utilisant les files de priorité implémenté est l'algorithme de compression de dictionnaire Huffman.
diff --git a/doc/intro.tex b/doc/intro.tex
new file mode 100644
index 0000000..46d0e3c
--- /dev/null
+++ b/doc/intro.tex
@@ -0,0 +1,11 @@
+\chapter*{Introduction}
+\addcontentsline{toc}{chapter}{Introduction}
+\markboth{INTRODUCTION}{INTRODUCTION}
+
+\paragraph{}
+Ce projet a pour but d'une part l'implémentation d'algorithmes de files de priorités et l'implémentation d'un algorithme
+utilisant ces files de priorités d'autre part.
+
+\paragraph{}
+Ce présent document va tenter de décrire en totalité la progression de la
+mise en forme de ce projet. Nous vous souhaitons bonne lecture. 
diff --git a/doc/manuel.tex b/doc/manuel.tex
new file mode 100644
index 0000000..fcdc3af
--- /dev/null
+++ b/doc/manuel.tex
@@ -0,0 +1,124 @@
+\chapter{Manuel d'utilisation}
+\paragraph{}
+Ce projet génère deux binaire. Le premier appelé testTas n'est qu'une petite application nous permettant d'utiliser l'API
+C++ générée par notre classe de file de priorités. Voici un exemple d'exécution:
+\begin{verbatim}
+Priority list type: 0 - Binary Heap
+Choice: Please select an action
+a - Add a key into the priority list
+c - Change priority list type
+d - Delete a Key from the priority list
+e - Extract Min onto the priority list
+l - Lower Key onto a key of the priority list
+p - Print the current priority list on the screen
+r - Remove the whole priority list
+t - Test the priority list algorithms
+q - Quit
+\end{verbatim}
+
+A partir de cet instant, le programme nous propose un menu nous permettant d'effectuer plusieurs actions sur le tas. La
+fonction 'a' permet d'ajouter une clef dans le tas en cours. Comme il est impossible d'effectuer une recherche sur un tas
+pour y retrouver le pointeur d'un élément, le programme nous propose de sauvegarder le pointeur résultat dans un tableau:
+
+\begin{verbatim}
+Choice: Please select a slot to save the cell
+0 - Empty slot
+1 - Empty slot
+2 - Empty slot
+3 - Empty slot
+4 - Empty slot
+5 - Empty slot
+6 - Empty slot
+7 - Empty slot
+8 - Empty slot
+9 - Empty slot
+n - Don't store
+c - Cancel
+\end{verbatim}
+
+Ce tableau apparaitra régulièrement dans toutes les fonctions du menu afin de choisir une cellule sur laquelle agir. Toutes
+les fonctions du menu parlent d'elles mêmes. La fonction 't' va lancer une batterie de tests sur les algorithmes de la
+file de priorité sélectionnée.
+
+\paragraph{}
+Le deuxième binaire généré est 'Huffman'. Il sert à utiliser l'algorithme d'huffman implémenté. Voici sa ligne d'aide:
+\begin{verbatim}
+$ ./Huffman -h
+Huffman [{-f|-i} file] {type}
+Huffman -h
+This will encode the input file with the Huffman code
+using the priority list defined by type.
+Type is a number taken from this list:
+  0 : Binary Heap (default)
+  1 : Binomial Heap
+  2 : Fibonacci Heap
+  3 : Sorted chained list
+-f file means that you specify a dictionnary file which is
+        structured as described into the README file.
+-i file means that you specify a file to encode. It will
+        built a quiet dumb dictionnary.
+By default, a dictionnary will be built from stdin.
+-h prints this help and exit.
+\end{verbatim}
+
+La structure d'un dictionnaire est la suivante:
+\begin{verbatim}
+Mot1 : Fréquence1
+Mot2 : Fréquence2
+...
+\end{verbatim}
+
+Chaque mot est une chaîne de caractères servant à identifier la fréquence associée. Voici un exemple complet de dictionnaire
+et d'utilisation du programme avec ce dictionnaire:
+
+\begin{verbatim}
+Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ cat dict.sample
+MOT1 : 2000
+MOT2 : 1234
+MOT3 : 15987
+MOT4 : 1203
+MOT5 : 192837
+MOT6 : 12987
+Pixel@the-babel-tower:~/Projets_LI/Semestre1/Projet-Algo/src$ ./Huffman -f dict.sample   
+MOT3 (15987) = 00
+MOT1 (2000) = 0100
+MOT4 (1203) = 01010
+MOT2 (1234) = 01011
+MOT6 (12987) = 011
+MOT5 (192837) = 1
+Bitstream length           : 283957 bits (= 35495 bytes)
+Real size input            : 7239936 bits (= 904992 bytes)
+Size squeezed by           : 96.0779 percents
+Dictionnary size           : 336 bits (= 42 bytes)
+Total bitstream length     : 284293 bits (= 35537 bytes)
+Real gain (4 bytes header) : 96.0728 percents
+\end{verbatim}
+
+Il est indiqué que le programme est capable de générer un dictionnaire à partir d'un fichier. Il s'agit simplement de compter
+les caractères provenant de l'entrée et d'en générer un dictionnaire. Exemple:
+
+\begin{verbatim}
+$ cat dict.sample | Huffman 
+\32 (12) = 00
+6 (1) = 01000
+4 (2) = 01001
+3 (4) = 0101
+0 (4) = 0110
+5 (2) = 01110
+7 (3) = 01111
+1 (6) = 1000
+M (6) = 1001
+: (6) = 1010
+\10 (6) = 1011
+O (6) = 1100
+8 (3) = 11010
+9 (3) = 11011
+2 (6) = 1110
+T (6) = 1111
+Bitstream length           : 294 bits (= 37 bytes)
+Real size input            : 608 bits (= 76 bytes)
+Size squeezed by           : 51.6447 percents
+Dictionnary size           : 512 bits (= 64 bytes)
+Total bitstream length     : 806 bits (= 101 bytes)
+Real gain (4 bytes header) : -38.1579 percents
+\end{verbatim}
diff --git a/doc/outils.tex b/doc/outils.tex
new file mode 100644
index 0000000..69bbc53
--- /dev/null
+++ b/doc/outils.tex
@@ -0,0 +1,21 @@
+\chapter{Outils utilisés}
+\paragraph{}
+Pour développer ce projet, nous avons choisi d'utiliser une série d'outils GNU pour nous simplifier la tâche.
+Nous utilisons entre-autres, GNU autoconf \& automake pour gérer notre arborescence de développement. Ainsi le
+présent projet est découpé en ces répertoires:
+\begin{itemize}
+\item src contenant les sources des programmes exécutables. C'est notemment dans ce répertoire que seront stoqués
+les binaires des exécutables produit par la compilation du projet.
+\item lib contenant tous les sources purement algorithmiques, dont ne dépend pas l'implémentation finale.
+\item include contenant tous les fichiers .h
+\item doc contenant le source \LaTeX\ de cette présente documentation
+\item po contenant les fichiers d'internationalisation (traduction française)
+\item intl contenant le code source nécessaire au support de l'internationalisation.
+\end{itemize}
+En dehors de autoconf \& automake, nous avons utilisé un serveur CVS (Concurrent Version System) qui nous a permis
+de travailler à plusieurs sur ce projet, sans avoir à nous soucier de rapatrier et de fusionner les codes sources
+de tout le monde.
+\paragraph{}
+Enfin, pour pouvoir compiler ce projet, il suffit de taper la commande './configure' au shell et de suivre les instructions.
+Les binaires seront placés dans le répertoire src. Pour générer cette documentation, il suffit d'aller dans le répertoire doc
+et de taper 'make ps'.
diff --git a/doc/polynom.tex b/doc/polynom.tex
new file mode 100644
index 0000000..c4d4157
--- /dev/null
+++ b/doc/polynom.tex
@@ -0,0 +1,83 @@
+%initialisations----------------------------------------------------------------
+\documentclass[french,11pt,a4paper,twoside,openright]{report}
+\usepackage[T1]{fontenc}
+\usepackage[latin1]{inputenc}
+\usepackage[francais]{babel}
+\usepackage{a4}
+\usepackage{ulem}
+\usepackage{multirow}
+\usepackage[dvips]{graphics}
+\usepackage{vmargin}
+\usepackage{fancyhdr}
+\usepackage{oldstyle}
+\usepackage{listings}
+\usepackage{verbatim}
+%fin des initialisations--------------------------------------------------------
+
+\pagestyle{fancyplain}
+\addtolength{\headwidth}{\marginparsep}
+\addtolength{\headwidth}{\marginparwidth}
+% titre de chapitre
+\renewcommand{\chaptermark}[1]{\markboth{#1} {}}
+% titre de section
+\renewcommand{\sectionmark}[1]{\markright{\thesection\ #1}}
+
+\lhead[\fancyplain{}{\bfseries\textos{\thepage}}]{\fancyplain{}{\bfseries\rightmark}}
+\rhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\textos{\thepage}}}
+\cfoot{\fancyplain{\textos{\thepage}}{}}
+
+\newcommand{\clearemptydoublepage}{\newpage{\pagestyle{empty}\cleardoublepage}}
+
+\def\addcontentsline#1#2#3{%                                                    
+  \addtocontents{#1}{\protect\contentsline{#2}{#3}{\textos{\thepage}}}}
+% \setmargrb{leftmargin}{topmargin}{rightmargin}{bottommargin}
+\setmargrb{1.5cm}{2cm}{1.5cm}{4cm}
+
+\begin{document}
+\renewcommand{\chaptername}{Section}
+\newcommand{\bracebits}{$\underbrace{\hspace{2cm}}$}
+
+%page de garde
+\title{Projet de C\\
+	Rapport \vspace{1.0cm}}
+\author{Vagner Alain, Noble Nicolas\vspace{2.0cm}}
+\date{\textit{dernière révision: \today}}
+\maketitle
+\strut\thispagestyle{empty}
+\vfill
+\pagebreak
+\setcounter{page}{1}
+
+
+
+\tableofcontents
+
+\clearemptydoublepage
+
+\input{intro}
+\clearemptydoublepage
+\part{Analyse}
+\input{description}
+\clearemptydoublepage
+\part{Synthèse}
+\input{manuel}
+\clearemptydoublepage
+\input{outils}
+\clearemptydoublepage
+
+\chapter{Code source}
+\lstset{language=C++,basicstyle=\scriptsize,stringspaces=false}
+\input{source}
+
+\clearemptydoublepage
+\input{conclusion}
+\clearemptydoublepage
+\input{bib}
+\clearpage
+\strut\thispagestyle{plain}
+\begin{tiny}
+\begin{center}
+Cette documentation a été réalisée sous Linux Slackware 7.1 à l'aide de \LaTeX\ et cvs.
+\end{center}
+\end{tiny}
+\end{document}
diff --git a/lib/polynom.c b/lib/polynom.c
index 859ae48..8478531 100644
--- a/lib/polynom.c
+++ b/lib/polynom.c
@@ -290,10 +290,10 @@ char *ply_affichage(polynome poly)
 						sprintf(temp, "%s%s ", rat, mute);
 						break;
 					case 2:
-						sprintf(temp, "%s%s² ", rat, mute);
+						sprintf(temp, "%s%s%c ", rat, mute, 178);
 						break;
 					case 3:
-						sprintf(temp, "%s%s³ ", rat, mute);
+						sprintf(temp, "%s%s%c ", rat, mute, 179);
 						break;
 					default:
 						sprintf(temp, "%s%s^%u ", rat, mute, poly->degre);