#include <stdio.h>
#include "config.h"
#include "PLList.h"

/*****************************************************\
*                                                     *
* File de priorité basée sur une liste chaînée triée. *
*                                                     *
\*****************************************************/

 /*

  * Cette file de priorité a une structure non récursive. Elle se base sur
  * une SList pour fonctionner. 
  *
  */


 /*
  * La méthode "Union" est en fait l'algorithme "Fusion" du tri-fusion.
  */

PriorityList *PLList::Union(PriorityList * P)
{
	if ((P->GetType()) != (((PriorityList *) this)->GetType())) {
		return GenericUnion(P);
	} else {
		CList *x, *y, *t;
		PLList *T = ((PLList *) P);

		x = &Head;
		y = T->Head.Right;
		Key += T->Key;

		while (x->Right && y) {
			if (x->Right->Key > y->Key) {
				t = y->Right;
				y->Right = x->Right;
				y->Left = x;
				x->Right->Left = y;
				x->Right = y;
				y = t;
			}
			x = x->Right;
		}

		if (y) {
			x->Right = y;
			y->Left = x;
		}

		T->Head.Right = NULL;
	}
	return this;
}


 /*
  * Cette méthode va "décrocher" l'élément de la liste
  * et va tenter de trouver sa nouvelle place, en se déplaçant
  * depuis son ancienne place vers la "gauche".
  */

bool PLList::Lower_Key(Cell x, Key_t NKey)
{
	CList *T = ((CList *) x), *t;

	if (T->Key < NKey)
		return false;

	T->Key = NKey;

	if (T->Left)
		T->Left->Right = T->Right;
	if (T->Right)
		T->Right->Left = T->Left;

	for (t = T->Left; ((t->Left->Left) && (NKey < t->Left->Key)); t = t->Left) ;

	T->Left = t->Left;
	T->Right = t;
	t->Left = T->Left->Right = T;
	return true;
}


 /*
  * Toutes les autres méthodes sont "simples" (c'est à dire une lignes ou deux)
  * et parlent d'elles-même. Nul besoin de commentaires pour elles. Elles se
  * basent en grande partie sur la SList présente dans la structure.
  */

PLList::PLList(void)
{
	type = T_PLLIST;
	Key = 0;
	Datas = NULL;
}

PLList::~PLList(void)
{
}

Key_t PLList::ReadKey(Cell C)
{
	return Head.ReadKey(C);
}

Datas_t PLList::ReadDatas(Cell C)
{
	return Head.ReadDatas(C);
}

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

	for (CList * x = Head.Right; x; x = x->Right)
		n++;
	return n;
}

void PLList::Dump(ostream & os)
{
	os << _(" * Head cell\n |\n");
	for (CList * x = Head.Right; x; x = x->Right)
		os << " |__ " << x->Key << endl;
}

bool PLList::IsEmpty(void)
{
	return (!(Head.Right));
}

Cell PLList::Min(void)
{
	return Head.Right;
}

Cell PLList::Insert(Key_t IKey, Datas_t const &IDatas)
{
	Key++;
	return Head.Insert(IKey, IDatas);
}

Key_t PLList::Extract_Min(Datas_t & Datas)
{
	if (!Key)
		exception(4, _("Extract_Min: Priority List is empty."));
	Key--;
	return Head.Delete(Datas, Head.Right);
}

Key_t PLList::Delete(Datas_t & Datas, Cell x)
{
	return Head.Delete(Datas, x);
}