/***********************************
  (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)

  InitBST : init this module

  ************************************/

#ifndef libst_H
#define libst_H


#include "listdh.h"


/*
 * Nodes of the Binary Search Trees.
 */

typedef void * DataBstTyp;

typedef struct bstn { DataBstTyp dat;    /* data.                 */
		      struct bstn *l,*r; /* left and right links. */
		    } BstNodeTyp, *BstTyp;

/* InitBST
 * Init the module
 */
extern void InitBST();


/* StatBST
 * Number of asked  and released bs nodes
 */
extern void StatBST(/* new, released */);
/*       int * new, *released; */


/* CreateBST
 * Creates an empty tree.
 */
#define CreateBST() (BstTyp)NULL


/* IsEmptyBST
 * TRUE if "t" is an empty tree.
 */
#define IsEmptyBST(t) (t==NULL)


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


/* 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.
 */
extern BstTyp InsertBST( /* e , t , f */ );
/* DataBstTyp e;
   BstTyp     t;
   int        (*f)(); */


/* 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.
 */
extern BstTyp LookForBST( /* e , t , k , c */ );
/* DataBstTyp e;
   BstTyp     t;
   int        (*k)();
   boolean    (*c)();  */


/* 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.
 */
extern BstTyp ExtractNodeBST( /* e , pt , k , c */ );
/* DataBstTyp e;
   BstTyp     *pt;
   int        (*k)();
   boolean    (*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.
 */
extern BstTyp RemoveNodeBST( /* t , e , k , c */ );
/* DataBstTyp e;
   BstTyp     t;
   int        (*k)();
   boolean    (*c)(); */


/* FreeBST
 * Deallocate the memory used by either a Tree and its datas.
 * "f" is the function to deallocate the memory used by the datas.
 */
extern void FreeBST( /* t , f */ );
/* BstTyp t;
   void   (*f)(); */


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

/* OrdenBST
 * Applies the procedure "p" to all the nodes of the tree "t",
 * travelling in central orden.
 */
extern void OrdenBST( /* t , p */ );
/*  BstTYp t;
    void   (*p)(); */


/* PreOrdenBST
 * Applies the procedure "p" to all the nodes of the tree "t",
 * travelling in pre-orden.
 */
extern void PreOrdenBST( /* t , p */ );
/*  BstTYp t;
    void   (*p)(); */


/* PostOrdenBST
 * Applies the procedure "p" to all the nodes of the tree "t",
 * travelling in post-orden.
 */
extern void PostOrdenBST( /* t , p */ );
/*  BstTYp t;
    void   (*p)(); */



#endif


