diff options
author | Joshua Leung <aligorith@gmail.com> | 2009-11-15 14:20:44 +0300 |
---|---|---|
committer | Joshua Leung <aligorith@gmail.com> | 2009-11-15 14:20:44 +0300 |
commit | 6468f21ddf25298f5b9d1c52955e185b368f496c (patch) | |
tree | a0401bd947c2f4b54a3cd797c33cd1dbcdd9f56e /source/blender/blenlib/BLI_dlrbTree.h | |
parent | 698086dfb1b3d5796115afed238b6d9225576ad8 (diff) |
Red-Black Tree Code Cleanups:
Added some more methods for the Red-Black Tree implementation in Blender (used for runtime viewing and searching of keyframes) which abstract away some of the lower-level handling of the BST (i.e. adding nodes without balancing and searching for nodes).
Also, improved the implementation of the jump next/prev keyframe operator so that it pops up an error message when the last keyframe in whatever direction is encountered.
Diffstat (limited to 'source/blender/blenlib/BLI_dlrbTree.h')
-rw-r--r-- | source/blender/blenlib/BLI_dlrbTree.h | 67 |
1 files changed, 62 insertions, 5 deletions
diff --git a/source/blender/blenlib/BLI_dlrbTree.h b/source/blender/blenlib/BLI_dlrbTree.h index a17cbbd1993..bced738b4e7 100644 --- a/source/blender/blenlib/BLI_dlrbTree.h +++ b/source/blender/blenlib/BLI_dlrbTree.h @@ -54,10 +54,10 @@ typedef struct DLRBT_Node { } DLRBT_Node; /* Red/Black defines for tree_col */ -enum eDLRBT_Colors { +typedef enum eDLRBT_Colors { DLRBT_BLACK= 0, DLRBT_RED, -}; +} eDLRBT_Colors; /* -------- */ @@ -70,9 +70,30 @@ typedef struct DLRBT_Tree { void *root; /* this should be based on DLRBT_Node-s */ } DLRBT_Tree; +/* Callback Types --------------------------------- */ + +/* return -1, 0, 1 for whether the given data is less than, equal to, or greater than the given node + * - node: <DLRBT_Node> the node to compare to + * - data: pointer to the relevant data or values stored in the bitpattern dependant on the function + */ +typedef short (*DLRBT_Comparator_FP)(void *node, void *data); + +/* return a new node instance wrapping the given data + * - data: pointer to the relevant data to create a subclass of node from + */ +typedef DLRBT_Node *(*DLRBT_NAlloc_FP)(void *data); + +/* update an existing node instance accordingly to be in sync with the given data * + * - node: <DLRBT_Node> the node to update + * - data: pointer to the relevant data or values stored in the bitpattern dependant on the function + */ +typedef void (*DLRBT_NUpdate_FP)(void *node, void *data); + /* ********************************************** */ /* Public API */ +/* ADT Management ------------------------------- */ + /* Create a new tree, and initialise as necessary */ DLRBT_Tree *BLI_dlrbTree_new(void); @@ -86,16 +107,52 @@ void BLI_dlrbTree_free(DLRBT_Tree *tree); void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree); +/* Searching ------------------------------------ */ -/* Balance the tree after the given element has been added to it - * (using custom code, in the Binary Tree way). +/* Find the node which matches or is the closest to the requested node */ +DLRBT_Node *BLI_dlrbTree_search(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + +/* Find the node which exactly matches the required data */ +DLRBT_Node *BLI_dlrbTree_search_exact(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + +/* Find the node which occurs immediately before the best matching node */ +DLRBT_Node *BLI_dlrbTree_search_prev(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + +/* Find the node which occurs immediately after the best matching node */ +DLRBT_Node *BLI_dlrbTree_search_next(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + + +/* Check whether there is a node matching the requested node */ +short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data); + + +/* Node Operations (Managed) --------------------- */ +/* These methods automate the process of adding/removing nodes from the BST, + * using the supplied data and callbacks */ -void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node); + +/* Add the given data to the tree, and return the node added */ +// NOTE: for duplicates, the update_cb is called (if available), and the existing node is returned +DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, + DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data); + /* Remove the given element from the tree and balance again */ // FIXME: this is not implemented yet... void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node); +/* Node Operations (Manual) --------------------- */ +/* These methods require custom code for creating BST nodes and adding them to the + * tree in special ways, such that the node can then be balanced. + * + * It is recommended that these methods are only used where the other method is too cumbersome... + */ + +/* Balance the tree after the given node has been added to it + * (using custom code, in the Binary Tree way). + */ +void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node); + /* ********************************************** */ #endif // BLI_DLRB_TREE_H |