/* BST.cpp */
//Aportaciones recogidas desde  http://penguin.ewu.edu/~trolfe/DSWpaper/Code.html

#include "stdafx.h"
#include "tagEquiv.h"

/* Clase básica del árbol binario de búsqueda (BST)

   
   NOTE:  in light of future use of this class, it has been designed
          to RECYCLE tree nodes:  rather than deleting them, they are
   entered into a "Free" list (maintained as a stack throug the Right
   link).  Consequently, when a node is inserted, it is taken from
   that Free list unless it is empty (in which case it is explicitly
   constructed).
*/

//#include <iostream.h>
//#include <iomanip.h>    // uses setw
#include <stdlib.h>     // uses atoi
#include <ctype.h>      // uses toupper
#include <assert.h>
#include "BST.h"        // NOTE:  Defines the structs and classes

//////////////////////////////////////////////////////////////////

BaseCell::~BaseCell (void)   // Traversal to delete done by BST
{/*cout << "Deleting " << wszORG << endl;*/}

//////////////////////////////////////////////////////////////////

// Generate a node, either re-using from the Free list or constructed
BasePtr BST::Build( wchar_t * wszData, int nUtil, BasePtr P, BasePtr L, BasePtr R )
{  BasePtr Rtn;

   if (Free == NULL)
   {  Rtn = new BaseCell (wszData, P, L, R);
      if ( Rtn == NULL )
      {  
		 //cout << "Out of heap space.  Aborting execution." << endl;
         exit(7);
      }
	  Rtn->Util = nUtil;
   }
   else
   {  Rtn = Free;
      Free = Free->Right;
      wcscpy(Rtn->wszORG, wszData); 
      Rtn->Parent = P; Rtn->Left = L; Rtn->Right = R;
	  Rtn->Util = nUtil;
   }
   return Rtn;
}

// Push Node onto Free list, then set to NULL
void BST::Recycle( BasePtr &Node )
{  Node->Right = Free;
   Free = Node;
   Node = NULL;
#ifdef DEBUG
   cout << "Recycling " << Free->wszORG << endl;
#endif
}

//////////////////////////////////////////////////////////////////

BST::~BST(void)      // Destructor
{  Autumn(Root);             // Traverse, deleting cells
   while (Free)              // Then empty out the Free list
   {  BasePtr Node = Free;
      Free = Free->Right;
      delete Node;           // Finally do an explicit delete
   }
}

void BST::Empty(void)      // Empty out a tree
{  Autumn(Root);  }     // Unlike ~BST, though, the tree remains

// In-order tree traversal to delete cells.  Called by ~BST.
void BST::Autumn(BasePtr &Node)
{  if (Node)
   {//Note:  Node->Right may be lost on the "delete Node"
      BasePtr Hold = Node->Right;

      Autumn(Node->Left);
      Recycle(Node);    // Note that this NULLs out Node
      Autumn(Hold);
   }
}

/******************* Recursive traversal *******************/

// Walk through the tree; display is to be ascending order
void BST::Walk(void)
{  if (Root)
   {  Nitems = 0;
      InOrder(Root);
   }
}

// To get ascending order, do an in-order traversal of the tree
void BST::InOrder(BasePtr Item)
{  if ( !Item ) return;                // I.e., NULL tree

   InOrder(Item->Left);                // Process Left sub-tree
   
   InOrder(Item->Right);               // Process Right sub-tree
}

wchar_t szLastSent[250];

void BST::InOrderSearch(BasePtr Item, wchar_t * wszKey, int * pnFoundElements, SRV_PROC *srvproc, FILE * pFile)
{
	tagEquiv Equiv1;
	int nRecord;
	DWORD dwLength;

	if (!Item) return;
	if (!wszKey) return;
	if (!wcslen(wszKey)) return;

	dwLength = sizeof(tagEquiv);

	InOrderSearch(Item->Left, wszKey, pnFoundElements, srvproc, pFile);
	//check for key
	if (!wcscmp(Item->wszORG, wszKey))
	{
		nRecord = Item->Util;
		fseek(pFile, nRecord*dwLength, SEEK_SET);
		fread(&Equiv1, dwLength,1,pFile);		

		if (wcscmp(szLastSent, Equiv1.wszORG))
		{
			(*pnFoundElements) = (*pnFoundElements) + 1;
			if (wcslen(Equiv1.wszORG))
			{
				/***********************************************/
				/* Enviar los datos a columnas de resultados:  *
				/***********************************************/
				
				wcscpy(szLastSent, Equiv1.wszORG);
			}
		}
	}
	InOrderSearch(Item->Right, wszKey, pnFoundElements, srvproc, pFile);
}


void BST::InOrderDel(BasePtr Item, 
						wchar_t * wszKey, 
						wchar_t * wszDST,
						int * pnFoundElements, 
						SRV_PROC *srvproc, 
						FILE * pFile)
{
	tagEquiv Equiv1;
	int nRecord;
	DWORD dwLength;

	if (!Item) return;
	if (!wszKey) return;
	if (!wcslen(wszKey)) return;

	dwLength = sizeof(tagEquiv);

	InOrderDel(Item->Left, wszKey, wszDST, pnFoundElements, srvproc, pFile);
	//check for key
	if (!wcscmp(Item->wszORG, wszKey))
	{
		nRecord = Item->Util;
		fseek(pFile, nRecord*dwLength, SEEK_SET);
		fread(&Equiv1, dwLength,1,pFile);

		if (!wcscmp(wszDST, Equiv1.wszDST))
		{
			(*pnFoundElements) = (*pnFoundElements) + 1;
			
			fseek(pFile, nRecord*dwLength, SEEK_SET);
			memset(&Equiv1,0,sizeof(tagEquiv));
			fwrite(&Equiv1, sizeof(tagEquiv),1,pFile);
		}
	}
	InOrderDel(Item->Right, wszKey, wszDST, pnFoundElements, srvproc, pFile);
}


// Recorridos no recursivos

// Vaciar la pila antes de destruirla
BSTstack::~BSTstack ( void )
{
   while ( Root != NULL )
   {
      StackCell *Tmp = Root;
      Root = Root->Next;
      delete Tmp;
   }
}

void BSTstack::Pop ( BasePtr &Item, int &Vst )
{
   StackCell *Tmp = Root;

   assert (Tmp != NULL);
   Root = Root->Next;

   Item = Tmp->Node;
   Vst  = Tmp->Visit;
   delete Tmp;
}

// La visita más sencilla consiste en no hacer nada
inline void Visit ( BasePtr Node )
{  
	//No hacer nada
}

// Algoritmos no recursivos de recorrido

// Carrano con modificaciones de Timothy Rolfe

void BST::Carrano(BasePtr Cur)  
{
   BSTstack Stack;
   int      Dmy = 0;

// Revisión:  En vez de usar una variable booleana de control de bucle, salimos con un break:

   while ( 1 ) // Salimos del bucle infinito mediante un break
   {
// Revision:  El código Carrano equivale a un "while"
      while ( Cur != NULL )
      {
         Stack.Push ( Cur, Dmy );
         Cur = Cur->Left;
      }
      if ( Stack.Empty() )
         break;                   // Salida del bucle
      else
      {
         Stack.Pop ( Cur, Dmy );
         Visit (Cur);
         Cur = Cur->Right;
      }
   }
}

// Implementación de la lógica de Weiss de recorrido post-orden
// generalizado por Timothy Rolfe para pre-orden y post-orden.

void BST::Weiss  (BasePtr Node, int Opt)
//       Opt = 1:  pre-orden
//       Opt = 3:  post-orden
// NOTA: La opción 2 no maneja adecuadamente el recorrido en-orden
{
   BSTstack Stack;
   int      Nvisit;

   Stack.Push(Node, 1);

   while ( ! Stack.Empty() )
   {
      Stack.Pop ( Node, Nvisit );
      if ( Nvisit == Opt )
         Visit(Node);
      else
         Stack.Push ( Node, Nvisit+1 );
      if ( Nvisit == 1 )
      {//Sacar de derecha a izquiera para simular el comportamiento recursivo
         if ( Node->Right != NULL )
            Stack.Push (Node->Right, 1);
         if ( Node->Left != NULL )
            Stack.Push (Node->Left, 1);
      }
   }
}

// Preparado para mostrar el árbol sobre cualquier dispositivo.
// Actualmente no se utiliza.
void BST::Pretty()
{
   int Skip = 0;

   if ( Root == NULL )  // No hay nodos
   {  
	   //Arbol vacío
   }

   SetPos (Root, Skip); // Encontrar la posición de línea de cada nodo
   Pretty (Root);       // recorrido por niveles mostrando los nodos.
}                       // Una línea por cada nivel en la posición adecuada

// Encontrar la posición de línea de cada nodo basándose en recorrido en-orden
void BST::SetPos (BasePtr Node, int &Skip)
{
// If the nodes were all printed on one line, their order is based
// in an in-order traversal.  Skip shows number of positions to skip
// to properly position the node.  Note that is MUST be a reference
// parameter --- the root depends on the reference parameter to come
// back with the size of the entire left subtree, for instance.
   if ( Node )
   {
      SetPos (Node->Left, Skip);
      Node->Util = Skip;     // Store skip value in Util data member
      Skip = Skip + 3;       // Update for printing THIS node
      SetPos (Node->Right, Skip);
   }
}

// Pretty-print:  each tree level prints on one line, with the node
// horizontally positioned to be visually the parent of its children.
void BST::Pretty (BasePtr Node)
{//Level-order traversal requires a queue --- build a quick one here.
   struct Queue
   {
      BasePtr Node;
      int     Level;    // Change in level is where the endl prints
      Queue  *Next;

      Queue(BasePtr N, int Lvl, Queue *Nxt = NULL)
      : Node(N), Level(Lvl), Next(Nxt) { /* nothing else */ }
   }  *Front = NULL, *Back;

   int Level = 0, Position = 0;

// Level-order traversal:  initialize the work queue with the root

   Front = Back = new Queue(Node, 0);  // Node initially IS the root

   while ( Front ) // Keep going till there's nothing left to do!
   {
      Queue *Add,                 // Queue pointer when we add a job
            *Current = Front;     // Begin the dequeue operation

      Front = Front->Next;        // Complete the dequeue operation

      Node = Current->Node;       // Node we're currently working on
      if (Node->Left)             // Enqueue child nodes
      {
         Add = new Queue (Node->Left, Current->Level+1);
         if ( Front )             // Begin the enqueue
            Back->Next = Add;
         else
            Front = Add;
         Back = Add;              // Finish the enqueue
      }
      if (Node->Right)
      {
         Add = new Queue (Node->Right, Current->Level+1);
         if ( Front )
            Back->Next = Add;
         else
            Front = Add;
         Back = Add;
      }
//    Check for line-break:  change in tree level
      if ( Current->Level != Level )
      {
         
         Position = 0;
         Level = Current->Level;
      }
//    Skip over to proper position
      for ( ; Position < Node->Util ; Position++ )
	  {
		  //Out << ' ';
	  }
      
      Position += 3;    // Update position for the output just done
      delete Current;   // Return heap space for re-use.
   }
}

/******************* Insertion *******************/

// Insert the Value into its proper place in the binary search tree
void BST::Insert(wchar_t * Value, int nUtil)
{  
	Insert(Root, Value, nUtil);  
}

// Little in-line function used in height adjustment
inline int maximum ( int L, int R )
{ 
	return L > R ? L : R ; 
}

void BST::Insert(BasePtr Node, wchar_t * Value, int nUtil)
{
   if ( Node == NULL )
      Root = Build (Value, nUtil, Node);
   else
      while(1)     // breaks on node creation
      {
         if ( Value < Node->wszORG )
            if ( Node->Left != NULL )
               Node = Node->Left;
            else
            {
               Node = Node->Left = Build (Value, nUtil, Node);
               break;
            }
         else                          
            if ( Node->Right != NULL )
               Node = Node->Right;
            else
            {
               Node = Node->Right = Build (Value, nUtil, Node);
               break;
            }
      }
   AdjustHt(Node);
}

/******************* Deletion *******************/

// Delete the node with the Value passed
void BST::Delete(wchar_t * Value)
{  
	Delete(Root, Value);  
}

// Before the utility Delete function, some utility functions
// on BaseCell struct objects as free functions:

// Return the computed height based on the children
inline int NewHt( BasePtr L, BasePtr R )
{
   if ( !L && !R )           // Leaf node is height 1
      return 1;
   else if (!L)
      return 1 + R->Height;  // Half node cases
   else if (!R)
      return 1 + L->Height;
   else                      // Full node --- need max
      return 1 + max(L->Height, R->Height);
}

// Overloaded --- passed a single node and calls above routine
inline int NewHt ( BasePtr Node )
{  return Node ? NewHt (Node->Left, Node->Right) : 0;  }

void BST::AdjustHt(BasePtr Node)
{
   while (Node)
   {
      Node->Height = NewHt(Node);
      Node = Node->Parent;
   }
}

// Interchange the ->wszORG and Util fields on two BaseCells passed by pointer
void SwapData (BasePtr d, BasePtr s)
{  
	wchar_t wszTemp[102];
	int nTempUtil;
	
	wcscpy(wszTemp, d->wszORG);  
	wcscpy(d->wszORG, s->wszORG);  
	wcscpy(s->wszORG, wszTemp); 

	nTempUtil = d->Util;
	d->Util = s->Util;
	s->Util = nTempUtil;
}

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

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

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

   if ( Node == NULL )
   {
      //No se pudo encontrar el vaor para borrarlo
      return;
   }

// If Node has ANY children, transform it into its
// replacement node and delete THAT node.  The
// height adjustments will always be from wherever
// the Parent pointer ends up.
   if ( ! Node->Left && ! Node-> Right )    // I.e., leaf node
   {
      Parent = Node->Parent;
      if ( Parent == NULL )                 // Single-node tree
         Root = NULL;
      else if ( Value < Parent->wszORG )      // Traversed left
         Parent->Left = NULL;
      else                                  // else we went right
         Parent->Right = NULL;
      Recycle(Node);                        // only time Node itself goes
   }
   else if ( Node->Left == NULL )           // Half-full to the right
   {
      Parent = Node;
      Child  = Node->Right;
      SwapData (Parent, Child);
      Parent->Left  = Child->Left;
      if (Parent->Left)
         Parent->Left->Parent = Parent;     // CRITICAL to keep the
      Parent->Right = Child->Right;         // parent pointers valid
      if (Parent->Right)
         Parent->Right->Parent = Parent;
      Recycle (Child);
   }
   else if ( Node->Right == NULL )          // Half-full to the left
   {
      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                                     // Full
   {
      Child = Node->Left;
      while (Child->Right)                  // In-order predecessor
      {
         Parent = Child;
         Child  = Parent->Right;
      }
      if ( Parent != NULL )                 // DID traverse in left subtree
      {
         SwapData (Node, Child);
         Parent->Right = Child->Left;
         if (Parent->Right)
            Parent->Right->Parent = Parent;
         Recycle (Child);
      }
      else                                  // I.e., Node->Left itself
      {
         Parent = Node;                     // for height adjustment
         SwapData (Node, Child);
         Parent->Left = Child->Left;
         if (Parent->Left)
            Parent->Left->Parent = Parent;
         Recycle (Child);
      }
   }
   AdjustHt (Parent);
}


/******************* Simple Find *******************/

// Find the cell with the data field corresponding to Value
BaseCell* BST::Find(wchar_t * Value)
{  Current = Root;
   while ( Current != NULL && wcscmp(Current->wszORG, Value) )
   {  if (wcscmp(Value, Current->wszORG)<0) //Value < Current->wszORG)
         Current = Current->Left;
      else
         Current = Current->Right;
   }

   return Current;
}

/******************* Miscellaneous other *******************/

int BST::Size(BasePtr Node)  // Traverse, counting nodes
{
   if ( Node )
      return 1 + Size(Node->Left) + Size(Node->Right);
   else
      return 0;
}

// Average depth of nodes within the tree:
double BST::AvgDepth(BasePtr Node)
{  double SigmaD = 0;
   long   Nnodes = 0;

   if (Node == NULL) return 0;

// Root is at depth 1
   DepthStats (Node, 1, Nnodes, SigmaD);
   return SigmaD / Nnodes;
}

// Total number of nodes and depth of each node
void BST::DepthStats(BasePtr Node, int Deep, long &N, double &Sigma)
{  if ( Node != NULL )
   {  DepthStats(Node->Left, Deep+1, N, Sigma);
      DepthStats(Node->Right, Deep+1, N, Sigma);
      N++;
      Sigma += Deep;
   }
}

