package dataStructures;

/**
 * <p>Titulo: Uma implementaçao dinâmica da Árvore Binária de Pesquisa</p>
 * <p>Descrição: Esta implementaçao usa um nó com duas referências
                 que guardam as subárvores esquerda e direita<br>
                 Para além disso, considera-se que os valores menores
                 que a raiz estão à esquerda e os maiores à direita.</p>
 * @version 1.0
 */

public class DSearchBinTree extends DBinTree implements SearchBinTree {

  public DSearchBinTree() {
    super();
  }

  //@ requires isSearchable(t);
  public DSearchBinTree(BinTree t) {
    constr(t.root(),t.left(),t.right());
  }

  /**
   * Determina se 'o' é < que os valores da árvore
   * @param t A arvore a procurar
   * @param o O Objecto a comparar
   * @return TRUE se 'o' é menor que o mínimo da árvore, FALSE c.c.
   */
  private boolean lt(BinTree t, Comparable o) {
    if (t.isEmpty())
      return true;

    return t.left().isEmpty()? o.compareTo(t.root())<0: lt(t.left(),o);
  }

  /**
   * Determina se 'o' é >= que os valores da árvore
   * @param t A arvore a procurar
   * @param o O Objecto a comparar
   * @return TRUE se 'o' é >= que o máximo da árvore, FALSE c.c.
   */
  private boolean gt(BinTree t, Comparable o) {
    if (t.isEmpty())
      return true;

    return t.right().isEmpty()? o.compareTo(t.root())>=0: gt(t.right(),o);
  }

  public boolean isSearchable(BinTree t) {
    if (t.isEmpty())
      return true;

    if (!(t.root() instanceof Comparable))
      return false;

    return isSearchable(t.left()) &&
           isSearchable(t.right()) &&
           gt(t.left(),(Comparable)t.root()) &&
           lt(t.right(),(Comparable)t.root());
  }

  public boolean occurs(Comparable o)  {
    if (isEmpty())
      return false;

    if (root().equals(o))
      return true;

    return o.compareTo(root())<0 ? ((SearchBinTree)left()).occurs(o) : ((SearchBinTree)right()).occurs(o);
  }

  public void insert(Comparable o) {
    if (isEmpty())     // se a árvore estiver vazia, insere novo nó
      constr(o,new DSearchBinTree(),new DSearchBinTree());
    else if (o.compareTo(root())<=0)  // se 'o' <= q a raiz, ir p/esquerda
        ((SearchBinTree)left()).insert(o);
      else                            // senão, ir p/direita
        ((SearchBinTree)right()).insert(o);
  }

  /**
   * @return A referência do nó mais à direita (ie, o maior elemento)
   */
  private Object rightNode() {
    return right().isEmpty() ? root() : ((DSearchBinTree)right()).rightNode();
  }

  /**
   * Elimina o nó que estiver mais à direita (ie, o maior elemento)
   */
  private void removeRightNode() {
    if (right().isEmpty()) {
      if (left().isEmpty())
        constr(null,null,null);
      else
        constr(left().root(),left().left(),left().right());
    }
    else
      ((DSearchBinTree)right()).removeRightNode();
  }

  public void remove(Comparable o) {
    if (isEmpty())
      return;

    if (root().equals(o)) { // encontrou!
      if (left().isEmpty() && right().isEmpty())
        constr(null,null,null);
      else if (left().isEmpty())
        constr(right().root(),right().left(),right().right());
      else if (right().isEmpty())
        constr(left().root(),left().left(),left().right());
      else {
        constr(((DSearchBinTree)left()).rightNode(),left(),right());
        ((DSearchBinTree)left()).removeRightNode();
      }
    }
    else                    // (ainda) não encontrou
      if (o.compareTo(root())<=0)
        ((SearchBinTree)left()).remove(o);
      else
        ((SearchBinTree)right()).remove(o);
  }

  public Object clone() {
    DSearchBinTree result = new DSearchBinTree();

    if (!isEmpty())
      result.constr(root(), (SearchBinTree)left().clone(), (SearchBinTree)right().clone());

    return result;
  }

  /////// versoes iterativas

  public boolean occursIt(Comparable o) {
    SearchBinTree t = this;

    while (!t.isEmpty())
      if (t.root().equals(o))
        return true;
      else
        t = (SearchBinTree)(o.compareTo(t.root())<0 ? t.left() : t.right());

    return false;
  }

  public void insertIt(Comparable o) {
    SearchBinTree t = this;

    while (!t.isEmpty())
      t = (SearchBinTree)(o.compareTo(t.root())<=0 ? t.left() : t.right());

    t.constr(o,new DSearchBinTree(),new DSearchBinTree());
  }

  public void removeIt(Comparable o) {
    SearchBinTree t = this;

    while (!t.isEmpty())
      if (t.root().equals(o)) {
        if (t.left().isEmpty() && t.right().isEmpty())      // is a leaf
          t.constr(null,null,null);
        else if (t.left().isEmpty())
          t.constr(t.right().root(),t.right().left(),t.right().right());
        else if (t.right().isEmpty())
          t.constr(t.left().root(),t.left().left(),t.left().right());
        else {
          // replace with the rightmost node of the left subtree
          t.constr(((DSearchBinTree)t.left()).rightNode(),t.left(),t.right());
          ((DSearchBinTree)t.left()).removeRightNode();
        }
        break;
      }
      else
        t = (SearchBinTree)(o.compareTo(t.root())<0 ? t.left() : t.right());
  }

 //********************************************************************
  public static void main(String[] args) {

    DSearchBinTree t = new DSearchBinTree();

     t.insert(new Integer(3)); System.out.print(t.isSearchable(t)?"y":"n");
     t.insert(new Integer(4)); System.out.print(t.isSearchable(t)?"y":"n");
     BinTree tr = t.right();
     t.remove(new Integer(3)); System.out.print(t.isSearchable(t)?"y":"n");
     System.out.println("tr==t?"+(t.equals(tr)?"y":"n"));
     t.insert(new Integer(5)); System.out.print(t.isSearchable(t)?"y":"n");
     t.insert(new Integer(1)); System.out.print(t.isSearchable(t)?"y":"n");
     t.insert(new Integer(2)); System.out.print(t.isSearchable(t)?"y":"n");
     t.insert(new Integer(3)); System.out.print(t.isSearchable(t)?"y":"n");
     System.out.print(t+"--------------\n");

     DSearchBinTree tit = new DSearchBinTree();

      tit.insertIt(new Integer(3));
      tit.insertIt(new Integer(4));
      tit.removeIt(new Integer(3));
      tit.insertIt(new Integer(50));
      tit.insertIt(new Integer(1));
      tit.insertIt(new Integer(2));
      tit.insertIt(new Integer(3));
      tit.removeIt(new Integer(3));
      tit.removeIt(new Integer(4));
      System.out.print(tit+"--------------\n"); System.out.print(tit.isSearchable(tit)?"y":"n");

     DSearchBinTree t1 = (DSearchBinTree)t.clone();
     System.out.println("t1==t?"+(t.equals(t1)?"y":"n"));

     t.remove(new Integer(5));
     t.remove(new Integer(3));
     t.remove(new Integer(20));

     System.out.print(t+"--------------\n");
     System.out.print(t1);

    System.out.print(t.occurs(new Integer(8))?"y":"n");
    System.out.print(t.occurs(new Integer(3))?"y":"n");
    System.out.print(t.occurs(new Integer(1))?"y":"n");
    System.out.print(t.occurs(new Integer(2))?"y":"n");
    System.out.print(t.occursIt(new Integer(8))?"It:y":"It:n");
    System.out.print(t.occursIt(new Integer(3))?"y":"n");
    System.out.print(t.occursIt(new Integer(1))?"y":"n");
    System.out.print(t.occursIt(new Integer(2))?"y":"n");
    System.out.print(t.length());
    System.out.print(t.isSearchable(t)?"y":"n");

    DBinTree tv = new DBinTree();
    DBinTree t1a = new DBinTree("M",tv,tv);
    DBinTree t2 = new DBinTree("D",tv,tv);
    DBinTree t3 = new DBinTree("B",tv,tv);
    DBinTree t4 = new DBinTree("I",tv,t1a);
    DBinTree t5 = new DBinTree("C",t3,t2);
    DBinTree t6 = new DBinTree("F",t5,t4);
    System.out.print(t.isSearchable(t6)?"y":"n");

    DSearchBinTree a = new DSearchBinTree(t6);
    System.out.println(a.isSearchable(a)?"y":"n");
    System.out.print(a);
  }

}  // endClass DBinTree