Premier jetstart

9 files changed, 915 insertions, 0 deletions

diff --git a/lib/BHeap.cc b/lib/BHeap.cc
new file mode 100644
index 0000000..4d7cc9e
--- /dev/null
+++ b/lib/BHeap.cc
@@ -0,0 +1,278 @@
+#include <stdio.h>
+#include "config.h"
+#include "BHeap.h"
+#include "CList.h"
+
+static int d, Depths[65536];
+
+void BHeap::Dump(ostream & os)
+{
+	int i;
+
+	if (Degree == -1) {
+		os << _(" * Head cell.\n |\n");
+		for (i = 0; i < 65535; i++)
+			Depths[i] = 1;
+		d = 1;
+	} else {
+		for (i = 1; i <= d; i++)
+			os << (Depths[i] ? " |" : "  ");
+		os << (Child ? "_  " : "__ ") << Key << endl;
+	}
+	if (Child) {
+		Depths[d] = (Brother != NULL);
+		d++;
+		Child->Dump(os);
+		d--;
+	}
+	if (Brother) {
+		Brother->Dump(os);
+	}
+}
+
+int BHeap::rn(void)
+{
+	int n = 0;
+
+	if (Degree != -1) {
+		n++;
+	}
+	if (Child) {
+		n += Child->rn();
+	}
+	if (Brother) {
+		n += Brother->rn();
+	}
+	return n;
+}
+
+void BHeap::Link(BHeap * z)
+{
+	Father = z;
+	Brother = z->Child;
+	z->Child = this;
+	z->Degree = z->Degree + 1;
+}
+
+void BHeap::Merge(BHeap * H)
+{
+	BHeap *P1, *P2, *T1, *T2;
+
+	Key += H->Key;
+	H->Key = 0;
+
+	for (P1 = this, P2 = H->Brother; P1->Brother && P2;) {
+		if (P1->Brother->Degree < P2->Degree) {	// P1 < P2, jump over P1.
+			P1 = P1->Brother;
+		} else {	// P1 >= P2. We will insert P2 after P1.
+			T1 = P1->Brother;
+			T2 = P2->Brother;
+			P1->Brother = P2;
+			P2->Brother = T1;
+			P1 = P2;
+			P2 = T2;
+		}
+	}
+	if (!(P1->Brother))
+		P1->Brother = P2;
+	H->Brother = NULL;
+}
+
+BHeap::BHeap(void):Degree(-1), Father(NULL), Child(NULL), Brother(NULL),
+FP(new CList)
+{
+  type = T_BHEAP;
+}
+
+BHeap::BHeap(Key_t IKey, Datas_t const &IDatas):PriorityList(IKey, IDatas),
+Degree(0), Father(NULL), Child(NULL), Brother(NULL)
+{
+  type = T_BHEAP;
+#ifdef DEBUG
+	nc++;
+#endif
+}
+
+BHeap::~BHeap(void)
+{
+	if (Degree == -1)
+		delete FP;
+
+	if (Child) {
+		delete Child;
+	}
+	if (Brother) {
+		delete Brother;
+	}
+#ifdef DEBUG
+	nd++;
+#endif
+}
+
+Cell BHeap::Min(void)
+{
+	BHeap *x = this, *y = NULL;
+	int min = P_INFINITY;
+
+	for (; x; x = x->Brother) {
+		if ((x->Key < min)) {
+			min = x->Key;
+			y = x;
+		}
+	}
+
+	return y->FP;
+}
+
+Cell BHeap::Insert(BHeap * E)
+{
+	BHeap *H;
+
+	if (Degree != -1)
+		exception(2, _("Insert: not over Head."));
+	if (!(H = new BHeap))
+		exception(5, _("Insert: No more memory."));
+	H->Brother = E;
+	Union(H);
+	delete H;
+
+	return ((E->FP = ((CList *) (FP->Insert(Key, E)))));
+}
+
+Cell BHeap::Insert(Key_t IKey, Datas_t const &IDatas)
+{
+	BHeap *P;
+
+	Key++;
+
+	if (!(P = new BHeap(IKey, IDatas)))
+		exception(5, _("Insert: No more memory."));
+	return (Insert(P));
+}
+
+Key_t BHeap::Extract_Min(Datas_t & Datas)
+{
+	BHeap *x, *y = NULL, *P, *P2, *P3, *Before;
+	Key_t k;
+	int min = P_INFINITY;
+
+	P = Before = this;
+
+	if (!Brother)
+		exception(4, _("Extract_Min: Priority List is empty."));
+
+	Key--;
+
+	for (x = Brother; x; x = x->Brother) {
+		if ((x->Key < min)) {
+			min = x->Key;
+			y = x;
+			Before = P;
+		}
+		P = x;
+	}
+
+	Before->Brother = y->Brother;
+
+	Before = new BHeap;
+
+	for (P = y->Child; P;) {
+		P2 = Before->Brother;
+		P3 = P->Brother;
+		Before->Brother = P;
+		P->Brother = P2;
+		P = P3;
+	}
+
+	Before->Key = 0;
+	Union(Before);
+
+	k = y->Key;
+	y->Brother = y->Child = NULL;
+	FP->Delete(Datas, ((Cell) y->FP));
+	Datas = y->Datas;
+	delete y;
+
+	return k;
+}
+
+PriorityList *BHeap::Union(PriorityList * P)
+{
+	BHeap *x, *Before, *After;
+
+	if ((P->GetType()) != (((PriorityList *) this)->GetType()))
+		return GenericUnion(P);
+
+	Merge((BHeap *) P);
+	if (!(Brother)) {
+		return this;
+	}
+	Before = this;
+	x = Brother;
+	After = x->Brother;
+	while (After) {
+		if ((x->Degree != After->Degree)
+		    || ((After->Brother)
+			&& (After->Brother->Degree == x->Degree))) {
+			Before = x;
+			x = After;
+		} else {
+			if (x->Key <= After->Key) {
+				x->Brother = After->Brother;
+				After->Link(x);
+			} else {
+				Before->Brother = After;
+				x->Link(After);
+				x = After;
+			}
+		}
+		After = x->Brother;
+	}
+	return this;
+}
+
+bool BHeap::Lower_Key(Cell x, Key_t NKey)
+{
+	BHeap *y, *z, *tx = ((BHeap *) ((CList *) x)->Datas);
+
+	if (NKey > tx->Key)
+		return false;
+	tx->Key = NKey;
+
+	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);
+		SWAP(((CList *) (y->FP))->Datas, ((CList *) (z->FP))->Datas);
+	}
+
+	return true;
+}
+
+Key_t BHeap::Delete(Datas_t & Datas, Cell x)
+{
+	Key_t K;
+
+	K = ReadKey(x);
+
+	Lower_Key(x, M_INFINITY);
+	Extract_Min(Datas);
+
+	return K;
+}
+
+bool BHeap::IsEmpty(void)
+{
+	return (!(Brother));
+}
+
+Key_t BHeap::ReadKey(Cell C)
+{
+	return ((BHeap *) ((CList *) C)->Datas)->Key;
+}
+
+Datas_t BHeap::ReadDatas(Cell C)
+{
+	return ((BHeap *) ((CList *) C)->Datas)->Datas;
+}
diff --git a/lib/CList.cc b/lib/CList.cc
new file mode 100644
index 0000000..c54e6e1
--- /dev/null
+++ b/lib/CList.cc
@@ -0,0 +1,62 @@
+#include <stdio.h>
+#include "config.h"
+#include "CList.h"
+
+CList::CList(CList * IPoint, Datas_t IDatas, Key_t IKey):Left(IPoint), Right(IPoint->Right), Key(IKey), Datas(IDatas)
+{
+	Left->Right = this;
+	if (Right)
+		Right->Left = this;
+}
+
+CList::CList(void):Left(NULL), Right(NULL), Key(0), Datas(NULL)
+{
+}
+CList::~CList(void)
+{
+	if (Right)
+		delete Right;
+}
+
+Datas_t CList::ReadDatas(Cell C)
+{
+	return ((CList *) C)->Datas;
+}
+
+Key_t CList::ReadKey(Cell C)
+{
+	return ((CList *) C)->Key;
+}
+
+Cell CList::Insert(Key_t IKey, Datas_t const &IDatas)
+{
+	return (new CList(this, IDatas, IKey));
+}
+
+Key_t CList::Delete(Datas_t & Datas, Cell C)
+{
+	Key_t K;
+
+	CList *x = ((CList *) C);
+
+	if (x->Left)
+		x->Left->Right = x->Right;
+	if (x->Right)
+		x->Right->Left = x->Left;
+	Datas = x->Datas;
+	K = x->Key;
+	x->Right = NULL;
+	delete x;
+
+	return K;
+}
+
+Cell CList::GetFirst(void)
+{
+	return Right;
+}
+
+Key_t CList::Pop(Datas_t & Datas)
+{
+	return Delete(Datas, GetFirst());
+}
diff --git a/lib/FHeap.cc b/lib/FHeap.cc
new file mode 100644
index 0000000..f8a206f
--- /dev/null
+++ b/lib/FHeap.cc
@@ -0,0 +1,340 @@
+#include <stdio.h>
+#include "config.h"
+#include "PCommon.h"
+#include "FHeap.h"
+
+/*
+
+  The Child of the Head of a FHeap is the min.
+  The Key of the Head of a FHeap is the number of cells.
+  The Degree of the Head is -1.
+
+*/
+
+static int d;
+
+void FHeap::Link(FHeap * x)
+{
+	Right->Left = Left;
+	Left->Right = Right;
+	Father = x;
+	if (x->Degree++) {
+		Left = x->Child->Left;
+		Right = x->Child;
+		Left->Right = Right->Left = this;
+	} else {
+		x->Child = this;
+		Left = Right = this;
+	}
+	Mark = false;
+}
+
+void FHeap::Rebuild(void)
+{
+	FHeap *A[DFMAX], *w, *x, *y;
+	int i, d;
+
+	for (i = 0; i < DFMAX; i++)
+		A[i] = NULL;
+
+	/* L'implémentation de la phrase du Cormen 'pour chaque noeud w de la
+	   liste des racines de T' se fait de cette manière: comme chaque noeud
+	   de la liste des racines se retrouvera dans le tableau A, si nous voulons
+	   effectuer le travail sur un noeud w et qu'il se trouve déjà dans le
+	   tableau A à l'emplacement de son propre degré, c'est que nous avons fait
+	   le tour de la liste des racines. */
+
+	for (w = Child; A[w->Degree] != w; w = w->Right) {
+		x = w;
+		d = x->Degree;
+		while (A[d]) {
+			y = A[d];
+			if (x->Key > y->Key) {
+				/* Attention, w va passer EN DESSOUS de la liste des racines. Nous devons
+				   préserver w, puisque x == y. Donc comme x va disparaître de la liste
+				   des racines, le prochain élément sur lequel nous travaillerons sera
+				   x->Right. Et son prédesseur est x->Right->Left->Left, c'est à dire
+				   x->Left. C'est pourquoi nous faisons w = x->Left maintenant. */
+				w = x->Left;
+				SWAP(x, y);
+			}
+			y->Link(x);
+			A[d++] = NULL;
+		}
+		A[d] = x;
+		/* Nous recalculons l'éventuelle nouvelle valeur de max[T]. */
+		if (ReadKey(Child) > ReadKey(w))
+			Child = w;
+	}
+
+	/* Contrairement au Cormen, nous n'avons pas besoin de reconstruire ici
+	   la liste des racines de T. */
+}
+
+void FHeap::Dump(ostream & os)
+{
+	int i;
+	FHeap *l;
+
+	if (Degree == -1) {
+		os << _(" * Head cell. (") << Key << ")\n |\n";
+		d = 0;
+	} else {
+		for (i = 1; i <= d; i++)
+			os << " |";
+		os << (Child ? "_  " : "__ ") << Key << " (" << Degree <<
+			")\n";
+	}
+	if (Child) {
+		d++;
+		Child->Dump(os);
+		d--;
+	}
+
+	l = Left->Right;
+	Left->Right = NULL;
+	if (Right) {
+		Right->Dump(os);
+	}
+	Left->Right = l;
+}
+
+int FHeap::rn(void)
+{
+	int n = 0;
+	FHeap *l;
+
+	if (Degree != -1) {
+		n++;
+	}
+	if (Child) {
+		n += Child->rn();
+	}
+
+	l = Left->Right;
+	Left->Right = NULL;
+	if (Right) {
+		n += Right->rn();
+	}
+	Left->Right = l;
+
+	return n;
+}
+
+FHeap::FHeap(void):Father(NULL), Child(NULL), Left(this), Right(this),
+Degree(-1), Mark(false)
+{
+  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;
+#ifdef DEBUG
+	nc++;
+#endif
+}
+
+FHeap::~FHeap(void)
+{
+	FHeap *T;
+
+	if (Child) {
+		delete Child;
+	}
+	if (Right != this) {
+		Left->Right = Right;
+		Right->Left = Left;
+		delete Right;
+	}
+#ifdef DEBUG
+	nd++;
+#endif
+}
+
+Cell FHeap::Min(void)
+{
+	return Child;
+}
+
+FHeap *FHeap::Insert(FHeap * E)
+{
+	if (Degree != -1)
+		exception(2, _("Insert: not over Head."));
+	if (Child) {
+		((FHeap *) E)->Father = NULL;
+		((FHeap *) E)->Left = Child;
+		((FHeap *) E)->Right = Child->Right;
+		Child->Right->Left = ((FHeap *) E);
+		Child->Right = ((FHeap *) E);
+		if (ReadKey(E) < (Child->Key)) {
+			Child = ((FHeap *) E);
+		}
+	} else {
+		Child = ((FHeap *) E);
+	}
+	Key++;
+	return E;
+}
+
+Cell FHeap::Insert(Key_t IKey, Datas_t const &IDatas)
+{
+	FHeap *P;
+
+	if (!(P = new FHeap(IKey, IDatas)))
+		exception(5, _("Insert: No more memory."));
+	return Insert(P);
+}
+
+Key_t FHeap::Extract_Min(Datas_t & Datas)
+{
+	FHeap *z, *w;
+	Key_t k;
+
+	if (!(z = Child))
+		exception(4, _("Extract_Min: Priority List is empty."));
+
+	Datas = z->Datas;
+	k = z->Key;
+
+	/* Nous inversons ici l'idée du Cormen... Au lieu de procéder cas par cas, nous
+	   mettons d'abord en globalité les pères de tous les fils de z à NULL (ce qui
+	   nous permet de faire facilement la boucle, puisque, lorsque nous retombons
+	   sur une cellule dont le père est NULL, cela signifie que nous avons fait
+	   le tour) et à ce moment-là, la liste des fils de z, indexée par z fait un
+	   superbe tas de Fibonacci que nous allons immédiatement fusionner avec le tas
+	   en cours. De plus, nous supprimons z de la liste des racines maintenant. */
+
+	z->Right->Left = z->Left;
+	z->Left->Right = z->Right;
+	if ((Child = z->Right) == z)
+		Child = NULL;
+
+	z->Father = NULL;
+	z->Left = z->Right = z;
+
+	if (z->Child) {
+		for (w = z->Child; w->Father; w = w->Left)
+			w->Father = NULL;
+		z->Degree = -1;
+		z->Key = Child ? 0 : Key;	// Pour conserver n[T] à jour.
+		Union(z);
+	}
+
+	if (!(--Key)) {
+		Child = NULL;
+	} else {
+		Rebuild();
+	}
+
+	z->Child = NULL;
+	delete z;
+
+	return k;
+}
+
+PriorityList *FHeap::Union(PriorityList * P)
+{
+	FHeap *Temp, *T = ((FHeap *) P);
+
+	if ((P->GetType()) != (((PriorityList *) P)->GetType()))
+		return GenericUnion(P);
+
+	/* Cette fonction ne suit pas du tout l'idée du Cormen. Elle va
+	   fusionner directement T dans le tas en cours, sans créer
+	   d'intermédiaires. Les données internes du tas sont mises à
+	   jour. */
+
+	if (!Child) {
+		Child = T->Child;
+		Key = T->Key;
+	} else if (T->Child) {
+		Child->Right->Left = T->Child;
+		T->Child->Right->Left = Child;
+		Temp = Child->Right;
+		Child->Right = T->Child->Right;
+		T->Child->Right = Temp;
+		if (T->Child->Key < Child->Key)
+			Child = T->Child;
+		Key += T->Key;
+	}
+
+	T->Child = NULL;
+	return this;
+}
+
+bool FHeap::Lower_Key(Cell x, Key_t NKey)
+{
+	FHeap *y, *tx = ((FHeap *) x);
+
+	if (NKey > tx->Key)
+		return false;
+
+	tx->Key = NKey;
+	y = tx->Father;
+	if ((y) && (tx->Key < y->Key)) {
+		Cut(tx, y);
+		CascadeCut(y);
+	}
+	if (NKey < Child->Key)
+		Child = tx;
+}
+
+Key_t FHeap::Delete(Datas_t & Datas, Cell x)
+{
+	Key_t K;
+
+	K = ReadKey(x);
+
+	Lower_Key(x, M_INFINITY);
+	Extract_Min(Datas);
+
+	return K;
+}
+
+void FHeap::Cut(FHeap * x, FHeap * y)
+{
+	/* Le fait de rajouter la cellule en cours à la liste des racines de T ne
+	   modifie en rien le comportement de min[T]. Sinon, cela voudrait dire que
+	   le minimum est la cellule que nous déplaçons et cela est impossible car
+	   le minimum est obligatoirement une racine. */
+
+	y->Degree--;
+
+	x->Right->Left = Left;
+	x->Left->Right = Right;
+
+	if (y->Child == x) {
+		y->Child = y->Degree ? x->Right : NULL;
+	}
+
+	x->Right = Child->Right;
+	x->Left = Child;
+
+	Child->Right->Left = x;
+	Child->Right = x;
+
+	x->Father = NULL;
+
+	x->Mark = false;
+}
+
+void FHeap::CascadeCut(FHeap * y)
+{
+	FHeap *z = y->Father;
+
+	if (z) {
+		if (!(y->Mark)) {
+			y->Mark = true;
+		} else {
+			Cut(y, z);
+			CascadeCut(z);
+		}
+	}
+}
+
+bool FHeap::IsEmpty(void)
+{
+	return (!(Child));
+}
diff --git a/lib/HTree.cc b/lib/HTree.cc
new file mode 100644
index 0000000..c651f48
--- /dev/null
+++ b/lib/HTree.cc
@@ -0,0 +1,40 @@
+#include <stdio.h>
+#include <iostream.h>
+#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(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;
+}
+
+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
new file mode 100644
index 0000000..146f061
--- /dev/null
+++ b/lib/Hash.cc
@@ -0,0 +1,3 @@
+#include <stdio.h>
+#include "config.h"
+#include "Hash.h"
diff --git a/lib/Makefile.am b/lib/Makefile.am
new file mode 100644
index 0000000..9e99421
--- /dev/null
+++ b/lib/Makefile.am
@@ -0,0 +1,11 @@
+localedir = $(datadir)/locale
+DEFS = -DLOCALEDIR=\"$(localedir)\" @DEFS@
+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_LDFLAGS = -version-info $(PriorityLists_VERSION_INFO)
+
+EXTRA_DIST = FHeap.cc
\ No newline at end of file
diff --git a/lib/PCommon.cc b/lib/PCommon.cc
new file mode 100644
index 0000000..20299ba
--- /dev/null
+++ b/lib/PCommon.cc
@@ -0,0 +1,44 @@
+#include <stdio.h>
+#include "config.h"
+#include "PCommon.h"
+
+PriorityList::PriorityList(Key_t IKey, Datas_t const &IDatas):Key(IKey),
+Datas(IDatas)
+{
+}
+
+PriorityList::PriorityList(void):Key(0), Datas(NULL)
+{
+}
+
+PriorityList::~PriorityList(void){}
+
+Key_t PriorityList::ReadKey(Cell C)
+{
+	return ((PriorityList *) C)->Key;
+}
+
+Datas_t PriorityList::ReadDatas(Cell C)
+{
+	return ((PriorityList *) C)->Datas;
+}
+
+int PriorityList::n(void)
+{
+	return Key;
+}
+
+PriorityList *PriorityList::GenericUnion(PriorityList * P)
+{
+	Key_t IKey;
+	Datas_t IDatas;
+
+	while (!(P->IsEmpty())) {
+		IKey = P->Extract_Min(IDatas);
+		Insert(IKey, IDatas);
+	}
+}
+
+int PriorityList::GetType(void) {
+  return type;
+}
diff --git a/lib/PLList.cc b/lib/PLList.cc
new file mode 100644
index 0000000..5234b91
--- /dev/null
+++ b/lib/PLList.cc
@@ -0,0 +1,126 @@
+#include <stdio.h>
+#include "config.h"
+#include "PLList.h"
+
+
+PriorityList *PLList::Union(PriorityList * P)
+{
+	if ((P->GetType()) != (((PriorityList *) this)->GetType())) {
+		return GenericUnion(P);
+	} else {
+		CList *x, *y, *t;
+		PLList *T = ((PLList *) P);
+
+		x = &Head;
+		y = T->Head.Right;
+		Key += T->Key;
+
+		while (x->Right && y) {
+			if (x->Right->Key > y->Key) {
+				t = y->Right;
+				y->Right = x->Right;
+				y->Left = x;
+				x->Right->Left = y;
+				x->Right = y;
+				y = t;
+			}
+			x = x->Right;
+		}
+
+		if (y) {
+			x->Right = y;
+			y->Left = x;
+		}
+
+		T->Head.Right = NULL;
+	}
+	return this;
+}
+
+bool PLList::Lower_Key(Cell x, Key_t NKey)
+{
+	CList *T = ((CList *) x), *t;
+
+	if (T->Key < NKey)
+		return false;
+
+	T->Key = NKey;
+
+	if (T->Left)
+		T->Left->Right = T->Right;
+	if (T->Right)
+		T->Right->Left = T->Left;
+
+	for (t = T->Left; ((t->Left->Left) && (NKey < t->Left->Key));
+	     t = t->Left) ;
+
+	T->Left = t->Left;
+	T->Right = t;
+	t->Left = T->Left->Right = T;
+	return true;
+}
+
+
+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;
+
+	for (CList * x = Head.Right; x; x = x->Right)
+		n++;
+	return n;
+}
+
+void PLList::Dump(ostream & os)
+{
+	os << _(" * Head cell\n |\n");
+	for (CList * x = Head.Right; x; x = x->Right)
+		os << " |__ " << x->Key << endl;
+}
+
+bool PLList::IsEmpty(void)
+{
+	return (!(Head.Right));
+}
+
+Cell PLList::Min(void)
+{
+	return Head.Right;
+}
+
+Cell PLList::Insert(Key_t IKey, Datas_t const &IDatas)
+{
+	Key++;
+	return Head.Insert(IKey, IDatas);
+}
+
+Key_t PLList::Extract_Min(Datas_t & Datas)
+{
+	if (!Key)
+		exception(4, _("Extract_Min: Priority List is empty."));
+	Key--;
+	return Head.Delete(Datas, Head.Right);
+}
+
+Key_t PLList::Delete(Datas_t & Datas, Cell x)
+{
+	return Head.Delete(Datas, x);
+}
diff --git a/lib/SList.cc b/lib/SList.cc
new file mode 100644
index 0000000..fef50e9
--- /dev/null
+++ b/lib/SList.cc
@@ -0,0 +1,11 @@
+#include <stdio.h>
+#include "SList.h"
+
+Cell SList::Insert(Key_t IKey, Datas_t const &IDatas)
+{
+	CList *I = this, *x;
+
+	for (x = Right; (x) && (x->Key <= IKey); x = x->Right)
+		I = x;
+	return (new CList(I, IDatas, IKey));
+}