import java.util.*;

public class ArbreImp implements Arbre {
    
    private Object data;
    private List fils;
    private ArbreImp pere;

    public ArbreImp(Object data) {
	this.data = data;
	fils = new ArrayList();
	pere = null;
    }

    public ArbreImp(Object data, ArbreImp [] fils) {
	this(data);
	for (int i = 0; i < fils.length; i++) {
	    ajouterFils(fils[i]);
	}
    }

    public void ajouterFils(ArbreImp f) {
	if (f.pere != null) { 
	    throw new IllegalArgumentException("Un arbre ne peut etre qu'une fois sous-arbre");
	}
        fils.add(f);
	f.pere = this;
    }

    public ArbreImp pere() {
	return pere;
    }

    public Iterator fils() {
	return fils.iterator();
    }

    public ArbreImp fils(int i) {
	return (ArbreImp) fils.get(i);
    }
    
    public int nfils() {
	return fils.size();
    }
		    
    public Object data() {
	return data;
    }

    public void changerData(Object data) {
	this.data = data;
    }
    
    public boolean estUneFeuille() {
	return fils.isEmpty();
    }

    private static int ordre(Iterator arbres) {
	int ordre = 0;

	for (; arbres.hasNext();) {
	    ordre += 1 + ordre(((ArbreImp) arbres.next()).fils());
	}
	return ordre;
    }

    public int ordre() {
	return 1 + ordre(fils.iterator());
    }

    private int hauteurMaxFils() {
	int hm = 0;
	for (Iterator i = fils(); i.hasNext();) {
	    hm = Math.max(hm, ((ArbreImp) i.next()).hauteur());
	}
	return hm;
    }

    public int hauteur() {
	return estUneFeuille() ? 0 : 1 + hauteurMaxFils();
    }

    public void parcours(Action a) {
	a.f(data);
	for (Iterator i = fils.iterator(); i.hasNext();) {
	    ((ArbreImp) i.next()).parcours(a);
	}
    }
	
    public int ordre2() {
	final int [] ordre = new int[1];
	parcours(new Action () {
		public void f(Object o) {
		    ordre[0] += 1;
		}
	    });
	return ordre[0];
    }

    public String toString() {
	StringBuffer sb = new StringBuffer(data.toString());
	Iterator i = fils.iterator();
	String fin = "";

	if (i.hasNext()) {
	    sb.append(" (");
	    sb.append(i.next().toString()); 
	    fin = ")";
	}
	while (i.hasNext()) {
	    sb.append(" ");
	    sb.append(((ArbreImp) i.next()).toString());
	}
	sb.append(fin);
	return sb.toString();
    }

    public static void main(String [] args) {
	char c = 'a';
	ArbreImp a = new ArbreImp(new Character(c++));
	System.out.println(a);

	for (int i = 0; i < 3; i++) {
	    ArbreImp fils = new ArbreImp(new Character(c++));
	    a.ajouterFils(fils);
	    for (int j = 0; j < 3; j++) {
		ArbreImp petitfils = new ArbreImp(new Character(c++));
		fils.ajouterFils(petitfils);
	    }
	}
	System.out.println(a);
	System.out.println("ordre : " + a.ordre());
	System.out.println("ordre2 : " + a.ordre2());
    }
}