#include "common.h"
#include "code.h"
#include "sym.h"
#include "machine.h"

/*
 * Routines to enumerate paths of a tree.  Firt call path_setup to
 * initialize the internal data structure.  Each component of the
 * path may be consecutively retrieved by calling path_getsym.
 */

/*
 * For trees, a path is defined to be the sequence of nodes and edges
 * from the root to a leaf.  A path is represented here as a list of
 * path components.  Each component is represented by the following
 * strucutre and may either be a pointer to a node or an integer.
 * If the integer is i then the next component is the ith child of the
 * previous component in the list.  For example, "a 3 b 1 c" is a path
 * for the tree "a(x,y,b(c,k))".  The tag field indicates whether the
 * component is a node or a branch.
 *	When the component represents a node then the node field points
 * the corresponding Node structure.  When the component is a branch then
 * branch is the index of the current branch followed (1 is leftmost...)
 * and node is a list of all unexamined children.
 */
struct path {
	int tag;
#define		P_NODE	0
#define		P_BRANCH	1
	int branch;
	Node *node;
};

/*
 * The path component list is stored in the path array.  Path_length
 * is the length of the path.  Path_ptr points to the first unread
 * component of the path component list. (see path_getsym
 * and path_build for details)
 */
#define MAXPATH 64
struct path path[MAXPATH];
static int path_length;
static struct path *path_ptr = NULL;

/*
 * Given a tree, path_setup updates the path array with the leftmost
 * of a subtree starting at root.  The leftmost path is produced by
 * following the leftmost branch of every encountered interior node 
 * starting at the root.  Note that this routine can be used to layout
 * the leftmost branch of a subtree into part of the path array and for
 * initializing the path array with the leftmost path of the whole tree.
 */
void
path_setup(Node *root)
{
	for(;;) {
		register struct path *pp = &path[path_length++];
		Node *ep;
		assert (root!=NULL);

		if(path_length > MAXPATH)
			error(1, "maxpathlength exceeded");

		/* Place node in the component list */
		pp->tag = P_NODE;
		pp->node = root;

		/* If leaf encountered exit */
		if ((ep=root->children)==NULL)
			break;

		/*
		 * Mark that the left branch (i.e. 1st in our numbering
		 * scheme) was followed.
		 */
		pp = &path[path_length++];
		if(path_length > MAXPATH)
			error(1, "maxpathlength exceeded");
		pp->tag = P_BRANCH;
		pp->branch = 1;
		pp->node = ep->siblings;
		root = ep;
	}
	path_ptr = path;
}

/*
 * Path_build generates the next path of the tree and returns 0 if
 * there are no more paths.  Each path can be associated
 * with exactly one leaf.  Hence the ordering of paths generated by
 * this routine is the same as a left to right ordering of the leaves.
 */
int
path_build(void)
{
	Node *np;
	struct path *pp = &path[path_length-1];

	/*
	 * Assert that the end of the last path was indeed
	 * a leaf.
	 */
	assert (pp->tag == P_NODE);
	assert ((pp->node)->children == NULL);

	/*
	 * back up until we find a node that still has children
	 */
	pp--;
	while (pp >= &path[1] && pp->node==NULL) pp -= 2;

	/*
	 * If we hit the beginning of the path array, there are
	 * no more leaves and hence no more paths.
	 */
	if (pp < &path[1]) {
		/* reset path_length */
		path_length = 0;
		return(0);
	}

	/*
	 * append the new leftmost branch onto the rest of
	 * the path component list.
	 */
	pp->branch++;
	np = pp->node;
	pp->node = np->siblings;
	path_length = pp-path+1;
	path_setup(np);
	return(1);
}

/*
 * Get the next component in the path component list.
 * When the end of a path is reached, NULL is returned and
 * the next call will retrieve the first component of the next path.
 * EOF is returned if there are no more paths.
 * A return value of 1 indicates that the value returned in mi is
 * valid.
 */
int
path_getsym(register struct machine_input *mi)
{
	if(path_ptr > &path[path_length]) {
		/*
		 * When the end of that path is passed, generate the
		 * next path.
		 */
		if(!path_build())
			return(EOF);
		path_ptr = path;
	}
	if (path_ptr == &path[path_length]) {
		/*
		 * Path_ptr just encountered the end of
		 * the path, return a marker value
		 * to notify caller.
		 */
		mi->value = 0;
		path_ptr++;
		return(NULL);
	} else if (path_ptr->tag != P_BRANCH) {
		/*
		 * Translate the right machine input value
		 */
		mi->sym = (path_ptr->node)->sym;
		switch((mi->sym)->attr) {

		case A_NODE:
			mi->value = MV_NODE((mi->sym)->unique);
			break;

		case A_LABEL:
			mi->value = MV_LABEL((mi->sym)->unique);
			break;

		default:
			assert(0);
		}
	} else {
		mi->value = MV_BRANCH(path_ptr->branch);
	}
	path_ptr++;
	return(1);
}

/*
 * Prints out path for debugging
 */
void
prpath(void)
{
	register int i;
	for(i=0; i < path_length; i++) {
		struct path *pp = &path[i];
		if (pp->tag==P_NODE) {
			struct node *np = pp->node;
			printf("[%s]", (np->sym)->name);
		} else {
			assert (pp->tag == P_BRANCH);
			printf("%d", pp->branch);
		}
	}
	putchar('\n');
}