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 { \
  61   _tree_new(sizeof(type)); \
  62 }
  63
  64 /**
  65  * @brief Copy constructor (shallow copy, ok for basic types).
  66  */
  67 Tree* tree_copy(
  68   Tree* tree ///< "this" pointer.
  69 );
  70
  71 /**
  72  * @brief Check if the tree is empty.
  73  */
  74 bool tree_empty(
  75   Tree* tree ///< "this" pointer.
  76 );
  77
  78 /**
  79  * @brief return current size of the tree (counting nodes).
  80  */
  81 UInt tree_size(
  82   Tree* tree ///< "this" pointer.
  83 );
  84
  85 /**
  86  * @brief Auxiliary function to get tree height.
  87  */
  88 UInt _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  */
  95 UInt tree_height(
  96   Tree* tree ///< "this" pointer.
  97 );
  98
  99 /**
 100  * @brief Check if a sub-tree is a leaf (without children).
 101  */
 102 bool 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  */
 109 void _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  */
 130 void* _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  */
 150 void _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  */
 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.
 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  */
 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.
 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  */
 219 void _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  */
 227 void 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  */
 235 void 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  */
 243 void tree_clear(
 244   Tree* tree ///< "this" pointer.
 245 );
 246
 247 /**
 248  * @brief Destroy the tree: clear it, and free 'tree' pointer.
 249  */
 250 void 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  */
 261 typedef 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  */
 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).
 273 } TreeIterator;
 274
 275 /**
 276  * @brief Obtain an iterator object, starting at tree root.
 277  */
 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).
 281 );
 282
 283 /**
 284  * @brief (Re)set current position inside tree to root.
 285  */
 286 void treeI_reset(
 287   TreeIterator* treeI ///< "this" pointer.
 288 );
 289
 290 /**
 291  * @brief Tell if there is some data at the current index.
 292  */
 293 bool treeI_has_data(
 294   TreeIterator* treeI ///< "this" pointer.
 295 );
 296
 297 /**
 298  * @brief Return current tree node.
 299  */
 300 TreeNode* 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  */
 327 void treeI_move_next(
 328   TreeIterator* treeI ///< "this" pointer.
 329 );
 330
 331 /**
 332  * @brief Free memory allocated for the iterator.
 333  */
 334 void treeI_destroy(
 335   TreeIterator* treeI ///< "this" pointer.
 336 );
 337
 338 #endif