src/Tree.c

   1 /**
   2  * @file Tree.c
   3  */
   4
   5 #include "cgds/Tree.h"
   6
   7 ////////////////
   8 // Tree logic //
   9 ////////////////
  10
  11 void _tree_init(Tree* tree, size_t dataSize)
  12 {
  13   tree->root = NULL;
  14   tree->dataSize = dataSize;
  15   tree->size = 0;
  16 }
  17
  18 Tree* _tree_new(size_t dataSize)
  19 {
  20   Tree* tree = (Tree*) safe_malloc(sizeof (Tree));
  21   _tree_init(tree, dataSize);
  22   return tree;
  23 }
  24
  25 Tree* tree_copy(Tree* tree)
  26 {
  27   Tree* treeCopy = _tree_new(tree->dataSize);
  28   if (tree->root == NULL)
  29     return treeCopy;
  30   _tree_set_root(treeCopy, tree->root->data);
  31
  32   // Now parallel run on both trees (manual breadth-first walk)
  33   TreeNode* treeNode = tree->root;
  34   TreeNode* treeNodeCopy = treeCopy->root;
  35   while (treeNode != NULL)
  36   {
  37     // process current children
  38     TreeNode* child = treeNode->firstChild;
  39     while (child != NULL)
  40     {
  41       _tree_add_child(treeCopy, treeNodeCopy, child->data);
  42       child = child->next;
  43     }
  44
  45     // try to go to next sibling (NOTE: already added as child of parent)
  46     if (treeNode->next != NULL)
  47     {
  48       treeNode = treeNode->next;
  49       treeNodeCopy = treeNodeCopy->next;
  50       continue;
  51     }
  52
  53     // try to go to next "cousin" on same level
  54     if (treeNode->parent != NULL && treeNode->parent->next != NULL)
  55     {
  56       TreeNode* treeNodeParent = treeNode->parent->next;
  57       TreeNode* treeNodeParentCopy = treeNodeCopy->parent->next;
  58       while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
  59       {
  60         treeNodeParent = treeNodeParent->next;
  61         treeNodeParentCopy = treeNodeParentCopy->next;
  62       }
  63       if (treeNodeParent != NULL)
  64       {
  65         treeNode = treeNodeParent->firstChild;
  66         treeNodeCopy = treeNodeParentCopy->firstChild;
  67         continue;
  68       }
  69     }
  70
  71     // try to go to next level, and move treeNodeCopy accordingly
  72     while (treeNode->prev != NULL)
  73     {
  74       treeNode = treeNode->prev;
  75       treeNodeCopy = treeNodeCopy->prev;
  76     }
  77     while (treeNode != NULL && tree_is_leaf(treeNode))
  78     {
  79       treeNode = treeNode->next;
  80       treeNodeCopy = treeNodeCopy->next;
  81     }
  82     if (treeNode != NULL)
  83     {
  84       treeNode = treeNode->firstChild;
  85       treeNodeCopy = treeNodeCopy->firstChild;
  86     }
  87   }
  88   return treeCopy;
  89 }
  90
  91 bool tree_empty(Tree* tree)
  92 {
  93   return (tree->root == NULL);
  94 }
  95
  96 UInt tree_size(Tree* tree)
  97 {
  98   return tree->size;
  99 }
 100
 101 UInt _tree_height_rekursiv(TreeNode* treeNode)
 102 {
 103   if (tree_is_leaf(treeNode))
 104     return 1;
 105   TreeNode* child = treeNode->firstChild;
 106   UInt maxHeightChild = 0;
 107   while (child != NULL)
 108   {
 109     UInt heightChild = _tree_height_rekursiv(child);
 110     if (heightChild > maxHeightChild)
 111       maxHeightChild = heightChild;
 112     child = child->next;
 113   }
 114   return 1 + maxHeightChild;
 115 }
 116
 117 UInt tree_height(Tree* tree)
 118 {
 119   if (tree_empty(tree))
 120     return 0;
 121   return _tree_height_rekursiv(tree->root);
 122 }
 123
 124 bool tree_is_leaf(TreeNode* treeNode)
 125 {
 126   return (treeNode->firstChild == NULL);
 127 }
 128
 129 void _tree_set_root(Tree* tree, void* data)
 130 {
 131   tree->root = (TreeNode*) safe_malloc(sizeof (TreeNode));
 132   tree->root->data = safe_malloc(tree->dataSize);
 133   memcpy(tree->root->data, data, tree->dataSize);
 134   tree->root->parent = NULL;
 135   tree->root->firstChild = NULL;
 136   tree->root->lastChild = NULL;
 137   tree->root->prev = NULL;
 138   tree->root->next = NULL;
 139   tree->size = 1;
 140 }
 141
 142 void* _tree_get(TreeNode* treeNode)
 143 {
 144   return treeNode->data;
 145 }
 146
 147 void _tree_set(Tree* tree, TreeNode* treeNode, void* data)
 148 {
 149   memcpy(treeNode->data, data, tree->dataSize);
 150 }
 151
 152 TreeNode* _tree_add_child(Tree* tree, TreeNode* treeNode, void* data)
 153 {
 154   TreeNode* newChildNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
 155   newChildNode->data = safe_malloc(tree->dataSize);
 156   memcpy(newChildNode->data, data, tree->dataSize);
 157   newChildNode->next = NULL;
 158   if (treeNode->lastChild != NULL)
 159     treeNode->lastChild->next = newChildNode;
 160   newChildNode->prev = treeNode->lastChild;
 161   treeNode->lastChild = newChildNode;
 162   if (treeNode->firstChild == NULL)
 163     treeNode->firstChild = newChildNode;
 164   newChildNode->parent = treeNode;
 165   newChildNode->firstChild = NULL;
 166   newChildNode->lastChild = NULL;
 167   tree->size++;
 168   return newChildNode;
 169 }
 170
 171 TreeNode* _tree_add_sibling(Tree* tree, TreeNode* treeNode, void* data)
 172 {
 173   TreeNode* newSiblingNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
 174   newSiblingNode->data = safe_malloc(tree->dataSize);
 175   memcpy(newSiblingNode->data, data, tree->dataSize);
 176   newSiblingNode->next = treeNode->next;
 177   if (treeNode->next != NULL)
 178     treeNode->next->prev = newSiblingNode;
 179   newSiblingNode->prev = treeNode;
 180   treeNode->next = newSiblingNode;
 181   newSiblingNode->parent = treeNode->parent;
 182   newSiblingNode->firstChild = NULL;
 183   newSiblingNode->lastChild = NULL;
 184   tree->size++;
 185   return newSiblingNode;
 186 }
 187
 188 void _tree_remove_rekursiv(Tree* tree, TreeNode* treeNode)
 189 {
 190   TreeNode* child = treeNode->firstChild;
 191   while (child != NULL)
 192   {
 193     TreeNode* nextChild = child->next;
 194     _tree_remove_rekursiv(tree, child);
 195     child = nextChild;
 196   }
 197   safe_free(treeNode->data);
 198   safe_free(treeNode);
 199   tree->size--;
 200 }
 201
 202 void tree_remove(Tree* tree, TreeNode* treeNode)
 203 {
 204   if (treeNode->parent != NULL)
 205   {
 206     if (treeNode->prev == NULL)
 207       treeNode->parent->firstChild = treeNode->next;
 208     if (treeNode->next == NULL)
 209       treeNode->parent->lastChild = treeNode->prev;
 210   }
 211   if (treeNode->next != NULL)
 212     treeNode->next->prev = treeNode->prev;
 213   if (treeNode->prev != NULL)
 214     treeNode->prev->next = treeNode->next;
 215   _tree_remove_rekursiv(tree, treeNode);
 216 }
 217
 218 void tree_rm_childs(Tree* tree, TreeNode* treeNode)
 219 {
 220   TreeNode* child = treeNode->firstChild;
 221   while (child != NULL)
 222   {
 223     TreeNode* nextChild = child->next;
 224     _tree_remove_rekursiv(tree, child);
 225     child = nextChild;
 226   }
 227   treeNode->firstChild = NULL;
 228   treeNode->lastChild = NULL;
 229 }
 230
 231 void tree_clear(Tree* tree)
 232 {
 233   if (tree->root != NULL)
 234     _tree_remove_rekursiv(tree, tree->root);
 235   _tree_init(tree, tree->dataSize);
 236 }
 237
 238 void tree_destroy(Tree* tree)
 239 {
 240   if (tree->root != NULL)
 241     tree_clear(tree);
 242   safe_free(tree);
 243 }
 244
 245 ////////////////////
 246 // Iterator logic //
 247 ////////////////////
 248
 249 TreeIterator* tree_get_iterator(Tree* tree, TreeIteratorMode mode)
 250 {
 251   TreeIterator* treeI = (TreeIterator*) safe_malloc(sizeof (TreeIterator));
 252   treeI->tree = tree;
 253   treeI->mode = mode;
 254   treeI_reset(treeI);
 255   return treeI;
 256 }
 257
 258 void treeI_reset(TreeIterator* treeI)
 259 {
 260   treeI->current = treeI->tree->root;
 261 }
 262
 263 bool treeI_has_data(TreeIterator* treeI)
 264 {
 265   return (treeI->current != NULL);
 266 }
 267
 268 TreeNode* treeI_get_raw(TreeIterator* treeI)
 269 {
 270   return treeI->current;
 271 }
 272
 273 void treeI_move_next(TreeIterator* treeI)
 274 {
 275   TreeIteratorMode mode = treeI->mode;
 276   switch (mode)
 277   {
 278     case IN_DEPTH:
 279       if (!tree_is_leaf(treeI->current))
 280       {
 281         // easy case: just descend deeper in the tree
 282         treeI->current = treeI->current->firstChild;
 283         return;
 284       }
 285       // leaf: while no next sibling is available, move up
 286       while (treeI->current != NULL && treeI->current->next == NULL)
 287         treeI->current = treeI->current->parent;
 288       if (treeI->current != NULL)
 289         // run goes on from next sibling
 290         treeI->current = treeI->current->next;
 291       break;
 292     case IN_BREADTH:
 293       if (treeI->current->next != NULL)
 294       {
 295         // easy case : just move to the next sibling
 296         treeI->current = treeI->current->next;
 297         return;
 298       }
 299       // try to go to next "cousin" on same level
 300       if (
 301         treeI->current->parent != NULL &&
 302         treeI->current->parent->next != NULL
 303       ) {
 304         TreeNode* treeNodeParent = treeI->current->parent->next;
 305         while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
 306           treeNodeParent = treeNodeParent->next;
 307         if (treeNodeParent != NULL)
 308         {
 309           treeI->current = treeNodeParent->firstChild;
 310           return;
 311         }
 312       }
 313       // try to go to next level
 314       while (treeI->current->prev != NULL)
 315         treeI->current = treeI->current->prev;
 316       while (treeI->current != NULL && tree_is_leaf(treeI->current))
 317         treeI->current = treeI->current->next;
 318       if (treeI->current != NULL)
 319         treeI->current = treeI->current->firstChild;
 320       break;
 321   }
 322 }
 323
 324 void treeI_destroy(TreeIterator* treeI)
 325 {
 326   safe_free(treeI);
 327 }