Plein de changements

1 files changed, 180 insertions, 0 deletions

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;
+}