summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/BHeap.cc159
-rw-r--r--lib/BinHeap.cc180
-rw-r--r--lib/CList.cc14
-rw-r--r--lib/FHeap.cc10
-rw-r--r--lib/HTree.cc64
-rw-r--r--lib/Hash.cc3
-rw-r--r--lib/Makefile.am2
-rw-r--r--lib/PCommon.cc56
-rw-r--r--lib/PLList.cc44
-rw-r--r--lib/SList.cc14
10 files changed, 484 insertions, 62 deletions
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;
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 14:14:34 +0000