update
[cgds.git] / src / Tree.h
CommitLineData
a7868768
BA
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 */
20typedef 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 */
32typedef 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 */
41void _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 */
49Tree* _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 */
65Tree* tree_copy(
66 Tree* tree ///< "this" pointer.
67);
68
69/**
70 * @brief Check if the tree is empty.
71 */
72Bool tree_empty(
73 Tree* tree ///< "this" pointer.
74);
75
76/**
77 * @brief return current size of the tree (counting nodes).
78 */
79UInt tree_size(
80 Tree* tree ///< "this" pointer.
81);
82
83/**
84 * @brief Auxiliary function to get tree height.
85 */
86UInt _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 */
93UInt tree_height(
94 Tree* tree ///< "this" pointer.
95);
96
97/**
98 * @brief Check if a sub-tree is a leaf (without children).
99 */
100Bool 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 */
107void _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 */
128void* _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 */
148void _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 */
171void _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 */
194void _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 */
217void _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 */
225void 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 */
233void 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 */
241void tree_clear(
242 Tree* tree ///< "this" pointer.
243);
244
245/**
246 * @brief Destroy the tree: clear it, and free 'tree' pointer.
247 */
248void 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 */
259typedef 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 */
267typedef 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 */
276TreeIterator* 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 */
284void treeI_reset(
285 TreeIterator* treeI ///< "this" pointer.
286);
287
288/**
289 * @brief Tell if there is some data at the current index.
290 */
291Bool treeI_has_data(
292 TreeIterator* treeI ///< "this" pointer.
293);
294
295/**
296 * @brief Return current tree node.
297 */
298TreeNode* 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 */
325void treeI_move_next(
326 TreeIterator* treeI ///< "this" pointer.
327);
328
329/**
330 * @brief Free memory allocated for the iterator.
331 */
332void treeI_destroy(
333 TreeIterator* treeI ///< "this" pointer.
334);
335
336#endif