#include <stdio.h>

#ifdef MEMDBG
#include "memdbg.h"
#endif

#include "treestruct.h"

treenode parent(n)
treenode n;
{
	list old;
	treebranch branch;
	treenode p=NULL;

	if(notnode(n))
		return(NULL);

	old=listnode(n->branches);

	startlist(n->branches);
	while((branch=listnext(n->branches))!=NULL)
		if(branch->up!=n)
		{
			p=branch->up;
			break;
		}
	setnode(n->branches, old);
	return(p);
}

int treeleaf(n)
/* returns 1 if it's a leaf node */
/* true if all branches point to parents */
treenode n;
{
	treebranch b;

	startlist(n->branches);
	while((b=listnext(n->branches))!=NULL)
		if(b->up==n)
			return(0);
	return(1);
}

int treechildren(n)
/* returns number of descendants of node n */
treenode n;
{
	static int i;
	static treebranch b;

	startlist(n->branches);
	i=0;
	while((b=listnext(n->branches))!=NULL)
		if(b->down!=n)
			i++;
	return(i);
}

int treeleaves(n)
/* returns number of leaves under node n */
treenode n;
{
	int i=0;
	list c;

	tforsubtree(n->branches, c)
	{
		if(treeleaf(subtree(c)))
			i++;
		else
			i+=treeleaves(subtree(c));
	}
	return(i);
}

treebranch getparentandbranch(n, p)
/* like parent, but returns 0 only if no parent pointer exists */
treenode n, *p;
{
	list old;
	treebranch branch;
	treebranch result=NULL;

	if(notnode(n))
		return(NULL);

	old=listnode(n->branches);

	startlist(n->branches);
	while((branch=listnext(n->branches))!=NULL)
		if(branch->up!=n)
		{
			*p=branch->up;
			result=branch;
			break;
		}
	setnode(n->branches, old);
	return(result);
}

treebranch branchtonode1(n, l, up)
/* at node n, looking for node l, came from node up */
treenode n, l, up;
{
	list old=listnode(n->branches);
	treebranch found=NULL;
	treenode tmp;
	treebranch branch;

	startlist(n->branches);
	while(found==NULL && (branch=listnext(n->branches))!=NULL)
	{
		tmp=othernode(n, branch);
		if(tmp==l)
			found=branch;
		else if(tmp!=up && tmp!=NULL)
		{
			if(branchtonode1(tmp, l, n)!=NULL)
				found=branch;
		}
	}
	setnode(n->branches, old);
	return(branch);
}

treebranch branchtonode(a, b)
treenode a, b;
/* returns the branch that heads off from a in the direction of b */
/* returns NULL if they aren't in the same tree */
{
	if(notnode(a) || notnode(b))
		return(NULL);
	
	if(tree_get_tree(a) != tree_get_tree(b))
		return(NULL);
	
	return(branchtonode1(a, b, NULL));
}

int ascendant(a, b)
/* returns 1 if a is the ascendant of b */
treenode a, b;
{
	treenode tmp;

	if(notnode(a) || notnode(b))
		return(0);
	
	if(tree_get_tree(a) != tree_get_tree(b))
		return(0);
	
	tmp=b;
	do
	{
		tmp=parent(tmp);
		if(tmp==a)
			return(1);
	} while(tmp!=NULL);
	return(0);
}

int descendant(a, b)
/* returns 1 if a is the descendant of b */
treenode a, b;
{
	return(ascendant(b, a));
}

int parentdistance(n, distance)
treenode n;
double *distance;
{
	list old;
	treebranch branch;
	int result;

	if(notnode(n))
		return(NULL);

	old=listnode(n->branches);

	result=0;
	startlist(n->branches);
	while((branch=listnext(n->branches))!=NULL)
		if(branch->up!=n)
		{
			result=branch->specified;
			if(branch->specified)
				*distance=branch->distance;
			else
				*distance=tree_get_tree(branch)->unspecdist;
			break;
		}
	setnode(n->branches, old);
	return(result);
}

int branchdistance(b, dist)
treebranch b;
double *dist;
{
	int result;

	result=b->specified;
	if(b->specified)
		*dist=b->distance;
	else
		*dist=tree_get_tree(b)->unspecdist;
	return(result);
}

int setparentdistance(n, distance)
/* sets the distance from n to it's parent */
treenode n;
double distance;
{
	list old;
	treebranch branch;
	int result;

	if(notnode(n))
		return(NULL);

	old=listnode(n->branches);

	result=0;
	startlist(n->branches);
	while((branch=listnext(n->branches))!=NULL)
		if(branch->up!=n)
		{
			branch->specified=1;
			branch->distance=distance;
			result=1;
			break;
		}
	setnode(n->branches, old);
	return(result);
}

double searchdistance(n, up, l, sp)
/* search links from n for l, not following those that go to up or NULL */
/* recursively add up the distances */
treenode n, up, l;
int *sp;
{
	treenode o;
	treebranch b;
	double result;
	int tmp;

	*sp=0;
	result=0.0;
	startlist(n->branches);
	while((b=listnext(n->branches))!=NULL)
	{
		o=othernode(n, b);
		if(o==l)
		{
			*sp=1;
			if(b->specified)
				result=b->distance;
			else
				result=tree_get_tree(b)->unspecdist;
			break;
		}
		if(o!=NULL && o!=up)
		{
			if(b->specified)
				result=b->distance+searchdistance(o, n, l, &tmp);
			else
				result=tree_get_tree(b)->unspecdist+
					searchdistance(o, n, l, &tmp);
			if(tmp)
			{
				*sp=1;
				break;
			}
		}
	}
	return(result);
}

int nodedistance(a, b, distance)
/* returns the distance from a to b.  returns 1 iff a and b are on same tree,
	and distance is specified */
/* returns -1:not found, 0: not specified, 1: specified */
treenode a, b;
double *distance;
{
	int result;
	double d;

	if(notnode(a) || notnode(b))
		return(0);
	if(tree_get_tree(a) != tree_get_tree(b))
		return(0);
	
	d=searchdistance(a, NULL, b, &result);
	*distance=d;
	return(result);
}