package dataStructures;

import java.util.*;

/**
 * <p>Titulo: Uma implementaçao vectorial do Amontoado</p>
 * <p>Descrição: Esta implementaçao a caracteristica de que os amontoados
 *               podem ser facilmente descritos em vectores, dado serem
 *               representados por árvores completas</p>
 * @version 1.0
 */

public class VHeap implements Heap,Cloneable {

  private final int DELTA = 128;
  private int       nElems;
  private Object[]  theHeap;

  public VHeap() {
    theHeap = new Object[DELTA];
    nElems  = 0;
  }

  //@ requires isHeap(t);
  public VHeap(BinTree t) {
    this();
    constr(t.root(),t.left(),t.right());
  }

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

  public void constr(Object item, BinTree left, BinTree right) {

    theHeap = new Object[DELTA + left.length() + right.length()];
    theHeap[0] = item;
    nElems = 1;

    VQueue qTrees = new VQueue();
    VQueue qIndex = new VQueue();

    qTrees.enqueue(left);
    qIndex.enqueue(new Integer(1));

    qTrees.enqueue(right);
    qIndex.enqueue(new Integer(2));

    while (!qTrees.isEmpty()) {

      BinTree t = ((BinTree)(qTrees.front()));
      int i = ((Integer)(qIndex.front())).intValue();

      qTrees.dequeue();
      qIndex.dequeue();

      theHeap[i] = t.root();
      nElems = i+1;

      if (!t.left().isEmpty()) {
        qTrees.enqueue(t.left());
        qIndex.enqueue(new Integer(left(i)));
      }

      if (!t.right().isEmpty()) {
        qTrees.enqueue(t.right());
        qIndex.enqueue(new Integer(right(i)));
      }
    } //while
  }

  public boolean isEmpty() {
    return nElems==0;
  }

  private int left(int index) {
    return 2 * index + 1;
  }

  private int right(int index) {
    return 2 * index + 2;
  }

  private int father(int index) {
    return (index-1)/2;
  }

  private boolean isEmpty(int index) {
    return index >= nElems || theHeap[index] == null;
  }

  private boolean isLeaf(int index) {
    return isEmpty(left(index)) && isEmpty(right(index));
  }

  public boolean isLeaf() {
    return isLeaf(0);
  }

  public Object root() {
    return theHeap[0];
  }

  public BinTree left() {
    int i=0;
    VHeap result = new VHeap();
    result.theHeap = new Object[nElems];  // ajustar dimensão

    for(int start=2,size=1; start<=nElems; start*=2,size*=2)
      for(int j=start-1;j<start-1+size;j++) {
        if (j>=nElems)
          break;
        result.theHeap[i++] = theHeap[j];
      }

    result.nElems = i;
    return result;
  }

  public BinTree right() {
    int i=0;
    VHeap result = new VHeap();
    result.theHeap = new Object[nElems];  // ajustar dimensão

    for(int start=2,size=1; start<=nElems; start*=2,size*=2)
      for(int j=start-1+size;j<start-1+2*size;j++) {
        if (j>=nElems)
          break;
        result.theHeap[i++] = theHeap[j];
      }

    result.nElems = i;
    return result;
  }

  /**
   * A árvore é cheia?
   * @param t A árvore
   * @return TRUE se 't' é cheia, FALSE c.c.
   */
  private boolean isFull(BinTree t) {
    return Math.pow(2,t.height())-1 == t.length();
  }

  /**
   * A árvore é completa? ie, é equilibrada e todas as folhas
   * do último nível estão preenchidas da esquerda para a direita
   * @param t A árvore
   * @return TRUE se 't' é completa, FALSE c.c.
   */
  private boolean isComplete(BinTree t) {
    if (t.isEmpty())
      return true;

    BinTree l = t.left(),
            r = t.right();

    return (l.height() == r.height()   && isFull(l) && isComplete(r)) ||
           (l.height() == r.height()+1 && isFull(r) && isComplete(l));
  }

  /**
   * A subárvore dada é de prioridade?
   * @param t A árvore
   * @return TRUE se 't' é de prioridade, FALSE c.c.
   */
  private boolean isPriority(BinTree t) {
    if (t.isEmpty() || t.isLeaf())
      return true;

    BinTree l = t.left(),
            r = t.right();

    if (l.isEmpty())
      return ((Comparable)t.root()).compareTo(r.root()) >= 0;

    if (r.isEmpty())
      return ((Comparable)t.root()).compareTo(l.root()) >= 0;

    return ((Comparable)t.root()).compareTo(r.root()) >= 0 &&
           ((Comparable)t.root()).compareTo(l.root()) >= 0 &&
           isPriority(r) && isPriority(l);
  }

  private int length(int index) {
   if (isEmpty(index))
      return 0;
    return 1 + length(left(index)) + length(right(index));
  }

  public int length() {
    return length(0);
  }

  private int height(int index) {
    if (isEmpty(index))
      return 0;
    return 1 + Math.max(height(left(index)),height(right(index)));
  }

  public int height() {
    return height(0);
  }

  /** Increments the structure nElems (adds 'DELTA' new slots) */
  private void grow() {
    Object[] newHeap = new Object[theHeap.length + DELTA];

    for(int i=0;i<theHeap.length;i++)
      newHeap[i] = theHeap[i];

    theHeap = newHeap;
  }

  // Heap Public methods

  public boolean isHeap(BinTree t) {
    return isComplete(t) && isPriority(t);
  }

/*  public void insert(Comparable o) {
    if (nElems==theHeap.length)
      grow();

    int pos = nElems;  // posição provisória onde vai ser colocado 'o'
    int prevPos = father(pos);

                // enquanto for 'pai' menor, coloca esse em 'pos'
                // actualiza o pos para a nova posição e repete
                // até chegar à raiz (pos!=0) ou o 'pai' ser > que 'o'
    while (pos!=0 && o.compareTo(theHeap[prevPos]) > 0) {
      theHeap[pos] = theHeap[prevPos];
      pos = prevPos;
      prevPos = father(pos);
    }
    theHeap[pos] = o;
    nElems++;
  }
*/

  public void insert(Comparable o) {
    if (nElems==theHeap.length)
      grow();

    theHeap[nElems++] = o;
    moveUp();
  }

  private void moveUp() {
    int pos = nElems-1;
    while (pos != 0 &&
           ((Comparable)theHeap[pos]).compareTo(theHeap[father(pos)]) > 0) {
      swap(pos, father(pos));
      pos = father(pos);
    }
  }

  public void remRoot() {
    if (nElems>1) {
      theHeap[0] = theHeap[nElems-1];
      moveDown();
    }
    theHeap[--nElems] = null;
  }

  private void moveDown() {
    int maxChild, pos = 0;

    while (pos  <= father(nElems-1)) {  // posição do último nó não folha
      maxChild = left(pos);
      if (maxChild < nElems-1)
        if (((Comparable)theHeap[maxChild]).compareTo(theHeap[maxChild+1]) < 0)
          maxChild++;
      if (((Comparable)theHeap[pos]).compareTo(theHeap[maxChild]) > 0)
        break;
      swap(pos, maxChild);
      pos = maxChild;
    }
  }

  private void swap(int i, int j) {
    Object tmp = theHeap[i];
    theHeap[i] = theHeap[j];
    theHeap[j] = tmp;
  }
/*
  public void remRoot() {
    int nextPos,
        pos = 0;    // a posição actual onde vai ser posto o último elemento
    int lastPos = nElems-1;                   // a posiçao do último elemento
    nElems--;

    while (pos <= (nElems+1)/2 - 1) {  // posição do último nó não folha
      nextPos = left(pos);            // raiz da subárvore esquerda
      if (nextPos < nElems)
        if (((Comparable)theHeap[nextPos]).compareTo(theHeap[nextPos+1]) < 0)
            nextPos++;  // escolher o maior filho (neste caso, o da direita)

      if (((Comparable)theHeap[lastPos]).compareTo(theHeap[nextPos]) < 0) {
        theHeap[pos] = theHeap[nextPos];  // o filho passa p/o lugar do pai
        pos = nextPos;                // vamos repetir agora p/o filho
      }
      else    // o filho é menor que o ultimo elemento! Saimos do ciclo
        break;
    } //while()

    theHeap[pos] = theHeap[lastPos];  // mudar esse último elemento p/o local certo
    theHeap[nElems] = null;
  }
*/
  ////////////////////////////////////////////////////

  public boolean equals(BinTree t) {
    if (isEmpty())
      return t.isEmpty();
    if (t.isEmpty())
      return false;

    return t.root().equals(root()) && t.left().equals(left()) && t.right().equals(right());
  }

  public String toString() {
    if (isEmpty())
      return "[]";

    String s = "[" + theHeap[0];

    for (int i=1; i<nElems; i++)
      s += "," + (theHeap[i]==null?"[]":theHeap[i]);
    return s + "]";
  }

  public Object clone() {
    VHeap newHeap   = new VHeap();
    newHeap.theHeap = (Object[])(theHeap.clone());
    newHeap.nElems  = nElems;
    return newHeap;
  }

  // Exercicio: preencher estes métodos
  public Iterator iterator() { return null; }
  public void prefix(Visitor op) {};
  public void sufix(Visitor op) {};
  public void infix(Visitor op) {};

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

    VHeap h = new VHeap();

    h.insert(new Integer(3));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(2));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(1));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(21));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(14));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(25));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(12));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(0));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(122));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(1222));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(77));
    System.out.println(h + "isHeap? " + h.isHeap(h));
    h.insert(new Integer(4));
    System.out.println("isHeap? " + h.isHeap(h));
    System.out.println(h);

    VHeap cp = (VHeap)(h.clone());
    h.remRoot();
    System.out.println(cp);
    System.out.println(cp.left().left());
    System.out.println(cp.right());

    System.out.println(h);
    System.out.println(h.height());
    System.out.println("nElems:" + h.length() + "==?" + cp.equals(h));

    DBinTree tv = new DBinTree();
    DBinTree t1 = new DBinTree("A",tv,tv);
    DBinTree t2 = new DBinTree("B",tv,tv);
    DBinTree t3 = new DBinTree("D",tv,tv);
    DBinTree t4 = new DBinTree("C",t1,t2);
    DBinTree t5 = new DBinTree("M",t3,t4);
//    DBinTree t5 = new DBinTree("A",t4,t3);  // a non heap
//    h.constr("M",t4,t3);
    h = new VHeap(t5);
    System.out.println(h);
    System.out.println("isHeap? " + h.isHeap(h));
    System.out.println(h.left());
    System.out.println(h.right());
    System.out.println(h.height());
    System.out.println(h.length());
//    h.insert("G");
//    h.insert("P");
    System.out.println(h);
    System.out.println("isHeap? " + h.isHeap(h));

  }
}  // endClass DHeap