#include <stdio.h>
#include <stdlib.h>
#include "config.h"
#include "BinHeap.h"
#include "CList.h"

#define FATHER(i) (i >> 1)
#define LEFT(i) (i << 1)
#define RIGHT(i) ((i << 1) + 1)

/**********************************\
*                                  *
*          Tas binaires            *
*                                  *
\**********************************/


 /*
  * Implémentation quasi directe de l'algorithme Entasser(A, i) avec A = this.
  * Seul le test de condition est inversé.
  */

void BinHeap::PackUp(int i)
{
	int l = LEFT(i), r = RIGHT(i), min;
	binheap_t *binheap = (binheap_t *) Datas;

	min = ((l <= Key) && (binheap[l - 1].Key < binheap[i - 1].Key)) ? l : i;
	if ((r <= Key) && (binheap[r - 1].Key < binheap[min - 1].Key))
		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);
	}
}

 /*
  * Il n'y a aucune méthode "rapide" pour effectuer l'union de deux tas
  * binaires. Nous utiliserons donc l'union générique.
  */

PriorityList *BinHeap::Union(PriorityList * P)
{
	return GenericUnion(P);
}


 /*
  * L'algorithme "Diminuer Clef" ressemble à l'algorithme "Inserer"
  */

bool BinHeap::Lower_Key(Cell x, Key_t NKey)
{
	int i = ((binheap_t *) (FP->ReadDatas(x))) - ((binheap_t *) Datas) + 1;
	binheap_t *binheap = (binheap_t *) Datas;

	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) : FP(new CList)
{
	Key = 0;
	Datas = NULL;
	type = T_BINHEAP;
}

BinHeap::~BinHeap(void)
{
	if (Datas)
		free(Datas);
}

Key_t BinHeap::ReadKey(Cell C)
{
	return ((binheap_t *) FP->ReadDatas(C))->Key;
}

Datas_t BinHeap::ReadDatas(Cell C)
{
	return ((binheap_t *) FP->ReadDatas(C))->Datas;
}

int BinHeap::rn(void)
{
	return n();
}

void BinHeap::Dump(ostream & os)
{
	int i;
	binheap_t *binheap = (binheap_t *) Datas;

	for (i = 0; i < Key; i++) {
		os << binheap[i].Key << " ";
	}
	os << endl;
}

bool BinHeap::IsEmpty(void)
{
	return (Key == 0);
}

Cell BinHeap::Min(void)
{
	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;
	int i = Key++;
	Cell r;

	if (!Datas || ((((Key >> GRANUL) + 1) << GRANUL) != (((i >> GRANUL) + 1) << GRANUL))) {
		if (!(Datas = realloc(Datas, (((Key >> GRANUL) + 1) << GRANUL) * sizeof(binheap_t)))) {
			exception(5, _("Not enough memory"));
		}
	}
	i = Key;

	binheap = (binheap_t *) Datas;

	while ((i > 1) && (binheap[FATHER(i) - 1].Key > IKey)) {
		binheap[i - 1] = binheap[FATHER(i) - 1];
		((CList *) binheap[FATHER(i) - 1].FP)->Datas = &binheap[i - 1];
		i = FATHER(i);
	}
	binheap[i - 1] = newcell;
	
	r = binheap[i - 1].FP = FP->Insert(0, &(binheap[i - 1]));
	return r;
}


 /*
  * Implémentation directe de l'algorithme EXTRAIRE-MIN-TAS(A) avec A = this.
  */

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


	ret = binheap[0].Key;
	Datas = binheap[0].Datas;
	FP->Delete(Dumb, binheap[0].FP);
	binheap[0] = binheap[Key - 1];

	int i = Key--;

	if (!this->Datas || ((((Key >> GRANUL) + 1) << GRANUL) != (((i >> GRANUL) + 1) << GRANUL))) {
		this->Datas = realloc(this->Datas, (((Key >> GRANUL) + 1) << GRANUL) * sizeof(binheap_t));
	}
	PackUp(1);
	return ret;
}


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

	K = ReadKey(x);
	Lower_Key(x, M_INFINITY);
	Extract_Min(Datas);

	return K;
}