[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	{
e45132ac BA	13	tree->root = NULL;
	14	tree->dataSize = dataSize;
	15	tree->size = 0;
a7868768 BA	16	}
	17
	18	Tree* _tree_new(size_t dataSize)
	19	{
e45132ac BA	20	Tree* tree = (Tree*) safe_malloc(sizeof (Tree));
	21	_tree_init(tree, dataSize);
	22	return tree;
a7868768 BA	23	}
	24
	25	Tree* tree_copy(Tree* tree)
	26	{
e45132ac BA	27	Tree* treeCopy = _tree_new(tree->dataSize);
	28	if (tree->root == NULL)
	29	return treeCopy;
	30	_tree_set_root(treeCopy, tree->root->data);
a7868768	31
e45132ac BA	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	}
a7868768	44
e45132ac BA	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	}
a7868768	52
e45132ac BA	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	}
a7868768	70
e45132ac BA	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;
a7868768 BA	89	}
a7868768 BA	90
1ff641f9	91	bool tree_empty(Tree* tree)
a7868768	92	{
e45132ac	93	return (tree->root == NULL);
a7868768 BA	94	}
	95
	96	UInt tree_size(Tree* tree)
	97	{
e45132ac	98	return tree->size;
a7868768 BA	99	}
	100
	101	UInt _tree_height_rekursiv(TreeNode* treeNode)
	102	{
e45132ac BA	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;
a7868768 BA	115	}
	116
	117	UInt tree_height(Tree* tree)
	118	{
e45132ac BA	119	if (tree_empty(tree))
	120	return 0;
	121	return _tree_height_rekursiv(tree->root);
a7868768 BA	122	}
a7868768 BA	123
1ff641f9	124	bool tree_is_leaf(TreeNode* treeNode)
a7868768	125	{
e45132ac	126	return (treeNode->firstChild == NULL);
a7868768 BA	127	}
	128
	129	void _tree_set_root(Tree* tree, void* data)
	130	{
e45132ac BA	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;
a7868768 BA	140	}
	141
	142	void* _tree_get(TreeNode* treeNode)
	143	{
e45132ac	144	return treeNode->data;
a7868768 BA	145	}
	146
	147	void _tree_set(Tree* tree, TreeNode* treeNode, void* data)
	148	{
e45132ac	149	memcpy(treeNode->data, data, tree->dataSize);
a7868768 BA	150	}
	151
	152	void _tree_add_child(Tree* tree, TreeNode* treeNode, void* data)
	153	{
e45132ac BA	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++;
a7868768 BA	168	}
	169
	170	void _tree_add_sibling(Tree* tree, TreeNode* treeNode, void* data)
	171	{
e45132ac BA	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++;
a7868768 BA	184	}
	185
	186	void _tree_remove_rekursiv(Tree* tree, TreeNode* treeNode)
	187	{
e45132ac BA	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--;
a7868768 BA	198	}
	199
	200	void tree_remove(Tree* tree, TreeNode* treeNode)
	201	{
e45132ac BA	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);
a7868768 BA	214	}
	215
	216	void tree_rm_childs(Tree* tree, TreeNode* treeNode)
	217	{
e45132ac BA	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;
a7868768 BA	227	}
	228
	229	void tree_clear(Tree* tree)
	230	{
e45132ac BA	231	if (tree->root != NULL)
	232	_tree_remove_rekursiv(tree, tree->root);
	233	_tree_init(tree, tree->dataSize);
a7868768 BA	234	}
	235
	236	void tree_destroy(Tree* tree)
	237	{
e45132ac BA	238	if (tree->root != NULL)
	239	tree_clear(tree);
	240	safe_free(tree);
a7868768 BA	241	}
	242
	243	////////////////////
	244	// Iterator logic //
	245	////////////////////
	246
	247	TreeIterator* tree_get_iterator(Tree* tree, TreeIteratorMode mode)
	248	{
e45132ac BA	249	TreeIterator* treeI = (TreeIterator*) safe_malloc(sizeof (TreeIterator));
	250	treeI->tree = tree;
	251	treeI->mode = mode;
	252	treeI_reset(treeI);
	253	return treeI;
a7868768 BA	254	}
	255
	256	void treeI_reset(TreeIterator* treeI)
	257	{
e45132ac	258	treeI->current = treeI->tree->root;
a7868768 BA	259	}
a7868768 BA	260
1ff641f9	261	bool treeI_has_data(TreeIterator* treeI)
a7868768	262	{
e45132ac	263	return (treeI->current != NULL);
a7868768 BA	264	}
	265
	266	TreeNode* treeI_get_raw(TreeIterator* treeI)
	267	{
e45132ac	268	return treeI->current;
a7868768 BA	269	}
	270
	271	void treeI_move_next(TreeIterator* treeI)
	272	{
e45132ac BA	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	}
a7868768 BA	318	}
	319
	320	void treeI_destroy(TreeIterator* treeI)
	321	{
e45132ac	322	safe_free(treeI);
a7868768	323	}