mirror of https://github.com/lianthony/NT4.0
You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
121 lines
4.9 KiB
121 lines
4.9 KiB
/**************************************************************/
|
|
/* user interface header file for top down splay package */
|
|
/* based on Sleator & Tarjan's Self Adjusting Trees */
|
|
/* Author: Dov Harel, 12/9/1988 */
|
|
/* Modified to: */
|
|
/* compact (space optimization) */
|
|
/* return Dict_Status */
|
|
/* changed interfaces */
|
|
/* Dov Harel, 11/90 */
|
|
/**************************************************************/
|
|
|
|
typedef
|
|
/* type of a comparison function */
|
|
int (*cmp_rec_func)(void *, void *);
|
|
|
|
typedef struct tnode {
|
|
struct tnode *left; /* left child pointer */
|
|
struct tnode *right; /* right child pointer */
|
|
void *item; /* pointer to some structure */
|
|
} TreeNode;
|
|
|
|
typedef struct dictnode {
|
|
TreeNode *root; /* pointer to the root of a SAT */
|
|
long size; /* number of records in dictionary */
|
|
void * state; /* reserved for state info */
|
|
/* int (*cmp_rec)(void *, void *); comparison function pointer */
|
|
cmp_rec_func cmp_rec;
|
|
TreeNode* (*splay)(TreeNode *, void *, cmp_rec_func);
|
|
/* pointer to a splay function */
|
|
void (*print_rec)(void *); /* one line print function */
|
|
} Dictionary;
|
|
|
|
/*************************************************************************/
|
|
/***** Core functions (internal) *****/
|
|
/*************************************************************************/
|
|
|
|
|
|
TreeNode * /* returns the new root */
|
|
tdSplay( /* general top down splay */
|
|
TreeNode *root, /* the current root of the tree */
|
|
void *keyItem, /* pointer to a "key item" searched for */
|
|
int (*cmp)(void *, void *) );
|
|
/* pointer to a comparison function */
|
|
|
|
TreeNode*
|
|
tdSplayLeft(TreeNode* root);
|
|
|
|
TreeNode*
|
|
tdSplayRight(TreeNode* root);
|
|
|
|
void
|
|
print_tree_sat( /* prints the binary tree (indented right subtree,
|
|
followed by the root, followed by the indented
|
|
right dubtree) */
|
|
Dictionary * dp,
|
|
int indent); /* number of blanks to indent subtrees */
|
|
|
|
/*************************************************************************/
|
|
/*** Minimal Dictionary Operations: ***/
|
|
/*** ***/
|
|
/*** Dictionary *Dict_New(Cmp_rec*, Splay*, print_rec*) ***/
|
|
/*** ***/
|
|
/*** Dict_Status Dict_Find(Dictionary*, Item*) ***/
|
|
/*** Dict_Status Dict_Next(Dictionary*, Item*) ***/
|
|
/*** Dict_Status Dict_Prev(Dictionary*, Item*) ***/
|
|
/*** Dict_Status Dict_Insert(Dictionary*, Item*) ***/
|
|
/*** Dict_Status Dict_Delete(Dictionary*, Item**) ***/
|
|
/*** ***/
|
|
/*** Item* DICT_CURR_ITEM(Dict*) ***/
|
|
/*************************************************************************/
|
|
|
|
typedef enum {
|
|
SUCCESS,
|
|
ITEM_ALREADY_PRESENT,
|
|
ITEM_NOT_FOUND,
|
|
FIRST_ITEM,
|
|
LAST_ITEM,
|
|
EMPTY_DICTIONARY,
|
|
NULL_ITEM
|
|
}
|
|
Dict_Status;
|
|
|
|
#define DICT_CURR_ITEM(pDict) ( (pDict)->root->item )
|
|
|
|
#define DICT_EMPTY(pDict) ( (pDict)->root == NULL )
|
|
|
|
Dictionary*
|
|
Dict_New( /* returns a new dictionary node */
|
|
int (*cmp_rec) /* pointer to item comparison function */
|
|
(void *, void *),
|
|
TreeNode* (*splay) /* pointer to a splay function */
|
|
(TreeNode *, void *, cmp_rec_func),
|
|
|
|
void (*print_rec) /* pointer to one line item print routine */
|
|
(void *) );
|
|
|
|
Dict_Status
|
|
Dict_Find(
|
|
Dictionary* dp, /* Dictionary to be searched. */
|
|
void* item); /* Item searched for. */
|
|
|
|
Dict_Status
|
|
Dict_Next(
|
|
Dictionary* dp, /* Dictionary to be searched. */
|
|
void* item); /* A Key item. Advance to successor of item in dp. */
|
|
|
|
Dict_Status
|
|
Dict_Prev(
|
|
Dictionary* dp, /* Dictionary to be searched. */
|
|
void* item); /* A Key item. Retreat to predecessor of item in dp. */
|
|
|
|
Dict_Status
|
|
Dict_Insert( /* insert the given item into the tree */
|
|
Dictionary* dp, /* the modified dictionary */
|
|
void* item); /* the item to be inserted */
|
|
|
|
Dict_Status
|
|
Dict_Delete( /* delete the given item into from the tree */
|
|
Dictionary* dp, /* the modified dictionary */
|
|
void** pItem); /* IN: points to the (key) item to be deleted */
|
|
/* OUT: points to the item just deleted */
|