package tpgenericite.abr;

/**
 * Arbre binaire de recherche. Les éléments de l'arbre ont un ordre naturel.
 * Les éléments sont rangés dans l'arbre selon cet ordre ordre naturel.
 * Un arbre ne contient pas de valeur null. Si la racine
 * est null l'arbre est considéré comme étant vide.
 * @version 1.0
 * @param <E> type des valeurs contenues dans l'arbre.
 */
public class ArbreBinaireRecherche<E extends Comparable<? super E>> {
  private Noeud<E> racine;

  /**
   * Crée un arbre vide (la racine contient la valeur null).
   */
  public ArbreBinaireRecherche() {
  }

  /**
   * Crée un arbre qui ne contient que la valeur elt.
   * @param elt la valeur unique que contient l'arbre.
   */
  public ArbreBinaireRecherche(E elt) {
    if (elt == null) {
      throw new IllegalArgumentException("Un ABR ne contient que des élements non null");
    }
    racine = new Noeud<>(elt);
  }

  /**
   * Insère un nouvel élément dans l'arbre.
   * Voir aussi variante dans la méthode inserer2.
   * @param elt le nouvel élément qu'on insère. Il ne doit pas être null.
   */
  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 l'élément elt dans l'arbre de racine n.
   * @param elt l'élément à insérer.
   * @param n noeud racine de l'arbre dans lequel on insère. 
   * Pré-condition : le noeud n n'est pas <code>null</code>.
   */
  private void insererRecursif(E elt, Noeud<E> n) {
    /* 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.
     */
    if (n.valeur.compareTo(elt) < 0)
      if (n.nd == null)
        n.nd = new Noeud<>(elt);
      else
        insererRecursif(elt, n.nd);
    else
      if (n.ng == null)
        n.ng = new Noeud<>(elt);
      else
        insererRecursif(elt, n.ng);
  }
  
  /**
   * Variante 2 de inserer. Code plus simple mais un peu plus difficile à comprendre.
   * Insère un nouvel élément dans l'arbre.
   * @param elt E le nouvel élément qu'on insère.
   */
  public void inserer2(E elt) {
    racine = insererRecursif2(elt, racine);
  }

  /**
   * Insère l'élément elt dans l'arbre de racine n.
   * La différence essentielle avec insererRecursif : retourne la racine de
   * l'arbre après l'insertion, ce qui permet de pouvoir avoir une valeur null
   * dans le paramètre n.
   * @param elt élément à insérer.
   * @param n noeud racine de l'arbre dans lequel on insère.
   * @return la racine de  l'arbre après insertion.
   */
  private Noeud<E> insererRecursif2(E elt, Noeud<E> n) {
    if (n == null) {
      return new Noeud<>(elt);
    }
    if (n.valeur.compareTo(elt) < 0)
      n.nd = insererRecursif2(elt, n.nd);
    else
      n.ng = insererRecursif2(elt, n.ng);
    return n;
  } 

  /**
   * Indique si l'arbre contient un élément égal (au sens de Comparable)
   * à l'élément passé en paramètre.
   * @param elt l'élément à rechercher.
   * @return <code>true</code> si l'arbre contient l'élément, 
   * <code>false</code> sinon.
   */
  public boolean contient(Object elt) {
    try {
      E e = (E) elt;
      return contientRecursif(e, racine);
    } catch (ClassCastException ex) {
      return false;
    }
  }

  private boolean contientRecursif(E elt, Noeud<E> n) {
    if (n == null) {
      return false;
    }
    int v = elt.compareTo(n.valeur);
    if (v == 0) {
      return true;
    }
    else if (v > 0) {
      return contientRecursif(elt, n.nd);
    }
    else {
      return contientRecursif(elt, n.ng);
    }
  }

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

  private void afficherInfixe(Noeud<E> noeud) {
    if (noeud != null) {
      afficherInfixe(noeud.ng);
      System.out.println(noeud.valeur);
      afficherInfixe(noeud.nd);
    }
  }

  @Override
  public String toString() {
    return "Abr{" + "racine=" + 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.
   */
  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);
    }

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