#ifndef __LISTE_CHAINEE_HXX__
#define __LISTE_CHAINEE_HXX__


// Classe Cellule
//
// Represente la cellule d'une liste chainee
//
// Parametree par le type d'element que contient la liste chainee
//
//
// Cette classe etant destinee a n'etre manipulee que par les classes
// ListeChainee et Iterateur qui seront ses amis, tous ses membres
// sont private
//
// En particulier, Le constructeur est private de maniere a eviter 
// que l'utilisateur ne puisse construire ses propres cellules
//
// 

template <typename T>
class ListeChainee;

template <typename T>
class Iterateur;

#include <utility>
#include <iostream>
using namespace std;


template <typename T>
class Cellule
{
  private:
    Cellule(const    T&element,
            Cellule<T> *precedente=0,
            Cellule<T> *suivante=0) :
      prec(precedente),
      suiv(suivante),
      item(element)
    {};

  // Utilise le constructeur par defaut de la classe T
  // pour initialiser l'attribut item

    Cellule(Cellule<T> *precedente=0,
            Cellule<T> *suivante=0) :
      prec(precedente),
      suiv(suivante)
    {};


  private:

    Cellule<T> *prec;
    Cellule<T> *suiv;
    T           item;

  template <typename T>
  friend class ListeChainee;

  template <typename T>
  friend class Iterateur;
};

template <typename T>
class ListeChainee
{
  public:

  // Constructeur :
  //
  // cree l'element de tete et le boucle sur lui meme

    ListeChainee(void)
    {
      tete=new Cellule<T>;
      tete->prec=tete;
      tete->suiv=tete;
    }

  // le nom des methodes suivantes et donne d'apres l'etude de la librairie
  // standard du C++

  // push_front
  // 
  // ajoute un element en tete

    void push_front(const T& element)
    {
      ajouterAvantCellule(tete->suiv,element);
    }

  // push_back
  //
  // ajoute un element en fin de liste

    void push_back(const T& element)
    {
      ajouterAvantCellule(tete,element);
    }
    
  // front
  //
  // donne acces a l'element en tete de liste
  //
  // fournie en versions const et non const

    const T& front (void) const
    {
      return tete->suiv->item;
    }

    T& front (void)
    {
      return tete->suiv->item;
    }

  // back
  //
  // donne acces a l'element en fin de liste
  //
  // fournie en versions const et non const

    const T& back(void) const
    {
      return tete->prec->item;
    }

    T& back (void)
    {
      return tete->prec->item;
    }

  // pop_front
  //
  // suppression de l'element en tete de liste

    void pop_front(void)
    {
      supprimerCellule(tete->suiv);
    }

  // pop_back
  //
  // suppression de l'element en fin de liste

    void pop_back(void)
    {
      supprimerCellule(tete->prec);
    }

  // taille
  // 
  // indique le nombre d'elements

    int taille(void) const
    {
      return nbElements;
    }

  template <typename T>
  friend class Iterateur;

  // begin()
  // renvoie un iterateur sur le debut
  // versions const et non const


  const Iterateur<T> begin(void) const
  {
    return Iterateur<T>(*this,tete->suiv);
  }

  Iterateur<T> begin(void)
  {
    return Iterateur<T>(*this,tete->suiv);
  }

  // end()
  // renvoie un iterateur juste apres la fin => ie sur l'element bateau

  const Iterateur<T> end(void) const
  {
    return Iterateur<T>(*this,tete);
  }
  
  Iterateur<T> end(void)
  {
    return Iterateur<T>(*this,tete);
  }

  // Insertion
  // ajoute un element avant la position specifie par l'iterateur
  
  void insert(const Iterateur<T> &position, const T&element)
  {
    ajouterAvantCellule(position.pos,element);
  }
  
  // Ne pas oublier le destructeur !!!
  
  ~ListeChainee(void)
  {
    Cellule<T> *p;
    Cellule<T> *q;
    
    p=tete->suiv;
    while (p != tete)
    {
      q=p->suiv;
      delete p;
      p=q;
    }
    
    delete tete;
    
    
  }
  
  
  

  private:
    Cellule<T> *tete;
    int         nbElements;

  // Methode utilitaire :
  // ajouterAvantCellule cree une nouvelle cellule avec 
  // l'element indique
  // puis l'insere avant la position indiquee

  void ajouterAvantCellule(Cellule<T> *position,
                           const T&    element)
  {
    // Cree la nouvelle cellule

    Cellule<T> *nouvelle = new Cellule<T>(element,
                                          position->prec,
                                          position);

    position -> prec -> suiv = nouvelle;
    position -> prec = nouvelle;

    nbElements ++ ;
  }

  // Methode utilitaire

  void supprimerCellule(Cellule<T> *position)
  {
    if (position != tete)
    {
      position -> prec -> suiv = position -> suiv;
      position -> suiv -> prec = position -> prec;
      delete position;
      nbElements -- ;
    }
  }

  friend ostream &operator<< <> (ostream &a, const ListeChainee<T> &l);

};


template <typename T>
ostream &operator<<  (ostream &a, const ListeChainee<T> &l)
{
  Iterateur<T> debut=l.begin();
  Iterateur<T> fin=l.end();

  while (debut != fin)
  {
    a << (*debut) << endl;
    ++debut;
  }
  return a;
}

template <typename T>
class Iterateur
{

  public:
    
    Iterateur(const ListeChainee<T> &sr) :
      source(sr),
      pos(sr.tete)
    {};

  // Operateur de dereferencement
  // Renvoie l'element pointe par l'iterateur
  // fourni en version const et non const

    const T& operator*(void) const
    {
      return pos->item;
    }
  
    T& operator*(void)
    {
      return pos->item;
    }

  // Avancee de l'iterateur

    void avance(void)
    {
      pos = pos -> suiv;
    }

  // La meme chose mais version operateur

    Iterateur<T>& operator++(void)
    {
      pos = pos -> suiv;
      return *this;
    }

    const Iterateur<T> operator++(int)
    {
      Iterateur<T> temp(*this);
      pos = pos -> suiv;
      return temp;
    }

    Iterateur<T>& operator--(void)
    {
      pos = pos ->prec ;
      return *this;
    }

    const Iterateur<T> operator--(int)
    {
      Iterateur<T> temp(*this);
      pos = pos -> prec;
      return temp;
    }
    

  // Reculade de l'iterateur
    
    void recule(void)
    {
      pos = pos -> prec;
    }


  private:
    const ListeChainee<T> &source;
    Cellule<T>            *pos;

    template <typename T>
    friend class ListeChainee;

  
    Iterateur(const ListeChainee<T> &sr,
              Cellule<T>            *position) :
      source(sr),
      pos(position)
    {};
  
  friend bool operator== <> (const Iterateur<T> &lhs, const Iterateur<T> &rhs);
};

template <typename T>
bool operator==(const Iterateur<T> &lhs, const Iterateur<T> &rhs)
{
  return (lhs.pos == rhs.pos);
}


#endif