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 (works well if items do not have allocated sub-pointers).
  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 Add a child to current node children.
 170  */
 171 void _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  */
 194 void _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  */
 217 void _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  */
 225 void 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  */
 233 void 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  */
 241 void tree_clear(
 242     Tree* tree ///< "this" pointer.
 243 );
 244
 245 /**
 246  * @brief Destroy the tree: clear it, and free 'tree' pointer.
 247  */
 248 void 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  */
 259 typedef 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  */
 267 typedef 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  */
 276 TreeIterator* 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  */
 284 void treeI_reset(
 285     TreeIterator* treeI ///< "this" pointer.
 286 );
 287
 288 /**
 289  * @brief Tell if there is some data at the current index.
 290  */
 291 Bool treeI_has_data(
 292     TreeIterator* treeI ///< "this" pointer.
 293 );
 294
 295 /**
 296  * @brief Return current tree node.
 297  */
 298 TreeNode* 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  */
 325 void treeI_move_next(
 326     TreeIterator* treeI ///< "this" pointer.
 327 );
 328
 329 /**
 330  * @brief Free memory allocated for the iterator.
 331  */
 332 void treeI_destroy(
 333     TreeIterator* treeI ///< "this" pointer.
 334 );
 335
 336 #endif