UNE LISTE CHAINÉE AVEC CLÉS

#ifndef _LISTEORDONNEE_H_
#define _LISTEORDONNEE_H_

class	Ordonnable
{
public:
	virtual	~Ordonnable(){}

	virtual int	compareTo(Ordonnable *obj)=0;
	//Précond : obj doit être de même type que this
	//Résultat:	retourne : -1,0 ou 1 selon que obj est resp <,= ou > à this

	virtual char *getIdentifiant()=0;
	//Précond : aucune
	//Résultat: retourne une chaine de caractères identifiant le type
	//			d'objet. La chaine est dans le tas, et doit être détruite par
	//			l'utilisateur. Cette fonction sert à la gestion des listes,
	//			afin de garantir qu'une liste ne contient qu'un type d'objet
	//			ordonnable (cette garantie n'est valable que dans la mesure
	//			où l'utilisateur donne des identifiants différents à chaque
	//			type d'objet ordonnable).
};

class	CLOrdonnable
{
	friend class ListeOrdonnee;
//private:
public:
	Ordonnable		*val;
	CLOrdonnable	*suiv;
protected:
public:
	CLOrdonnable(Ordonnable *val, CLOrdonnable *suiv=NULL);
	virtual ~CLOrdonnable();
};

class	ListeOrdonnee
{
//private:
public:
	//Tête de la liste chaînée
	CLOrdonnable	*tete;
	//Identifiant des éléments reçus par la liste
	char			*identifiant;

	int	chercheCOrdonnable(	Ordonnable		*valCherchee,
							CLOrdonnable	*&celTrouvee,
							CLOrdonnable	*&celPrecedente);
	//Précond : val ne doit pas être nul.
	//Résultat: retourne 1 si valCherchee a été trouvée dans la liste, ou 3 si elle n'a
	//			pas été trouvée.
	//			si une erreur s'est produite, retourne son code.
	//			Si la valeur a été trouvée, celTrouvee et celPrecedente pointent
	//			respectivement la cellule contenant la valeur cherchée, et celle
	//			la précédant.
	//			Si la valeur n'a pas été trouvée, celTrouvee et celPrecedente pointent
	//			resp sur la cellule contenant la valeur sup, et celle la précédant

protected:
public:
	ListeOrdonnee(char *identifiant=NULL);
	~ListeOrdonnee();

	CLOrdonnable *getTete();
	//Précond : aucune
	//Résultat: retourne un pointeur sur la tete de la liste

	int ajouteElement (Ordonnable *val);
	//Précond : Si l'identifiant de type est déjà renseigné, l'objet passé
	//			en paramètre doit posséder le même identifiant de type.
	//			Si l'identifiant de type n'est pas renseigné, la liste prend
	//			pour seul identifiant acceptable le type de l'objet passé en argument.
	//			L'identifiant de l'instance de l'objet ne doit pas être déjà présent
	//			dans la liste.
	//			Si l'opération réussit, la méthode retourne 0. Si elle échoue,
	//			un code d'erreur est retourné.
	//Action  : Stocke l'objet passé en paramètre dans la liste ordonnée.

	int	supprimeElement(Ordonnable *val);
	//Précond : Si l'identifiant de type est déjà renseigné, l'objet passé
	//			en paramètre doit posséder le même identifiant de type.
	//			L'identifiant de l'instance de l'objet ne doit pas être déjà présent
	//			dans la liste.
	//			Si l'opération réussit, la méthode retourne 0. Si elle échoue,
	//			un code d'erreur est retourné.
	//Action  :	supprime l'objet possédant le même identifiant d'instance que celui
	//			passé en paramètre, si il existe.

	int	getNombreElements();
	//Précond : aucune
	//Résultat: retourne le nombre d'éléments présents dans la liste chaînée

	void vide();
	//Précond : aucune
	//Action  : vide la liste. Tous les éléments sont supprimés de la liste,
	//			et sont détruits.
};

#endif

/*
Codes des erreurs retournées
0	pas d'erreur
1	identifiant d'instance déjà présent
2	identifiant de type incorrect
3	identifiant d'instance non trouvé
4	pointeur nul interdit
*/

CLOrdonnable::CLOrdonnable(Ordonnable *val, CLOrdonnable *suiv)
{
	this->val = val;
	this->suiv = suiv;
}

CLOrdonnable::~CLOrdonnable()
{
	delete(this->val);
}

ListeOrdonnee::ListeOrdonnee(char *identifiant)
{
	int l;
	this->tete = NULL;

	if (identifiant==NULL)
	{
		this->identifiant=NULL;
	}
	else
	{
		l=strlen(identifiant);
		this->identifiant = new char[l+1];
		strcpy(this->identifiant,identifiant);
	}
}

ListeOrdonnee::~ListeOrdonnee()
{
	this->vide();
	delete(this->identifiant);
}

CLOrdonnable *ListeOrdonnee::getTete()
{
	return	this->tete;
}

int ListeOrdonnee::chercheCOrdonnable(	Ordonnable *valCherchee,
										/*R*/CLOrdonnable *&celTrouvee,
										/*R*/CLOrdonnable *&celPrecedente)
{
	int		resultComp;
	char	*ident;

	if (valCherchee==NULL)
	{
		//erreur valeur nulle interdite
		return	4;
	}

	//test sur l'identifiant de type
	if (this->identifiant==NULL)
	{
		//Si l'identifiant de la liste n'a pas été initialisé,
		//on l'initialise avec l'identifiant de type de l'instance passée
		this->identifiant=valCherchee->getIdentifiant();
	}
	else
	{
		//Comparaison de l'identifiant de type de la liste, avec celui
		//du type de l'instance recherchée.
		ident = valCherchee->getIdentifiant();
		if (strcmp(ident,this->identifiant)!=0)
		{
			delete(ident);
			//erreur type incorrect pour cette liste
			return	2;
		}
		delete (ident);
	}
	
	//Recherche de l'indentifiant d'instance :
	//parcours partiel de la liste chainée, jusqu'à rencontrer une instance
	//dont la comparaison indique qu'elle est supérieure ou égale à celle recherchée
	resultComp=-1;
	celPrecedente = NULL;
	celTrouvee = this->tete;
	while (	celTrouvee!=NULL &&/*alors*/
			(resultComp=valCherchee->compareTo(celTrouvee->val))<0)
	{
		celPrecedente = celTrouvee;
		celTrouvee = celTrouvee->suiv;
	}
	if (resultComp!=0)
	{
		//identifiant d'instance non trouvé
		return	3;
	}
	//identifiant d'instance trouvé
	return	1;
}


int ListeOrdonnee::ajouteElement (Ordonnable *val)
{
	CLOrdonnable	*precedent=NULL;
	CLOrdonnable	*trouve=NULL;
	CLOrdonnable	*nouvelle=NULL;
	int	result;

	result = chercheCOrdonnable(val,trouve,precedent);
	if (result != 3)
	{
		//erreur
		return	result;
	}
	//création de la nouvelle cellule
	nouvelle = new CLOrdonnable(val,trouve);
	if (precedent==NULL)
	{
		//on est en tête de la liste
		this->tete = nouvelle;
	}
	else
	{
		precedent->suiv = nouvelle;
	}
	return	0;
}

int	ListeOrdonnee::supprimeElement(Ordonnable *val)
{
	CLOrdonnable	*precedent=NULL;
	CLOrdonnable	*trouve=NULL;
	int	result;

	result = chercheCOrdonnable(val,trouve,precedent);
	if (result != 1)
	{
		//erreur
		return	result;
	}
	if (precedent==NULL)
	{
		//on est en tête de la liste
		this->tete = trouve->suiv;
	}
	else
	{
		precedent->suiv = trouve->suiv;
	}
	delete(trouve);
	return	0;
}

int	ListeOrdonnee::getNombreElements()
{
	int nombre = 0;
	CLOrdonnable *parcours = this->tete;

	//Parcours total de la liste
	while (parcours!=NULL)
	{
		parcours = parcours->suiv;
		nombre++;
	}
	return 0;
}

void ListeOrdonnee::vide()
{
	CLOrdonnable	*temp;

	//parcours total de la liste
	while (this->tete!=NULL)
	{
		temp=this->tete;
		this->tete=temp->suiv;
		delete(temp);
	}
}