path: root/lib/BHeap.cc

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