#ifndef lint
static char sccsid[] = "@(#)retniop.c	1.7 (UKC) 4/7/86";
#endif lint
/*
 *	Pointer-reversing tree walk requires no extra space (including stack)
 *	to walk an arbitrarily big tree.
 *
 *	State of the tree in mid-walk:
 *
 *				   ROOT
 *				 ---------
 *		       .------->|wentleft |
 *		      /		|---------|
 *		     .		|NIL |	  |
 *		     |		 ---------
 *		     |			\
 *		     |			 \
 *		     |			  J
 *		     |	 ---------	 ---------
 *		   .-|->|wentleft |	|unvisited|
 *		  /  |	|---------|	|---------|
 *		 .   '	|    |	  |	|    |	  |
 *		 |    \	 ---------	 ---------
 *		 '     \__/	\
 *		  \		 \
 *		   '--------.	  J
 *		 ---------  |
 *   parent --> |wentright| |
 *		|---------| |
 *		|    |	  | |
 *		 ---------  '
 *		  /	\__/
 *		 /
 *		L
 *			 ---------
 *			|unvisited| <-- current
 *			|---------|
 *			|    |	  |
 *			 ---------
 *			  /	\
 *			 /	 \
 *			L	  J
 *
 */

#include <stdio.h>

#include "ptr.h"

/*
 *	Some defines to do the pointer-twiddling required to move about in the
 *	tree. To follow them, dry-run them on the above tree diagram.
 *	The do { ... } while (0) is syntactic garbage to make the define
 *	behave exactly like a function call in if-else clauses.
 *
 *	goleft performs the following transformation:
 *
 *		.---------.			.---------.
 *     parent-->|	  |		     .->|	  |
 *		|---------|		    /	|---------|
 *		|    |	  |		   .	|    |	  |
 *		'---------'		   |	'---------'
 *					   |
 *					   |
 *					   |
 *		.---------.		   |	.---------.
 *    current-->|	  |		   '	|wentleft |<--parent
 *		|---------|		    \	|---------|
 *		|  . |	  |		     '--+--  |	  |
 *		'--+------'			'---------'
 *		  /
 *		 /
 *		L
 *	.---------.			.---------.
 *	|	  |	      current-->|	  |
 *	|---------|			|---------|
 *	|    |	  |			|    |	  |
 *	'---------'			'---------'
 *
 */

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

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

#define goright(current, parent) do {	\
	node_t *child;			\
					\
	current->history = wentright;	\
	/* go down right branch */	\
	child = current->right;		\
	current->right = 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 {		\
	switch (parent->history) {		\
		node_t *grandparent;		\
						\
	case wentleft:				\
						\
		grandparent = parent->left;	\
		parent->left = current;		\
		current = parent;		\
		parent = grandparent;		\
		break;				\
						\
	case wentright:				\
						\
		grandparent = parent->right;	\
		parent->right = current;	\
		current = parent;		\
		parent = grandparent;		\
		break;				\
	}					\
} 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 != NULL) {
			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 != NULL) {
			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 = NULL;

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

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