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.

---
 lib/BinHeap.cc | 27 ++++++++++++++++++---------
 1 file changed, 18 insertions(+), 9 deletions(-)

(limited to 'lib/BinHeap.cc')

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 <stdlib.h>
 #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--;
-- 
cgit v1.2.3