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