#include <stdio.h>
#include "config.h"
#include "BHeap.h"
#include "CList.h"

/**********************************\
*                                  *
*         Tas binomial             *
*                                  *
\**********************************/

/*
 *
 * Le tas binomial impl�ment� suit exactement les algorithmes pr�sent�s dans
 * le livre "Introduction � l'algorithmique". La structure est r�cursive et
 * les donn�es de l'ent�te sont r�parties comme suit:
 *   - Degree = -1 (pour signaler que nous somme dans l'ent�te)
 *   - Key contient le nombre d'�l�ments enregistr�s
 *   - Brother est le pointeur sur le premier �l�ment du tas
 *
 */

static int d, Depths[65536];


/*
 * Cette fonction sert � afficher le contenu du tas binomial sur le stream
 * pass� en argument. L'affichage sera structur� de sorte � ressembler aux
 * diagrammes pr�sent�s dans le livre "Introduction � l'algorithmique", �
 * ceci pr�s qu'ils sont pr�sent�s � la verticale. Exemple:
 *
 *  * Head cell.
 *  |
 *  |__ 6
 *  |_  15
 *  | |__ 18
 *  |_  5
 *  | |_  10
 *  | | |__ 29
 *  | |__ 9
 *  |_  2
 *    |_  3
 *    | |_  16
 *    | | |__ 23
 *    | |__ 17
 *    |_  11
 *    | |__ 25
 *    |__ 14
 *
 */

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


 /*
  * Cette fonction est utilis�e dans les tests "parano�aques" pour compter
  * le nombre v�ritable de cellules lors d'un parcours r�cursif.
  */

int BHeap::rn(void)
{
	int n = 0;

	if (Degree != -1) {
		n++;
	}
	if (Child) {
		n += Child->rn();
	}
	if (Brother) {
		n += Brother->rn();
	}
	return n;
}


 /*
  * Impl�mentation directe de la primitive LIEN-BINOMIAL(y, z) avec y = this.
  */

void BHeap::Link(BHeap * z)
{
	Father = z;
	Brother = z->Child;
	z->Child = this;
	z->Degree = z->Degree + 1;
}


 /*
  * Impl�mentation de la primitive FUSIONNER-TAS-BINOMIAUX(T1, T2) avec T1 = this.
  * L'algorithme a du �tre inventer car il n'est pas pr�sent� dans le livre.
  * Par contre, il s'inspire fortement de l'algorithme "Fusion" pour le
  * tri-fusion. De plus, contrairement aux indication du livre, T2 sera rajout�
  * APRES T1, et aucun tas binaire nouveau ne sera cr��. (voir rapport)
  */

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


 /*
  * Constructeur d'un tas binomial.
  */

BHeap::BHeap(void):Degree(-1), Father(NULL), Child(NULL), Brother(NULL), FP(new CList)
{
	type = T_BHEAP;
}


 /*
  * Constructeur interne. La structure est r�cursive, donc nous impl�mentons
  * un constructeur priv�.
  */

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
}


 /*
  * Le destructeur. S'il est appel� sur l'ent�te, nous effacons r�cursivement
  * la liste des pointeurs interm�diaires, ainsi que tout le tas
  * r�cursivement.
  */

BHeap::~BHeap(void)
{
	if (Degree == -1)
		delete FP;

	if (Child) {
		delete Child;
	}
	if (Brother) {
		delete Brother;
	}
#ifdef DEBUG
	nd++;
#endif
}


 /*
  * Impl�mentation directe de l'algorithme MINIMUM-TAS-BINOMIAL(T) avec T = this.
  */

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


 /*
  * Insertion d'une cellule d�j� cr�� dans le tas.
  * La routine fonctionne comme dans l'algorithme conseill�.
  */

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


 /*
  * Insertion d'un couple (Clef, Donn�es) dans le tas.
  */

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


 /*
  * Impl�mentation de l'algorithme TAS-BINOMIAL-EXTRAIRE-MIN(T) avec T = this.
  * La clef extraite sera renvoy�e et les donn�es satellites seront �crites dans
  * la variable Datas. L'impl�mentation est beaucoup plus longue que
  * l'algorithme de quatre lignes pr�sent� dans le livre mais il s'agit de la
  * traduction entre les phrases en fran�ais pr�sent�es et le langage C.
  */

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

	// 1. Trouver la racine x de cl� minimum dans la liste des racines de T...

	for (x = Brother; x; x = x->Brother) {
		if ((x->Key < min)) {
			min = x->Key;
			y = x;
			Before = P;
		}
		P = x;
	}

	//    ... et supprimer x.
	Before->Brother = y->Brother;

	// 2. T' <- CREER-TAS-BINOMIAL
	Before = new BHeap;

	// 3. inverser l'ordre de la liste cha�n�e des fils de x,
	//    et faire pointer t�te[T'] sur la t�te de la liste r�sultante.
	//    Comme pour fusionner, nous effectuons le travail "sur place",
	//    pour �viter les probl�mes dues aux recopies. (voir rapport)
	for (P = y->Child; P;) {
		P->Father = NULL;
		P2 = Before->Brother;
		P3 = P->Brother;
		Before->Brother = P;
		P->Brother = P2;
		P = P3;
	}

	// 4. T <- UNION-TAS-BINOMIAUX(T, T')
	Before->Key = 0;
	Union(Before);

	// 5. retourner x (et l'effacer)
	k = y->Key;
	y->Brother = y->Child = NULL;
	FP->Delete(Datas, ((Cell) y->FP));
	Datas = y->Datas;
	delete y;

	return k;
}


 /*
  * Impl�mentation de l'algorithme UNION-TAS-BINOMIAUX(T1, T2) avec T1 = this.
  * Il y a quelques changements par rapport a l'algorithme du cormen (voir rapport)
  */

PriorityList *BHeap::Union(PriorityList * P)
{
	BHeap *x, *Before, *After;

	if ((P->GetType()) != 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;
}


 /*
  * Impl�mentation de l'algorithme TAS-BINOMIAL-DIMINUER-CLE(T,x,k) avec T = this.
  * L'impl�mentation de cette routine a n�cessit� le rajout d'une table de pointeurs
  * pour conserver une structure correcte (voir rapport)
  */

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


 /*
  * 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 BHeap::Delete(Datas_t & Datas, Cell x)
{
	Key_t K;

	K = ReadKey(x);

	Lower_Key(x, M_INFINITY);
	Extract_Min(Datas);

	return K;
}


 /*
  * Bool�en qui d�termine si le tas est vide ou pas.
  */

bool BHeap::IsEmpty(void)
{
	return (!(Brother));
}


 /*
  * Lit la clef d'une cellule d'un tas.
  */

Key_t BHeap::ReadKey(Cell C)
{
	return ((BHeap *) ((CList *) C)->Datas)->Key;
}


 /*
  * Lit les donn�es d'une cellule d'un tas.
  */

Datas_t BHeap::ReadDatas(Cell C)
{
	return ((BHeap *) ((CList *) C)->Datas)->Datas;
}