/* * Created on 15 nov. 2004 * */ package arbre; import java.util.Iterator; import java.util.NoSuchElementException; /** * @author baudon * */ public class Arbre { private Arbre gauche; private Arbre droit; private T data; private Arbre pere = null; private int nIterateurs = 0; private void traiterFils(Arbre fils, String type) throws ModificationInterditeException { if (fils != null) { if (fils.premier().nIterateurs != 0) { throw new ModificationInterditeException(nIterateurs); } if (fils.pere != null) { throw new IllegalArgumentException("fils " + type + " invalide"); } fils.pere = this; } } public Arbre(Arbre gauche, Arbre droit, T data) throws ModificationInterditeException { traiterFils(gauche, "gauche"); this.gauche = gauche; traiterFils(droit, "droit"); this.droit = droit; this.data = data; } public Arbre droit() { return droit; } public Arbre gauche() { return gauche; } public Arbre pere() { return pere; } public T data() { return data; } public boolean racine() { return pere == null; } public boolean feuille() { return gauche == null && droit == null; } private Arbre premier() { if (gauche != null) { return gauche.premier(); } else if (droit != null) { return droit.premier(); } else { return this; } } private Arbre suivant() { if (pere != null && pere.gauche == this && pere.droit != null) { return pere.droit.premier(); } else { return pere; } } public void appliquer(Fonction f) { for (Arbre a = premier(); a != null && f.f(a.data); a = a.suivant()) ; } public Iterator iteration() { Iterator it = new Iterator() { Arbre suivant = Arbre.this.premier(); public boolean hasNext() { return suivant != null; } public T next() { if (suivant == null) { throw new NoSuchElementException(); } T res = suivant.data(); suivant = suivant.suivant(); if (suivant == null) { Arbre.this.premier().nIterateurs--; } return res; } public void remove() { throw new UnsupportedOperationException(); } }; premier().nIterateurs++; return it; } private void elaguer(Arbre fils) throws ModificationInterditeException { int nit = premier().nIterateurs; if (nit != 0) { throw new ModificationInterditeException(nit); } fils.pere = null; } public void elaguerDroit() throws ModificationInterditeException { elaguer(droit); droit = null; } public void elaguerGauche() throws ModificationInterditeException { elaguer(gauche); gauche = null; } }