#include "list.h"
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "mem.h"




/*initialize the linked list with the given comparison function*/
list_head_t *list_init(int (*cmp)(const void *, const void *)) {
    list_head_t *new_ptr = (void *)malloc(sizeof(list_head_t));
    new_ptr->cmp = cmp;
    new_ptr->list = NULL;
    return new_ptr;
}
/*search the list for the given key and return the value if the key is in the list
return NULL if it is not*/
void *list_search(list_head_t *list, void *key) {

    list_entry_t *element = list_get_element(list, key);
    if(element == NULL) {
        return NULL;
    } else {
        return element->value;
    }
}
int list_remove(list_head_t *list, void *key) {
    assert(list != NULL);
    list_entry_t *current = list->list;
    int (*cmp)(const void *, const void *) = list->cmp;
    if(!cmp(current->key,key)) {
        list->list = current->next;
        free(current->key);
        free(current->value);
        free(current);
        return 1;
    }
    while(current->next != NULL) {
        if(current->next->key == key) {
            free(current->next->key);
            free(current->next->value);
            list_entry_t *old = current->next;
            current->next = old->next;
            memfree(old);

            return 1;
        }
        current = current->next;
    }

    return 0;    
}
list_entry_t *list_get_element(list_head_t *list, void *key) {
    assert(list != NULL);
    list_entry_t *current = list->list;
    int (*cmp)(const void *, const void *) = list->cmp;
    int eq;
    if(current == NULL) {
        return NULL;
    }
    while(1) {
        eq = cmp(current->key, key);
        if(!eq) {
            return current;
        }
        if(current->next == NULL) {
            break;
        } else {
            current = (current->next);
        }
    }
    return NULL;
}

//returns the last entry in the list.
//this is used for append
list_entry_t *list_get_last(list_head_t* list) {
    assert(list != NULL);
    list_entry_t *cur = list->list;
    if(cur == NULL) {
        return NULL;
    } 
   // assert(cur->next != cur);
    while(cur->next != NULL) {
    cur = cur->next;

    }
    return cur;

}
int length_of_list(list_head_t* l) {
    assert(l != NULL);
    list_entry_t* ent = l->list;
    if(ent == NULL) {
        return 0;
    }
    int count = 0;
    while(ent != NULL) {
          ent = ent->next;
            ++count;
    }
    return count;

}
//append p2 to p1 and return p1
//TODO: make sure that we're allowed to modify
list_head_t *list_merge(list_head_t *p1, list_head_t *p2) {
    assert(p1 != NULL);
    if(p2 != NULL && p1->list != p2->list) list_get_last(p1)->next = p2->list;
    return p1;
}

/*Insert the given key/value pair into the linked list*/
list_entry_t *list_insert(list_head_t *list, void *key, void *value) {
    assert(list != NULL);
    list_entry_t *element_ptr;
    element_ptr = list->list;
    if(element_ptr == NULL) {
        list_entry_t * new_element = malloc(sizeof(list_entry_t));
        new_element->key = key;
        new_element->value = value;
        new_element->next = NULL;


        list->list = new_element;
        return new_element;
    }
    list_entry_t *element = element_ptr;
    while(element->next != NULL) {
        element = (element->next);
    }

    list_entry_t *new_element = malloc(sizeof(list_entry_t));

    new_element->key = key;
    new_element->value = value;
    new_element->next = NULL;
    element->next = new_element;


    return new_element;


}


/*this should not be called directly. It recursively frees all nodes connected to the given entry
 * and then deletes the given entry
 */
void list_entry_delete(list_entry_t *node) {
    if(node->next != NULL) {
        list_entry_delete(node->next);
    }
    free(node);
}
/*deletes the list*/
void list_delete(list_head_t *list) {
    if(list == NULL) {
        return;
    }
    if(list->list != NULL) {
        list_entry_delete(list->list);
    }
    free(list);
}
/*the size of my hash table*/
const int HASH_SIZE = 50;


hash_head_t* hash_init(int (*hash)(const void *),int (*cmp)(const void *, const void *)) {
    hash_head_t *new_hash = (hash_head_t*)malloc(sizeof(hash_head_t));
    new_hash->buckets = (list_head_t**)calloc(HASH_SIZE, sizeof(void*));
    int i;
    for(i =0 ; i< HASH_SIZE;++i) {
        new_hash->buckets[i] =  list_init(cmp);
    }
    new_hash->cmp = cmp;
    new_hash->hash = hash;
    return new_hash;
}
/*insert the given key/value pair into the hash table*/
list_entry_t *hash_insert(hash_head_t *table, void *key, void *value) {
    assert(key != NULL);
    int hash = table->hash(key);
    return list_insert(table->buckets[hash % HASH_SIZE],key,value);
}
/*turns the hash table into a linked list, without modifying the underlying hash table*/
list_head_t *hash_to_list(hash_head_t *table) {
    list_head_t *hash_list = list_init(table->cmp);
    int i;
    for(i = 0; i < HASH_SIZE;++i) {
        list_head_t *bucket_list = table->buckets[i];
        list_entry_t *item = bucket_list->list;
        while(item != NULL) {
        list_insert(hash_list,item->key, item->value);
        item = item->next;
        }
    }
    return hash_list;
}

//remove the given key from the hash table
int hash_remove(hash_head_t *table, void *key) {
    assert(table != NULL);
    assert(key != NULL);
    int hash = table->hash(key);
    return list_remove(table->buckets[hash % HASH_SIZE],key);

}

//a function used to find the number of elements in the
//given hash table
int length_of_hash(hash_head_t *table) {
    assert(table != NULL);
    int i = 0;
    int len = 0; 
    for(i = 0; i < HASH_SIZE; ++i) {
        len += length_of_list(table->buckets[i]);
    }
    return len;

}
/*search the hash tree for the given key. Return the associated value if the key is in the table, return NULL otherwise*/
void *hash_search(hash_head_t *table, void *key) {
    assert(key != NULL);
    int hash = table->hash(key);
    return list_search(table->buckets[hash % HASH_SIZE], key);
}
list_entry_t *hash_get_element(hash_head_t *table, void *key) {
    assert(key != NULL);
    int hash = table->hash(key);
    list_entry_t* ans= list_get_element(table->buckets[hash % HASH_SIZE], key);
    return ans;
}
/*free the list.*/
void hash_delete(hash_head_t *table) {
    int i = 0;
    for(i = 0; i < HASH_SIZE;++i) {;
        list_delete(table->buckets[i]);
    }
    free(table);
}