Now using 2 spaces instead of tabs. Fix copyright years. Improve documentation
[cgds.git] / src / Tree.h
... / ...
CommitLineData
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{ \
61 _tree_new(sizeof(type)); \
62}
63
64/**
65 * @brief Copy constructor (shallow copy, ok for basic types).
66 */
67Tree* tree_copy(
68 Tree* tree ///< "this" pointer.
69);
70
71/**
72 * @brief Check if the tree is empty.
73 */
74bool tree_empty(
75 Tree* tree ///< "this" pointer.
76);
77
78/**
79 * @brief return current size of the tree (counting nodes).
80 */
81UInt tree_size(
82 Tree* tree ///< "this" pointer.
83);
84
85/**
86 * @brief Auxiliary function to get tree height.
87 */
88UInt _tree_height_rekursiv(
89 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
90);
91
92/**
93 * @brief Return tree height (max depth from root to leaves).
94 */
95UInt tree_height(
96 Tree* tree ///< "this" pointer.
97);
98
99/**
100 * @brief Check if a sub-tree is a leaf (without children).
101 */
102bool tree_is_leaf(
103 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
104);
105
106/**
107 * @brief Initialize tree root when the tree is empty.
108 */
109void _tree_set_root(
110 Tree* tree, ///< "this" pointer.
111 void* data ///< Pointer to data to be assigned.
112);
113
114/**
115 * @brief Initialize tree root when the tree is empty.
116 * @param tree "this" pointer.
117 * @param data Data to be assigned.
118 *
119 * Usage: void tree_set_root(Tree* tree, void data)
120 */
121#define tree_set_root(tree, data) \
122{ \
123 typeof((data)) tmp = data; \
124 _tree_set_root(tree, &tmp); \
125}
126
127/**
128 * @brief Return data contained in a given tree node.
129 */
130void* _tree_get(
131 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
132);
133
134/**
135 * @brief Retrieve data contained in a given tree node.
136 * @param treeNode Pointer to a node in the "this" tree.
137 * @param data Data to be assigned.
138 *
139 * Usage: void tree_get(TreeNode* treeNode, void data)
140 */
141#define tree_get(treeNode, data) \
142{ \
143 void* pData = _tree_get(treeNode); \
144 data = *((typeof(&data))pData); \
145}
146
147/**
148 * @brief Set (alter) data at tree node passed as argument.
149 */
150void _tree_set(
151 Tree* tree, ///< "this" pointer.
152 TreeNode* treeNode, ///< Pointer to a node in the "this" tree.
153 void* data ///< Pointer to data to be assigned.
154);
155
156/**
157 * @brief Set (alter) data at tree node passed as argument.
158 * @param tree "this" pointer.
159 * @param treeNode Pointer to a node in the "this" tree.
160 * @param data Data to be assigned.
161 *
162 * Usage: void tree_set(Tree* tree, TreeNode* treeNode, void data)
163 */
164#define tree_set(tree, treeNode, data) \
165{ \
166 typeof((data)) tmp = data; \
167 _tree_set(tree,treeNode,&tmp); \
168}
169
170/**
171 * @brief Add a child to current node children.
172 */
173void _tree_add_child(
174 Tree* tree, ///< "this" pointer.
175 TreeNode* treeNode, ///< Pointer to a node in the "this" tree.
176 void* data ///< Pointer to data to be added.
177);
178
179/**
180 * @brief Add a child to current node children.
181 * @param tree "this" pointer.
182 * @param treeNode Pointer to a node in the "this" tree.
183 * @param data Data to be added.
184 *
185 * Usage: void tree_add_child(Tree* tree, TreeNode* treeNode, void data)
186 */
187#define tree_add_child(tree,treeNode,data) \
188{ \
189 typeof((data)) tmp = data; \
190 _tree_add_child(tree,treeNode,&tmp); \
191}
192
193/**
194 * @brief Add a sibling to current node (after it on the right).
195 */
196void _tree_add_sibling(
197 Tree* tree, ///< "this" pointer.
198 TreeNode* treeNode, ///< Pointer to a node in the "this" tree.
199 void* data ///< Pointer to data to be added.
200);
201
202/**
203 * @brief Add a sibling to current node (after it on the right).
204 * @param tree "this" pointer.
205 * @param treeNode Pointer to a node in the "this" tree.
206 * @param data Data to be added.
207 *
208 * Usage: void 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 */
219void _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 */
227void 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 */
235void 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 */
243void tree_clear(
244 Tree* tree ///< "this" pointer.
245);
246
247/**
248 * @brief Destroy the tree: clear it, and free 'tree' pointer.
249 */
250void 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 */
261typedef 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 */
269typedef 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 */
278TreeIterator* 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 */
286void treeI_reset(
287 TreeIterator* treeI ///< "this" pointer.
288);
289
290/**
291 * @brief Tell if there is some data at the current index.
292 */
293bool treeI_has_data(
294 TreeIterator* treeI ///< "this" pointer.
295);
296
297/**
298 * @brief Return current tree node.
299 */
300TreeNode* 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 */
327void treeI_move_next(
328 TreeIterator* treeI ///< "this" pointer.
329);
330
331/**
332 * @brief Free memory allocated for the iterator.
333 */
334void treeI_destroy(
335 TreeIterator* treeI ///< "this" pointer.
336);
337
338#endif