package dataStructures;

import java.util.*;

/**
 * <p>Titulo: Uma implementaçao dinâmica da Árvore Binária</p>
 * <p>Descrição: Esta implementaçao usa um nó com duas referências
                 que guardam as subárvores esquerda e direita</p>
 * @version 1.0
 */

public class DBinTree implements BinTree,Cloneable {

  private DBinTree   leftTree, rightTree;
  private Object     infoTree;

  public DBinTree() {
    infoTree = null;
    leftTree = rightTree = null;
  }

  public DBinTree(Object o, BinTree left, BinTree right) {
    constr(o, left, right);
  }

  public BinTree empty() {
    return new DBinTree();
  }

  public void constr(Object item, BinTree left, BinTree right) {
    infoTree  = item;
    leftTree  = (DBinTree)left;
    rightTree = (DBinTree)right;
  }

  public boolean isEmpty() {
    return infoTree == null;
  }

  public Object root() {
    return infoTree;
  }

  public BinTree left() {
    return leftTree;
  }

  public BinTree right() {
    return rightTree;
  }

  public int length() {
    if (isEmpty())
      return 0;
    return 1 + left().length() + right().length();
  }

  public int height() {
    if (isEmpty())
      return 0;

    return 1 + Math.max(right().height(), left().height());
  }

  public boolean isLeaf() {
    if (isEmpty())
      return false;
    return left().isEmpty() && right().isEmpty();
  }

  public boolean equals(BinTree t) {
    if (isEmpty() && t.isEmpty())
      return true;
    if (isEmpty() || t.isEmpty())
      return false;
    return root().equals(t.root()) && left().equals(t.left()) && right().equals(t.right());
  }

  public void prefix(Visitor op) {
    if (!isEmpty()) {
      op.visit(root());
      left().prefix(op);
      right().prefix(op);
    }
  }

  public void prefixIterative(Visitor op) { // an example of iterative solution
    if (isEmpty())
      return;

    VStack stack = new VStack();
    stack.push(this);

    while (!stack.isEmpty()) {
      DBinTree actual = (DBinTree)stack.top();
      stack.pop();

      op.visit(actual.root());
      if (!actual.right().isEmpty())
        stack.push(actual.right());
      if (!actual.left().isEmpty())
        stack.push(actual.left());
    }
  }

  public void breathIterative(Visitor op) {
    if (isEmpty())
      return;

    VQueue queue = new VQueue();
    queue.enqueue(this);

    while (!queue.isEmpty()) {
      DBinTree actual = (DBinTree)queue.front();
      queue.dequeue();

      op.visit(actual.root());
      if (!actual.left().isEmpty())
        queue.enqueue(actual.left());
      if (!actual.right().isEmpty())
        queue.enqueue(actual.right());
    }
  }

  public void infix(Visitor op) {
    if (!isEmpty()) {
      left().prefix(op);
      op.visit(root());
      right().prefix(op);
    }
  }

  public void sufix(Visitor op) {
    if (!isEmpty()) {
      left().prefix(op);
      right().prefix(op);
      op.visit(root());
    }
  }

  public Iterator iterator() {
    return new BinTreeIterator(this);
  }

  public String toString() {
    return isEmpty() ? "[]" : makeTree(0, this);
  }

  private String makeTree(int level, DBinTree T) {
    if (T.isEmpty())                   // base da recursão
      return mark(level) + "[]\n";
    if (T.isLeaf())                    // base da recursão
      return mark(level) + T.root() + "\n";

         // passo da recursão
    return mark(level) + T.root() + "\n" + makeTree(level+1,(DBinTree)T.left()) + makeTree(level+1,(DBinTree)T.right());
  }

  private String mark(int level) {  // identar o símbolo '|'
    String s="";

    for (int i=0;i<level-1;i++)
      s += " ";
    return s+ ((level>0)?"|":"");
  }

  public Object clone() {
    if (isEmpty())
      return new DBinTree();
    return new DBinTree(root(), (DBinTree)(left().clone()), (DBinTree)(right().clone()));
  }

  /* Tipo Iterator  */

  private class BinTreeIterator implements Iterator {
    private VQueue qNodes;
    private Object actualObject;

    private BinTreeIterator(DBinTree t) {
      qNodes = new VQueue();
      qNodes.enqueue(t);
      actualObject = null;
    }

    public boolean hasNext() {
      return !qNodes.isEmpty();
    };

    public Object next() {
      if (qNodes.isEmpty()) {
        actualObject = null;
        return null;
      }

      DBinTree t = (DBinTree)(qNodes.front());

      if (!t.leftTree.isEmpty())
        qNodes.enqueue(t.leftTree);

      if (!t.rightTree.isEmpty())
        qNodes.enqueue(t.rightTree);

      qNodes.dequeue();
      actualObject = t.infoTree;
      return actualObject;
    };

    public void remove() {
      throw new UnsupportedOperationException();
    }

  } // endLocalClass BinTreeIterator

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

    DBinTree tv = new DBinTree();
    DBinTree t1 = new DBinTree("F",tv,tv);
    DBinTree t2 = new DBinTree("E",tv,tv);
    DBinTree t3 = new DBinTree("D",tv,tv);
    DBinTree t4 = new DBinTree("C",tv,t1);
    DBinTree t5 = new DBinTree("B",t3,t2);
    DBinTree t6 = new DBinTree("A",t5,t4);

    System.out.println(t6);
    System.out.println("length " + t6.length() + " height " + t6.height());
    System.out.println(t1.isLeaf() + ":" + t6.isLeaf() + ":" + t1.equals(t6) + t1.equals(t1));

    Concat cc = new Concat();
    t6.prefix(cc);
    System.out.println(cc.result());

    cc.reset(); t6.prefixIterative(cc);
    System.out.println(cc.result());

    cc.reset(); t6.breathIterative(cc);
    System.out.println(cc.result());

/*
    cc.reset();    t6.infix(cc);
    System.out.println(cc.getResult());
    cc.reset();    t6.sufix(cc);
    System.out.println(cc.getResult());*/

    Iterator it = t6.iterator();
    while (it.hasNext())
      System.out.print(it.next() + " / ");

  }

}  // endClass DBinTree

//****** exemplo *********

class Concat implements Visitor {

  private String result = "";

  public void visit(Object info) {
    result += (String)info;
  }

  public void reset() {
    result = "";
  }

  public Object result() {
    return result;
  }
}