//A very simple and poorly designed hashmap implementation + AVL BST
//Dedicated to flying big guanren, admin of North America Kancolle Group, who knows programming and has a lot meizi
//Didn't remove test stuff in main function, ignore them
//WTFPL

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

#define CALC_TIME

#ifdef CALC_TIME
#include <time.h>
#endif


#define BIG_PRIME 19260817
//+1s

#define MAX(a, b) (a > b ? (a) : (b))

struct treenode{
    long key;
    struct treenode * leftChild;
    struct treenode * rightChild;
    long height;
    //long timeAppeared;
};

struct treenode * constructAVLNode(long, struct treenode*, struct treenode*);
long getAVLHeight(struct treenode*);
struct treenode* AVLTreeRotateLeft(struct treenode*);
struct treenode* AVLTreeRotateRight(struct treenode*);
int updateAVLNodeHeight(struct treenode*);
struct treenode* AVLTreeAddKeyAndBalance(struct treenode*, long);
bool findInAVLTree(struct treenode*, long);

unsigned long hashStr(const char[]);
unsigned long hash(unsigned long);
int addToHashMap(struct treenode*[], long);
bool findInHashMap(struct treenode*[], long);

struct treenode *
constructAVLNode(
                long newKey,
                struct treenode* lchild,
                struct treenode* rchild
                ){
    struct treenode * node;
    node = (struct treenode*)malloc(sizeof(struct treenode));
    if(node == NULL){
        return EXIT_FAILURE;
    }
    node->key = newKey;
    node->leftChild = lchild;
    node->rightChild = rchild;
    node->height = 0;
    return node;
}

long getAVLHeight(struct treenode* node){
    if(node == NULL){
        return 0;
    }
    else{
        return node->height;
    }
    return EXIT_FAILURE;
}

//Do this when right child is bigger
struct treenode*
AVLTreeRotateLeft(struct treenode* node){
    struct treenode* newnode;
    newnode = node -> rightChild;
    node -> rightChild = newnode -> leftChild;
    newnode -> leftChild = node;
    updateAVLNodeHeight(node);
    updateAVLNodeHeight(newnode);

    return newnode;
}

//Do this when left child is bigger
struct treenode*
AVLTreeRotateRight(struct treenode* node){
    struct treenode* newnode;
    newnode = node -> leftChild;
    node -> leftChild = newnode ->rightChild;
    newnode ->rightChild = node;
    updateAVLNodeHeight(node);
    updateAVLNodeHeight(newnode);
    return newnode;
}

int updateAVLNodeHeight(struct treenode* node){
    node->height = MAX(getAVLHeight(node->leftChild),getAVLHeight(node->rightChild)) + 1;
    return 0;
}

struct treenode* AVLTreeAddKeyAndBalance(struct treenode* node, long newkey){
    if(node == NULL){
        node = constructAVLNode(newkey, NULL, NULL);
        if(node == NULL){
            return EXIT_FAILURE;
        }
    }
    else if(newkey < node->key){//new key should be added to the left of the tree, in this case
        node->leftChild = AVLTreeAddKeyAndBalance(node -> leftChild, newkey);
        //left child is bigger
        if (getAVLHeight(node->leftChild) - getAVLHeight(node->rightChild) > 1){//Tree gets unbalanced
            if(newkey < node->leftChild->key){
                node = AVLTreeRotateRight(node);
            }
            else{
                node->leftChild = AVLTreeRotateLeft(node->leftChild);
                node = AVLTreeRotateRight(node);
            }
        }
    }
    else if(newkey > node->key){
        node->rightChild = AVLTreeAddKeyAndBalance(node -> rightChild, newkey);
        if (getAVLHeight(node->rightChild) - getAVLHeight(node->leftChild) > 1){//Tree gets unbalanced
            if(newkey > node->rightChild->key){
                node = AVLTreeRotateLeft(node);
            }
            else{
                node->rightChild = AVLTreeRotateRight(node->rightChild);
                node = AVLTreeRotateLeft(node);
            }
        }
    }
    else{
        return -1;
        //node->timeAppeared += 1;
    }
    updateAVLNodeHeight(node);
    return node;
}

bool findInAVLTree(struct treenode* node, long newKey){

    if (node == NULL) return false;
    if(newKey == node->key) return true;

    return findInAVLTree(newKey > node->key?node->rightChild:node->leftChild, newKey);
}

//Use time33 algorithm
unsigned long hashStr(const char str[]){
    unsigned long result = 5381;
    while(*str != '\0'){
        result = (result << 5) + (*str) * 33;
        *str++;
    }
    return (result & 0x7FFFFFFF);
}

unsigned long hash(unsigned long prehash){
    return prehash % BIG_PRIME;
}

int addToHashMap(struct treenode* hashMap[], long key){
    unsigned long hashedkey = hash(key);
    hashMap[hashedkey] = AVLTreeAddKeyAndBalance(hashMap[hashedkey], key);
    return EXIT_SUCCESS;
}

bool findInHashMap(struct treenode* hashMap[], long key){
    #ifdef CALC_TIME
    clock_t begin = clock();
    #endif

    unsigned long hashedkey = hash(key);

    #ifdef CALC_TIME
    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("Query completed. Time consumed: %lf\n", time_spent);
    #endif

    return findInAVLTree(hashMap[hashedkey], key);
}

int main(void) {
    struct treenode* hashmap[BIG_PRIME + 1] = {NULL};

    //long list[2000];
    FILE* fp;
    if((fp = fopen("randomdata1.txt", "r")) == NULL){
        return EXIT_FAILURE;
    }
    for(int i=0;i<5000;i++){
        long tmp;
        fscanf(fp,"%ld", &tmp);
        addToHashMap(hashmap, tmp);
    }
    bool b1, b2, b3;
    b1 = findInHashMap(hashmap, 780645712);//yes
    b2 = findInHashMap(hashmap, 35825069);//false
    b3 = findInHashMap(hashmap, 770721382);//yes
    printf("%d %d %d", b1, b2, b3);

    #ifdef CALC_TIME
    char ch;
    FILE* status = fopen( "/proc/self/status", "r" );
    while((ch = fgetc(status)) != EOF)
        printf("%c", ch);
    #endif

    return 0;
}