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

typedef struct
{
    struct node* left;
    struct node* right;
    struct node* parent;
    char data[20];
}node;

node *treeroot=NULL;


node* create_node(char* data)
{
    node *new_node = (node*)malloc(sizeof(node));
    if(new_node == NULL)
    {
        fprintf (stderr, "OUT OF MEMORY!!! (create_node)\n");
        exit(1);
    }
    strcpy(new_node->data,data);
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->parent = NULL;
    return new_node;
}

int compare(char *left,char *right)
{
    if(strcmp(left,right)>0)
        return 1;
    else if(strcmp(left,right)<0)
        return -1;
    return 0;
}

node* insert_node(node *root, char* data)
{
    if(root == NULL)
    {
        root = create_node(data);
        treeroot=root;
    }
    else
    {
        printf("trying to insert\n");
        int is_left  = 0;
        int r        = 0;
        node* cursor = root;
        node* prev   = NULL;

        while(cursor != NULL)
        {
            r = compare(data,cursor->data);
            prev = cursor;
            if(r < 0)
            {
                is_left = 1;
                cursor = cursor->left;
            }
            else if(r > 0)
            {
                is_left = 0;
                cursor = cursor->right;
            }

        }
        if(is_left)
            prev->left = create_node(data);
        else
            prev->right = create_node(data);
    }
    return root;
}

node* search(node *root,char *data)
{
    if(root == NULL)
        return NULL;

    int r;
    node* cursor = root;
    while(cursor != NULL)
    {
        r = compare(data,cursor->data);
        if(r < 0)
            cursor = cursor->left;
        else if(r > 0)
            cursor = cursor->right;
        else
            return cursor;
    }
    return cursor;
}

void display_tree(node* nd)
{
    if (nd == NULL)
        return;
    printf("%s",nd->data);
    if(nd->left != NULL)
    {
        node* temp = nd->left;
        printf("(Left kid:%s )",temp->data);
    }
    if(nd->right != NULL)
    {
        node* temp = nd->right;
        printf("(Right kid:%s)",temp->data);
    }
    printf("\n");

    display_tree(nd->left);
    display_tree(nd->right);
}

void presucc(node *root, node *succ, node *pre, char* key)
{
    if(root==NULL)
    {
        return 0;
    }
    else{
     if(strcmp(root->data,key)==0)
     {
        if (root->left != NULL)
        {
            node* tmp = root->left;
            while (tmp->right)
                tmp = tmp->right;
            pre = tmp ;
        }
        if (root->right != NULL)
        {
            node* tmp = root->right ;
            while (tmp->left)
                tmp = tmp->left ;
            succ = tmp ;
        }
     }
    if (strcmp(root->data,key)>0)
    {
        succ = root ;
        root=root->left;
        presucc(root, pre, succ, key);
    }
    else
    {
        pre = root;
        root=root->right;
        presucc(root, pre, succ, key);
    }
    }
}

node* sortedArrayToBST(int arr[], int start, int end)
{
    if (start > end)
      return NULL;

    int mid = (start + end)/2;
    node *root = create_node(arr[mid]);

    root->left =  sortedArrayToBST(arr, start, mid-1);
    root->right = sortedArrayToBST(arr, mid+1, end);

    return root;
}

void Spellcheck(char* Sentence)
{

}

int main()
{
    FILE *f;
    int i;
    char path[100];
    char Entry[3000][20];
    char Sentence[100];
    node* pre = NULL, *suc = NULL,*root;

    printf("ENTER FILE PATH (INCLUDING FILENAME AND EXTENSION) \n");
    fgets(path,sizeof(path),stdin);
    path[strlen(path) - 1] = 0;
    f=fopen(path,"r");
    if(f==NULL)
	{
		printf("\n%s\" File NOT FOUND! PRESS ANY KEY TO CONTINUE ...",path);
		getch();
		exit(1);
	}
	else
    {

        while (!feof(f))
        {
            for(i=0;i<3000;i++)
            {
                    fscanf(f,"%s",&Entry[i]);
                    fscanf(f,"\n");
            }
        }
    printf("trying");
    root=sortedArrayToBST(Entry,0,2999);
    display_tree(root);
    printf("DICTIONARY LOADED ...\n");
    fclose(f);
    printf("Please enter the sentence to be checked:\n");
    fgets(Sentence,sizeof(Sentence),stdin);
    Sentence[strlen(Sentence) - 1] = 0;
    Spellcheck(Sentence);
    getchar();
    }
    return 0;
}