[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [24568] trunk/blender/source/blender: Red-Black Tree Code Cleanups:
Joshua Leung
aligorith at gmail.com
Sun Nov 15 12:20:44 CET 2009
Revision: 24568
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=24568
Author: aligorith
Date: 2009-11-15 12:20:44 +0100 (Sun, 15 Nov 2009)
Log Message:
-----------
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.
Modified Paths:
--------------
trunk/blender/source/blender/blenlib/BLI_dlrbTree.h
trunk/blender/source/blender/blenlib/intern/DLRB_tree.c
trunk/blender/source/blender/editors/animation/keyframes_draw.c
trunk/blender/source/blender/editors/armature/poseSlide.c
trunk/blender/source/blender/editors/include/ED_keyframes_draw.h
trunk/blender/source/blender/editors/screen/screen_ops.c
Modified: trunk/blender/source/blender/blenlib/BLI_dlrbTree.h
===================================================================
--- trunk/blender/source/blender/blenlib/BLI_dlrbTree.h 2009-11-15 08:34:31 UTC (rev 24567)
+++ trunk/blender/source/blender/blenlib/BLI_dlrbTree.h 2009-11-15 11:20:44 UTC (rev 24568)
@@ -54,10 +54,10 @@
} 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 @@
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_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
Modified: trunk/blender/source/blender/blenlib/intern/DLRB_tree.c
===================================================================
--- trunk/blender/source/blender/blenlib/intern/DLRB_tree.c 2009-11-15 08:34:31 UTC (rev 24567)
+++ trunk/blender/source/blender/blenlib/intern/DLRB_tree.c 2009-11-15 11:20:44 UTC (rev 24568)
@@ -130,6 +130,155 @@
}
/* *********************************************** */
+/* Tree Search Utilities */
+
+/* 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)
+{
+ DLRBT_Node *node = (tree) ? tree->root : NULL;
+ short found= 0;
+
+ /* check that there is a comparator to use */
+ // TODO: if no comparator is supplied, try using the one supplied with the tree...
+ if (cmp_cb == NULL)
+ return NULL;
+
+ /* iteratively perform this search */
+ while (node && found==0)
+ {
+ /* check if traverse further or not
+ * NOTE: it is assumed that the values will be unit values only
+ */
+ switch (cmp_cb(node, search_data)) {
+ case -1: /* data less than node */
+ if (node->left)
+ node= node->left;
+ else
+ found= 1;
+ break;
+
+ case 1: /* data greater than node */
+ if (node->right)
+ node= node->right;
+ else
+ found= 1;
+ break;
+
+ default: /* data equals node */
+ found= 1;
+ break;
+ }
+ }
+
+ /* return the nearest matching node */
+ return node;
+}
+
+/* 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)
+{
+ DLRBT_Node *node = (tree) ? tree->root : NULL;
+ short found= 0;
+
+ /* check that there is a comparator to use */
+ // TODO: if no comparator is supplied, try using the one supplied with the tree...
+ if (cmp_cb == NULL)
+ return NULL;
+
+ /* iteratively perform this search */
+ while (node && found==0)
+ {
+ /* check if traverse further or not
+ * NOTE: it is assumed that the values will be unit values only
+ */
+ switch (cmp_cb(node, search_data)) {
+ case -1: /* data less than node */
+ if (node->left)
+ node= node->left;
+ else
+ found= -1;
+ break;
+
+ case 1: /* data greater than node */
+ if (node->right)
+ node= node->right;
+ else
+ found= -1;
+ break;
+
+ default: /* data equals node */
+ found= 1;
+ break;
+ }
+ }
+
+ /* return the nearest matching node */
+ return (found == 1) ? (node) : (NULL);
+}
+
+/* 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)
+{
+ DLRBT_Node *node;
+
+ /* check that there is a comparator to use */
+ // TODO: if no comparator is supplied, try using the one supplied with the tree...
+ if (cmp_cb == NULL)
+ return NULL;
+
+ /* get the node which best matches this description */
+ node= BLI_dlrbTree_search(tree, cmp_cb, search_data);
+
+ if (node) {
+ /* if the item we're searching for is greater than the node found, we've found the match */
+ if (cmp_cb(node, search_data) > 0)
+ return node;
+
+ /* return the previous node otherwise */
+ // NOTE: what happens if there is no previous node?
+ return node->prev;
+ }
+
+ /* nothing matching was found */
+ return NULL;
+}
+
+/* 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)
+{
+ DLRBT_Node *node;
+
+ /* check that there is a comparator to use */
+ // TODO: if no comparator is supplied, try using the one supplied with the tree...
+ if (cmp_cb == NULL)
+ return NULL;
+
+ /* get the node which best matches this description */
+ node= BLI_dlrbTree_search(tree, cmp_cb, search_data);
+
+ if (node) {
+ /* if the item we're searching for is less than the node found, we've found the match */
+ if (cmp_cb(node, search_data) < 0)
+ return node;
+
+ /* return the previous node otherwise */
+ // NOTE: what happens if there is no previous node?
+ return node->next;
+ }
+
+ /* nothing matching was found */
+ return NULL;
+}
+
+
+/* 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)
+{
+ /* check if an exact search throws up anything... */
+ return (BLI_dlrbTree_search_exact(tree, cmp_cb, search_data) != NULL);
+}
+
+/* *********************************************** */
/* Tree Relationships Utilities */
/* get the 'grandparent' - the parent of the parent - of the given node */
@@ -161,6 +310,7 @@
/* *********************************************** */
/* Tree Rotation Utilities */
+/* make right child of 'root' the new root */
static void rotate_left (DLRBT_Tree *tree, DLRBT_Node *root)
{
DLRBT_Node **root_slot, *pivot;
@@ -194,6 +344,7 @@
*root_slot= pivot;
}
+/* make the left child of the 'root' the new root */
static void rotate_right (DLRBT_Tree *tree, DLRBT_Node *root)
{
DLRBT_Node **root_slot, *pivot;
@@ -332,7 +483,7 @@
/* Balance the tree after the given element has been added to it
* (using custom code, in the Binary Tree way).
*/
-void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node)
+void BLI_dlrbTree_insert (DLRBT_Tree *tree, DLRBT_Node *node)
{
/* sanity checks */
if ((tree == NULL) || (node == NULL))
@@ -345,6 +496,90 @@
insert_check_1(tree, 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)
+{
+ DLRBT_Node *parNode, *node=NULL;
+ short new_node = 0;
+
+ /* sanity checks */
+ if (tree == NULL)
+ return NULL;
+
+ // TODO: if no comparator is supplied, try using the one supplied with the tree...
+ if (cmp_cb == NULL)
+ return NULL;
+ // TODO: if no allocator is supplied, try using the one supplied with the tree...
+ if (new_cb == NULL)
+ return NULL;
+ // TODO: if no updater is supplied, try using the one supplied with the tree...
+
+ /* try to find the nearest node to this one */
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list