#include <stdio.h>
#include <getopt.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

typedef struct bstsort_node
{
    char *word;
    int count;

    struct bstsort_node* left;
    struct bstsort_node* right;

}node;

int stringCompare(char *str1, char *str2)
{
   int i = 0;
   char case1, case2;

   while(str1[i] != 0 && str2[i] != 0)
   {
       case1 = str1[i];
       case2 = str2[i];
       if(case1 != case2)
       {
           return case1-case2;
           i++;
       }
       if(str1[i] == 0 && str2 != 0)
       {
           return str2[i];
       }
       else if(str1 != 0 && str2 == 0)
       {
           return str1[i];
       }
       else
       {
           return 0;
       }
   }
}
int stringCompare2(char *str1, char *str2)
{
   int i = 0;
   char case1, case2;
   while(str1[i] != 0 && str2[i] != 0)
   {
       case1 = str1[i];
       case2 = str2[i];
       if(case1 >= 'A' && case1 <= 'Z')
       {
           case1 = case1 - 'A' + 'a';
       }
       if(case2 >= 'A' && case2 <= 'Z')
       {
           case2 = case2 - 'A' + 'a';
       }

       if(case1 != case2)
       {
           return case1 - case2;
           i++;
       }
       if(str1[i] == 0 && str2 != 0)
       {
           return str2[i];
       }
       else if(str1 != 0 && str2 == 0)
       {
           return str1[i];
       }
       else
       {
           return 0;
       }
   }
}

void freeNode(node *root)
{

    if (root != NULL)
    {
        freeNode(root->left);
        freeNode(root->right);

        free(root->word);
        free(root);
     }

}
node* createNode(char *string)
{
   node* n = (node*) malloc(sizeof(node));
   n->word = (char*) malloc(strlen(string)+1);
   strcpy(n->word, string);
   n->left = NULL;
     n->right = NULL;
    return n;
}
void insert(node *currentNode, char *string, int cases)
{
    node *position;
    int compare;

    if(currentNode == NULL)
    {
        currentNode = createNode(string);
    }
        if(cases==1)
        {
            if(stringCompare(string, currentNode->word) < 0)
            {
                insert(currentNode->right,string, cases);
            }
            else if(stringCompare(string,currentNode->word) == 0)
            {
                currentNode->count = currentNode-> count + 1;
            }
        }
        if(cases == 0)
        {
            if(stringCompare2(string,currentNode->word) < 0)
            {
                insert(currentNode->left, string, cases);
            }
            else if(stringCompare2(string, currentNode->word) > 0)
            {
                insert(currentNode->right, string, cases);
            }
            else if(stringCompare2(string,currentNode->word) == 0)
            {
                currentNode->count = currentNode->count + 1;
            }
        }
        //return node;
        printf("on insert %p", currentNode);
}

void inOrder(FILE *outFile, node *node)
{
   printf("for inorder %p", node);
   if(node == NULL)
   {
       return;
   }

   inOrder(outFile, node->left);
   fprintf(outFile, "%s[%d]\n", node->word, node->count);
   inOrder(outFile, node->right);

}

int main(int argc, char **argv)
{
   extern char *optarg;
   extern int optind;
   int c, err = 0;
   int cflag=0, oflag=0;
   int cases = 0;
   char string[100], temp[100], ch;
   node *root = NULL;
   int results = 1;
   //int i = 0;
   char *output_file_name, *input_file_name;
   FILE* inFile = stdin;
   FILE* outFile = stdout;
   static char usage[] = "usage: % bstsort [-c][-o output_file_name][input_file_name]\n";

   while ((c = getopt(argc, argv, "co:")) != -1)
       switch (c) {
       case 'c':
           cflag = 1;
           break;
       case 'o':
           oflag = 1;
           output_file_name = optarg;
           break;
       case '?':
           err = 1;
           break;
       }
    if(cflag == 1)
    {
       cases = 1;
    }
    if(oflag == 1)
    {
       if((outFile = fopen(output_file_name, "r")) == NULL)
       {

           printf("Could not open file.\n");

           exit(1);

       }

    }
    if(optind > argc)
   {
       input_file_name = argv[optind];

       if((inFile = fopen(input_file_name, "r")) == NULL)
       {

           printf("Could not open file.\n");


           exit(1);

       }
   }

   while(fgets(string, 100, inFile) != NULL)
   {
       if(stringCompare("\n", string) == 0)
       break;

       string[strlen(string) - 1] = 0;
       insert(root, string, cases);
   }
   fclose(inFile);
   inOrder(outFile, root);
   fclose(outFile);
   freeNode(root);
   exit(0);
}