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

typedef struct node {
    char* key;
    struct node *left;
    struct node *right;
    int height;
}node;

int max(int a, int b);

// A utility function to get height of the tree
int height(node* N)
{
    if(N==NULL)
        return 0;

    return N->height;
}

// A utility function to get maximum of two integers
int max(int a, int b)
{
    if(a > b)
    {
        return a;
    }
    else
        return b;
}

int avlHeight(node* N) {
    if(N == NULL)
        return -1;
    else
        return max(height(N->left), height(N->right)) + 1;
}

int nodeCount(node *root)
{
    int count = 0;
    if (root != NULL) {
        count = 1 + nodeCount(root->left) + nodeCount(root->right);
    }
    return count;
}

/* Helper function that allocates a new node with the given key and
    NULL left and right pointers. */
node* newNode(node* node, char* key)
{
    node = malloc(sizeof(struct node*));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;  // new node is initially added at leaf
    return(node);
}

// A utility function to right rotate subtree rooted with y
node *rightRotate(node *y)
{
    node *x = y->left;
    node *T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    //printf("%d",height(x->left));
    y->height = max(height(y->left), height(y->right))+1;
    x->height = max(height(x->left), height(x->right))+1;

    // Return new root
    return x;
}

// A utility function to left rotate subtree rooted with x
node *leftRotate(node *x)
{
    node *y = x->right;
    node *T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    //  Update heights
    x->height = max(height(x->left), height(x->right))+1;
    y->height = max(height(y->left), height(y->right))+1;

    // Return new root
    return y;
}

// Get Balance factor of node N
int getBalance(node *N)
{
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

node* insert(node* node, char* key)
{
    //int i = strcmp(key,node->key);
    /* 1.  Perform the normal BST rotation */

    if (node == NULL)
        return(newNode(node, key));
    if (strcmp(key, node->key) < 0) {
        node->left = insert(node->left, key);
    }
    else {
        node->right = insert(node->right, key);
        //printf("%s", node->right->key);
    }

    /* 2. Update height of this ancestor node */
    node->height = max(height(node->left), height(node->right)) + 1;

    /* 3. Get the balance factor of this ancestor node to check whether
       this node became unbalanced */
    int balance = getBalance(node);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && strcmp(key, (node->left)->key)<0){
        printf("1stn");
        return rightRotate(node);
    }

    // Right Right Case
    if (balance < -1 && strcmp(key, (node->right)->key)>0){
        printf("2ndn");
        return leftRotate(node);
    }
    // Left Right Case
    //i = strcmp(key, (node->left)->key);
    //printf("!%d!",i);
    if (balance > 1 && strcmp(key, (node->left)->key)>0){
        printf("3rdn");
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && strcmp(key, node->right->key)<0)
    {
        printf("4thn");
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    //stuff = '/0';
    /* return the (unchanged) node pointer */
    return node;
}

// A utility function to print preorder traversal of the tree.
// The function also prints height of every node
void preOrder(node *root)
{
    if(root != NULL)
    {
        printf("%s ", root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}


void nick() {//initial banner addition
    printf("**********************************************************n");
    printf("Welcome to the Arethmatic Expression calculator!n");
    printf("Created by: Nicholas Bastiann");
    printf("Student ID #: 0843261n");
    printf("**********************************************************nn");
}

void menu()//menu function
{
    printf("nWhat would you like to do? (Please input a single number)n");
    printf("1. Initializationn");
    printf("2. Findn");
    printf("3. Insertn");
    printf("4. Removen");
    printf("5. Check Height and Sizen");
    printf("6. Find All (above a given frequency)n");
    printf("7. Exitn");
    printf("avl/> ");
}

int main()
{
    char value[100];
    char str[100];
    int counter = 1, choice, height, size;
    char*token;
    node* root= NULL;
    static const char input[] = "avl.dat";
    FILE* textFile = fopen(input,"r");
    while(!feof(textFile)) {

    fgets(str, 100, textFile);
        token = strtok(str," n");

        while (token != NULL)
        {
            //printf("%sn",token);
            root = insert(root, token);
            token = strtok (NULL, " n");
        }
    }

    nick();
    do{

    menu();
    fgets(value,100,stdin);
    choice = atoi(value);//user proofed menu

    switch(choice)
    {
        case 1:
        printf("filename: ");
        printf("Pre order traversal of the constructed AVL tree is n");
        preOrder(root);
        break;

        case 2:
        /*printf("findkey: %s");
        printf(", frequency: %d");*/
        break;

        case 3:
        printf("insert key: ");
        break;

        case 4:
        printf("remove key: ");
        break;

        case 5:
        height = avlHeight(root);
        size = nodeCount(root);
        printf("height: %d", height);
        printf(", size: %d", size);
        break;

        case 6:
        printf("frequency: ");
        break;

        case 7:
        printf("Exiting program...n");
        exit(0);
        break;

        default:
        printf("nPlease put input a number from 1 to 7 (only a single integer).nn");
        break;
    }

    }while(counter==1);

    return(0);
}