63193a224e004b9105960a72bb849f82cd42b469
[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 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 }