1ee3b515824b85cdb4a670849018ef2159a121db
[cgds.git] / 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 }