/** Définition d'un ensemble d'entiers implanté sous d'éléments chaînés.
  * @author	Xavier Crégut	(cregut@enseeiht.fr)
  * @version	1.7
  */
public class EnsembleChaine<E> implements Ensemble<E> {
	//@ private invariant this.premiere == null <==> this.estVide();

	protected Cellule<E> premiere;	// accès à la première cellule
	protected long nbModifications;	// nb de modifications faites sur la liste

	/** Construction d'un ensemble vide. */
	//@ ensures cardinal() == 0;
	public EnsembleChaine() {
		this.premiere = null;
		this.nbModifications = 0;
	}

	private int getNombreCellule(Cellule<E> cellule) {
		if (cellule == null) {
			return 0;
		} else {
			return 1 + getNombreCellule(cellule.suivante);
		}
	}

	@Override public int cardinal() {
		return getNombreCellule(this.premiere);
	}

	private boolean contient(E x, Cellule<E> cellule) {
		if (cellule == null) {
			return false;
		} else if (cellule.element.equals(x)) {
			return true;
		} else {
			return contient(x, cellule.suivante);
		}
	}

	@Override public boolean estVide() {
		return this.premiere == null;
	}
	
	@Override public boolean contient(E x) {
		return contient(x, this.premiere);
	}
	
	@Override public void ajouter(E x) {
		if (!contient(x)) {
			this.premiere = new Cellule<E>(x, this.premiere);
			this.nbModifications++;
		}
	}

	@Override public void supprimer(E x) {
		if (this.premiere != null) {
			if (this.premiere.element.equals(x)) {
				// Supprimer la première cellule
				this.premiere = this.premiere.suivante;
				this.nbModifications++;
			} else {
				// Chercher la cellule avant l'élément.
				Cellule<E> curseur = this.premiere;
				while (curseur.suivante != null && ! curseur.suivante.element.equals(x)) {
					curseur = curseur.suivante;
				}

				if (curseur.suivante != null) {
					curseur.suivante = curseur.suivante.suivante;
					this.nbModifications++;
				}
			}
		}
	}
	
	@Override public String toString() {
		String resultat = "{";
		if (this.premiere != null) {
			// traiter la première cellule
			resultat += " " + this.premiere.element;

			// traiter les autres cellules
			Cellule<E> curseur = this.premiere.suivante;
			while (curseur != null) {
				resultat += " " + curseur.element;
				curseur = curseur.suivante;
			}
		}
		resultat += " }";
		return resultat;
	}

}