4d20741a38a29227ab551b7579ff1a234bae2ca7
[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 (shallow copy, ok for basic types).
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 Append a child to current node.
170 */
171 TreeNode* _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 * @return The newly added tree node.
183 *
184 * Usage: TreeNode* tree_add_child(Tree* tree, TreeNode* treeNode, void data)
185 */
186 #define tree_add_child(tree,treeNode,data) \
187 { \
188 typeof(data) tmp = data; \
189 _tree_add_child(tree, treeNode, &tmp); \
190 }
191
192 /**
193 * @brief Add a sibling to current node (after it on the right).
194 */
195 TreeNode* _tree_add_sibling(
196 Tree* tree, ///< "this" pointer.
197 TreeNode* treeNode, ///< Pointer to a node in the "this" tree.
198 void* data ///< Pointer to data to be added.
199 );
200
201 /**
202 * @brief Add a sibling to current node (after it on the right).
203 * @param tree "this" pointer.
204 * @param treeNode Pointer to a node in the "this" tree.
205 * @param data Data to be added.
206 * @return The newly added tree node.
207 *
208 * Usage: TreeNode* tree_add_sibling(Tree* tree, TreeNode* treeNode, void data)
209 */
210 #define tree_add_sibling(tree, treeNode, data) \
211 { \
212 typeof(data) tmp = data; \
213 _tree_add_sibling(tree, treeNode, &tmp); \
214 }
215
216 /**
217 * @brief Auxiliary to remove a subtree.
218 */
219 void _tree_remove_rekursiv(
220 Tree* tree, ///< "this" pointer.
221 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
222 );
223
224 /**
225 * @brief Remove the whole subtree rooted at 'treeNode'.
226 */
227 void tree_remove(
228 Tree* tree, ///< "this" pointer.
229 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
230 );
231
232 /**
233 * @brief Remove children of the tree node given as argument.
234 */
235 void tree_rm_childs(
236 Tree* tree, ///< "this" pointer.
237 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
238 );
239
240 /**
241 * @brief Clear the entire tree.
242 */
243 void tree_clear(
244 Tree* tree ///< "this" pointer.
245 );
246
247 /**
248 * @brief Destroy the tree: clear it, and free 'tree' pointer.
249 */
250 void tree_destroy(
251 Tree* tree ///< "this" pointer.
252 );
253
254 //***************
255 // Iterator logic
256 //***************
257
258 /**
259 * @brief Type of tree search: depth first or breadth first walk.
260 */
261 typedef enum TreeIteratorMode {
262 IN_DEPTH = 0, ///< Depth first.
263 IN_BREADTH = 1 ///< Breadth first.
264 } TreeIteratorMode;
265
266 /**
267 * @brief Iterator on a tree object.
268 */
269 typedef struct TreeIterator {
270 Tree* tree; ///< Pointer to the tree to iterate over.
271 TreeNode* current; ///< Current iterator position.
272 TreeIteratorMode mode; ///< Mode of iteration (in depth or in breadth).
273 } TreeIterator;
274
275 /**
276 * @brief Obtain an iterator object, starting at tree root.
277 */
278 TreeIterator* tree_get_iterator(
279 Tree* tree, ///< Pointer to the tree to iterate over.
280 TreeIteratorMode mode ///< Mode of iteration (in depth or in breadth).
281 );
282
283 /**
284 * @brief (Re)set current position inside tree to root.
285 */
286 void treeI_reset(
287 TreeIterator* treeI ///< "this" pointer.
288 );
289
290 /**
291 * @brief Tell if there is some data at the current index.
292 */
293 bool treeI_has_data(
294 TreeIterator* treeI ///< "this" pointer.
295 );
296
297 /**
298 * @brief Return current tree node.
299 */
300 TreeNode* treeI_get_raw(
301 TreeIterator* treeI ///< "this" pointer.
302 );
303
304 /**
305 * @brief Get data at current tree node.
306 * @param treeI "this" pointer.
307 * @param data Data to be assigned.
308 *
309 * Usage: void treeI_get(TreeIterator* treeI, void data)
310 */
311 #define treeI_get(treeI, data) \
312 tree_get(treeI->current, data)
313
314 /**
315 * @brief Set (alter) data at current tree node.
316 * @param treeI "this" pointer.
317 * @param data Data to be assigned.
318 *
319 * Usage: void treeI_set(TreeIterator* treeI, void data)
320 */
321 #define treeI_set(treeI, data) \
322 tree_set(treeI->tree, treeI->current, data)
323
324 /**
325 * @brief Move current iterator position forward (toward leaves).
326 */
327 void treeI_move_next(
328 TreeIterator* treeI ///< "this" pointer.
329 );
330
331 /**
332 * @brief Free memory allocated for the iterator.
333 */
334 void treeI_destroy(
335 TreeIterator* treeI ///< "this" pointer.
336 );
337
338 #endif