/* Binary tree "interpreter"
 *
 * Skeleton program written by Alistair Moffat, September 2014
 *
 * Modifications by William Pan , October 2014
 * Assignment 2 COMP10002
 * William Pan 694945
 * wpan1
 * 694945
 *
 * Algorithms are fun!
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
#include <ctype.h>
#include <assert.h>

#define LINELEN	80	/* maximum length of any input line */

#define RIGHT 1 /* right traversal of tree */
#define LEFT  0 /* left traversal of tree */

#define INSERT	'i'	/* command to add a string */
#define PRINT1	'p'	/* command to do plain print */
#define PRINT2	's'	/* command to do snazzy print */
#define ROTATE	'r'	/* command to do a tree edge rotation */
#define TABULA	't'	/* command to tabulate statistics */
#define FREEIT	'f'	/* command to free all space */
#define ALLOPS  "irpstf" /* list of all valid operators */
#define FILINP	1	/* indicates input coming from a file */
#define PROMPT	"> "


/****************************************************************/

typedef struct node tree_t;

struct node {
	char *str;
	tree_t *left, *rght;
};

/****************************************************************/

/* Function prototypes */

int     checkargs(int argc, char **argv);
void    print_prompt();
int     read_line(int fileinput, char *line, int maxlen);
tree_t *process_line(tree_t *root, char *line);
tree_t *do_insert(tree_t *root, char *str);
tree_t *do_rotate(tree_t *root, char *str);
tree_t *go_to(tree_t *root, char *str);
tree_t *go_to_prev(tree_t *root,tree_t *prev, char *str);
void    do_print_p(tree_t *root);
void	do_print_p_2(tree_t *root, int level);
void    do_print_s(tree_t *root);
void	do_print_s_2(tree_t *root, int level, int *history, int lr);
int 	do_print_s_3(int *history,int p_space, int level);
void    do_tabulate(tree_t *root);
int 	do_t_size(tree_t *root);
int     do_t_alldepth(tree_t *root,int level);
int 	do_t_maxdepth(tree_t *root,int level);
void    do_freeit(tree_t *root);

/****************************************************************/

/* Main program controls all the action */
int
main(int argc, char *argv[]) {
	char line[LINELEN+1];
	int fileinput=0;
	tree_t *root=NULL;
	/* check commandline, process argv */
	fileinput = checkargs(argc, argv);
	/* start the main execution loop */
	print_prompt();
	while (read_line(fileinput, line, LINELEN)) {
		if (strlen(line)>0) {
			/* non empty line, so process it */
			root = process_line(root, line);
		}
		/* then round we go */
		print_prompt();
	}
	/* all done, so pack up and go home */
	printf("Ta daaa!\n");
	return 0;
}

/****************************************************************/

/* If there is a valid filename on the commandline, redirect stdin
 * so that the file is read, and return FILINP to show that input
 * input lines should be echoed to the output when they are read */
int
checkargs(int argc, char **argv) {
	if (argc==2) {
		if (freopen(argv[1], "r", stdin)==NULL) {
			printf("Unable to open \"%s\"\n", argv[1]);
			exit(EXIT_FAILURE);
		}
		/* stdin successfully reopened to the named file */
		printf("Input file: %s\n", argv[1]);
		return FILINP;
	} else if (argc>2) {
		printf("Usage: %s [filename]\n", argv[0]);
		exit(EXIT_FAILURE);
	}
	/* no command line parameters, so stdin is used unchanged */
	return 0;
}

/****************************************************************/

/* Print the "ready for input" prompt */
void
print_prompt() {
	printf(PROMPT);
}

/****************************************************************/

/* Read a line of input into the array passed as argument
 * Returns false if there is no input available
 * All whitespace characters are removed */
int
read_line(int fileinput, char *line, int maxlen) {
	int i=0, c;
	/* get a whole input line, retain non-blanks only */
	while (((c=getchar())!=EOF) && (c!='\n')) {
		if (i<maxlen && !isspace(c)) {
			line[i++] = c;
		}
	}
	line[i] = '\0';
	if (fileinput) {
		/* print out the input command */
		if (line[0]) {
			printf("%c", line[0]);
		}
		if (i>1) {
			/* and the argument */
			printf(" %s", line+1);
		}
		printf("\n");
	}
	return ((i>0) || (c!=EOF));
}

/****************************************************************/

/* Process a command by parsing the input line into parts, returns
   a tree build from the old one by returning a new root pointer */
tree_t
*process_line(tree_t *root, char *line) {
	int optype;
	/* determine the operation to be performed, it
	 * must be first character in line
	 */
	optype = line[0];
	if (strchr(ALLOPS, optype) == NULL) {
		printf("Unknown operator\n");
		return root;
	}
	/* determine the string argument (if one is required),
	 * it must start in second character of line
	 */
	if (optype==PRINT1 || optype==PRINT2 ||
			optype==TABULA || optype==FREEIT) {
		if (strlen(line)>1) {
			printf("No argument required\n");
			return root;
		}
	}
	if (optype==INSERT || optype==ROTATE) {
		if (strlen(line)<2) {
			printf("An argument is required\n");
			return root;
		}
	}
	/* finally, do the actual operation
	 */
	if (optype == PRINT1) {
		do_print_p(root);
		return root;
	} else if (optype == PRINT2) {
		do_print_s(root);
		return root;
	} else if (optype == TABULA) {
		do_tabulate(root);
		return root;
	} else if (optype == FREEIT) {
		do_freeit(root);
		return NULL;
	} else if (optype == INSERT) {
		return do_insert(root, line+1);
	} else if (optype == ROTATE) {
		return do_rotate(root, line+1);
	}
	/* should never get here, but keeps compiler silent... */
	return root;
}

/****************************************************************/

/* Print out a tree, simple formatting */
void
do_print_p(tree_t *root) {
	do_print_p_2(root, 0);
}

/****************************************************************/

/* Finds each word in reverse-alphabetic order,
printing spaces according to it's level */
void
do_print_p_2(tree_t *root, int level) {
	int p_space = 0;
	/* Double recursive loop traversing down right
	leaves first - reverse alphabetic order */
	if (root != NULL){
		do_print_p_2(root->rght,level + 1);
		/* Print space according to current level */
		while(p_space<5*(level)){
			printf(" ");
			p_space++;
		}
		printf("%s\n",root->str);
		do_print_p_2(root->left,level + 1);
	}
}

/****************************************************************/

/* print out a tree, snazzy formatting */
void
do_print_s(tree_t *root) {
	/* Creates history array of max depth of tree */
	int maxdepth = do_t_maxdepth(root,0);
	int *history = malloc(maxdepth*sizeof(root->str));
	/* Snazzy print function part 2 */
	do_print_s_2(root, 0, history, -1);
}

/****************************************************************/

/* Finds each word in reverse-alphabetic order,
printing spaces according to it's level */
void
do_print_s_2(tree_t *root, int level, int *history, int lr) {
	int p_space = 0;
	/* Adds left or right traversal to history array */
	if (lr == RIGHT) history[level] = RIGHT;
	else history[level] = LEFT;
	/* Double recursive loop traversing down right
	leaves first - reverse alphabetic order */
	if (root != NULL){
		do_print_s_2(root->rght, level + 1, history, RIGHT);
		/* Print space according to current level
		Five spaces for the rest of the str and prints
		'|' if needed */
		while(p_space<5*(level)-3){
				/* Checks if '|' is needed */
				if (do_print_s_3(history,p_space,level)){
					printf("|");
					p_space++;
				}
				printf(" ");
				p_space++;
			}
		/* Print string with +-- */
		if (level>0) printf("+--%s\n",root->str);
		else printf("%s\n",root->str);
		do_print_s_2(root->left,level + 1,history, LEFT);
	}
	else{
		/* Print NULL (empty) leaf with +-- */
		if (level>0){
			while(p_space<5*(level)-3){
				if (do_print_s_3(history,p_space,level)){
					printf("|");
					p_space++;
				}
				printf(" ");
				p_space++;
			}
			printf("+--\n");
		}
	}
}

/****************************************************************/

/* Checks if | needs to be printed */
int
do_print_s_3(int *history,int p_space, int level){
	/* If tree traverses in alternating directions (i.e right then left
	or right then left) '|' is printed at corresponding level */
	if (level>0 && ((p_space+3) % 5*(level) == 0)
	 && history[(p_space-2)/5+1] != history[(p_space-2)/5+2]){
		return 1;
		}
	return 0;
}

/****************************************************************/

/* update the tree by adding in the new string; if already there
   return the same tree */
tree_t
*do_insert(tree_t *root, char *str) {
	/* If the tree is empty, new node is created at root
	location */
	if (root == NULL) {
		root = malloc(sizeof(tree_t));
		root->str = malloc(strlen(str)*sizeof(str));
		assert(root->str);
		strcpy(root->str,str);
		root->rght = NULL;
		root->left = NULL;
		return root;
  	}
  	/* Recursive calls to traverse down right side first
  	until a NULL pointer is found */
    else {
       	if (strcmp(str,root->str) < 0) {
    		root->left = do_insert(root->left, str);
    	}
    	else if (strcmp(str,root->str) > 0) {
    		root->rght = do_insert(root->rght, str);
    	}
    	/* Return the root pointer (unchanged) */
    	return root;
	}
}

/****************************************************************/

/* Update the tree by rotating it at item specified, return the
   new root; if item is not there, return the original tree */
tree_t
*do_rotate(tree_t *root, char *str) {
	/* Node of str and node before str defined */
	tree_t *root_str = go_to(root, str);
	tree_t *root_str_prev = go_to_prev(root, NULL, str);
	char *temp = 0;
	/* If string not found or already
	at top of tree, return original tree */
	if (root_str == NULL || root_str_prev == NULL) {
		return root;
	}
	/* Replaces entire root_str_prev leaf and root_str leaf
	with respective outcomes when rotated left */
	if (root_str_prev->rght != NULL &&
		strcmp(root_str_prev->rght->str,root_str->str) == 0){
		/* Swapping pointers */
		root_str_prev->rght = root_str->rght;
		root_str->rght = root_str->left;
		root_str->left = root_str_prev->left;
		root_str_prev->left = root_str;
		/* Swapping strings of main pointers */
		temp = root_str_prev->str;
		root_str_prev->str = root_str->str;
		root_str->str = temp;
	}
	/* Replaces entire root_str_prev leaf and root_str leaf
	with respective outcomes when rotated right */
	else if (root_str_prev->left != NULL &&
		strcmp(root_str_prev->left->str,root_str->str) == 0){
		/* Swapping pointers */
		root_str_prev->left = root_str->left;
		root_str->left = root_str->rght;
		root_str->rght = root_str_prev->rght;
		root_str_prev->rght = root_str;
		/* Swapping strings of main pointers */
		temp = root_str_prev->str;
		root_str_prev->str = root_str->str;
		root_str->str = temp;
	}
	/* Return the root pointer (unchanged) */
	return root;
}

/****************************************************************/

/* Return the *node of where previous string is */
tree_t
*go_to_prev(tree_t *root,tree_t *prev, char *str) {
	if (root != NULL){
		/* If string found return locaton */
		if(strcmp(root->str, str) == 0){
			return prev;
		}
		/* If string larger than node->str go to rght pointer */
		if(strcmp(root->str,str) < 0){
			prev = root;
			return go_to_prev(root->rght, root, str);
		}
		/* If string larger than node->str go to left pointer */
		if(strcmp(root->str,str) > 0){
			prev = root;
			return go_to_prev(root->left, root, str);
		}
	}
	return prev;
}

/****************************************************************/

/* Return the *node of where string is NULL returned if not found */
tree_t
*go_to(tree_t *root, char *str) {
	if (root != NULL){
		/* If string found return locaton */
		if(strcmp(root->str,str) == 0){
			return root;
		}
		/* If string larger than node->str go to rght pointer */
		if(strcmp(root->str,str) < 0){
			return go_to(root->rght, str);
		}
		/* If string larger than node->str go to left pointer */
		if(strcmp(root->str,str) > 0){
			return go_to(root->left, str);
		}
	}
	return root;
}

/****************************************************************/

/* Print the final size of the tree, and average node depth */
void
do_tabulate(tree_t *root) {
	int size = 0, maxdepth = 0;
	double alldepth = 0;
	/* Size of tree */
	size = do_t_size(root);
	printf("size     :%6d\n",size);
	/* If empty, do not print average or max depth */
	if (size){
		/* Sum of depth of each element */
		alldepth = do_t_alldepth(root,0);
		printf("avg depth:%6.2f\n",alldepth/size);
		/* Max depth of tree */
		maxdepth = do_t_maxdepth(root,0);
		printf("max depth:%6d\n",maxdepth);
	}

}

/****************************************************************/

/* Find the number of elements in tree */
int
do_t_size(tree_t *root) {
	/* Recursive loop adds one for every traversal */
	if (root != NULL) {
    	return(do_t_size(root->rght) + do_t_size(root->left) + 1);
	}
  	else {
  		return 0;
	}
}

/****************************************************************/

/* Adds all the levels of nodes */
int
do_t_alldepth(tree_t *root,int level) {
	int lnum = 0, rnum = 0, total = 0;
	/* Recursive loop adds the level of all elements in tree
	+1 added to total as root node == 0 */
	if (root != NULL) {
		lnum = do_t_alldepth(root->rght, level + 1);
		rnum = do_t_alldepth(root->left, level + 1);
		total += level + lnum + rnum + 1;
	}
	return total;
}

/****************************************************************/

/* Find the maximum depth of tree */
int
do_t_maxdepth(tree_t *root,int level) {
	int lnum = 0, rnum = 0;
	/* Recursive loop adds one at end of tree */
	if (root != NULL) {
		lnum = do_t_maxdepth(root->rght, level + 1);
		rnum = do_t_maxdepth(root->left, level + 1);
	}
	/* Returns max level, first root node is 0, however NULL
	nodes also add to total */
	if (lnum > rnum) {
		if (lnum > level) return lnum;
	}
	if (rnum > level) return rnum;
	return level;
}

/****************************************************************/

/* Free all of the space, and make empty tree again */
void
do_freeit(tree_t *root) {
	if (root != NULL){
		do_freeit(root->rght);
		do_freeit(root->left);
		free(root);
	}
}