/* BinTree- a binary tree data structure. Requires the user provide
**          custom insert and search comparison functions. The optional free
**          function will be called on a node's value before deleting the node
**          if it is provided.
**
**          It is recommended that the insert function be such that any two
**          values will be considered unique (not equal), but the search
**          function can allow values to be equal with no nasty side-effects.
**          If a value is less (greater) than another value based on the
**          insertion comparison, it should be less (greater) than or equal to
**          the other value based on the search comparison. Both functions
**          should result in the same ordering regardless of the order of the
**          arguments (if a < b, b > a). If these rules are not followed,
**          behavior is undefined.
**
**          comp(a, b) should return </=/> zero if a is </=/> b
*/
#ifndef _JSW_BINTREE_H_
#define _JSW_BINTREE_H_

/* BinTree data structure, members should never be accessed directly */
typedef struct bintree_t BinTree;


/*******************       constructors/destructor         *******************/
/* initBinTree- returns an initialized BinTree data structure
**
** *input parameters*
** function      * icomp   comparison function for insertion/deletion
** function      * fcomp   comparison function for finding
** function      * freeVal function used to free values inserted into the tree
**                         if NULL, user is responsible for freeing values
**
** *return*
** BinTree       *         pointer to the tree structure or NULL on error
*/
BinTree *initBinTree(int (*icomp)(const void*, const void*),
                     int (*fcomp)(const void*, const void*),
                     void (*freeVal)(void*));

/* freeBinTree- frees a binary tree data structure
**
** *input parameters*
** BinTree       * bt    tree to free
*/
void freeBinTree(BinTree *bt);

/*******************           accessor functions          *******************/
/* bt_getLength- gets the number of nodes in the binary tree
**
** *input parameters*
** const BinTree * bt tree to get the length of
**
** *returns*
** unsigned int         number of nodes in the tree, or 0 if bt = NULL
*/
unsigned int bt_getLength(const BinTree *bt);

/* bt_getFirst- gets the first (smallest) value in the tree based on the
**              insert comparison function
**
** *input parameters*
** BinTree       * bt tree to get the first value in
**
** *returns*
** const void    *      first value stored in the tree
*/
const void *bt_getFirst(BinTree *bt);

/* bt_getLast- gets the last (largest) value in the tree based on the
**             insert comparison function
**
** *input parameters*
** BinTree       * bt tree to get the last value in
**
** *returns*
** const void    *      last value stored in the tree
*/
const void *bt_getLast(BinTree *bt);

/* bt_getNext- gets the next largest value in the tree after the previously
**             searched for value based on the insert comparison function
**
** *input parameters*
** BinTree       * bt tree to get the next value in
**
** *returns*
** const void    *      next value stored in the tree
*/
const void *bt_getNext(BinTree *bt);

/* bt_getCurrent- gets the last value searched for in the tree
**
** *input parameters*
** BinTree       * bt tree to get the last value searched for in
**
** *returns*
** const void    *      last value searched for in the tree
*/
const void *bt_getCurrent(BinTree *bt);

/* bt_getPrev- gets the next smallest value in the tree before the previously
**             searched for value based on the insert comparison function
**
** *input parameters*
** BinTree       * bt tree to get the next value in
**
** *returns*
** const void    *      previous value stored in the tree
*/
const void *bt_getPrev(BinTree *bt);

/* bt_findVal- finds the provided value in the tree or, if the provided value
**             is NULL, returns the next value matching the previous search
**             (based on fcomp function)
**
** *input parameters*
** BinTree       * bt tree to search in
** const void    * val  value to search for, if NULL, finds the next value
**                      that matches the prevoius search value
**                      (based on fcomp function)
**
** *return*
** void          *      the smallest value matching val, or, if val = NULL,
**                      the next biggest value matching the last non-null val
*/
const void *bt_findVal(BinTree *bt, const void *val);

/*******************           modifier functions          *******************/

/* bt_deleteFirst- deletes a node that matches the first value in the tree
**                 (based on the icomp function)
**
** *input parameters*
** BinTree       * bt tree to delete from
**
** *return*
** int                  0 if a value was successfully deleted
**                      < 0 if error (including not found)
*/
int bt_deleteFirst(BinTree *bt);

/* bt_deleteLast- deletes a node that matches the last value in the tree
**                (based on the icomp function)
**
** *input parameters*
** BinTree       * bt tree to delete from
**
** *return*
** int                  0 if a value was successfully deleted
**                      < 0 if error (including not found)
*/
int bt_deleteLast(BinTree *bt);

/* bt_deleteCurrent- deletes a node that matches the last value searched for
**                   in the tree (based on the icomp function)
**
** *input parameters*
** BinTree       * bt tree to delete from
**
** *return*
** int                  0 if a value was successfully deleted
**                      < 0 if error (including not found)
*/
int bt_deleteCurrent(BinTree *bt);

/* bt_deleteVal- deletes a node that matches the provided value in the tree
**               (based on the icomp function). If found, the node's value
**               will be deleted with the freeVal function
**
** *input parameters*
** BinTree       * bt tree to delete from
** const void    * val  value to match for deletion
**
** *return*
** int                  0 if a value was successfully deleted
**                      < 0 if error (including not found)
*/
int bt_deleteVal(BinTree *bt, const void *val);

/*  bt_deleteVal- inserts a node with the provided value into the tree
**               (based on the icomp function)
** 
** *input parameters*
** BinTree       * bt tree to insert into
** void          * val  value to insert
**
** *return*
** int                  0 if a value was successfully inserted
**                      < 0 if error
*/
int bt_insertVal(BinTree *bt, void *val);

#endif
