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.

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