package fr.eisti.arbre;

import java.util.*;
import java.io.*;

/**
 * classe Arbre
 * représente une arbre binaire de recherche
 * - les valeurs de l'arbre doivent être comparables entre elles
 * - l'arbre et ses valeurs sont sérialisables
 * - un arbre a une valeur et un sous-arbre droit et un sous-arbre-gauche
 * - toutes les valeurs du sous-arbre droit sont plus grandes que la valeur de la racine
 * - toutes les valeurs du sous-arbre gauche sont plus petites que la valeur de la racine
 * - on peut parcourir un arbre de la plus petite à la plus grande valeur
 *
 * @author Matthias Colin
 * @version 1.0 (28/06/2011)
 */
 public class Arbre<V extends Comparable<V> & Serializable> 
		implements Iterable<V>, Serializable {
	
	// valeur mémorisée dans le noeud racine de l'arbre
	// ne peut pas être vide (!= null)
	private V valeur;
	
	// sous-arbre gauche éventuellement vide (==null)
	private Arbre<V> filsGauche;
	
	// sous-arbre droit éventuellement vide (==null)
	private Arbre<V> filsDroit;
	
	/**
	 * constructeur d'un arbre composé uniquement de sa racine
	 * @param valeur valeur de la racine
	 * @throws NullPointerException si la valeur est vide (==null)
	 */
	public Arbre(V valeur) {
		if (valeur == null) {
			throw new NullPointerException("Un arbre ne peut contenir de valeurs nulles");
		}
		this.valeur = valeur;
		// this.filsGauche = null; // implicite
		// this.filsDroit = null;  // implicite
	}
	
	/**
	 * constructeur d'un arbre à partir d'une collection d'élément (non demandé)
	 * @param collection la collection des valeurs de l'ABR à créer
	 * @throws NullPointerException si la collection est vide ou si une valeur est vide
	 */
	public Arbre(Collection<? extends V> collection) {
		if (collection == null || collection.isEmpty()) {
			throw new NullPointerException("Un arbre ne peut contenir de valeurs nulles");
		}
		Iterator<? extends V> it = collection.iterator();
		// création de l'arbre avec la 1ère valeur
		V valeur = it.next();
		if (valeur == null) {
			throw new NullPointerException("Un arbre ne peut contenir de valeurs nulles");
		}
		this.valeur = valeur;
		// ajout des autres valeurs dans l'ABR
		while (it.hasNext()) {
			this.ajouter(it.next());
		}
	}
	
	public Arbre<V> getFilsDroit() {
		return filsDroit;
	}
	
	// Pour une meilleure encapsulation
	// mais laisser absolument privée pour éviter
	// la construction d'ABR mal formé.
	// Tous les éléments de sousArbre doivent être 
	// plus grands que la valeur courante
	private void setFilsDroit(Arbre<V> sousArbre) {
		filsDroit = sousArbre;
	}
	
	public Arbre<V> getFilsGauche() {
		return filsGauche;
	}
	
	// Tous les éléments de sousArbre doivent être 
	// plus petits que la valeur courante
	private void setFilsGauche(Arbre<V> sousArbre) {
		filsGauche = sousArbre;
	}
	
	public V getValeur() {
		return valeur;
	}
	
	public boolean estFeuille() {
		return (!aFilsGauche() && !aFilsDroit());
	}
	
	public boolean aFilsDroit() {
		return (getFilsDroit() != null);
	}
	
	public boolean aFilsGauche() {
		return (getFilsGauche() != null);
	}
	
	/**
	 * ajoute une valeur dans l'arbre binaire
	 * @param valeurAjoutee valeur à ajoter dans l'arbre
	 * @return true si la valeur a bien été ajoutée, false en si la
	 * valeur était déjà présente
	 * @throws NullPointerException si la valeur ou le comparateur est vide (==null)
	 */
	public boolean ajouter(V valeurAjoutee) {
		if (valeurAjoutee == null) {
			throw new NullPointerException("Un arbre ne peut contenir de valeurs nulles");
		}
		// comparaison de la valeur à ajouter avec la valeur courante
		// pour guider la direction de recherche d'emplacement
		int cmp = this.valeur.compareTo(valeurAjoutee);
		if (cmp == 0) { // valeurs identiques en terme de kilométrage et type de moteur
			return false;
		} else if (cmp <0) { // valeur courante plus petite que valeur ajoutée
			// insertion à droite
			if (aFilsDroit()) {
				return getFilsDroit().ajouter(valeurAjoutee);
			} else {
				setFilsDroit(new Arbre<V>(valeurAjoutee));
				return true;
			}
		} else { // valeur courante plus grande que valeur ajoutée
			// insertion à gauche
			if (aFilsGauche()) {
				return getFilsGauche().ajouter(valeurAjoutee);
			} else {
				setFilsGauche(new Arbre<V>(valeurAjoutee));
				return true;
			}
		}
	}
	
	// on peut ajouter des éléments qui héritent de V
	public boolean ajouter(Arbre<? extends V> arbre) {
		// TODO
		return false;
	}
	
	// on peut ajouter des V dans un arbre défini sur des valeurs plus générales
	public boolean extraire(Arbre<? super V> arbre, V seuil) {
		// TODO
		return false;
	}
	
	/**
	 * recherche une valeur dans l'arbre binaire
	 * @param valeurCherche valeur à rechercher dans l'arbre
	 * @return true si la valeur est bien présente
	 */
	public boolean contains(V valeurCherche) {
		if (valeurCherche == null) {
			return false;
		}
		// comparaison de la valeur recherchée avec la valeur courante
		// pour guider la direction de recherche
		int cmp = this.valeur.compareTo(valeurCherche);
		if (cmp == 0) { // valeurs identiques en terme de kilométrage et type de moteur
			return true;
		} else if (cmp <0) { // valeur courante plus petite que valeur recherchée
			// recherche à droite
			if (aFilsDroit()) {
				return getFilsDroit().contains(valeurCherche);
			} else {
				return false;
			}
		} else { // valeur courante plus grande que valeur recherchée
			// recherche à gauche
			if (aFilsGauche()) {
				return getFilsGauche().contains(valeurCherche);
			} else {
				return false;
			}
		}
	}
	
	// NB : non demandé à l'exam
	public V min() {
		if (aFilsGauche()) {
			return getFilsGauche().min();
		} else {
			return valeur;
		}
	}
	
	// NB : non demandé à l'exam
	public V max() {
		if (aFilsDroit()) {
			return getFilsDroit().max();
		} else {
			return valeur;
		}
	}
	
	@Override
	public Iterator<V> iterator() {
		return new IterateurOrdonneArbre<V>(this);
	}
	
	public void sauver(String filename) throws SauvegardeArbreException {
		try {
			ObjectOutputStream oos = new ObjectOutputStream(
					new FileOutputStream(filename));
			oos.writeObject(this);
			oos.close();
		} catch (IOException e) {
			throw new SauvegardeArbreException(e);
		}
	}
}