From 833d20a69fe17ab846c153e35230c66a41d8fca9 Mon Sep 17 00:00:00 2001
From: Pixel <>
Date: Wed, 28 Feb 2001 11:40:25 +0000
Subject: Premier jet

---
 lib/BHeap.cc | 278 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 278 insertions(+)
 create mode 100644 lib/BHeap.cc

(limited to 'lib/BHeap.cc')

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;
+}
-- 
cgit v1.2.3