/* 
 * File:   main.c
 * Author: Guilherme Oki
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
 * fator de carga = #chaves / #buckets f = m/n
 */
int temp = 0;

typedef struct aluno {
    char nome[100];
    float CR;
    int DRE;
}ALUNO;

typedef struct node {
    ALUNO * aluno;
    int chave;
    struct node* prox;
    struct node* prox_linked;
    struct node* anterior_linked;
}LINKEDHASHMAP_NODE;

typedef struct linked_list {
    LINKEDHASHMAP_NODE*primeiro;
    LINKEDHASHMAP_NODE*fim;

    int node_count;
}LINKED_LIST;

typedef struct linkedhashmap {
    //LINKEDHASHMAP_NODE ** buckets;
    LINKED_LIST * buckets;
    LINKEDHASHMAP_NODE*inicio;
    LINKEDHASHMAP_NODE*fim;
    int buckets_size;  //m
    int elements_count; //n
    float load_factor;
    
}LINKEDHASHMAP;

int hash(int chave,LINKEDHASHMAP *lhm){
    return chave % lhm->buckets_size;
}

ALUNO *get(LINKEDHASHMAP* lhm,int key){
    int bucket_index = hash(key,lhm);
    LINKED_LIST lista = lhm->buckets[bucket_index];
    LINKEDHASHMAP_NODE * No = lista.primeiro;
    //vou varrendo o no
    while(No != NULL) {
        if (No->chave == key){
            return No->aluno;
        }
        No = No->prox;
    }
    return NULL;
}

LINKEDHASHMAP * inicializa_hash(int length,float load_factor) {
    LINKED_LIST *buckets;
    LINKEDHASHMAP *hashmap;
    LINKEDHASHMAP_NODE *no_proximo;
    LINKEDHASHMAP_NODE *no_anterior;
    
    int m = length/load_factor;
    int i;
    
    no_proximo = (LINKEDHASHMAP_NODE*)malloc(sizeof(LINKEDHASHMAP_NODE));
    no_anterior = (LINKEDHASHMAP_NODE*)malloc(sizeof(LINKEDHASHMAP_NODE));
    hashmap = (LINKEDHASHMAP*)malloc(sizeof(LINKEDHASHMAP));
    buckets = (LINKED_LIST*)malloc(m*sizeof(LINKED_LIST));
    
    for (i=0;i<m;i++){
        buckets[i].primeiro = NULL;
        buckets[i].fim = NULL;
        buckets[i].node_count = 0;
    }
    
    hashmap->buckets = buckets;
    hashmap->load_factor = load_factor;
    hashmap->buckets_size = m;
    hashmap->elements_count = 0;
    
    hashmap->inicio = hashmap->fim = NULL;
    
    return hashmap;
}

void insert_linked_list(int key,LINKEDHASHMAP *lhm,ALUNO *aluno,LINKEDHASHMAP_NODE *NovoNo) {
    int bucket_index = hash(key,lhm);
    
    LINKED_LIST lista = lhm->buckets[bucket_index];
    LINKEDHASHMAP_NODE *No = lista.primeiro;
    
    if (No==NULL){
        lista.primeiro = NovoNo;
        lista.fim = NovoNo;
        lista.node_count++;
        temp++;
        lhm->buckets[bucket_index] = lista;
        return;
    }
    else {
        while(1){
            if (No->chave == key && No->prox == NULL){
                No->prox = NovoNo;
                lista.fim = NovoNo;
                lista.node_count++;
                lhm->buckets[bucket_index] = lista;
                return;
            }
            else {
                return; //tratar colisão
            }
            No = No->prox;
        }
    }
    
    
}



void insert_linked_hash(int key,LINKEDHASHMAP*lhm,ALUNO *aluno,LINKEDHASHMAP_NODE *NovoNo){
    int bucket_index = hash(key,lhm);
    LINKED_LIST lista = lhm->buckets[bucket_index];
    LINKEDHASHMAP_NODE *No = lista.primeiro;
    
    if(lhm->elements_count == 0){
        lhm->inicio = lhm->fim = NovoNo;
    }
    else if( lhm->elements_count < lhm->buckets_size ) {
        lhm->inicio->anterior_linked  = NovoNo;
        NovoNo->prox_linked = lhm->inicio;
        lhm->inicio = NovoNo;
    }
    //hash cheia, esvazia um bucket
    else if (lhm->elements_count >= lhm->buckets_size) {
        int bucket_index_removed = hash(lhm->fim->chave,lhm);
        LINKED_LIST list;
        lhm->buckets[bucket_index_removed] = list;
        lhm->fim->anterior_linked->prox_linked = NULL;
        free(lhm->fim);
        lhm->fim = lhm->fim->anterior_linked;
        lhm->inicio->anterior_linked  = NovoNo;
        NovoNo->prox_linked = lhm->inicio;
        lhm->inicio = NovoNo;
        temp--; //lhm->element_count--
    }
}

void insert(int key,LINKEDHASHMAP* lhm,ALUNO *aluno){
    LINKEDHASHMAP_NODE *NovoNo = (LINKEDHASHMAP_NODE*)malloc(sizeof(LINKEDHASHMAP_NODE));
    NovoNo->chave = key;
    NovoNo->aluno = aluno;
    
    insert_linked_list(key,lhm,aluno,NovoNo);
    insert_linked_hash(key,lhm,aluno,NovoNo);
    lhm->elements_count = temp;
}

ALUNO *create_aluno(char* nome,float CR, int dre){
    ALUNO *aluno;
    aluno = (ALUNO*)malloc(sizeof(ALUNO));
    strcpy(aluno->nome,nome);
    aluno->DRE = dre;
    aluno->CR = CR;
    return aluno;
}

void print_linkedhashmap(LINKEDHASHMAP *lhm){
    LINKEDHASHMAP_NODE *Node = lhm->inicio;
    
    while(1){
        if(Node!=NULL){
            printf("%d %s\n",hash(Node->chave,lhm) , Node->aluno->nome);
        }
        else if (Node==NULL){
            return;
        }
        Node = Node->prox_linked;
    }
}

int main(int argc, char** argv) {
    int key = 1;
    int key2 = 2;
    int key3 = 3;
    int key4 = 4;
    int key5 = 5;
    int key6 = 6;
    
    
    LINKEDHASHMAP *lhm = inicializa_hash(4,1);
    ALUNO *aluno1 = create_aluno("Fulano",6.7,111333444);
    ALUNO *aluno2 = create_aluno("Ciclano",6.7,111333444);
    ALUNO *aluno3 = create_aluno("Beltrano",6.7,111333444);
    ALUNO *aluno4 = create_aluno("Ultrano",6.7,111333444);
    ALUNO *aluno5 = create_aluno("Raltrano",6.7,111333444);
    ALUNO *aluno6 = create_aluno("Geltrano",6.7,111333444);
    
    insert(key,lhm,aluno1);
    insert(key2,lhm,aluno2);
    insert(key3,lhm,aluno3);
    insert(key4,lhm,aluno4);
    insert(key5,lhm,aluno5);
    insert(key2,lhm,aluno6);
    
    ALUNO *alunoget2 = get(lhm,key2);
    
    print_linkedhashmap(lhm);
    
    return (EXIT_SUCCESS);
}