[cgds.git] / src / Tree.c

/**
 * @file Tree.c
 */

#include "cgds/Tree.h"

////////////////
// Tree logic //
////////////////

void _tree_init(Tree* tree, size_t dataSize)
{
	tree->root = NULL;
	tree->dataSize = dataSize;
	tree->size = 0;
}

Tree* _tree_new(size_t dataSize)
{
	Tree* tree = (Tree*) safe_malloc(sizeof (Tree));
	_tree_init(tree, dataSize);
	return tree;
}

Tree* tree_copy(Tree* tree)
{
	Tree* treeCopy = _tree_new(tree->dataSize);
	if (tree->root == NULL) 
		return treeCopy;
	_tree_set_root(treeCopy, tree->root->data);

	// Now parallel run on both trees (manual breadth-first walk)
	TreeNode* treeNode = tree->root;
	TreeNode* treeNodeCopy = treeCopy->root;
	while (treeNode != NULL)
	{
		// process current children
		TreeNode* child = treeNode->firstChild;
		while (child != NULL)
		{
			_tree_add_child(treeCopy, treeNodeCopy, child->data);
			child = child->next;
		}

		// try to go to next sibling (NOTE: already added as child of parent)
		if (treeNode->next != NULL)
		{
			treeNode = treeNode->next;
			treeNodeCopy = treeNodeCopy->next;
			continue;
		}

		// try to go to next "cousin" on same level
		if (treeNode->parent != NULL && treeNode->parent->next != NULL)
		{
			TreeNode* treeNodeParent = treeNode->parent->next;
			TreeNode* treeNodeParentCopy = treeNodeCopy->parent->next;
			while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
			{
				treeNodeParent = treeNodeParent->next;
				treeNodeParentCopy = treeNodeParentCopy->next;
			}
			if (treeNodeParent != NULL)
			{
				treeNode = treeNodeParent->firstChild;
				treeNodeCopy = treeNodeParentCopy->firstChild;
				continue;
			}
		}

		// try to go to next level, and move treeNodeCopy accordingly
		while (treeNode->prev != NULL)
		{
			treeNode = treeNode->prev;
			treeNodeCopy = treeNodeCopy->prev;
		}
		while (treeNode != NULL && tree_is_leaf(treeNode))
		{
			treeNode = treeNode->next;
			treeNodeCopy = treeNodeCopy->next;
		}
		if (treeNode != NULL)
		{
			treeNode = treeNode->firstChild;
			treeNodeCopy = treeNodeCopy->firstChild;
		}
	}
	return treeCopy;
}

Bool tree_empty(Tree* tree)
{
	return (tree->root == NULL);
}

UInt tree_size(Tree* tree)
{
	return tree->size;
}

UInt _tree_height_rekursiv(TreeNode* treeNode)
{
	if (tree_is_leaf(treeNode)) 
		return 1;
	TreeNode* child = treeNode->firstChild;
	UInt maxHeightChild = 0;
	while (child != NULL)
	{
		UInt heightChild = _tree_height_rekursiv(child);
		if (heightChild > maxHeightChild) 
			maxHeightChild = heightChild;
		child = child->next;
	}
	return 1 + maxHeightChild;
}

UInt tree_height(Tree* tree)
{
	if (tree_empty(tree)) 
		return 0;
	return _tree_height_rekursiv(tree->root);
}

Bool tree_is_leaf(TreeNode* treeNode)
{
	return (treeNode->firstChild == NULL);
}

void _tree_set_root(Tree* tree, void* data)
{
	tree->root = (TreeNode*) safe_malloc(sizeof (TreeNode));
	tree->root->data = safe_malloc(tree->dataSize);
	memcpy(tree->root->data, data, tree->dataSize);
	tree->root->parent = NULL;
	tree->root->firstChild = NULL;
	tree->root->lastChild = NULL;
	tree->root->prev = NULL;
	tree->root->next = NULL;
	tree->size = 1;
}

void* _tree_get(TreeNode* treeNode)
{
	return treeNode->data;
}

void _tree_set(Tree* tree, TreeNode* treeNode, void* data)
{
	memcpy(treeNode->data, data, tree->dataSize);
}

void _tree_add_child(Tree* tree, TreeNode* treeNode, void* data)
{
	TreeNode* newChildNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
	newChildNode->data = safe_malloc(tree->dataSize);
	memcpy(newChildNode->data, data, tree->dataSize);
	newChildNode->next = NULL;
	if (treeNode->lastChild != NULL) 
		treeNode->lastChild->next = newChildNode;
	newChildNode->prev = treeNode->lastChild;
	treeNode->lastChild = newChildNode;
	if (treeNode->firstChild == NULL) 
		treeNode->firstChild = newChildNode;
	newChildNode->parent = treeNode;
	newChildNode->firstChild = NULL;
	newChildNode->lastChild = NULL;
	tree->size++;
}

void _tree_add_sibling(Tree* tree, TreeNode* treeNode, void* data)
{
	TreeNode* newSiblingNode = (TreeNode*) safe_malloc(sizeof (TreeNode));
	newSiblingNode->data = safe_malloc(tree->dataSize);
	memcpy(newSiblingNode->data, data, tree->dataSize);
	newSiblingNode->next = treeNode->next;
	if (treeNode->next != NULL) 
		treeNode->next->prev = newSiblingNode;
	newSiblingNode->prev = treeNode;
	treeNode->next = newSiblingNode;
	newSiblingNode->parent = treeNode->parent;
	newSiblingNode->firstChild = NULL;
	newSiblingNode->lastChild = NULL;
	tree->size++;
}

void _tree_remove_rekursiv(Tree* tree, TreeNode* treeNode)
{
	TreeNode* child = treeNode->firstChild;
	while (child != NULL)
	{
		TreeNode* nextChild = child->next;
		_tree_remove_rekursiv(tree, child);
		child = nextChild;
	}
	safe_free(treeNode->data);
	safe_free(treeNode);
	tree->size--;
}

void tree_remove(Tree* tree, TreeNode* treeNode)
{
	if (treeNode->parent != NULL)
	{
		if (treeNode->prev == NULL) 
			treeNode->parent->firstChild = treeNode->next;
		if (treeNode->next == NULL) 
			treeNode->parent->lastChild = treeNode->prev;
	}
	if (treeNode->next != NULL) 
		treeNode->next->prev = treeNode->prev;
	if (treeNode->prev != NULL) 
		treeNode->prev->next = treeNode->next;
	_tree_remove_rekursiv(tree, treeNode);
}

void tree_rm_childs(Tree* tree, TreeNode* treeNode)
{
	TreeNode* child = treeNode->firstChild;
	while (child != NULL)
	{
		TreeNode* nextChild = child->next;
		_tree_remove_rekursiv(tree, child);
		child = nextChild;
	}
	treeNode->firstChild = NULL;
	treeNode->lastChild = NULL;
}

void tree_clear(Tree* tree)
{
	if (tree->root != NULL) 
		_tree_remove_rekursiv(tree, tree->root);
	_tree_init(tree, tree->dataSize);
}

void tree_destroy(Tree* tree)
{
	if (tree->root != NULL) 
		tree_clear(tree);
	safe_free(tree);
}

////////////////////
// Iterator logic //
////////////////////

TreeIterator* tree_get_iterator(Tree* tree, TreeIteratorMode mode)
{
	TreeIterator* treeI = (TreeIterator*) safe_malloc(sizeof (TreeIterator));
	treeI->tree = tree;
	treeI->mode = mode;
	treeI_reset(treeI);
	return treeI;
}

void treeI_reset(TreeIterator* treeI)
{
	treeI->current = treeI->tree->root;
}

Bool treeI_has_data(TreeIterator* treeI)
{
	return (treeI->current != NULL);
}

TreeNode* treeI_get_raw(TreeIterator* treeI)
{
	return treeI->current;
}

void treeI_move_next(TreeIterator* treeI)
{
	TreeIteratorMode mode = treeI->mode;
	switch (mode)
	{
	case IN_DEPTH:
		if (!tree_is_leaf(treeI->current))
		{
			// easy case: just descend deeper in the tree
			treeI->current = treeI->current->firstChild;
			return;
		}
		// leaf: while no next sibling is available, move up
		while (treeI->current != NULL && treeI->current->next == NULL)
			treeI->current = treeI->current->parent;
		if (treeI->current != NULL)
			// run goes on from next sibling
			treeI->current = treeI->current->next;
		break;
	case IN_BREADTH:
		if (treeI->current->next != NULL)
		{
			// easy case : just move to the next sibling
			treeI->current = treeI->current->next;
			return;
		}
		// try to go to next "cousin" on same level
		if (treeI->current->parent != NULL && treeI->current->parent->next != NULL)
		{
			TreeNode* treeNodeParent = treeI->current->parent->next;
			while (treeNodeParent != NULL && tree_is_leaf(treeNodeParent))
				treeNodeParent = treeNodeParent->next;
			if (treeNodeParent != NULL)
			{
				treeI->current = treeNodeParent->firstChild;
				return;
			}
		}
		// try to go to next level
		while (treeI->current->prev != NULL)
			treeI->current = treeI->current->prev;
		while (treeI->current != NULL && tree_is_leaf(treeI->current))
			treeI->current = treeI->current->next;
		if (treeI->current != NULL)
			treeI->current = treeI->current->firstChild;
		break;
	}
}

void treeI_destroy(TreeIterator* treeI)
{
	safe_free(treeI);
}
Commit	Line	Data
a7868768 BA	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	}