#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);
			}
			if (y == Child) {
				Child = x;
			}
			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)
{
	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 (GetType() != (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;
	return true;
}

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 = x->Left;
	x->Left->Right = x->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));
}