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 void _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 }
 169
 170 void _tree_add_sibling(Tree* tree, TreeNode* treeNode, void* data)
 171 {
 172     TreeNode* newSiblingNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
 173     newSiblingNode->data = safe_malloc(tree->dataSize);
 174     memcpy(newSiblingNode->data, data, tree->dataSize);
 175     newSiblingNode->next = treeNode->next;
 176     if (treeNode->next != NULL)
 177         treeNode->next->prev = newSiblingNode;
 178     newSiblingNode->prev = treeNode;
 179     treeNode->next = newSiblingNode;
 180     newSiblingNode->parent = treeNode->parent;
 181     newSiblingNode->firstChild = NULL;
 182     newSiblingNode->lastChild = NULL;
 183     tree->size++;
 184 }
 185
 186 void _tree_remove_rekursiv(Tree* tree, TreeNode* treeNode)
 187 {
 188     TreeNode* child = treeNode->firstChild;
 189     while (child != NULL)
 190     {
 191         TreeNode* nextChild = child->next;
 192         _tree_remove_rekursiv(tree, child);
 193         child = nextChild;
 194     }
 195     safe_free(treeNode->data);
 196     safe_free(treeNode);
 197     tree->size--;
 198 }
 199
 200 void tree_remove(Tree* tree, TreeNode* treeNode)
 201 {
 202     if (treeNode->parent != NULL)
 203     {
 204         if (treeNode->prev == NULL)
 205             treeNode->parent->firstChild = treeNode->next;
 206         if (treeNode->next == NULL)
 207             treeNode->parent->lastChild = treeNode->prev;
 208     }
 209     if (treeNode->next != NULL)
 210         treeNode->next->prev = treeNode->prev;
 211     if (treeNode->prev != NULL)
 212         treeNode->prev->next = treeNode->next;
 213     _tree_remove_rekursiv(tree, treeNode);
 214 }
 215
 216 void tree_rm_childs(Tree* tree, TreeNode* treeNode)
 217 {
 218     TreeNode* child = treeNode->firstChild;
 219     while (child != NULL)
 220     {
 221         TreeNode* nextChild = child->next;
 222         _tree_remove_rekursiv(tree, child);
 223         child = nextChild;
 224     }
 225     treeNode->firstChild = NULL;
 226     treeNode->lastChild = NULL;
 227 }
 228
 229 void tree_clear(Tree* tree)
 230 {
 231     if (tree->root != NULL)
 232         _tree_remove_rekursiv(tree, tree->root);
 233     _tree_init(tree, tree->dataSize);
 234 }
 235
 236 void tree_destroy(Tree* tree)
 237 {
 238     if (tree->root != NULL)
 239         tree_clear(tree);
 240     safe_free(tree);
 241 }
 242
 243 ////////////////////
 244 // Iterator logic //
 245 ////////////////////
 246
 247 TreeIterator* tree_get_iterator(Tree* tree, TreeIteratorMode mode)
 248 {
 249     TreeIterator* treeI = (TreeIterator*) safe_malloc(sizeof (TreeIterator));
 250     treeI->tree = tree;
 251     treeI->mode = mode;
 252     treeI_reset(treeI);
 253     return treeI;
 254 }
 255
 256 void treeI_reset(TreeIterator* treeI)
 257 {
 258     treeI->current = treeI->tree->root;
 259 }
 260
 261 Bool treeI_has_data(TreeIterator* treeI)
 262 {
 263     return (treeI->current != NULL);
 264 }
 265
 266 TreeNode* treeI_get_raw(TreeIterator* treeI)
 267 {
 268     return treeI->current;
 269 }
 270
 271 void treeI_move_next(TreeIterator* treeI)
 272 {
 273     TreeIteratorMode mode = treeI->mode;
 274     switch (mode)
 275     {
 276     case IN_DEPTH:
 277         if (!tree_is_leaf(treeI->current))
 278         {
 279             // easy case: just descend deeper in the tree
 280             treeI->current = treeI->current->firstChild;
 281             return;
 282         }
 283         // leaf: while no next sibling is available, move up
 284         while (treeI->current != NULL && treeI->current->next == NULL)
 285             treeI->current = treeI->current->parent;
 286         if (treeI->current != NULL)
 287             // run goes on from next sibling
 288             treeI->current = treeI->current->next;
 289         break;
 290     case IN_BREADTH:
 291         if (treeI->current->next != NULL)
 292         {
 293             // easy case : just move to the next sibling
 294             treeI->current = treeI->current->next;
 295             return;
 296         }
 297         // try to go to next "cousin" on same level
 298         if (treeI->current->parent != NULL && treeI->current->parent->next != NULL)
 299         {
 300             TreeNode* treeNodeParent = treeI->current->parent->next;
 301             while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
 302                 treeNodeParent = treeNodeParent->next;
 303             if (treeNodeParent != NULL)
 304             {
 305                 treeI->current = treeNodeParent->firstChild;
 306                 return;
 307             }
 308         }
 309         // try to go to next level
 310         while (treeI->current->prev != NULL)
 311             treeI->current = treeI->current->prev;
 312         while (treeI->current != NULL && tree_is_leaf(treeI->current))
 313             treeI->current = treeI->current->next;
 314         if (treeI->current != NULL)
 315             treeI->current = treeI->current->firstChild;
 316         break;
 317     }
 318 }
 319
 320 void treeI_destroy(TreeIterator* treeI)
 321 {
 322     safe_free(treeI);
 323 }