Spelling Cleanup
[blender.git] / source / blender / blenlib / BLI_dlrbTree.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2009 Blender Foundation, Joshua Leung
19  * All rights reserved.
20  *
21  * Contributor(s): Joshua Leung (original author)
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 #ifndef __BLI_DLRBTREE_H__
27 #define __BLI_DLRBTREE_H__
28
29 /** \file BLI_dlrbTree.h
30  *  \ingroup bli
31  *  \author Joshua Leung
32  */
33
34 /* Double-Linked Red-Black Tree Implementation:
35  * 
36  * This is simply a Red-Black Tree implementation whose nodes can later
37  * be arranged + retrieved as elements in a Double-Linked list (i.e. ListBase).
38  * The Red-Black Tree implementation is based on the methods defined by Wikipedia.
39  */
40
41 /* ********************************************** */
42 /* Data Types and Type Defines  */
43
44 /* Base Structs --------------------------------- */
45
46 /* Basic Layout for a Node */
47 typedef struct DLRBT_Node {
48         /* ListBase capabilities */
49         struct DLRBT_Node *next, *prev;         
50         
51         /* Tree Associativity settings */
52         struct DLRBT_Node *left, *right;
53         struct DLRBT_Node *parent;
54         
55         char tree_col;
56         /* ... for nice alignment, next item should usually be a char too... */
57 } DLRBT_Node;
58
59 /* Red/Black defines for tree_col */
60 typedef enum eDLRBT_Colors {
61         DLRBT_BLACK= 0,
62         DLRBT_RED,
63 } eDLRBT_Colors;
64
65 /* -------- */
66
67 /* The Tree Data */
68 typedef struct DLRBT_Tree {
69         /* ListBase capabilities */
70         void *first, *last;                     /* these should be based on DLRBT_Node-s */
71
72         /* Root Node */
73         void *root;                                     /* this should be based on DLRBT_Node-s */
74 } DLRBT_Tree;
75
76 /* Callback Types --------------------------------- */
77
78 /* return -1, 0, 1 for whether the given data is less than, equal to, or greater than the given node 
79  *      - node: <DLRBT_Node> the node to compare to
80  *      - data: pointer to the relevant data or values stored in the bitpattern dependent on the function
81  */
82 typedef short (*DLRBT_Comparator_FP)(void *node, void *data);
83
84 /* return a new node instance wrapping the given data 
85  *      - data: pointer to the relevant data to create a subclass of node from
86  */
87 typedef DLRBT_Node *(*DLRBT_NAlloc_FP)(void *data);
88
89 /* update an existing node instance accordingly to be in sync with the given data *     
90  *      - node: <DLRBT_Node> the node to update
91  *      - data: pointer to the relevant data or values stored in the bitpattern dependent on the function
92  */
93 typedef void (*DLRBT_NUpdate_FP)(void *node, void *data);
94
95 /* ********************************************** */
96 /* Public API */
97
98 /* ADT Management ------------------------------- */
99
100 /* Create a new tree, and initialise as necessary */
101 DLRBT_Tree *BLI_dlrbTree_new(void);
102
103 /* Initialises some given trees */
104 void BLI_dlrbTree_init(DLRBT_Tree *tree);
105
106 /* Free some tree */
107 void BLI_dlrbTree_free(DLRBT_Tree *tree);
108
109 /* Make sure the tree's Double-Linked list representation is valid */
110 void BLI_dlrbTree_linkedlist_sync(DLRBT_Tree *tree);
111
112
113 /* Searching ------------------------------------ */
114
115 /* Find the node which matches or is the closest to the requested node */
116 DLRBT_Node *BLI_dlrbTree_search(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
117
118 /* Find the node which exactly matches the required data */
119 DLRBT_Node *BLI_dlrbTree_search_exact(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
120
121 /* Find the node which occurs immediately before the best matching node */
122 DLRBT_Node *BLI_dlrbTree_search_prev(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
123
124 /* Find the node which occurs immediately after the best matching node */
125 DLRBT_Node *BLI_dlrbTree_search_next(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
126
127
128 /* Check whether there is a node matching the requested node */
129 short BLI_dlrbTree_contains(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, void *search_data);
130
131
132 /* Node Operations (Managed) --------------------- */
133 /* These methods automate the process of adding/removing nodes from the BST, 
134  * using the supplied data and callbacks
135  */
136
137 /* Add the given data to the tree, and return the node added */
138 // NOTE: for duplicates, the update_cb is called (if available), and the existing node is returned
139 DLRBT_Node *BLI_dlrbTree_add(DLRBT_Tree *tree, DLRBT_Comparator_FP cmp_cb, 
140                         DLRBT_NAlloc_FP new_cb, DLRBT_NUpdate_FP update_cb, void *data);
141
142
143 /* Remove the given element from the tree and balance again */
144 // FIXME: this is not implemented yet... 
145 // void BLI_dlrbTree_remove(DLRBT_Tree *tree, DLRBT_Node *node);
146
147 /* Node Operations (Manual) --------------------- */
148 /* These methods require custom code for creating BST nodes and adding them to the 
149  * tree in special ways, such that the node can then be balanced.
150  *
151  * It is recommended that these methods are only used where the other method is too cumbersome...
152  */
153
154 /* Balance the tree after the given node has been added to it 
155  * (using custom code, in the Binary Tree way).
156  */
157 void BLI_dlrbTree_insert(DLRBT_Tree *tree, DLRBT_Node *node);
158
159 /* ********************************************** */
160
161 #endif // __BLI_DLRBTREE_H__