/***********************************
  (C) Copyright 1992-1993; dit/upm
  Distributed under the conditions stated in the
  TOPO General Public License (see file LICENSE)
  ***********************************/

/***********************************
  
  Santiago Pavon
  
  July 9, 1992
  
  Type and function definitions to manage Binary Search Trees.
  
  The nodes in the tree must satisfy these conditions:
  
  n->dat <= n->l->dat  (if n->l != NULL)
  n->dat >  n->r->dat  (if n->r != NULL)
  
  ************************************/

/* LINTLIBRARY */

#include "libst.h"
#include "limisc.h"


/******************************************************************
 *
 * Emalloc and free functions.
 *
 *******************************************************************/


static int new_bsn_count      = 0;
static int released_bsn_count = 0;

/* InitBST
 * Init the module
 */
void InitBST()
{
#ifdef SDEBUG
  new_bsn_count      = 0;
  released_bsn_count = 0;
#endif
}

/*----------------------------------------------------------------*/

/* StatBST
 * Number of asked  and released bs nodes
 */
void StatBST( new, released )
     int * new, *released;
{
  *new      = new_bsn_count;
  *released = released_bsn_count;
}

/*----------------------------------------------------------------*/

static BstTyp NewBSTNode()
{ 
  
#ifdef SDEBUG
  new_bsn_count++;
#endif
  return (BstTyp)NewCellM( sizeof(BstNodeTyp) );
}


/*----------------------------------------------------------------*/

/* DispBSTNode
 * Disposes the memory used by the node "n".
 */
static void DispBSTNode( n )
     BstTyp n;
{
#ifdef SDEBUG
  released_bsn_count++;
#endif
  FreeCellM( (void*)n, sizeof(BstNodeTyp) );
}


/******************************************************************
 *
 * Insertion, searching and deletion functions.
 *
 *******************************************************************/

static int keye;

static void AuxInsertBST( e , pt , f )
     DataBstTyp e;
     BstTyp     *pt;
     int        (*f)();
{
  BstTyp n;
  int    k;
  
  if (*pt==NULL) {
    *pt = NewBSTNode();
    (*pt)->l = (*pt)->r = NULL;
    (*pt)->dat = e;
  }
  else {
    k = f((*pt)->dat);
    if (k > keye)
      AuxInsertBST( e , &((*pt)->l) , f );
    else if (k < keye)
      AuxInsertBST( e , &((*pt)->r) , f );
    else {
      n = NewBSTNode();
      n->r = NULL;
      n->l = (*pt)->l;
      n->dat = e;
      (*pt)->l = n;
    }
  }
}

/* InsertBST
 * Inserts the element "e" in the tree "t".
 * "f" is the function to calculate the key value of "e" (to calculate
 * what its position in the tree is.
 * Returns the new tree.
 */
BstTyp InsertBST( e , t , f )
     DataBstTyp e;
     BstTyp     t;
     int        (*f)();
{
  keye = f(e);
  AuxInsertBST( e , &t , f );
  return t;
}


/*----------------------------------------------------------------*/


BstTyp AuxLookForBST( e , t , k , c )
     DataBstTyp e;
     BstTyp     t;
     int        (*k)();
     boolean    (*c)();
{
  int kn;
  
  if (t==NULL)
    return NULL;
  else {
    kn = k(t->dat);
    if (keye==kn)
      if (c(e,t->dat))
	return t;
      else
	return AuxLookForBST( e , t->l , k , c );
    else if (keye<kn)
      return AuxLookForBST( e , t->l , k , c );
    else 
      return AuxLookForBST( e , t->r , k , c );
  }
}


/* LookForBST
 * Returns a pointer to the node of the tree "t" such as the data in the
 * node is equal to "e".
 * "k" is the function to calculate the key of each element, and "c" is
 * the function to compare  two elements.
 */
BstTyp LookForBST( e , t , k , c )
     DataBstTyp e;
     BstTyp     t;
     int        (*k)();
     boolean    (*c)();
{
  keye = k(e);
  return AuxLookForBST( e , t , k , c );
}


/*----------------------------------------------------------------*/

/* GetBSTNode
 * Extract the node "*pn" from the tree where it is included.
 * This function returns a pointer to the extracted node.
 */
static BstTyp GetBSTNode( pn )
     BstTyp *pn;
{
  BstTyp father, aux;
  DataBstTyp  daux;
  
  aux = *pn;
  if ((*pn)->r == NULL)
    *pn = (*pn)->l; /* there is no right son */
  else if ((*pn)->l == NULL)  
    *pn = (*pn)->r; /* there is no left son */
  else { /* node with two sons */
    /* looking for the node with the previous value */
    father = *pn; 
    aux = (*pn)->l;
    while (aux->r != NULL) {
      father = aux;
      aux = aux->r;
    }
    /* exchanging values */
    daux = (*pn)->dat;
    (*pn)->dat = aux->dat;
    aux->dat = daux;
    /* extraction of the node pointed by aux */
    if ( father == *pn )
      (*pn)->l = aux->l;
    else
      father->r = aux->l;
    aux->l = NULL; 
    aux->r = NULL;
  }
  return aux;
}



static BstTyp AuxExtractNodeBST( e , pt , k , c )
     DataBstTyp e;
     BstTyp     *pt;
     int        (*k)();
     boolean    (*c)();
{
  BstTyp  p,n;
  int kn;
  
  p = NULL; 
  n = *pt;
  while (n!=NULL) {
    p = n;
    kn = k(n->dat);
    if (keye==kn) 
      if (c(n->dat,e))
	break;
      else 
	n = p->l;
    else if (keye>kn)
      n = p->r;
    else 
      n = p->l;
  }
  if (n==NULL)
    return NULL;
  else if (n==*pt) /* the root of the tree */
    return GetBSTNode(pt);
  else if (n==p->l)
    return GetBSTNode(&(p->l));
  else
    return GetBSTNode(&(p->r));
}


/* ExtractNodeBST
 * Extract from the tree "t" a node such as its data is equal to "e".
 * Returns a pointer to the extracted node and the new tree.
 * If the node is not found then it returns NULL.
 * "k" is the function to calculate the key of each element, and "c" is
 * the function to compare  two elements.
 */
BstTyp ExtractNodeBST( e , pt , k , c )
     DataBstTyp e;
     BstTyp     *pt;
     int        (*k)();
     boolean    (*c)();
{
  keye = k(e);
  return AuxExtractNodeBST( e , pt , k , c );
}


/*----------------------------------------------------------------*/


/* RemoveNodeBST
 * Extracts and removes the node which data is "e" from the tree "t".
 * Returns the new tree (without the removed node).
 * "k" is the function to calculate the key of each element, and "c" is
 * the function to compare  two elements.
 */
BstTyp RemoveNodeBST( t , e , k , c )
     DataBstTyp e;
     BstTyp     t;
     int        (*k)();
     boolean    (*c)();
{
  BstTyp n;
  
  n = ExtractNodeBST( e , &t , k , c );
  if (n!=NULL)
    DispBSTNode( n );
  return t;
}


/*----------------------------------------------------------------*/


/* FreeBST
 * Deallocate the memory used by either a Tree and its node datas.
 * "f" is the function to deallocate the memory used by the datas.
 */
void FreeBST( t , f )
     BstTyp t;
     void   (*f)(); 
{
  if (t!=NULL) {
    FreeBST( t->l, f );
    FreeBST( t->r, f );
    if (f!=NULL)
      f(t->dat);
    DispBSTNode(t);
  }
}


/******************************************************************
 *
 * Function to travel the trees.
 *
 *******************************************************************/

/* OrdenBST
 * Applies the procedure "p" to all the nodes of the tree "t", 
 * travelling in central orden.
 */
void OrdenBST( t , p )
     BstTyp t;
     void   (*p)();
{
  if (t!=NULL) {
    OrdenBST( t->l, p );
    p(t->dat);
    OrdenBST( t->r, p );
  }
}

/*----------------------------------------------------------------*/


/* PreOrdenBST
 * Applies the procedure "p" to all the nodes of the tree "t", 
 * travelling in pre-orden.
 */
void PreOrdenBST( t , p )
     BstTyp t;
     void   (*p)();
{
  if (t!=NULL) {
    p(t->dat);
    PreOrdenBST( t->l, p );
    PreOrdenBST( t->r, p );
  }
}

/*----------------------------------------------------------------*/


/* PostOrdenBST
 * Applies the procedure "p" to all the nodes of the tree "t", 
 * travelling in post-orden.
 */
void PostOrdenBST( t , p )
     BstTyp t;
     void   (*p)();
{
  if (t!=NULL) {
    PostOrdenBST( t->l, p );
    PostOrdenBST( t->r, p );
    p(t->dat);
  }
}

/*----------------------------------------------------------------*/



























