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

TreeNode* _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++;
  return newChildNode;
}

TreeNode* _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++;
  return newSiblingNode;
}

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	}
a7868768 BA	151
7820a2aa	152	TreeNode* _tree_add_child(Tree* tree, TreeNode* treeNode, void* data)
a7868768	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++;
7820a2aa	168	return newChildNode;
a7868768 BA	169	}
a7868768 BA	170
7820a2aa	171	TreeNode* _tree_add_sibling(Tree* tree, TreeNode* treeNode, void* data)
a7868768	172	{
e45132ac BA	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++;
7820a2aa	185	return newSiblingNode;
a7868768 BA	186	}
	187
	188	void _tree_remove_rekursiv(Tree* tree, TreeNode* treeNode)
	189	{
e45132ac BA	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--;
a7868768 BA	200	}
	201
	202	void tree_remove(Tree* tree, TreeNode* treeNode)
	203	{
e45132ac BA	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);
a7868768 BA	216	}
	217
	218	void tree_rm_childs(Tree* tree, TreeNode* treeNode)
	219	{
e45132ac BA	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;
a7868768 BA	229	}
	230
	231	void tree_clear(Tree* tree)
	232	{
e45132ac BA	233	if (tree->root != NULL)
	234	_tree_remove_rekursiv(tree, tree->root);
	235	_tree_init(tree, tree->dataSize);
a7868768 BA	236	}
	237
	238	void tree_destroy(Tree* tree)
	239	{
e45132ac BA	240	if (tree->root != NULL)
	241	tree_clear(tree);
	242	safe_free(tree);
a7868768 BA	243	}
	244
	245	////////////////////
	246	// Iterator logic //
	247	////////////////////
	248
	249	TreeIterator* tree_get_iterator(Tree* tree, TreeIteratorMode mode)
	250	{
e45132ac BA	251	TreeIterator* treeI = (TreeIterator*) safe_malloc(sizeof (TreeIterator));
	252	treeI->tree = tree;
	253	treeI->mode = mode;
	254	treeI_reset(treeI);
	255	return treeI;
a7868768 BA	256	}
	257
	258	void treeI_reset(TreeIterator* treeI)
	259	{
e45132ac	260	treeI->current = treeI->tree->root;
a7868768 BA	261	}
a7868768 BA	262
1ff641f9	263	bool treeI_has_data(TreeIterator* treeI)
a7868768	264	{
e45132ac	265	return (treeI->current != NULL);
a7868768 BA	266	}
	267
	268	TreeNode* treeI_get_raw(TreeIterator* treeI)
	269	{
e45132ac	270	return treeI->current;
a7868768 BA	271	}
	272
	273	void treeI_move_next(TreeIterator* treeI)
	274	{
e45132ac BA	275	TreeIteratorMode mode = treeI->mode;
	276	switch (mode)
	277	{
1d60b10a BA	278	case IN_DEPTH:
1d60b10a BA	279	if (!tree_is_leaf(treeI->current))
e45132ac	280	{
1d60b10a BA	281	// easy case: just descend deeper in the tree
1d60b10a BA	282	treeI->current = treeI->current->firstChild;
e45132ac BA	283	return;
e45132ac BA	284	}
1d60b10a BA	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;
e45132ac	321	}
a7868768 BA	322	}
	323
	324	void treeI_destroy(TreeIterator* treeI)
	325	{
e45132ac	326	safe_free(treeI);
a7868768	327	}