initial commit
[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
152void _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
170void _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
186void _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
200void 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
216void 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
229void 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
236void 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
247TreeIterator* 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
256void treeI_reset(TreeIterator* treeI)
257{
258 treeI->current = treeI->tree->root;
259}
260
261Bool treeI_has_data(TreeIterator* treeI)
262{
263 return (treeI->current != NULL);
264}
265
266TreeNode* treeI_get_raw(TreeIterator* treeI)
267{
268 return treeI->current;
269}
270
271void 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
320void treeI_destroy(TreeIterator* treeI)
321{
322 safe_free(treeI);
323}