#ifndef lint
static char sccsid[] = "@(#)eorptr.c	1.1 (UKC) 4/7/86 from retniop.c 1.6 (UKC) 3/7/86";
#endif lint
/*
 *	Pointer-eoring tree requires no extra space (including stack)
 *	to walk an arbitrarily big tree.
 *
 *	Instead of regular pointers in each branch, we store the exclusive OR
 *	of the addresses of the child and the parent of the current node.
 *
 *	State of the tree in mid-walk: (only history bits are modified)
 *
 *				   ROOT
 *				 ---------
 *		               A|wentleft |
 *		       		|---------|
 *		      		| B  | C  |
 *		      		 ---------
 *		      		  /     \
 *		      		 /	 \
 *		      		L	  J
 *		      	 ---------	 ---------
 *		       B|wentleft |    C|         |
 *		      	|---------|	|---------|
 *		      	|A^D | A  |	| A  | A  |
 *		       	 ---------	 ---------
 *		          /	 
 *		   	 /	  
 *		        L    	   
 *		 ---------   
 *   parent -->D|wentright|  
 *		|---------|  
 *		| B  |B^E |  
 *		 ---------   
 *		   	\   
 *		  	 \
 *		 	  J
 *			 ---------
 *		       E|         | <-- current
 *			|---------|
 *			| D  | D  |
 *			 ---------
 */

#include <stdio.h>

#include "ptr.h"

/*
 *	Some defines to move about in the tree.
 */

#define goleft(current, parent) do {	\
	node_t *child;			\
					\
	/* go down left branch */	\
	current->history = wentleft;	\
	child = (node_t *)((int)(current->left)^(int)parent);	\
	parent = current;		\
	current = child;		\
} while (0)

/* goright: same as goleft, but to the right (surprise!) */

#define goright(current, parent) do {	\
	node_t *child;			\
					\
	/* go down right branch */	\
	current->history = wentright;	\
	child = (node_t *)((int)(current->right)^(int)parent);\
	parent = current;		\
	current = child;		\
} while (0)

/*
 * find grandparent in one of the parent's pointers.
 * Which one it was stored in depends upon which way
 * we came down from the parent.
 *
 * Performs the exact inverse transformation of goleft or goright.
 */
		
#define goup(current, parent) do {		\
	node_t *grandparent;			\
						\
	switch (parent->history) {		\
	case wentleft:				\
		grandparent = (node_t *)((int)(parent->left)^(int)current);\
		break;				\
	case wentright:				\
		grandparent = (node_t *)((int)(parent->right)^(int)current);\
		break;				\
	}					\
	current = parent;			\
	parent = grandparent;			\
} while (0)

treewalk(order, current, process)
order_t order;		/* which sort of treewalk to do */
node_t *current;	/* pointer to root of tree */
void (*process)();	/* function to apply to each node */
{
	node_t *parent = NULL;

	if (current == NULL) return;

	goto unvisited;

	for (;;) switch (current->history) {

unvisited:	/* Deal with a node to which we have just come down. */
		if (order == preorder) (* process)(current);
		if (current->left != parent) {
			goleft(current, parent);
			goto unvisited;
		}
		/* else we have processed the (null) left branch so */
		/* go for the right branch */

	case wentleft:
		/* Deal with a node whose left branch has been processed. */

		if (order == inorder) (* process)(current);
		/* try going down the right branch */
		if (current->right != parent) {
			goright(current, parent);
			goto unvisited;
		}
		/* else we have processed the right branch completely so */
		/* do the necessary and go back up */

	case wentright:
		/* Deal with a node where both branches have been done */

		if (order == postorder) (* process)(current);

		/* the left branch, the current node and the right
		 * branch have been processed. Go back up. */
		
		/* check to see if we are back at the root */
		if (parent == NULL) return;

		goup(current, parent);
		/* loop and switch according to which branch we just came up */
	}
}

addnode(root, n)
node_t **root;		/* ptr to root (var for first node) */
{
	char *malloc();
	node_t *current = *root;
	node_t *parent = NULL;

	/* wend our way down to the leaf we have to add the new entry to */
	while (current != NULL) {
		if (n < current->contents)
			goleft(current, parent);
		else 
			goright(current, parent);
	}

	/* now current == NULL and parent points to the leaf node we are to
	 * add to. Parent->history determines which of the branches to add the
	 * new cell onto. This happens for free on the way back up.
	 */
		
	current = (node_t *) malloc(sizeof(node_t));
	if (current == (node_t *) 0) {
		fputs("Out of memory", stderr);
		exit(1);
	}
	current->contents = n;
	current->left = current->right = parent;
	switch (parent->history) {
	case wentleft:
		parent->left = (node_t *)((int)(parent->left)^(int)current);
		break;
	case wentright:
		parent->right = (node_t *)((int)(parent->right)^(int)current);
		break;
	}

	while (parent != NULL) goup(current, parent);

	/* This only has an effect for the first node.
	 * After that it is a no-op
	 */
	*root = current;
}