path: root/utils/ptree.c

#include "../stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "ptree.h"

//#define VERIFY_TREE

struct ptree_node {
	void *pn_value;
	struct ptree_node *pn_parent;
	struct ptree_node *pn_left;
	struct ptree_node *pn_right;
};

static int
_walk_to(void *v, 
		 struct ptree_node **startp, 
		 struct ptree_node ***pp,
		 int (*cmp)(const void *v1, const void *v2))
{
	struct ptree_node **nextp;
	int c = -1;

	nextp = startp;
	while (*nextp)
	{
		c = cmp(v, (*nextp)->pn_value);
		*startp = *nextp;
		if (c == 0)
			break;
		if (c < 0)
			nextp = &(*nextp)->pn_left;
		else
			nextp = &(*nextp)->pn_right;
		if (pp)
			*pp = nextp;
	}

	return c;
}


static ptree_walk_res_t
_visit(struct ptree_node *pn, 
	   int level, 
	   void *arg1, 
	   void *arg2)
{
	ptree_walk_res_t (*func)(const void *, int, void *, void *) = arg1;
	
	return func(pn->pn_value, level, arg2, pn);
}

static ptree_node_t *
_find_min(ptree_node_t *pn, 
		  int *levelp)
{
	while (pn->pn_left)
	{
		pn = pn->pn_left;
		if (levelp)
			(*levelp)++;
	}
	return pn;
}

static ptree_node_t *
_find_succ(ptree_node_t *pn, 
		   int *levelp)
{
	if (pn->pn_right)
	{
		pn = pn->pn_right;
		if (levelp)
			(*levelp)++;
		while (pn->pn_left)
		{
			pn = pn->pn_left;
			if (levelp)
				(*levelp)++;
		}
	}
	else
	{
		while (pn->pn_parent && pn->pn_parent->pn_right == pn)
		{
			pn = pn->pn_parent;
			if (levelp)
				(*levelp)--;
		}
		pn = pn->pn_parent;
		if (levelp)
			(*levelp)--;
	}
		
	return pn;
}

static int
_walk_int(struct ptree_node *pn, 
		  ptree_order_t order, 
		  int level,
		  ptree_walk_res_t (*func)(struct ptree_node *, int level, void *, void *),
		  void *arg1, 
		  void *arg2)
{
	ptree_walk_res_t res;
	ptree_node_t *next;

	if (!pn)
		return PTREE_WALK_CONTINUE;

	if (order == PTREE_INORDER)
	{
		int nlevel;

		pn = _find_min(pn, &level);
		while (pn) 
		{
			nlevel = level;
			next = _find_succ(pn, &nlevel);
			if ((res = func(pn, level, arg1, arg2)) != PTREE_WALK_CONTINUE)
				return res;
			level = nlevel;
			if (level < 0)
				level = 0;
			pn = next;
		}
		return PTREE_WALK_CONTINUE;
	}
	if (order == PTREE_PREORDER && (res = func(pn, level, arg1, arg2)) != PTREE_WALK_CONTINUE)
		return res;
	if ((res = _walk_int(pn->pn_left, order, level + 1, func, arg1, arg2)) != PTREE_WALK_CONTINUE)
		return res;
	if ((res = _walk_int(pn->pn_right, order, level + 1, func, arg1, arg2)) != PTREE_WALK_CONTINUE)
		return res;
	if (order == PTREE_POSTORDER && (res = func(pn, level, arg1, arg2)) != PTREE_WALK_CONTINUE)
		return res;
	return PTREE_WALK_CONTINUE;
}

#ifdef VERIFY_TREE
static ptree_walk_res_t
_count(struct ptree_node *pn, 
	   int level, 
	   void *arg1, 
	   void *arg2)
{
	int *counter = arg1;
	(*counter)++;
	return PTREE_WALK_CONTINUE;
}

//counts the number of nodes
static int
_count_nodes(ptree_node_t **rootp)
{
	int counter = 0;
	_walk_int(*rootp, PTREE_INORDER, 0, _count, &counter, 0);
	return counter;	
}

static ptree_walk_res_t
_verify_node(struct ptree_node *pn, 
	   int level, 
	   void *arg1, 
	   void *arg2)
{
	int (*cmp)(const void *v1, const void *v2) = arg1;
	struct ptree_node **prev_pn_p = (struct ptree_node **)arg2;
	struct ptree_node *prev_pn = *prev_pn_p;
	
	if(pn->pn_left != NULL && pn->pn_left->pn_parent != pn)
   		return PTREE_WALK_STOP;
	if(pn->pn_right != NULL && pn->pn_right->pn_parent != pn)
   		return PTREE_WALK_STOP;

	if(prev_pn != NULL)
	{
		//this value should always be greater then the last value
		if(cmp(pn->pn_value, prev_pn->pn_value) <= 0)
   			return PTREE_WALK_STOP;
	}
	*prev_pn_p = pn;
		   
   return PTREE_WALK_CONTINUE;
}

//static int
//pdecmp(const void *sv, const void *dv)
//{
//	int res;
//	
//	char *str1 = *(char **)sv;
//	char *str2 = *(char **)dv;
//	
//	res = strcmp(str1, str2);
//	
//	if(res <= 0)
//		return res;
//	
//	return res;
//}

//Verifies that the tree is a valid Binary search tree
static int
_verify_tree(ptree_node_t **rootp, int (*cmp)(const void *v1, const void *v2))
{
	struct ptree_node *prev_pn = NULL;
	if(_walk_int(*rootp, PTREE_INORDER, 0, _verify_node, cmp, &prev_pn) == PTREE_WALK_STOP)
		return 0;
	return 1;
}
#endif

static void
_remove_node(ptree_node_t **rootp, 
			 ptree_node_t *pn, 
			 void **oldval)
{
	ptree_node_t **pp;
	ptree_node_t **predp;
	ptree_node_t *pred;
	
#ifdef VERIFY_TREE
	int countStart = _count_nodes(rootp), countEnd=0;
#endif

	//Find pn in the tree
	if (!pn->pn_parent)
	{
		assert(rootp && pn == *rootp);
		pp = rootp;
	}
	else
	{
		if (pn->pn_parent->pn_left == pn)
			pp = &pn->pn_parent->pn_left;
		else
			pp = &pn->pn_parent->pn_right;
	}
	
	//pp should now point at the location where pn is stored in the tree
	assert(pp);
	
	//Best case - only one child, on no children, just remove as in a list
	if (!pn->pn_left)
	{
		*pp = pn->pn_right;
		if (pn->pn_right)
			pn->pn_right->pn_parent = pn->pn_parent;
	}
	else if (!pn->pn_right)
	{
		*pp = pn->pn_left;
		if (pn->pn_left)
			pn->pn_left->pn_parent = pn->pn_parent;
	}

	//Worst case: pn contains both left and right children
	else 
	{
		for (predp = &pn->pn_left; (*predp)->pn_right; )
			predp = &(*predp)->pn_right;
		pred = *predp;

		//pred either has a left child or no child
		if (pred->pn_parent->pn_left == pred)
			pred->pn_parent->pn_left = pred->pn_left;
		else
			pred->pn_parent->pn_right = pred->pn_left;
		if(pred->pn_left)
			pred->pn_left->pn_parent = pred->pn_parent;

		*pp = pred;

		pred->pn_parent = pn->pn_parent;
		pred->pn_left = pn->pn_left;
		pred->pn_right = pn->pn_right;

		if (pn->pn_left)
			pn->pn_left->pn_parent = pred;
		pn->pn_right->pn_parent = pred;
	}

	//Return the value of the removed node
	if (oldval)
		*oldval = pn->pn_value;

	free(pn);
	
#ifdef VERIFY_TREE
	countEnd = _count_nodes(rootp);
	countStart--;
	assert(countEnd == countStart);
#endif
}

int
ptree_inorder_walk_remove(ptree_node_t **rootp, 
						  void **oldval, 
						  void *pn,
						  int (*cmp)(const void *v1, const void *v2))
{
	assert(pn);
	if (!pn)
		return 0;
#ifdef VERIFY_TREE
	assert(_verify_tree(rootp, cmp));
#endif
	_remove_node(rootp, pn, oldval);
#ifdef VERIFY_TREE
	assert(_verify_tree(rootp, cmp));
#endif
	return 1;
}

ptree_walk_res_t
ptree_walk(ptree_node_t *start, 
		   ptree_order_t order,
		   ptree_walk_res_t (*func)(const void *v1, int level, void *arg, void *ptree_inorder_walking_remove_arg), 
		   int (*cmp)(const void *v1, const void *v2),
		   void *arg)
{
#ifdef VERIFY_TREE
	ptree_node_t *start_p = start;
	if(cmp != NULL)
		assert(_verify_tree(&start_p, cmp));
#endif

	return _walk_int((struct ptree_node *)start, order, 0, _visit, (void *)func, arg);
}

ptree_walk_res_t
ptree_clear_func(struct ptree_node *pn, 
				 int level, 
				 void *arg1, 
				 void *arg2)
{
	free(pn); pn = NULL;

	return PTREE_WALK_CONTINUE;
}

void
ptree_clear(ptree_node_t **rootp)
{
	_walk_int(*rootp, PTREE_POSTORDER, 0, ptree_clear_func, 0, 0);
	*rootp = 0;
}

int
ptree_remove(void *v, 
			 ptree_node_t **rootp, 
			 int (*cmp)(const void *v1, const void *v2), 
			 void **oldval)
{
	struct ptree_node *cur;
	
#ifdef VERIFY_TREE
	assert(_verify_tree(rootp, cmp));
#endif

	cur = *rootp;
	if (_walk_to(v, &cur, NULL, cmp) != 0)
		return 0;
	_remove_node(rootp, cur, oldval);
	
#ifdef VERIFY_TREE
	assert(_verify_tree(rootp, cmp));
#endif

	return 1;
}

int
ptree_replace(void *v, 
			  ptree_node_t **rootp, 
			  int (*cmp)(const void *v1, const void *v2), 
			  void **oldval)
{
	struct ptree_node **parentpp;
	struct ptree_node *parentp;
	struct ptree_node *pn;
	int c;
	
#ifdef VERIFY_TREE
	int countStart = _count_nodes(rootp), countEnd=0;
#endif
	
	parentp = *rootp;
	parentpp = rootp;
	
#ifdef VERIFY_TREE
	assert(_verify_tree(rootp, cmp));
#endif

	//if we find v in the tree, replace it
	if ((c = _walk_to(v, &parentp, &parentpp, cmp)) == 0)
	{
		if (oldval)
			*oldval = parentp->pn_value;
		parentp->pn_value = v;
	
#ifdef VERIFY_TREE
	assert(_verify_tree(rootp, cmp));
#endif
	
#ifdef VERIFY_TREE
	countEnd = _count_nodes(rootp);
	assert(countEnd == countStart);
#endif
		
		return 1;
	}
	
	//otherwise, add it to the tree
	if (!(pn = malloc(sizeof (*pn))))
		return 0;
	
	memset(pn, 0, sizeof (*pn));
	pn->pn_value = v;
	pn->pn_parent = parentp;
	*parentpp = pn;
	if (oldval)
		*oldval = 0;
	
#ifdef VERIFY_TREE
	assert(_verify_tree(rootp, cmp));
#endif
	
#ifdef VERIFY_TREE
	countEnd = _count_nodes(rootp);
	countStart++;
	assert(countEnd == countStart);
#endif

	return 1;
}

int
ptree_contains(void *v, 
			   ptree_node_t *parentp, 
			   int (*cmp)(const void *v1, const void *v2), 
			   void **nodeval)
{
	int c;

	if ((c = _walk_to(v, &parentp, NULL, cmp)) == 0)
	{
		if (nodeval)
			*nodeval = parentp->pn_value;
		return 1;
	}
	if (nodeval)
		*nodeval = 0;
	return 0;
}