6ac08640166baf9203e5df9acbd8bc5906e8f218
10 #include "cgds/safe_alloc.h"
11 #include "cgds/types.h"
18 * @brief Tree node, containing some generic data.
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).
30 * @brief Generic multi-ary 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.
39 * @brief Initialize an empty tree.
42 Tree
* tree
, ///< "this" pointer.
43 size_t dataSize
///< Size in bytes of a tree element.
47 * @brief Return an allocated and initialized tree.
50 size_t dataSize
///< Size in bytes of a tree node element.
54 * @brief Return an allocated and initialized tree.
55 * @param type Type at a tree node (int, char*, ...).
57 * Usage: Tree* tree_new(<Type> type)
59 #define tree_new(type) \
61 _tree_new(sizeof(type)); \
65 * @brief Copy constructor (shallow copy, ok for basic types).
68 Tree
* tree
///< "this" pointer.
72 * @brief Check if the tree is empty.
75 Tree
* tree
///< "this" pointer.
79 * @brief return current size of the tree (counting nodes).
82 Tree
* tree
///< "this" pointer.
86 * @brief Auxiliary function to get tree height.
88 UInt
_tree_height_rekursiv(
89 TreeNode
* treeNode
///< Pointer to a node in the "this" tree.
93 * @brief Return tree height (max depth from root to leaves).
96 Tree
* tree
///< "this" pointer.
100 * @brief Check if a sub-tree is a leaf (without children).
103 TreeNode
* treeNode
///< Pointer to a node in the "this" tree.
107 * @brief Initialize tree root when the tree is empty.
110 Tree
* tree
, ///< "this" pointer.
111 void* data
///< Pointer to data to be assigned.
115 * @brief Initialize tree root when the tree is empty.
116 * @param tree "this" pointer.
117 * @param data Data to be assigned.
119 * Usage: void tree_set_root(Tree* tree, void data)
121 #define tree_set_root(tree, data) \
123 typeof((data)) tmp = data; \
124 _tree_set_root(tree, &tmp); \
128 * @brief Return data contained in a given tree node.
131 TreeNode
* treeNode
///< Pointer to a node in the "this" tree.
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.
139 * Usage: void tree_get(TreeNode* treeNode, void data)
141 #define tree_get(treeNode, data) \
143 void* pData = _tree_get(treeNode); \
144 data = *((typeof(&data))pData); \
148 * @brief Set (alter) data at tree node passed as argument.
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.
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.
162 * Usage: void tree_set(Tree* tree, TreeNode* treeNode, void data)
164 #define tree_set(tree, treeNode, data) \
166 typeof((data)) tmp = data; \
167 _tree_set(tree,treeNode,&tmp); \
171 * @brief Add a child to current node children.
173 void _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.
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.
185 * Usage: void tree_add_child(Tree* tree, TreeNode* treeNode, void data)
187 #define tree_add_child(tree,treeNode,data) \
189 typeof((data)) tmp = data; \
190 _tree_add_child(tree,treeNode,&tmp); \
194 * @brief Add a sibling to current node (after it on the right).
196 void _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.
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.
208 * Usage: void tree_add_sibling(Tree* tree, TreeNode* treeNode, void data)
210 #define tree_add_sibling(tree, treeNode, data) \
212 typeof((data)) tmp = data; \
213 _tree_add_sibling(tree, treeNode, &tmp); \
217 * @brief Auxiliary to remove a subtree.
219 void _tree_remove_rekursiv(
220 Tree
* tree
, ///< "this" pointer.
221 TreeNode
* treeNode
///< Pointer to a node in the "this" tree.
225 * @brief Remove the whole subtree rooted at 'treeNode'.
228 Tree
* tree
, ///< "this" pointer.
229 TreeNode
* treeNode
///< Pointer to a node in the "this" tree.
233 * @brief Remove children of the tree node given as argument.
236 Tree
* tree
, ///< "this" pointer.
237 TreeNode
* treeNode
///< Pointer to a node in the "this" tree.
241 * @brief Clear the entire tree.
244 Tree
* tree
///< "this" pointer.
248 * @brief Destroy the tree: clear it, and free 'tree' pointer.
251 Tree
* tree
///< "this" pointer.
259 * @brief Type of tree search: depth first or breadth first walk.
261 typedef enum TreeIteratorMode
{
262 IN_DEPTH
= 0, ///< Depth first.
263 IN_BREADTH
= 1 ///< Breadth first.
267 * @brief Iterator on a tree object.
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).
276 * @brief Obtain an iterator object, starting at tree root.
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).
284 * @brief (Re)set current position inside tree to root.
287 TreeIterator
* treeI
///< "this" pointer.
291 * @brief Tell if there is some data at the current index.
294 TreeIterator
* treeI
///< "this" pointer.
298 * @brief Return current tree node.
300 TreeNode
* treeI_get_raw(
301 TreeIterator
* treeI
///< "this" pointer.
305 * @brief Get data at current tree node.
306 * @param treeI "this" pointer.
307 * @param data Data to be assigned.
309 * Usage: void treeI_get(TreeIterator* treeI, void data)
311 #define treeI_get(treeI, data) \
312 tree_get(treeI->current, data)
315 * @brief Set (alter) data at current tree node.
316 * @param treeI "this" pointer.
317 * @param data Data to be assigned.
319 * Usage: void treeI_set(TreeIterator* treeI, void data)
321 #define treeI_set(treeI, data) \
322 tree_set(treeI->tree, treeI->current, data)
325 * @brief Move current iterator position forward (toward leaves).
327 void treeI_move_next(
328 TreeIterator
* treeI
///< "this" pointer.
332 * @brief Free memory allocated for the iterator.
335 TreeIterator
* treeI
///< "this" pointer.