/************************************************
Marcus De Young
CSE 220 - Prof. Sarkar
Programming Assignment

file: MarcusDeYoung.c


Gets strings of 1's and 0's from command line.
Takes and puts them into a binary tree.
When done, prints out a list, in order, of the
entered strings.
Does this in O(N) time - by using tree and 
preorder traversal.

!!Set max input to 20 characters!!

You can change this by altering the char[] arg
in the structure nodetype.

Using the preorder traversal, the sorted list
of strings is printed out to the screen.

This program uses some of the convention set 
forth in "Data Structures Using C and C++" by
Y. Langsam, M. Augenstein, and A. Tenembaum.

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

#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>

//max number of chars in binary string
#define MAXNOCHARS 20

struct nodetype{
 
  char info[MAXNOCHARS];
  struct nodetype *left;
  struct nodetype *right;

};

typedef struct nodetype *NODEPTR;


NODEPTR getnode();
void freenode(NODEPTR p);
void insertNode(NODEPTR p, char *x, int ptr);
void freeAll(NODEPTR p);
void clearLine();
void printString(char *input);
void printPreOrder(NODEPTR p);
NODEPTR maketree(char *x);

int main()
{

  NODEPTR ptree; //tree - root we use
  char user_in;
  char binary_input[MAXNOCHARS]; //input max of 20 - can change
  int test;

  printf("Program to sort out binary strings.\n");
  printf("At the prompt, enter 'y' to enter more data ");
  printf("or enter 'n' to stop and print out a list of the ");
  printf("strings you have entered in order.\n");

  ptree = maketree(NULL);

  //loop to gather all input
  while(1){
    
    printf("Enter y or n: ");
    scanf("%c", &user_in);
    clearLine();

    if(user_in == 'y'){

      printf("Ok.  Enter a string of 1's and 0's: ");
      scanf("%s", binary_input);
      clearLine();
      test = checkString(binary_input);
      if(test){
	insertNode(ptree, binary_input, 0);
      }
      else{
	printf("Sorry, please enter only 0's and 1's.\n");
      }
    }
    
    else if(user_in == 'n'){
      printf("Here is an ordered list of your input: \n");
      break;
    }
    
    else {printf("Please enter y or n.\n");}


  }

  //print out in order all binary strings
  printPreOrder(ptree);

  //free the memory used
  freeAll(ptree);

  return(0);
}

/*getnode makes a node by allocating mem for it*/

NODEPTR getnode()
{
  NODEPTR p = calloc(1, sizeof(struct nodetype));
  return p;
}

void freenode(NODEPTR p)
{
  
  free(p);
 
}

/*function makes a node/tree*/

NODEPTR maketree(char *x)
{
  
  NODEPTR p;

  p = getnode();

  if(x != NULL){
    strcpy(p->info, x);
  }

  else{
    (p->info[0] = NULL);
  }

  p->left = NULL;
  p->right = NULL;
  return(p);
}

/* insertNode - important function
   inserts according to each character
   if 0 - goes right, look at next char
   if 1 - goes left, look at next char
*/

void insertNode(NODEPTR p, char *x, int ptr)
{
  //If current value = 0 -> put it in left node

  if(x[ptr] == '0'){

    if(x[ptr+1] == NULL){

      if(p->left == NULL){
	p->left = maketree(x);
      }
      else{
	strcpy(p->left->info,x);
      }

    }

    else{
      if(p->left == NULL){
	p->left = maketree(NULL);
      }
      insertNode(p->left, x, ptr+1);
    }

  }

  //If current value = 1 -> put it in right node
  if(x[ptr] == '1'){

    if(x[ptr+1] == NULL){

      if(p->right == NULL){
	p->right = maketree(x);
      }
      else{
	strcpy(p->right->info, x);
      }
    }

    else{
      
      if(p->right == NULL){
	p->right = maketree(NULL);
      }
      insertNode(p->right, x, ptr+1);
    }


  }
}


/* Clearline function used for character input */
void clearLine()
{
        char nextChar;

	//Just clean up anything that was inputted.
	//used to get rid of \n after user types command
	//if they type "yes" the e,s and \n would be ignored

        while (1) {
                scanf("%c", &nextChar);
                if (nextChar == '\n')
                        break;
        }
}

/* This function prints out the list by using
   the preorder traversal.
*/
void printPreOrder(NODEPTR p){

  if(p != NULL){
    //if a string is present, print it
    if(p->info[0] != NULL){
      printf("%s\n", p->info);
    }
    printPreOrder(p->left);
    printPreOrder(p->right);
  }

}

/* Function frees all the memory */
void freeAll(NODEPTR p){
  
  if(p != NULL){
    freeAll(p->left);
    freeAll(p->right);
    freenode(p);
  }

}

/* Function checks to see if the string is 
   comprised of only 1's and 0's
*/
int checkString(char *x)
{
  int i;

  for(i=0; x[i] != '\0'; i++){
    
    if( (x[i] != '0') && (x[i] != '1') ){
      return 0;
    }
  }
  
  //success!
  return 1;
}