Some fixes + improvements (Vector) + code reformatting
[cgds.git] / src / Tree.c
... / ...
CommitLineData
1/**
2 * @file Tree.c
3 */
4
5#include "cgds/Tree.h"
6
7////////////////
8// Tree logic //
9////////////////
10
11void _tree_init(Tree* tree, size_t dataSize)
12{
13 tree->root = NULL;
14 tree->dataSize = dataSize;
15 tree->size = 0;
16}
17
18Tree* _tree_new(size_t dataSize)
19{
20 Tree* tree = (Tree*) safe_malloc(sizeof (Tree));
21 _tree_init(tree, dataSize);
22 return tree;
23}
24
25Tree* 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
91bool tree_empty(Tree* tree)
92{
93 return (tree->root == NULL);
94}
95
96UInt tree_size(Tree* tree)
97{
98 return tree->size;
99}
100
101UInt _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
117UInt tree_height(Tree* tree)
118{
119 if (tree_empty(tree))
120 return 0;
121 return _tree_height_rekursiv(tree->root);
122}
123
124bool tree_is_leaf(TreeNode* treeNode)
125{
126 return (treeNode->firstChild == NULL);
127}
128
129void _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
142void* _tree_get(TreeNode* treeNode)
143{
144 return treeNode->data;
145}
146
147void _tree_set(Tree* tree, TreeNode* treeNode, void* data)
148{
149 memcpy(treeNode->data, data, tree->dataSize);
150}
151
152TreeNode* _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
171TreeNode* _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
188void _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
202void 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
218void 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
231void 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
238void 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
249TreeIterator* 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
258void treeI_reset(TreeIterator* treeI)
259{
260 treeI->current = treeI->tree->root;
261}
262
263bool treeI_has_data(TreeIterator* treeI)
264{
265 return (treeI->current != NULL);
266}
267
268TreeNode* treeI_get_raw(TreeIterator* treeI)
269{
270 return treeI->current;
271}
272
273void 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
324void treeI_destroy(TreeIterator* treeI)
325{
326 safe_free(treeI);
327}