initial commit
[cgds.git] / src / Tree.h
1 /**
2 * @file Tree.h
3 */
4
5 #ifndef CGDS_TREE_H
6 #define CGDS_TREE_H
7
8 #include <stdlib.h>
9 #include <string.h>
10 #include "cgds/safe_alloc.h"
11 #include "cgds/types.h"
12
13 //***********
14 // Tree logic
15 //***********
16
17 /**
18 * @brief Tree node, containing some generic data.
19 */
20 typedef struct TreeNode {
21 void* data; ///< Generic data contained in this node.
22 struct TreeNode* parent; ///< Pointer to parent node (NULL if node is root).
23 struct TreeNode* firstChild; ///< Pointer to the first child (if any).
24 struct TreeNode* lastChild; ///< Pointer to the last child (if any).
25 struct TreeNode* prev; ///< Pointer to the previous sibling (on the left).
26 struct TreeNode* next; ///< Pointer to the next sibling (on the right).
27 } TreeNode;
28
29 /**
30 * @brief Generic multi-ary tree.
31 */
32 typedef struct Tree {
33 TreeNode* root; ///< Root node of the tree.
34 size_t dataSize; ///< Size of *data at a tree node, in bytes.
35 UInt size; ///< Count nodes in the tree.
36 } Tree;
37
38 /**
39 * @brief Initialize an empty tree.
40 */
41 void _tree_init(
42 Tree* tree, ///< "this" pointer.
43 size_t dataSize ///< Size in bytes of a tree element.
44 );
45
46 /**
47 * @brief Return an allocated and initialized tree.
48 */
49 Tree* _tree_new(
50 size_t dataSize ///< Size in bytes of a tree node element.
51 );
52
53 /**
54 * @brief Return an allocated and initialized tree.
55 * @param type Type at a tree node (int, char*, ...).
56 *
57 * Usage: Tree* tree_new(<Type> type)
58 */
59 #define tree_new(type) \
60 _tree_new(sizeof(type))
61
62 /**
63 * @brief Copy constructor (works well if items do not have allocated sub-pointers).
64 */
65 Tree* tree_copy(
66 Tree* tree ///< "this" pointer.
67 );
68
69 /**
70 * @brief Check if the tree is empty.
71 */
72 Bool tree_empty(
73 Tree* tree ///< "this" pointer.
74 );
75
76 /**
77 * @brief return current size of the tree (counting nodes).
78 */
79 UInt tree_size(
80 Tree* tree ///< "this" pointer.
81 );
82
83 /**
84 * @brief Auxiliary function to get tree height.
85 */
86 UInt _tree_height_rekursiv(
87 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
88 );
89
90 /**
91 * @brief Return tree height (max depth from root to leaves).
92 */
93 UInt tree_height(
94 Tree* tree ///< "this" pointer.
95 );
96
97 /**
98 * @brief Check if a sub-tree is a leaf (without children).
99 */
100 Bool tree_is_leaf(
101 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
102 );
103
104 /**
105 * @brief Initialize tree root when the tree is empty.
106 */
107 void _tree_set_root(
108 Tree* tree, ///< "this" pointer.
109 void* data ///< Pointer to data to be assigned.
110 );
111
112 /**
113 * @brief Initialize tree root when the tree is empty.
114 * @param tree "this" pointer.
115 * @param data Data to be assigned.
116 *
117 * Usage: void tree_set_root(Tree* tree, void data)
118 */
119 #define tree_set_root(tree, data) \
120 { \
121 typeof((data)) tmp = data; \
122 _tree_set_root(tree, &tmp); \
123 }
124
125 /**
126 * @brief Return data contained in a given tree node.
127 */
128 void* _tree_get(
129 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
130 );
131
132 /**
133 * @brief Retrieve data contained in a given tree node.
134 * @param treeNode Pointer to a node in the "this" tree.
135 * @param data Data to be assigned.
136 *
137 * Usage: void tree_get(TreeNode* treeNode, void data)
138 */
139 #define tree_get(treeNode, data) \
140 { \
141 void* pData = _tree_get(treeNode); \
142 data = *((typeof(&data))pData); \
143 }
144
145 /**
146 * @brief Set (alter) data at tree node passed as argument.
147 */
148 void _tree_set(
149 Tree* tree, ///< "this" pointer.
150 TreeNode* treeNode, ///< Pointer to a node in the "this" tree.
151 void* data ///< Pointer to data to be assigned.
152 );
153
154 /**
155 * @brief Set (alter) data at tree node passed as argument.
156 * @param tree "this" pointer.
157 * @param treeNode Pointer to a node in the "this" tree.
158 * @param data Data to be assigned.
159 *
160 * Usage: void tree_set(Tree* tree, TreeNode* treeNode, void data)
161 */
162 #define tree_set(tree, treeNode, data) \
163 { \
164 typeof((data)) tmp = data; \
165 _tree_set(tree,treeNode,&tmp); \
166 }
167
168 /**
169 * @brief Add a child to current node children.
170 */
171 void _tree_add_child(
172 Tree* tree, ///< "this" pointer.
173 TreeNode* treeNode, ///< Pointer to a node in the "this" tree.
174 void* data ///< Pointer to data to be added.
175 );
176
177 /**
178 * @brief Add a child to current node children.
179 * @param tree "this" pointer.
180 * @param treeNode Pointer to a node in the "this" tree.
181 * @param data Data to be added.
182 *
183 * Usage: void tree_add_child(Tree* tree, TreeNode* treeNode, void data)
184 */
185 #define tree_add_child(tree,treeNode,data) \
186 { \
187 typeof((data)) tmp = data; \
188 _tree_add_child(tree,treeNode,&tmp); \
189 }
190
191 /**
192 * @brief Add a sibling to current node (after it on the right).
193 */
194 void _tree_add_sibling(
195 Tree* tree, ///< "this" pointer.
196 TreeNode* treeNode, ///< Pointer to a node in the "this" tree.
197 void* data ///< Pointer to data to be added.
198 );
199
200 /**
201 * @brief Add a sibling to current node (after it on the right).
202 * @param tree "this" pointer.
203 * @param treeNode Pointer to a node in the "this" tree.
204 * @param data Data to be added.
205 *
206 * Usage: void tree_add_sibling(Tree* tree, TreeNode* treeNode, void data)
207 */
208 #define tree_add_sibling(tree, treeNode, data) \
209 { \
210 typeof((data)) tmp = data; \
211 _tree_add_sibling(tree, treeNode, &tmp); \
212 }
213
214 /**
215 * @brief Auxiliary to remove a subtree.
216 */
217 void _tree_remove_rekursiv(
218 Tree* tree, ///< "this" pointer.
219 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
220 );
221
222 /**
223 * @brief Remove the whole subtree rooted at 'treeNode'.
224 */
225 void tree_remove(
226 Tree* tree, ///< "this" pointer.
227 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
228 );
229
230 /**
231 * @brief Remove children of the tree node given as argument.
232 */
233 void tree_rm_childs(
234 Tree* tree, ///< "this" pointer.
235 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
236 );
237
238 /**
239 * @brief Clear the entire tree.
240 */
241 void tree_clear(
242 Tree* tree ///< "this" pointer.
243 );
244
245 /**
246 * @brief Destroy the tree: clear it, and free 'tree' pointer.
247 */
248 void tree_destroy(
249 Tree* tree ///< "this" pointer.
250 );
251
252 //***************
253 // Iterator logic
254 //***************
255
256 /**
257 * @brief Type of tree search: depth first or breadth first walk.
258 */
259 typedef enum TreeIteratorMode {
260 IN_DEPTH = 0, ///< Depth first.
261 IN_BREADTH = 1 ///< Breadth first.
262 } TreeIteratorMode;
263
264 /**
265 * @brief Iterator on a tree object.
266 */
267 typedef struct TreeIterator {
268 Tree* tree; ///< Pointer to the tree to iterate over.
269 TreeNode* current; ///< Current iterator position.
270 TreeIteratorMode mode; ///< Mode of iteration (in depth or in breadth).
271 } TreeIterator;
272
273 /**
274 * @brief Obtain an iterator object, starting at tree root.
275 */
276 TreeIterator* tree_get_iterator(
277 Tree* tree, ///< Pointer to the tree to iterate over.
278 TreeIteratorMode mode ///< Mode of iteration (in depth or in breadth).
279 );
280
281 /**
282 * @brief (Re)set current position inside tree to root.
283 */
284 void treeI_reset(
285 TreeIterator* treeI ///< "this" pointer.
286 );
287
288 /**
289 * @brief Tell if there is some data at the current index.
290 */
291 Bool treeI_has_data(
292 TreeIterator* treeI ///< "this" pointer.
293 );
294
295 /**
296 * @brief Return current tree node.
297 */
298 TreeNode* treeI_get_raw(
299 TreeIterator* treeI ///< "this" pointer.
300 );
301
302 /**
303 * @brief Get data at current tree node.
304 * @param treeI "this" pointer.
305 * @param data Data to be assigned.
306 *
307 * Usage: void treeI_get(TreeIterator* treeI, void data)
308 */
309 #define treeI_get(treeI, data) \
310 tree_get(treeI->current, data)
311
312 /**
313 * @brief Set (alter) data at current tree node.
314 * @param treeI "this" pointer.
315 * @param data Data to be assigned.
316 *
317 * Usage: void treeI_set(TreeIterator* treeI, void data)
318 */
319 #define treeI_set(treeI, data) \
320 tree_set(treeI->tree, treeI->current, data)
321
322 /**
323 * @brief Move current iterator position forward (toward leaves).
324 */
325 void treeI_move_next(
326 TreeIterator* treeI ///< "this" pointer.
327 );
328
329 /**
330 * @brief Free memory allocated for the iterator.
331 */
332 void treeI_destroy(
333 TreeIterator* treeI ///< "this" pointer.
334 );
335
336 #endif