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