/*
 * tree.h
 * A package for managing generic binary trees.
 */

/* Representation of a binary tree node: */
struct _Node
{
  struct _Node  *p_parent;    /* Points to the parent node
                                 (or NULL in case of the tree root). */
  void          *p_object;    /* Points to the object stored in the node. */
  struct _Node  *p_right;     /* Points to the right child (or NULL). */
  struct _Node  *p_left;      /* Points to the left child (or NULL). */
};

typedef struct _Node Node;

/* Pointer to a function that receives two pointers (to objects), and
   returns a negative integer, a positive integer or zero - indicating
   whether the first object is greater than, less than or equals the second
   object. */
typedef int (*Comp_func) (const void *, const void *);

/* Representation of a binary tree: */
struct _Tree
{
  Node      *p_root;          /* Points to the root node
                                 (or NULL if the tree is empty). */
  int       n_objects;        /* Number of objects stored in the tree. */
  Comp_func f_comp;           /* The comparison function used to manage
                                 the tree order. */
  int       is_owner;         /* Does the tree own its objects (and is
                                 responsible for freeing them). */
};

typedef struct _Tree Tree;

/* ------------------------------------------------------------------------
 * Function: tree_init
 * Purpose:  Initialize a binary tree.
 * Input:    f_comp   - A pointer to a comparison function.
 *           is_owner - Should the tree own its objects and be
 *                      responsible for freeing them.
 * Returns:  A pointer to an allocated tree.
 *           Note that this pointer should eventually be freed using 
 *           tree_reset() and then free().
 */
Tree *tree_init (Comp_func f_comp, int is_owner);

/* ------------------------------------------------------------------------
 * Function: tree_insert
 * Purpose:  Insert an object to a binary tree.
 * Input:    p_tree - The binary tree.
 *           p_obj  - A pointer to the inserted object.
 * Returns:  Nothing.
 */
void tree_insert (Tree *p_tree, void *p_obj);

/* ------------------------------------------------------------------------
 * Function: tree_find
 * Purpose:  Find an object in a binary tree.
 * Input:    p_tree - The binary tree.
 *           p_obj  - A pointer to the queried object.
 * Returns:  A pointer to the node that contains the queried object,
 *           or NULL if the object is not found in the tree.
 */
const Node *tree_find (const Tree *p_tree, void *p_obj);

/* ------------------------------------------------------------------------
 * Function: tree_delete
 * Purpose:  Delete an object from a binary tree.
 * Input:    p_tree - The binary tree.
 *           p_obj  - A pointer to the deleted object.
 * Returns:  Non-zero in case the object was successfully deleted,
 *           or 0 if the object is not found in the tree.
 */
int tree_delete (Tree *p_tree, void *p_obj);

/* ------------------------------------------------------------------------
 * Function: tree_reset
 * Purpose:  Delete all objects from a binary tree.
 * Input:    p_tree - The binary tree.
 * Returns:  Nothing.
 */
void tree_reset (Tree *p_tree);

/* ------------------------------------------------------------------------
 * Function: tree_min
 * Purpose:  Get the minimal node in the tree.
 * Input:    p_tree - The binary tree.
 * Returns:  A pointer to the minimal node,
 *           or NULL if the tree is empty.
 */
const Node *tree_min (const Tree *p_tree);

/* ------------------------------------------------------------------------
 * Function: tree_next
 * Purpose:  Get the successor node in the tree.
 * Input:    p_node - A pointer to the current node.
 * Returns:  A pointer to the successor node,
 *           or NULL if the node does not have a successor.
 */
const Node *tree_next (const Node *p_node);

/* ------------------------------------------------------------------------
 * Function: tree_max
 * Purpose:  Get the maximal node in the tree.
 * Input:    p_tree - The binary tree.
 * Returns:  A pointer to the maximal node,
 *           or NULL if the tree is empty.
 */
const Node *tree_max (const Tree *p_tree);

/* ------------------------------------------------------------------------
 * Function: tree_prev
 * Purpose:  Get the predecessor node in the tree.
 * Input:    p_node - A pointer to the current node.
 * Returns:  A pointer to the predecessor node,
 *           or NULL if the node does not have a predecessor.
 */
const Node *tree_prev (const Node *p_node);