// Este código fuente viene de diversas fuentes traducidas y modificadas
// por diversos programadores. Entre ellos están:
// - Georgi Maximovich Adelson-Velskii (Гео́ргий Макси́мович Адельсо́н-Ве́льский)
// - Yevgueni Mijáilovich Landis (Евгений Михайлович Ландис)
// - A. Colin Day
// - Quentin F. Stout
// - Bette L. Warren
// - Timothy Rolfe
// - Robert Sedgewick
// - Alfons González
// La teoría del árbol binario optimizado (auto balanceable) es de Adelson-Velskii y Landis.
// El código de Colin Day sobre rotaciones y árboles degenerados (vines) fue escrito 
// en Fortran y traducido a Pascal por Stout y Warren.
// Timothy Rolfe tradujo el código Pascal de Stout y Warren a C y lo integró con el resto de
// los algoritmos de Adelson-Velskii y Landis, también en C.
// Mark Weiss y Frank Carrano aportaron algoritmos para atravesar el árbol de forma óptima.
// Sedgewick mejoró el código, optimizándolo especialmente lo relativo al AVL.
// Alfons González ha adaptado el código para compilar con Visual C++ .NET 2008
// en Unicode, eliminando librerías y funciones no soportadas, convirtiendo structs en clases
// y añadiendo funciones concretas para transformarlo en una extended stored
// procedure de SQL Server.
// Parte del código se ha publicado en "Algorithms in C++, Third Edition,"
// de Robert Sedgewick, Addison-Wesley, 1999.
// Otra parte se ha publicado en "Tree Rebalancing in Optimal Time and Space",
// de Quentin F. Stout and Bette L. Warren
// Communications of the ACM, Vol. 29, No. 9
// (September 1986), p. 904.

/* BST_Lib.h */

/* Binary Search Tree class

   Aportación básica de Timothy Rolfe, modificada por Alfons González

   Definición de nodo:
      wszORG      --- clave principal en Unicode
      Height      --- height within the tree of THIS node
      Util        --- miscellaneous int value, should we every need it
      Parent link --- allow upward adjustment of heights
      Left link   --- left subtree
      Right link  --- right subtree

      Note:  constructor and destructor also declared for the struct

      BaseCell: Nodo básico del árbol binario de búsqueda

   Funciones públicas:

      constructor --- constructor del árbol propiamente dicho
      destructor  --- tal cual
      Walk        --- Atraviesa la estructura de menor a mayor
      TstNR(Opt)  --- funciones de recorrido de Carrano (Opción=2) y Weiss (Opción=1 o 3)
                      que corresponden a algoritmos no recursivos para recorrer el árbol.
      Insert      --- Insertar un nodo con una nueva clave
      Find        --- Buscar una clave. Retorna el puntero al nodo encontado.
      Delete      --- Elimina una clave.
      AvgDepth    --- Promedio de altura de todos los nodos del árbol
      Height      --- Altura del árbol entero.
*/

#ifndef BST_H  // Evitar múltiples includes
#define BST_H

#include <stdlib.h>    
#include <stdio.h>

typedef struct BaseCell*  BasePtr;

struct BaseCell    // Nodo básico
{                  //   Menores a la izquierda
                   //   Mayores a la derecha
   wchar_t    wszORG[100]; // Clave principal
   //wchar_t    wszDST[100]; // Destino sólo figura en el árbol de datos
   //           Se podría colocar aquí para tener un acceso aún más rápido, 
   //           pero consumiría el doble de memoria, por lo que hemos preferido 
   //           colocarlo en archivo de acceso aleatorio
   int     Height; // Altura del árbol en niveles
   int     Util;   // Aquí es donde se guarda el número de registro para acceder 
                   // al archivo de acceso aleatorio.
   BasePtr Parent, // Punteros a nodos a la derecha y a la izquierda.
           Left,
           Right;

   BaseCell ( wchar_t * wszORGParam = NULL,
              BasePtr P = NULL, BasePtr L = NULL, BasePtr R = NULL )
   { 
	   if (wszORGParam)
	   {
		   wcscpy(wszORG, wszORGParam);
	   }
	   else
	   {
		   wcscpy(wszORG, L"");
	   }

	   Parent = P;
	   Left = L;
	   Right = R;
	   Height = 1;
   }
   ~BaseCell (void);
};

class BST
{  
public:

      BST(void) : Root(NULL), Free(NULL), Nitems(0)
      { 
		  //No hacer nada
	  }

      void Empty(void);      // Empty out a tree
      ~BST(void);

      void    Walk(void);
      void    Pretty();
      void    Insert(wchar_t *, int);
      void    Delete(wchar_t *);
      BasePtr Find(wchar_t *);

//    Algoritmos no recursivos de recorrido del árbol:
//       Opción = 1:  Weiss en modo pre-order
//       Opción = 2:  Carrano en modo in-order
//       Opción = 3:  Weiss en modo post-order
      void    TstNR(int Opt)
      {  if   (Opt==2)  Carrano(Root);
         else           Weiss(Root, Opt);
      }

      int     Size(void)
      {  return Size(Root);  }
      double  AvgDepth(void)
      {  return AvgDepth(Root); }
//    Función de averiguar altura
      int     Height(void)   // Root = NULL significa que vacío = 0
      {  return Root == NULL ? 0 : Root->Height;  }
      int     HeightLt(void)
      {  return (Root && Root->Left) ? Root->Left->Height : 0; }
      int     HeightRt(void)
      {  return (Root && Root->Right) ? Root->Right->Height : 0; }

	protected:

//    Generar un nodo o reutilizar uno de entre los nodos libres
      BasePtr Build( wchar_t * lpszData=NULL, int nUtil = 0, BasePtr P=NULL, BasePtr L=NULL, BasePtr R=NULL );

//    Sacar el nodo hacia la lista de nodos libres y ponerlo a NULL
      void Recycle( BasePtr &Node );

      void Carrano(BasePtr);
      void Weiss  (BasePtr, int);
//       Opt = 1:  Weiss pre-order
//       Opt = 3:  Weiss post-order
      void InOrder(BasePtr); // Llamada desde la función Walk()

      void SetPos (BasePtr, int&);     
      void Pretty (BasePtr); // Level-order display

      void Autumn(BasePtr&); // En Otoño se caen las hojas. Se limpia totalmente el árbol.

      void Insert(BasePtr, wchar_t *, int);     // Para insertar claves

      void Delete(BasePtr, wchar_t *);     // Para borrar claves

      void AdjustHt(BasePtr);        // Ajuste de equilibrado de árbol. Se usa tras Insert y Delete

      double AvgDepth(BasePtr);

      int Size(BasePtr);             // Recorrer todos los nodos del árbol contándolos

//    Estadísticas de nodos y alturas de cada nodo
      void DepthStats(BasePtr, int, long&, double&);

      BasePtr Root,
              Current;
      int Nitems;                 // Se uda como función privada en el recorrido del árbol
      BasePtr Free;               // Nodos para reutilizar
public:
	void InOrderSearch(BasePtr Item, 
						wchar_t * szKey, 
						int * pnFoundElements, 
						SRV_PROC *srvproc, FILE * pFile);

	void InOrderDel(BasePtr Item, 
						wchar_t * szKey, 
						wchar_t * wszDST,
						int * pnFoundElements, 
						SRV_PROC *srvproc, 
						FILE * pFile);
};

// Tanto Carrano() como Weiss() usan una pila de nodos
// de manera que es más eficiente implementar la clase que
// colocar el código dentro de las funciones.

class BSTstack
{  public:
      BSTstack ( void ) : Root(NULL)  
	  { 
		  //No hacer nada en concreto. Libre. 
	  }
     ~BSTstack ( void );

      int  Empty ( void )
      {  
		  return Root == NULL; 
	  }

      void Push( BasePtr  Item, int  Vst ) 
      {  
		  Root = new StackCell(Item, Vst, Root);  
	  }

      void Pop ( BasePtr &Item, int &Vst );

   private:
      struct StackCell 
      {  BasePtr    Node;
         int        Visit;
         StackCell *Next;
         StackCell ( BasePtr Item, int Vst, StackCell *Nxt = NULL )
         : Node(Item), Visit(Vst), Next(Nxt) 
		 { 
			 //No hacer nada en concreto. Libre.
		 }
      } *Root;

};

#endif

