Some fixes + improvements (Vector) + code reformatting
[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 {
e45132ac
BA
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).
a7868768
BA
27} TreeNode;
28
29/**
30 * @brief Generic multi-ary tree.
31 */
32typedef struct Tree {
e45132ac
BA
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.
a7868768
BA
36} Tree;
37
38/**
39 * @brief Initialize an empty tree.
40 */
41void _tree_init(
e45132ac
BA
42 Tree* tree, ///< "this" pointer.
43 size_t dataSize ///< Size in bytes of a tree element.
a7868768
BA
44);
45
46/**
47 * @brief Return an allocated and initialized tree.
48 */
49Tree* _tree_new(
e45132ac 50 size_t dataSize ///< Size in bytes of a tree node element.
a7868768
BA
51);
52
53/**
54 * @brief Return an allocated and initialized tree.
55 * @param type Type at a tree node (int, char*, ...).
1ff641f9 56 *
a7868768
BA
57 * Usage: Tree* tree_new(<Type> type)
58 */
59#define tree_new(type) \
eed1b5d2 60 _tree_new(sizeof(type))
a7868768
BA
61
62/**
1ff641f9 63 * @brief Copy constructor (shallow copy, ok for basic types).
a7868768
BA
64 */
65Tree* tree_copy(
e45132ac 66 Tree* tree ///< "this" pointer.
a7868768
BA
67);
68
69/**
70 * @brief Check if the tree is empty.
71 */
1ff641f9 72bool tree_empty(
e45132ac 73 Tree* tree ///< "this" pointer.
a7868768
BA
74);
75
76/**
77 * @brief return current size of the tree (counting nodes).
78 */
79UInt tree_size(
e45132ac 80 Tree* tree ///< "this" pointer.
a7868768
BA
81);
82
83/**
84 * @brief Auxiliary function to get tree height.
85 */
86UInt _tree_height_rekursiv(
e45132ac 87 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
a7868768
BA
88);
89
90/**
91 * @brief Return tree height (max depth from root to leaves).
92 */
93UInt tree_height(
e45132ac 94 Tree* tree ///< "this" pointer.
a7868768
BA
95);
96
97/**
98 * @brief Check if a sub-tree is a leaf (without children).
99 */
1ff641f9 100bool tree_is_leaf(
e45132ac 101 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
a7868768
BA
102);
103
104/**
105 * @brief Initialize tree root when the tree is empty.
106 */
107void _tree_set_root(
e45132ac
BA
108 Tree* tree, ///< "this" pointer.
109 void* data ///< Pointer to data to be assigned.
a7868768
BA
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.
1ff641f9 116 *
a7868768
BA
117 * Usage: void tree_set_root(Tree* tree, void data)
118 */
119#define tree_set_root(tree, data) \
120{ \
eed1b5d2 121 typeof(data) tmp = data; \
e45132ac 122 _tree_set_root(tree, &tmp); \
a7868768
BA
123}
124
125/**
126 * @brief Return data contained in a given tree node.
127 */
128void* _tree_get(
e45132ac 129 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
a7868768
BA
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.
1ff641f9 136 *
a7868768
BA
137 * Usage: void tree_get(TreeNode* treeNode, void data)
138 */
139#define tree_get(treeNode, data) \
140{ \
e45132ac
BA
141 void* pData = _tree_get(treeNode); \
142 data = *((typeof(&data))pData); \
a7868768
BA
143}
144
145/**
146 * @brief Set (alter) data at tree node passed as argument.
147 */
148void _tree_set(
e45132ac
BA
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.
a7868768
BA
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.
1ff641f9 159 *
a7868768
BA
160 * Usage: void tree_set(Tree* tree, TreeNode* treeNode, void data)
161 */
162#define tree_set(tree, treeNode, data) \
163{ \
eed1b5d2
BA
164 typeof(data) tmp = data; \
165 _tree_set(tree, treeNode, &tmp); \
a7868768
BA
166}
167
168/**
7820a2aa 169 * @brief Append a child to current node.
a7868768 170 */
7820a2aa 171TreeNode* _tree_add_child(
e45132ac
BA
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.
a7868768
BA
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.
7820a2aa 182 * @return The newly added tree node.
1ff641f9 183 *
7820a2aa 184 * Usage: TreeNode* tree_add_child(Tree* tree, TreeNode* treeNode, void data)
a7868768
BA
185 */
186#define tree_add_child(tree,treeNode,data) \
187{ \
eed1b5d2
BA
188 typeof(data) tmp = data; \
189 _tree_add_child(tree, treeNode, &tmp); \
a7868768
BA
190}
191
192/**
193 * @brief Add a sibling to current node (after it on the right).
194 */
7820a2aa 195TreeNode* _tree_add_sibling(
e45132ac
BA
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.
a7868768
BA
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.
7820a2aa 206 * @return The newly added tree node.
1ff641f9 207 *
7820a2aa 208 * Usage: TreeNode* tree_add_sibling(Tree* tree, TreeNode* treeNode, void data)
a7868768
BA
209 */
210#define tree_add_sibling(tree, treeNode, data) \
211{ \
eed1b5d2 212 typeof(data) tmp = data; \
e45132ac 213 _tree_add_sibling(tree, treeNode, &tmp); \
a7868768
BA
214}
215
216/**
217 * @brief Auxiliary to remove a subtree.
218 */
219void _tree_remove_rekursiv(
e45132ac
BA
220 Tree* tree, ///< "this" pointer.
221 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
a7868768
BA
222);
223
224/**
225 * @brief Remove the whole subtree rooted at 'treeNode'.
226 */
227void tree_remove(
e45132ac
BA
228 Tree* tree, ///< "this" pointer.
229 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
a7868768
BA
230);
231
232/**
233 * @brief Remove children of the tree node given as argument.
234 */
235void tree_rm_childs(
e45132ac
BA
236 Tree* tree, ///< "this" pointer.
237 TreeNode* treeNode ///< Pointer to a node in the "this" tree.
a7868768
BA
238);
239
240/**
241 * @brief Clear the entire tree.
242 */
243void tree_clear(
e45132ac 244 Tree* tree ///< "this" pointer.
a7868768
BA
245);
246
247/**
248 * @brief Destroy the tree: clear it, and free 'tree' pointer.
249 */
250void tree_destroy(
e45132ac 251 Tree* tree ///< "this" pointer.
a7868768
BA
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 {
e45132ac
BA
262 IN_DEPTH = 0, ///< Depth first.
263 IN_BREADTH = 1 ///< Breadth first.
a7868768
BA
264} TreeIteratorMode;
265
266/**
267 * @brief Iterator on a tree object.
268 */
269typedef struct TreeIterator {
e45132ac
BA
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).
a7868768
BA
273} TreeIterator;
274
275/**
276 * @brief Obtain an iterator object, starting at tree root.
277 */
278TreeIterator* tree_get_iterator(
e45132ac
BA
279 Tree* tree, ///< Pointer to the tree to iterate over.
280 TreeIteratorMode mode ///< Mode of iteration (in depth or in breadth).
a7868768
BA
281);
282
283/**
284 * @brief (Re)set current position inside tree to root.
285 */
286void treeI_reset(
e45132ac 287 TreeIterator* treeI ///< "this" pointer.
a7868768
BA
288);
289
290/**
291 * @brief Tell if there is some data at the current index.
292 */
1ff641f9 293bool treeI_has_data(
e45132ac 294 TreeIterator* treeI ///< "this" pointer.
a7868768
BA
295);
296
297/**
298 * @brief Return current tree node.
299 */
300TreeNode* treeI_get_raw(
e45132ac 301 TreeIterator* treeI ///< "this" pointer.
a7868768
BA
302);
303
304/**
305 * @brief Get data at current tree node.
306 * @param treeI "this" pointer.
307 * @param data Data to be assigned.
1ff641f9 308 *
a7868768
BA
309 * Usage: void treeI_get(TreeIterator* treeI, void data)
310 */
311#define treeI_get(treeI, data) \
e45132ac 312 tree_get(treeI->current, data)
a7868768
BA
313
314/**
315 * @brief Set (alter) data at current tree node.
316 * @param treeI "this" pointer.
317 * @param data Data to be assigned.
1ff641f9 318 *
a7868768
BA
319 * Usage: void treeI_set(TreeIterator* treeI, void data)
320 */
321#define treeI_set(treeI, data) \
e45132ac 322 tree_set(treeI->tree, treeI->current, data)
a7868768
BA
323
324/**
325 * @brief Move current iterator position forward (toward leaves).
326 */
327void treeI_move_next(
e45132ac 328 TreeIterator* treeI ///< "this" pointer.
a7868768
BA
329);
330
331/**
332 * @brief Free memory allocated for the iterator.
333 */
334void treeI_destroy(
e45132ac 335 TreeIterator* treeI ///< "this" pointer.
a7868768
BA
336);
337
338#endif