#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	"> "


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

/* 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 = (int*)malloc(maxdepth*sizeof(root->key));
	/* 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->right, 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->key);
		else printf("%s\n",root->key);
		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;
}


/* 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->right, 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;
}


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