import java.util.Iterator;

/**
 * <p>Clase para árboles binarios ordenados. Los árboles son genéricos, pero
 * acotados a la interfaz {@link Comparable}.</p>
 *
 * <p>Un árbol instancia de esta clase siempre cumple que:</p>
 * <ul>
 *   <li>Cualquier elemento en el árbol es mayor o igual que todos sus
 *       descendientes por la izquierda.</li>
 *   <li>Cualquier elemento en el árbol es menor o igual que todos sus
 *       descendientes por la derecha.</li>
 * </ul>
 */
public class ArbolBinarioOrdenado<T extends Comparable<T>>
   extends ArbolBinario<T> {

   /* Clase privada para iteradores de árboles binarios ordenados. */
   private class Iterador implements Iterator<T> {

      /* Pila para emular la pila de ejecución. */
      private Pila<ArbolBinario<T>.Vertice> pila;

      /* Construye un iterador con el vértice recibido. */
      public Iterador(ArbolBinario<T>.Vertice vertice) {
         pila = new Pila<ArbolBinario<T>.Vertice>();
         meteIzq(vertice);
      }

      /*Metodo auxiliar para Iterador*/
      private void meteIzq(ArbolBinario<T>.Vertice vertice) {
         if(vertice == null)
            return;
         pila.mete(vertice);
         meteIzq(vertice.izquierdo);
      }

      /* Nos dice si hay un siguiente elemento. */
      @Override public boolean hasNext() {
         return pila.esVacia() != true;
      }

      /* Regresa el siguiente elemento del árbol en orden. */
      @Override public T next() {
         if(hasNext()) {
            ArbolBinario<T>.Vertice vertice = pila.saca();
            meteIzq(vertice.derecho);
            return vertice.elemento;
         } else
            return null;
      }

      /* No lo implementamos: siempre lanza una excepción. */
      @Override public void remove() {
         throw new UnsupportedOperationException();
      }
   }

   /**
    * Constructor sin parámetros. Sencillamente ejecuta el constructor sin
    * parámetros de {@link ArbolBinario}.
    */
   public ArbolBinarioOrdenado() {
      super();
   }

   /**
    * Construye un árbol binario ordenado a partir de un árbol binario. El
    * árbol binario ordenado tiene los mismos elementos que el árbol recibido,
    * pero ordenados.
    * @param arbol el árbol binario a partir del cuál creamos el
    *        árbol binario ordenado.
    */
   public ArbolBinarioOrdenado(ArbolBinario<T> arbol) {
      Vertice raiz = arbol.vertice(arbol.raiz());
      ordenaVertices(raiz);
   }

   private void ordenaVertices(Vertice vertice) {
      if(vertice == null)
         return;
      ordenaVertices(vertice.izquierdo);
      agrega(vertice.elemento);
      ordenaVertices(vertice.derecho);
   }

   /**
    * Agrega un nuevo elemento al árbol. El árbol conserva su orden in-order.
    * @param elemento el elemento a agregar.
    */
   @Override public void agrega(T elemento) {
      elementos++;
      if(raiz == null) {
         raiz = nuevoVertice(elemento);
         ultimoAgregado = raiz;
      } else
         agrega(raiz, elemento);
   }

   /*Metodo auxiliar para agrega*/
   private void agrega(Vertice vertice, T elemento) {
      if(vertice == null)
         return;
      if(vertice.elemento.compareTo(elemento) < 0) {
         /*Si el elemento que queremos agregar es mayor entonces nos vamos a su derecha*/
         if(!vertice.hayDerecho()) {
            vertice.derecho = nuevoVertice(elemento);
            vertice.derecho.padre = vertice;
            ultimoAgregado = vertice.derecho;
         } else
            agrega(vertice.derecho, elemento);
      } else {
         if(!vertice.hayIzquierdo()) {
            vertice.izquierdo = nuevoVertice(elemento);
            vertice.izquierdo.padre = vertice;
            ultimoAgregado = vertice.izquierdo;
         } else
            agrega(vertice.izquierdo, elemento);
      }
   }

   /**
    * Elimina un elemento. Si el elemento no está en el árbol, no hace nada; si
    * está varias veces, elimina el primero que encuentre (in-order). El árbol
    * conserva su orden in-order.
    * @param elemento el elemento a eliminar.
    */
   @Override public void elimina(T elemento) {
      Vertice v = vertice(busca(elemento));
      if(v != null) {
         elimina(v);
         elementos--;
      }
      return;
   }

   /*Metodo auxiliar para elimina*/
   private void elimina(Vertice vertice) {
      Vertice v1 = buscaAnterior(vertice);
      if(v1 == null) {
         if(vertice.padre == null) {
            raiz = vertice.derecho;
            if(vertice.derecho != null)
               vertice.derecho.padre = null;
            return;
         }
         if(vertice.padre.izquierdo == vertice)
            vertice.padre.izquierdo = vertice.derecho;
         else
            vertice.padre.derecho = vertice.derecho;
         if(vertice.derecho != null)
            vertice.derecho.padre = vertice.padre;
         return;
      }
      vertice.elemento = v1.elemento;
      if(v1.padre.izquierdo == v1)
         v1.padre.izquierdo = v1.izquierdo;
      else
         v1.padre.derecho = v1.izquierdo;
      if(v1.izquierdo != null)
         v1.izquierdo.padre = v1.padre;
   }

   /*Metodo auxiliar para elemina que recibe un Vertice*/
   private Vertice buscaAnterior(Vertice vertice) {
      if(vertice.izquierdo == null)
         return null;
      return veDerecha(vertice.izquierdo);
   }

   /*Metodo auxiliar para buscaAnterior*/
   private Vertice veDerecha(Vertice vertice) {
      if(vertice.derecho == null)
         return vertice;
      return veDerecha(vertice.derecho);
   }

   /**
    * Nos dice si un elemento está contenido en el árbol.
    * @param elemento el elemento que queremos ver si está en el árbol.
    * @return <code>true</code> si el elemento está contenido en el árbol,
    *         <code>false</code> en otro caso.
    */
   @Override public boolean contiene(T elemento) {
      VerticeArbolBinario<T> v = busca(elemento);
      Vertice vertice = vertice(v);
      if(vertice == null)
         return false;
      return true;
   }

   /**
    * Busca un elemento en el árbol recorriéndolo in-order. Si lo encuentra,
    * regresa el vértice que lo contiene; si no, regresa <tt>null</tt>.
    * @param elemento el elemento a buscar.
    * @return un vértice que contiene al elemento buscado si lo
    *         encuentra; <tt>null</tt> en otro caso.
    */
   @Override public VerticeArbolBinario<T> busca(T elemento) {
      return busca(raiz, elemento);
   }

   /**
    * Busca recursivamente un elemento, a partir del vértice recibido.
    * @param vertice el vértice a partir del cuál comenzar la búsqueda. Puede
    *                ser <code>null</code>.
    * @param elemento el elemento a buscar a partir del vértice.
    * @return el vértice que contiene el elemento a buscar, si se encuentra en
    *         el árbol; <code>null</code> en otro caso.
    */
   @Override protected Vertice busca(Vertice vertice, T elemento) {
      if(vertice == null)
         return null;
      else if(vertice.elemento.compareTo(elemento) > 0)
         return busca(vertice.izquierdo, elemento);
      if(vertice.elemento.compareTo(elemento) < 0)
         return busca(vertice.derecho, elemento);
      else
         return vertice;
   }

   /**
    * Regresa el vértice máximo en el subárbol cuya raíz es el vértice que
    * recibe.
    * @param vertice el vértice raíz del subárbol del que queremos encontrar el
    *                máximo.
    * @return el vértice máximo el subárbol cuya raíz es el vértice que recibe.
    */
   protected Vertice maximoEnSubarbol(Vertice vertice) {
      if(vertice == null)
         return null;
      if(vertice.derecho == null)
         return vertice;
      else
         return maximoEnSubarbol(vertice.derecho);
   }

   /**
    * Regresa un iterador para iterar el árbol. El árbol se itera en orden.
    * @return un iterador para iterar el árbol.
    */
   @Override public Iterator<T> iterator() {
      return new Iterador(raiz);
   }

   /**
    * Gira el árbol a la derecha sobre el vértice recibido. Si el vértice no
    * tiene hijo izquierdo, el método no hace nada.
    * @param vertice el vértice sobre el que vamos a girar.
    */
   public void giraDerecha(VerticeArbolBinario<T> vertice) {
      Vertice v = vertice(vertice);
      giraDerecha(v);
   }

   /* Gira el árbol a la derecha sobre el vértice recibido. */
   private void giraDerecha(Vertice vertice) {
      if(vertice.izquierdo == null)
         return;
      Vertice ls = vertice.izquierdo;
      if(vertice.padre != null)
         if(vertice.padre.derecho == vertice)
            vertice.padre.derecho = ls;
         else vertice.padre.izquierdo = ls;
      else raiz = ls;
      ls.padre = vertice.padre;

      vertice.izquierdo = ls.derecho;
      if(vertice.izquierdo != null)
         vertice.izquierdo.padre = vertice;
      ls.derecho = vertice;
      ls.derecho.padre = ls;
   }

   /**
    * Gira el árbol a la izquierda sobre el vértice recibido. Si el vértice no
    * tiene hijo derecho, el método no hace nada.
    * @param vertice el vértice sobre el que vamos a girar.
    */
   public void giraIzquierda(VerticeArbolBinario<T> vertice) {
      Vertice v = vertice(vertice);
      giraIzquierda(v);
   }

   /* Gira el árbol a la izquierda sobre el vértice recibido. */
   private void giraIzquierda(Vertice vertice) {
      if(vertice.derecho == null)
         return;
      Vertice rs = vertice.derecho;
      rs.padre = vertice.padre;
      if(vertice.padre != null)
         if(vertice.padre.derecho == vertice)
            vertice.padre.derecho = rs;
         else
            vertice.padre.izquierdo = rs;
      else
         raiz = rs;
      vertice.derecho = rs.izquierdo;
      if(vertice.derecho != null)
         vertice.derecho.padre = vertice;
      rs.izquierdo = vertice;
      vertice.padre = rs;
   }
}