CRÉATION D'UN CONTENEUR C++ : LISTE CHAINEE

#include <iostream.h>
namespace vieuxLion
{
class Liste;//déclaration forward nécessaire pour "friend"

/* "PARTIE I: "
On commencera par choisir la liste chaînée comme support
Elle est meilleure que le simple tableau pour les insertions et suppressions
Dans cette première partie, on raisonnera avec le type 'int' pour les valeurs des éléments

On créera une classe Element dont le rôle est de supporter la valeur ET les chaînages avant et arrières
sur les éléments suivant et précédent
L'élément suivant sera utilisé pour le parcours de la liste (en avant)
L'élément précédent sera utile en cas de destruction d'élément (pour mettre à jour le pointeur suivant du précédent)
 ou en cas de parcours arrière
Cette classe aura donc trois données membres (deux seulement dans cette partie I) et un constructeur correspondant
*/
class Element
{ friend Liste;//l'accès aux données des Elements est OK pour la Liste
private:
    int valeur_;//la valeur de l'élément est pour l'instant limitée à 'int'
    Element* suivant_;
public:
    Element(int valeur): valeur_(valeur), suivant_(NULL){}
};

/*On créera ensuite une classe Liste composée des Elements
Pour des raisons d'efficacité, il est bon de mémoriser la tête et la queue de la liste
La tête sera utile pour parcourir la liste à partir du bébut
La queue sera utile pour insérer efficacement un nouvel élément à la fin
*/
  
class Liste
{
private:
   Element* tete_;
   Element* queue_;//la mémorisation de la queue est pratique pour les Ajouts
   Liste (const Liste& l);//empêche la copie par Ctor
   void operator=(const Liste& l);//empêche la copie par affectation
public:
   Liste();
   ~Liste();
   Element* Ajouter(int valeur, Element* pE=NULL);//ajouter derrière pElt
   void Vider();//détruire la liste ainsi que les objets pointés
   void Afficher() const;//parcours et affichage des éléments
};
 /* Il est à noter que la liste contient des pointeurs sur les éléments et 
  qu'en cas de copie, la copie des pointeurs n'est pas recommandée (problème d'aliassing)
  Il serait donc nécessaire de surcharger les opérateurs = et Ctor de copie...
  La solution la plus simple ici, est d'interdire la copie
  On rendra donc private les deux opérations.

  Implémentation :
Le Ctor de Liste crée une liste vide 
Le Dtor de Liste nettoie les éléments (s'il y en a)
La technique de parcours de la liste est toujours la même :
 démarrer à la tête puis naviguer sur le suivant, etc...
*/
Liste::Liste()
{ tete_ = NULL; queue_ = NULL;}

Liste::~Liste()
{ Vider(); }

Element* Liste::Ajouter(int valeur, Element* pE )
{//pE est l'élément derrière lequel se fait l'insertion
  if (!pE) pE = queue_ ;//par défaut, ajout en queue

  Element* pNew = new Element(valeur);//création de l'Elt à partir de la valeur
  if (tete_==NULL)
  { tete_ = queue_ = pNew;//le premier est aussi le dernier, il est le seul}
  else
  {
    pNew->suivant_ = pE->suivant_;//le suivant du nouveau est 'le suivant de pE'
    pE->suivant_  = pNew;//le nouveau devient le suivant de 'pE'
    if (pE==queue_) queue_ = pNew;
  }

  return pNew;
}


void Liste::Afficher() const //afficher toute la liste
{
   if (tete_ == NULL) cout << "la liste est vide..." << endl;
   else
   {
      cout << "la liste contient : " << endl;
      Element* iter = tete_;
      do	
      {
	cout << "\t" << iter->valeur_ << endl;
	iter = iter->suivant_;	
      }
      while (iter); 
   }
}

void Liste::Vider()  // Vider toute la liste
{
	if (tete_ == NULL) 
	{	cout << "la liste est deja vide" << endl; 
		return;
	}
	else
	{
		Element* iter = tete_;
		Element* pSuivant; 
		do
		{
			pSuivant = iter->suivant_;
			delete iter;
			iter = pSuivant;
		}
		while (iter); 
	}
	tete_ = queue_ = NULL;
	cout << "la liste est videe" << endl; 
}


}//namespace vieuxLion

using vieuxLion::Liste;
using vieuxLion::Element;

int main()
{
	cout << "creer une liste (vide)" << endl;
	Liste l;
	cout << "ajouter un nouvel element cree par valeur (1)" << endl;
	Element* pE1 = l.Ajouter(1);
	cout << "ajouter un nouvel element cree par valeur (2)" << endl;
	Element* pE2 = l.Ajouter(2);
	cout << "afficher la liste" << endl;
	l.Afficher();
	cout << "inserer un Element (3) derriere un autre (1)" << endl;
	Element* pE3 = l.Ajouter(3, pE1);
	cout << "afficher la liste" << endl;
	l.Afficher();
	cout << "rechercher un element par valeur (3)" << endl;
	cout << "ajouter des nouveaux elements (3,4,5,6)" << endl;
	l.Ajouter(3);l.Ajouter(4);l.Ajouter(5);l.Ajouter(6);
	l.Afficher();

	//Le Ctor de copie est inhibé
	//Liste l2 = l;
	//L'operator= est inhibé
	//Liste l3;
	//l3 = l;
	cout << "Vider la liste" << endl;
	l.Vider();
	return 0;
	}

/* "PARTIE I bis:"
Dans cette partie, nous nous proposons de gérer l'opération Compte
La solution consistant à effectuer un parcours complet des éléments 
pour compter étant TRES inefficace, il faudra ajouter un compteur 'compte_' comme attribut
Ce compteur sera initialisé à 0 dans le Ctor, puis incrémenté lors de chaque
insertion. Il sera remis à 0 dans la méthode Vider()
La méthode Compte() sera très efficace : elle renverra simplement l'attribut compte_ 

Cf code source 'ClassList-Ibis.CPP' du ZIP

  "PARTIE II:"
Amélioration de la classe Liste pour accepter les destructions d'éléments
- L'argument de la destruction est un pointeur sur un élément existant
Le problème est que la destruction d'un élément provoque une rupture de chaîne.
Il est nécessaire de raccrocher les deux bouts.
Ce qui signifie : positionner le suivant de l'élément détruit comme nouveau suivant
de l'élément "précédant" l'élément détruit
Dans notre implémentation, il est facile de connaître le suivant mais le précédent
n'est pas prévu. => Rajoutons le de façon à obtenir une liste doublement chaînée.
- Il est pratique de fournir aussi une fonction de destruction par valeur:
L'argument sera la valeur portée par l'élément plutôt que le pointeur
Elle servira dans les cas où l'on n'a pas mémorisé le pointeur renvoyé par l'Ajout.
On fournira alors de plus une méthode "helper" chargée de trouver le pointeur correspondant
à partir d'une valeur - elle renverra le premier pointeur trouvé dont la valeur correspond.
Pour des raisons d'efficacité, il est bon de pouvoir fournir à cette méthode
le point(eur) de départ. Ainsi, elle pourra servir à trouver tous les éléments de valeur
donnée par des appels successifs sans repartir de la 'tête'.
On la nommera 'ChercherPremier' 
- On ajoutera une fonction pour vérifier l'existence d'un pointeur donné 
La méthode sera nommée 'Existe' : elle devra parcourir la liste jusqu'à trouver l'élément.

Cf code source 'ClassList-II.CPP' du ZIP


  "PARTIE III (technique avancée - facultatif)" :
Refactoring interne léger
Lors de la création de la pile et lors de son vidage
il faut ramener les trois variables membres à zero
on peut créer une méthode privée pour faire cela
	void init(){ tete_ = queue_ = NULL;	compte_=0;}
Elle sera appelée dans le Ctor et dans Vider()

Refactoring interne plus lourd
  Remarquez la similitude des méthodes Afficher, Vider et ChercherPremier.
Toutes font un parcours de la liste. Comment peut-on faire pour partager ce code ?
Le point commun est le parcours
La différence est le traitement à faire sur chacun des éléments
La solution suivante crée une méthode 'iterer' appelée par les trois précédentes.
 Elle sera chargée de parcourir la liste et de rappeler pour chaque élément
 une fonction spécialisée (nommée par exemple affiche, detruire et compare)
La technique est réalisable avec une méthode 'iter' prenant en argument un pointeur de fonction
vers les fonctions spécialisées. La contrainte est que ces fonctions devront
avoir le même prototype
Nous avons choisi le suivant :
la fonction spécialisée doit 
- connaitre l'élément : elle le reçoit par pointeur
- pouvoir arrêter le parcours : elle reçoit un booléen par référence
- connaître l'élément de comparaison : elle le reçoit par pointeur. 
  ceci est seulement utilisé dans le cas de l'appel par la méthode ChercherPremier,
  pour savoir si l'élément est de la bonne valeur.
  On mettra donc une valeur par défaut à NULL pour cet argument
Voici la déclaration du pointeur de fonction :
typedef void (Liste::*PFN)(Element *, bool&, Element* p=NULL);

Cf code source 'ClassList-III.CPP' du ZIP

  "PARTIE IV" :
  Génericité
  Pour traiter des valeurs différente de 'int', la solution normalisée est de
  passer par des Templates
  La technique est de rajouter 'template <class T>' devant chaque classe et fonction
  puis de remplacer toutes les occurences des 'int' à rendre génériques par 'T'.

  Pour tester, on créera une classe Scalaire et une classe Composee
  Elle devront être munies des opérateurs == et << qui sont utilisés dans la Liste.

Cf code source 'ClassList-IV.CPP' du ZIP

*/