package tpgenericite.abr;

import java.util.Comparator;

/**
 * Arbre binaire de recherche. 
 * Les éléments sont rangés dans l'arbre selon leur ordre ordre naturel
 * ou selon l'ordre donné par un comparateur.
 * @version 1.1
 * @param <E> type des valeurs contenues dans l'arbre.
 */
public class ArbreBinaireRecherche<E> {
  private Noeud<E> racine;
  /**
   * Comparateur utilisé pour comparer les éléments.
   * null si l'arbre utilise l'ordre naturel sur E (Comparable).
   */
  private Comparator<? super E> comparator;

  public ArbreBinaireRecherche(Comparator<? super E> comparator, E e) {
    this.comparator = comparator;
    racine = new Noeud<E>(e);
  }

  public ArbreBinaireRecherche(E e) {
    this(null, e);
  }

  public ArbreBinaireRecherche(Comparator<? super E> comparator) {
    this.comparator = comparator;
  }

  public ArbreBinaireRecherche() {
  }

  /**
   * Insère un nouvel élément dans l'arbre.
   * @param elt E le nouvel élément qu'on insère.
   */
  public void inserer(E elt) {
    if (elt == null) {
      throw new IllegalArgumentException("Un ABR ne contient que des élements non null");
    }
    if (racine == null)
      racine = new Noeud<>(elt);
    else
      insererRecursif(elt, racine);
  }

  /**
   * Insère un élément à partir d'un noeud.
   * Si l'élément est < à la valeur du noeud, il est inséré dans l'arborescence
   * du sous-noeud gauche, sinon il est inséré à partir du sous-noeud droit.
   * Pré-condition : le noeud n'est pas <code>null</code>.
   * @param elt E l'élément à insérer
   * @param n Noeud le noeud dans l'arborescence duquel elt sera inséré.
   */
  private void insererRecursif(E elt, Noeud<E> n) {
    if (compare(n.getValeur(), elt) < 0)
      if (n.getNd() == null)
        n.setNd(new Noeud<> (elt));
      else
        insererRecursif(elt, n.getNd());
    else
      if (n.getNg() == null)
	n.setNg(new Noeud<>(elt));
      else
	insererRecursif(elt, n.getNg());
  }

  /**
   * Indique si l'arbre contient un élément égal (au sens de equals)
   * à l'élément passé en paramètre.
   * @param elt l'élément à rechercher. De type Object pour éviter les restrictions
   * pour ArbreBinaireRecherche<? extends UnType> (voir cours généricité).
   * @return <code>true</code> si l'arbre contient l'élément, 
   * <code>false</code> sinon.
   * @throws ClassCastException si elt ne peut être comparé aux 
   * éléments actuellement dans l'arbre.
   */
  public boolean contient(Object elt) {
	// A cause de l'effacement de type on ne peut pas tester "elt instanceof E".
	// On peut quand même éviter le crash si on passe un elt différent de E
	// en attrapant ClassCastException dans "contient" (le catch retourne alors false).
    return contientRecursif(elt, racine);
  }

  private boolean contientRecursif(Object elt, Noeud<E> n) {
    if (n == null)
      return false;
    int v = compare(elt, n.getValeur());
    if (v == 0)
      return true;
    else if (v > 0)
      return contientRecursif(elt, n.getNd());
    else
      return contientRecursif(elt, n.getNg());
  }

  /**
   * Compare 2 éléments de type E. Utilise l'ordre naturel sur E (Comparable)
   * ou un comparateur, suivant le cas.
   * @param e1 E
   * @param e2 E
   * @return nombre entier positif si e1 est plus grand, nombre entier négatif si e2 est plus grand et 0
   * si e1 et e2 sont égaux au sens de equals.
   */
  private int compare(Object e1, E e2) {
    return comparator == null ? ((Comparable<? super E>) e1).compareTo(e2)
                            : comparator.compare((E)e1, e2);
}


  public void afficheTesElements() {
    System.out.println("Contenu de l'arbre : ");
    afficheInfixe(racine);
  }

  private void afficheInfixe(Noeud<E> noeud) {
    if (noeud != null) {
      afficheInfixe(noeud.getNg());
      System.out.println(noeud.getValeur());
      afficheInfixe(noeud.getNd());
    }
  }

  @Override
  public String toString() {
    return "[ArbreBinaireRecherche: Comparateur=" + comparator + "; données=" + racine;
  }


  /**
   * Noeud d'un arbre binaire.
   * Classe interne static car elle ne possède aucune référence vers une variable d'instance de
   * la classe englobante.
   * @version 1.0
   */
  private static class Noeud<E> {
    /**
     * Valeur du noeud.
     */
    private E valeur;
    /**
     * Noeuds gauche (ng) et droit (nd) de l'arbre.
     * nd contient les éléments supérieurs à la valeur du noeud.
     * ng contient les éléments inférieurs ou égaux à la valeur du noeud.
     */
    private Noeud<E> nd, ng;

    public Noeud(E valeur, Noeud<E> noeud1, Noeud<E> noeud2) {
      this.valeur = valeur;
      this.nd = noeud1;
      this.ng = noeud2;
    }

    public Noeud(E valeur) {
      this(valeur, null, null);
    }

    public E getValeur() {
      return valeur;
    }

    public Noeud<E> getNd() {
      return nd;
    }

    public Noeud<E> getNg() {
      return ng;
    }

    public void setNd(Noeud<E> noeud) {
      this.nd = noeud;
    }

    public void setNg(Noeud<E> noeud) {
      this.ng = noeud;
    }

    @Override
    public String toString() {
      return "[Noeud:valeur=" + valeur +"; ng=" + ng + "; nd=" + nd + "]";
    }

  } // Fin NoeudE>

}