/*
 * Deleting a node
 *  (When a node is deleted, free its memory space for use by
 *   new nodes by passing a pointer to the deleted node to
 *   tfree().)
 *      1. Start at the node to be deleted.
 *      2. If the node to be deleted has no children, delete it.
 *         Change the parent's pointer that pointed to the 
 *         deleted node to point to NULL.
 *      3. If the node to be deleted has only one child, make
 *         the parent of the node to be deleted point to the 
 *         child of the node to be deleted.  Then delete the
 *         node to be deleted.
 *      4. Else the node has two children.
 *              A. Descend to the leftmost node of the right
 *                 subtree of the node to be deleted: first
 *                 descend to the right child of the node to be
 *                 deleted.
 *              B. Descend to the left child, if there is one.
 *                 Continue descending to left children until
 *                 there is no left child.
 *              C. Copy this node (the leftmost child of the
 *                 right subtree) to the node to be deleted.
 *              D. Delete this (the leftmost child of the right
 *                 subtree) node.
 *
 * Inserting a node:
 *      1. Start at the root.
 *      2. If the node is greater then the root, descend to the
 *         right.  If the node is less then the root, descend to 
 *         the left.  (If the node equals the root, the node to
 *         be added has a duplicate key, so return an error.)  
 *         Continue descending this way until you can go no 
 *         further.
 *      3. Call talloc() to get a pointer to the new node.  
 *         Insert the pointer into the appropriate lnode or 
 *         rnode pointer of the new parent.
 *              A. If the inserted node is a left child, add a 
 *                 thread in its rnode pointer to the parent and 
 *                 set the rtnode bit.
 *              B. If the inserted node is a right child, remove
 *                 the thread from the parent and give it to the
 *                 new child.
 *
 * Inorder traversal of the tree (nonrecursive):
 *      1. Starting at the root, descend to the left until there
 *         is no successive left child.  This is the first node
 *         in the order.  Print the key.  
 *      2. If the node has a right child, set assign the right
 *         child as the root.  Then go to 1.
 *      3. If the node has no right child, then 
 *         follow the thread.  Then go to 2.
 */
 
#include <stdio.h>
#include <malloc.h>

#define BUFFER	128		/* command string buffer size (characters) */
#define MAGIC   0xabcdef12L     /* to check validity of freed memory block */

struct datastruct {
        int field1;
        } Record;

typedef struct node {
        int Threadflag;		
        struct node *Lchild;
	struct node *Rchild;
        struct datastruct *Record;
        }; 

        static char cmdstring[128];     /* a command string     */


/*-------------------------------------------------------------------
 * Get the left child of the Node.  Return NULL if no child.
 */
struct node * getlchild (nodep)
struct node *nodep;              /* information for the current node */
{
	printf("getlchild() entered\n");/* DEBUGGER */
	if (nodep->Threadflag & 2 == 1)	/* if pointer is a thread    */
	{
		return NULL;
	}

	else
	{
        	return nodep->Lchild;
	}
}


/*-------------------------------------------------------------------
 * Get the right child of the Node.  Return NULL if no child.
 */
struct node * getrchild (nodep)
struct node *nodep;              /* information for the current node */
{
	printf("getrchild() entered\n");/* DEBUGGER */
	if (nodep->Threadflag & 1 == 1)	/* if pointer is a thread    */
	{
		return NULL;
	}

	else
	{
		return nodep->Rchild;
	}
}


/*-------------------------------------------------------------------
 * If the node has a thread, get it. If not, return NULL.
 */
struct node * thread (nodep)
struct node *nodep;
{
	printf("thread() entered\n");/* DEBUGGER */

	if (nodep->Threadflag & 1 == 1)	/* if right pointer is a thread     */
	{
        	return nodep->Rchild;
	}

	if (nodep->Threadflag & 2 == 1)	/* if left  pointer is a thread     */
	{
        	return nodep->Lchild;
	}

	else
	{
		return NULL;
	}
}
/*-------------------------------------------------------------------
 * Return the leftmost node of the tree whose root is Node.
 * Return NULL if there is no left child to the node passed to goleftmost.
 */
struct node * goleftmost (Node)
struct node *Node;                      /* information for the current node */
{
        struct node *Newnode;           /* information about a new node     */

	printf("goleftmost() entered\n");/* DEBUGGER */

        while (Newnode = getlchild (Node) )
        {
                Node = Newnode;
        }

        return Node;
}


/*-------------------------------------------------------------------
 * Print this when a command input error has been made.
 */
cmderror()
{
	printf ("\nTree does not take arguments.\n");
	printf ("Input is a series of single line commands:\n\n");
	printf ("       [i, d] key\n\n");
	printf (" i inserts key into the tree.\n");
	printf (" d deletes key from the tree.\n");
	return ;
}


/*-------------------------------------------------------------------
 * Print the data for Node.
 */
print(Node)
struct node *Node;                      /* information for the current node */
{
	printf("print() entered\n");/* DEBUGGER */
        printf (" %d", (Node->Record)->field1);
}


/*-------------------------------------------------------------------
 * Allocate memory for a new node.  Return a pointer to that space.
 */
struct node * talloc()
{
        struct node *nodep;             /* pointer to space for a new node  */

	printf("talloc() entered\n");	/* DEBUGGER */
	nodep = (struct node *) malloc( sizeof( struct node) );
	return nodep;
}


/*-------------------------------------------------------------------
 * Free memory used by a node.  Use pointer provided by talloc().
 */
tfree (nodep)
struct node *nodep;
{
	printf("tfree() entered\n");	/* DEBUGGER */
	free ( (char *)nodep);
	return;
}


/*-------------------------------------------------------------------
 * Remove spaces from the stdin command string.
 */
char * getcommand()
{
        char command[BUFFER];           /* command string buffer            */
	char cmdchar;			/* a character from command string  */
	char * oldplace;		/* chars old position in string     */
	char * newplace;		/* chars new position in string     */
	char * cmdbuffer;		/* buffer addr returned by gets()   */

        oldplace = command;
	newplace = command;

	if ( (cmdbuffer = gets(command) ) != NULL);
	{
		do
		{
			if ((cmdchar = *oldplace++) != ' ')
			{
				*newplace++ = cmdchar;
			}
		} while (cmdchar != '\0');
	}
        return cmdbuffer;
}


/*-------------------------------------------------------------------
 * Get the key at the Node.
 */
int getkey(Node)
struct node *Node;              /* information for the current node */
{
	int key;

	printf("getkey() entered\n");/* DEBUGGER */
	/* key = Node->Record->field1; */
	return key;
}


/*-------------------------------------------------------------------
 * Get the key from the stdin input line.
 */
int cmdkey(asciikey)
char * asciikey;			/* ASCII key string from stdin      */
{
	int binkey;
	printf ("cmdkey() entered\n");	/* DEBUGGER */	
	binkey = atoi(asciikey);
	return binkey;
}


/*-------------------------------------------------------------------
 * Return 1 if nodep is not the last in a postorder traversal of its
 * tree, return 0 if it is last.
 */
notlast (n)
struct node *n;
{
	printf ("notlast() entered\n");	/* DEBUGGER */	
return (getlchild(n) != NULL || getrchild(n) != NULL || thread(n) != NULL);
}

/*-------------------------------------------------------------------
 * Traverse tree inorder by following threads.  Print key of each node.
 */
inorder(rootnode)
struct node *rootnode;			/* the root node of the whole tree  */
{
        struct node *lchild;            /* left child                       */
        struct node *rchild;            /* right child                      */ 
        struct node *node;              /* information for the current node */
	struct node *nextnode;		/* next node in travel through tree */
	int dir = 0;			/* init travel direction set down   */

        while (notlast(node))
	printf ("inorder() entered\n");	/* DEBUGGER */	
        {
		if ( (nextnode = goleftmost(node)) && dir == 0)
                {
                        node = nextnode;
			print(node);
                }

		if (nextnode = thread(node))
		{
			node = nextnode;
			print (node);
			dir = 1;	/* set direction to up             */
		}

		if (nextnode = getrchild(node))
		{
			node = nextnode;
			if ((nextnode = goleftmost(node)) == 0)
			{
				print(node);
			}

			dir = 0;
		}
	}
	return;
}


/*-------------------------------------------------------------------
 * Delete the node containing key from the tree whose root is Rootnode.
 * Return a pointer to the deleted node or to NULL if not found.
 */
struct node * delete (rootnode, delkey) 
int delkey;				/* the key of the node to delete    */
struct node *rootnode;			/* the root node of the whole tree  */

{
	struct node * parentnode;      	/* a temporary node holder          */
	int rootkey;			/* the key of the current root node */

	printf ("delete() entered\n");	/* DEBUGGER */
	while ( ((rootkey = getkey(rootnode)) != delkey) && (rootkey != NULL) )
	{
		parentnode = rootnode;
		if (rootkey > delkey)
		{
			rootnode = rootnode->Lchild;
		}

		else
		{
			rootnode = rootnode->Rchild;
		}
	}

	if (rootkey == NULL)
	{
		return NULL;			/* key not found */
	}

	else
	{
		/* actual deleting goes here */
	}
	return;
}


/*-------------------------------------------------------------------
 * Insert a node into a binary threaded tree.
 * Return a pointer to the new node or to NULL if key already in tree. 
 */
struct node * insert (rootnode, newnode)
struct node *newnode;           	/* the node to be inserted          */
struct node *rootnode;			/* the root node of the whole tree  */
{
	int newkey;			/* the key of node to be inserted   */
	struct node *  nextnode;	/* node to check after this node    */

	printf("insert() entered\n");       /* DEBUGGER */

	newnode->Lchild = 0;            /* Initialize new node's pointers  */
	newnode->Rchild = 0;
	newnode->Threadflag = 0;

	if (rootnode == NULL)		/* If there is no root node yet     */
	{
		rootnode = newnode;
		return rootnode;	/* Return success		    */
	}

	newkey = getkey(newnode);

	for ( ; ; )
	{
		if (newkey == rootnode->Record->field1)
		{
			return NULL;		/* duplicate key	    */
		}

		else if (newkey > rootnode->Record->field1)
		{
		       nextnode = getrchild(rootnode);

		       if(nextnode == NULL || nextnode->Record->field1 > newkey)
		       {
				addrnode (rootnode, newnode);
				return newnode;
		       }
		}

		else			/* newkey must be < root nodes key */
		{
		       nextnode = getlchild(rootnode);

		       if(nextnode == NULL || nextnode->Record->field1 < newkey)
		       {
				addlnode (rootnode, newnode);
				return newnode;
		       }
		}

		rootnode = nextnode;
	}
}


/*-------------------------------------------------------------------
 * Insert newnode as the right child of oldnode.
 */
addrnode(oldnode, newnode)
struct node *oldnode;           	/* parent of node to be inserted    */
struct node *newnode;           	/* the node to be inserted          */
{
	printf("addrnode() entered\n");/* DEBUGGER */
	newnode->Rchild = oldnode->Rchild;
	oldnode->Rchild = newnode;
	newnode->Threadflag = oldnode->Threadflag;
	oldnode->Threadflag = 0;
	return;
}


/*-------------------------------------------------------------------
 * Insert newnode as the left child of oldnode.
 */
addlnode(oldnode, newnode)
struct node *oldnode;           	/* parent of node to be inserted    */
struct node *newnode;           	/* the node to be inserted          */
{
	printf("addlnode() entered\n");/* DEBUGGER */
	newnode->Lchild = oldnode->Lchild;
	oldnode->Lchild = newnode;
	newnode->Threadflag = 1;
	newnode->Rchild = oldnode;
	return;
}


/*-------------------------------------------------------------------
 * Program to test talloc(), tfree(), insert(), delete(), and inorder().
 */
main (argc, argv)
int argc;
char *argv[];
{
        struct node *Node;              /* information for the current node */
        struct node *newnode;           /* information about a new node     */
	struct node *rootnode;		/* the root node of the whole tree  */
	struct node *delnode;		/* deleted node returned by delete()*/
        char * command;                 /* an input command line            */
	int newkey;			/* key from input node command      */

        if (argc != 1)
	{
		cmderror();		/* print command instructions       */
		return 1;
	}
	
	rootnode = NULL;		/* initially tree is empty          */

	for ( ; ; )
	{
		printf ("tree: ");	/* prompt                           */
		command = getcommand();
		printf("Input command was %s\n", command);	/* DEBUGGER */
		
		if (*command == '\0')		/* if empty line entered    */ 
		{
			printf("quit? (y/n): ");

			if (* (getcommand()) == 'y')
			{
				return 0;	/* normal termination       */
			}
		}

		else if (*command == 'i')	/* command to insert a node */
		{
			printf("insert command detected\n"); /* DEBUGGER */
			newnode = talloc();
			if (newnode == NULL)
			{
				perror("tree: memory allocation error");
				return 1;
			}
			newkey = cmdkey(++command);
			newnode->Record->field1 = newkey; /* put key in node */
			rootnode = insert(rootnode, newnode);
			inorder (rootnode);
		}

		else if (*command == 'd')	/* command to delete a node */
		{
			delnode = delete (rootnode, cmdkey(++command) );
			if (delnode == NULL) 
			{
				printf("Key not found");
			}

			else
			{
				tfree (delnode);
			}
			inorder (rootnode);
		}

		else			/* unrecognized command             */
		{
			cmderror();	/* print command instructions       */
		}
	} 
}