/***********************************************************/
/*                                                         */
/* Funciones del árbol AVL.                                */
/* Aportaciones de Timothy Rolfe                           */
/*                                                         */
/***********************************************************/

#include "stdafx.h"
#include <stdlib.h>
#include <ctype.h>
#include "AVL.h"

int AVL::Valid(BasePtr Node)
{  int Lht, Rht;

   if (Node == NULL) return 1;
   Lht = Node->Left  == NULL ? 0 : Node->Left->Height;
   Rht = Node->Right == NULL ? 0 : Node->Right->Height;

   if ( abs(Lht-Rht) > 1 ) return 0;
   return Valid(Node->Left) && Valid(Node->Right);
}

// Redefinir los Insert y Delete de la clase BST:
void AVL::Insert(BasePtr Node, wchar_t * wszValue, int nUtil)
{
   BasePtr Parent = NULL,
           Child  = Node;

   if ( Node == NULL )
      Root = Build (wszValue, nUtil, Node);
   else
      while(1)     // Creación de nodo. Sale.
      {
         if ( wcscmp(wszValue, Node->wszORG)<0) 
            if ( Node->Left != NULL )
               Node = Node->Left;
            else
            {
               Node = Node->Left = Build (wszValue, nUtil, Node);
               break;
            }
         else                          
            if ( Node->Right != NULL )
               Node = Node->Right;
            else
            {
               Node = Node->Right = Build (wszValue, nUtil, Node);
               break;
            }
      }

   AVLadjust(Node);
}

// Intercambio de datos entre nodos, consistente en intercambiar clave
// y número de registro. Se pasa como argumento el puntero a los nodos 
// a intercambiar.
void SwapData (BasePtr d, BasePtr s);  // Implemented in BST_Lib.cpp.

// The following always chooses the in-order predecessor as the
// replacement node on the delete.

void AVL::Delete(BasePtr Node, wchar_t * Value)
{
   BasePtr Parent = NULL, Child;

   while ( Node != NULL && wcscmp(Node->wszORG, Value) )
      if ( wcscmp(Value, Node->wszORG) < 0 )
         Node = Node->Left;
      else
         Node = Node->Right;

   if ( Node == NULL )
   {
      //No se ha podido encontrar y por consiguiente no se puede borrar.
	  //Aquí se podría insertar algún código de notificación...
      return;
   }

   //Si el nodo en cuestión tiene algún hijo a derecha o izquierda
   //hay que atar el puntero al hijo y luego sacar el nodo que se desea borrar.
   //El ajuste de altura se hace desde donse señala el puntero padre del nodo.
   if ( ! Node->Left && ! Node-> Right )    // I.e., nodo final o "hoja"
   {
      Parent = Node->Parent;
      if ( Parent == NULL )                 // Arbol compuesto por un solo nodo
         Root = NULL;
      else if ( Value < Parent->wszORG )    // Recorrido a la izquierda
         Parent->Left = NULL;
      else                                  // Si no, vamos por la derecha
         Parent->Right = NULL;
      Recycle(Node);                        // Sólo se va el nodo en cuestión
   }
   else if ( Node->Left == NULL )           // Mitad derecha
   {
      Parent = Node;
      Child  = Node->Right;
      SwapData (Parent, Child);
      Parent->Left  = Child->Left;
      if (Parent->Left)
         Parent->Left->Parent = Parent;     // ESENCIAL para que los punteros al padre
      Parent->Right = Child->Right;         // sean válidos
      if (Parent->Right)
         Parent->Right->Parent = Parent;
      Recycle (Child);
   }
   else if ( Node->Right == NULL )          // Mitad izquierda
   {
      Parent = Node;
      Child  = Node->Left;
      SwapData (Parent, Child);
      Parent->Left  = Child->Left;
      if (Parent->Left)
         Parent->Left->Parent = Parent;
      Parent->Right = Child->Right;
      if (Parent->Right)
         Parent->Right->Parent = Parent;
      Recycle (Child);
   }
   else                                     // Entero
   {
      Child = Node->Left;
      while (Child->Right)                  // Predecesor In-order
      {
         Parent = Child;
         Child  = Parent->Right;
      }
      if ( Parent != NULL )                 // ATRAVESÓ el sub-árbol izquierdo
      {
         SwapData (Node, Child);
         Parent->Right = Child->Left;
         if (Parent->Right)
            Parent->Right->Parent = Parent;
         Recycle (Child);
      }
      else                                  // O sea, el propio Node->Left
      {
         Parent = Node;                     // Para ajustar la altura
         SwapData (Node, Child);
         Parent->Left = Child->Left;
         if (Parent->Left)
            Parent->Left->Parent = Parent;
         Recycle (Child);
      }
   }
   AdjustHt (Parent);
   AVLadjust(Parent);
}

inline int maximum (int L, int R)
{  return L > R ? L : R;  }

// Ajuste de altura
void AVL::HtAdjust(BasePtr Node)
{
   int Lht, Rht;

   if (Node == NULL)
      return;
   Lht = Node->Left  == NULL ? 0 : Node->Left->Height;
   Rht = Node->Right == NULL ? 0 : Node->Right->Height;
   Node->Height = 1 + max(Lht, Rht);
}

// Si fuera necesario, realizar rotaciones para equilibrar el AVL:
void AVL::AVLadjust(BasePtr Node)
{
   while ( Node != NULL )
   {
      int Lht = Node->Left  == NULL ? 0 : Node->Left->Height,
          Rht = Node->Right == NULL ? 0 : Node->Right->Height,
          Diff = Lht - Rht;

      if ( abs(Diff) > 1 ) // Factor de equilibrio no se cumple
      {
		 //Hace falta reequilibrar el árbol:
         if ( Lht > Rht )  // La rama izquierda es dos niveles más alta que la derecha
         {  int Lck = Node->Left->Left  == NULL ? 0 : Node->Left->Left->Height,
                Rck = Node->Left->Right == NULL ? 0 : Node->Left->Right->Height;
            if ( Lck < Rck )
               RotateLeft (Node->Left);
            RotateRight (Node);
         }
         else  // Por lógica, la parte simétrica: derecha más alta que izquierda
         {  int Lck = Node->Right->Left  == NULL ? 0
                                                 : Node->Right->Left->Height,
                Rck = Node->Right->Right == NULL ? 0
                                                 : Node->Right->Right->Height;
            if ( Lck > Rck )
               RotateRight (Node->Right);
            RotateLeft (Node);
         }
      }
      HtAdjust(Node);   // No importa lo que haya pasado: ajustar la altura

      Node = Node->Parent;
   }
}

// Funciones de rotación (que también ajustan alturas)

// Nota:  Ya que no tenemos un parámetro de referencia, 
//        tomamos como estrategia TRANSFORMAR ambos 
//        nodos involucrados uno contra el otro y después 
//        lidiar con los hijos.

void AVL::RotateLeft (BasePtr Lt)
// Rotar hacia la izquierda:
// El nodo de la izquierda baja y el nodo de la derecha sube.
{  BasePtr  Rt = Lt->Right,
            N1 = Lt, N2 = Rt;

   SwapData (N1, N2);        // Ahora N1 es Rt, N2 es Lt
   N1->Right = N2->Right;    // ajustar Rt->Right 
   if (N1->Right != NULL)
      N1->Right->Parent = N1;
   N2->Right = N2->Left;     // Moverse a través del sub-árbol medio
   if (N2->Right != NULL)
      N2->Right->Parent = N2;
   N2->Left  = N1->Left;     // Ajustar Lt->Left
   if (N2->Left != NULL)
      N2->Left->Parent = N2;
   N1->Left   = N2;          // Lt es el sub-hijo de Rt
   N2->Parent = N1;

   HtAdjust (N2);            // NB:  ajustar el HIJO antes del PADRE
   HtAdjust (N1);
}

void AVL::RotateRight(BasePtr Rt)
{  BasePtr  Lt = Rt->Left,
            N1 = Rt, N2 = Lt;

   SwapData (N1, N2);        // Ahora N1 es Lt, N2 es Rt

   N1->Left = N2->Left;      // Ajuste Lt->Left
   if (N1->Left != NULL)
      N1->Left->Parent = N1;
   N2->Left = N2->Right;     // Atravesar el sub-árbol medio
   if (N2->Left != NULL)
      N2->Left->Parent = N2;
   N2->Right = N1->Right;    // Ajuste Rt->Right
   if (N2->Right != NULL )
      N2->Right->Parent = N2;
   N1->Right  = N2;          // Rt es el sub-árbol derecho de Lt
   N2->Parent = N1;

   HtAdjust (N2);            // NB:  ajustar HIJO antes que el PADRE
   HtAdjust (N1);
}


int AVL::GetItems()
{
	return this->Nitems;
}

void AVL::InOrderFind(wchar_t * wszKey, int *pnFoundResults, SRV_PROC *srvproc, FILE * pFile)
{
	InOrderSearch(Root, wszKey, pnFoundResults, srvproc, pFile);
}

void AVL::InOrderDelete(wchar_t * wszKey, wchar_t * wszDST, int *pnFoundResults, SRV_PROC *srvproc, FILE * pFile)
{
	InOrderDel(Root, wszKey, wszDST, pnFoundResults, srvproc, pFile);
}

int AVL::GetDepth()
{
	return this->Height();
}
