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

typedef struct Node Node;
typedef struct Node{
    Node *prev;
    Node *next;
    int key;
    int val;
} Node;

typedef struct{
    // only need pointers to head and tail for eviction pop
    // and recent use push respectively 
    Node *head;
    Node *tail;
    Node **hashtable;
    int capacity;
    int curr_size;
} LRUCache;

void deleteNode(Node *);

void addprevNode(Node *, Node *);

void printCache(LRUCache *);

LRUCache* lRUCacheCreate(int);

int lRUCacheGet(LRUCache*, int);

void lRUCachePut(LRUCache*, int, int);

void lRUCacheFree(LRUCache*);

/*
  Aware of special cases:
  1. empty cache
  2. one node cache
  3. two nodes cache
*/
void deleteNode(Node *target){
    assert(target != NULL);
    // includes cases for end nodes and non-end nodes
    if(target->prev != NULL){
        target->prev->next = target->next;
    }
    if(target->next != NULL){
        target->next->prev = target->prev;
    }
    // if target is the only node in the table, nothing happens
}

/*
  Aware of special cases:
  1. empty cache
  2. one node cache
  3. target is the original head node
  4. target = newNode!
*/
void addprevNode(Node *target, Node *newNode){
    assert(target  != NULL);
    assert(newNode != NULL);

    // case of target = newNode!
    if (target == newNode){
        return;
    }
    
    newNode->next = target;
    newNode->prev = target->prev;
    target->prev  = newNode;
    
    // if target is not the original head 
    // and newNode becomes the new head
    if(newNode->prev != NULL){
        newNode->prev->next = newNode;
    }
}

void printCache(LRUCache *obj){
    assert(obj != NULL);
    Node *current = obj->head;
    printf("---------------Cache head--------------- \n");
    while(current){
        printf("Key-value pair of current node is : %d-%d \n", current->key, current->val);
        current = current->next;
    }
    printf("---------------Cache tail--------------- \n");
    printf("\n");
}

LRUCache* lRUCacheCreate(int capacity){
    const int MAX_KEY_SIZE = 10000;
    int index;
    LRUCache *Cache = (LRUCache *)malloc(sizeof(LRUCache));
    assert(Cache != NULL);
    Cache->capacity  = capacity;
    Cache->hashtable = (Node **)malloc(sizeof(Node *) * MAX_KEY_SIZE);
    assert(Cache->hashtable != NULL);
    for(index = 0; index < MAX_KEY_SIZE; index++){
        Cache->hashtable[index] = NULL;
    }
    Cache->curr_size = 0;
    Cache->head      = NULL;
    Cache->tail      = NULL;
    
    return Cache;
}

/*
  Aware of special cases:
  1. empty cache
  2. one node cache
  3. modifying head and tail nodes
*/
int lRUCacheGet(LRUCache* obj, int key){
    // 1. compare the key with keys in keylist in interation
    // 2. if match, move that node to tail for recent use
    // So, need to use deletenode and addprevnode!
    assert(obj != NULL);
    assert(obj->capacity > 0);
    assert(obj->hashtable != NULL);
    
    int result = -1;
    // Requires O(1) so must uses hashtable
    Node *targetNode;
    // if key value pair exists in cache

    // may be improved by using curr_size when dealing removing head node and re-inserting it
    
    if(obj->hashtable[key] != NULL){
        targetNode = obj->hashtable[key];
        result     = targetNode->val;
        deleteNode(targetNode);
         
        // case of modifying head and tail nodes
        if(targetNode == obj->head && targetNode->next != NULL){
            obj->head = targetNode->next;
        }
        if(targetNode == obj->tail && targetNode->prev != NULL){
            obj->tail = targetNode->prev;
        }
        addprevNode(obj->head, targetNode);
        obj->head = targetNode;
    }
    printf("Value to key %d is : %d, and cache after fetching it is: \n", key, result);
    printCache(obj);
    return result;
}

/*
  Aware of special cases:
  1. empty cache
  2. one node cache
  3. modifying head and tail nodes
*/
void lRUCachePut(LRUCache* obj, int key, int value){
    // 1. compare the key with keys in keylist in interation
    // 2. if match, update the the value corresponds to the key
    // 3. if doesn't match, if current size exceeds capacity, evicts the tail         
    //    node and add new node at tail; if current size doesn't exceed, ad new       
    //    node at tail
    // So, need to use deletenode and addprevnode!
    assert(obj != NULL);
    assert(obj->capacity > 0);
    assert(obj->hashtable != NULL);
    
    // if the key-value pair already exists
    Node *targetNode;
    if(obj->hashtable[key] != NULL){
        targetNode      = obj->hashtable[key];
        targetNode->val = value;
        deleteNode(targetNode);
         
        // case of modifying head and tail nodes
        if(targetNode == obj->head && targetNode->next != NULL){
            obj->head = targetNode->next;
        }
        if(targetNode == obj->tail && targetNode->prev != NULL){
            obj->tail = targetNode->prev;
        }
        addprevNode(obj->head, targetNode);
        obj->head = targetNode;
        
        printf("Value of key %d is updated to : %d \n", key, value);
    }
    // if the key-value pair doesn't exist yet
    else{
        // if exceeds the capacity after adding the new key-value pair 
        if(obj->curr_size >= obj->capacity){
            Node *evictNode = obj->tail;
            obj->tail = evictNode->prev;
            // case of one node cache
            if(evictNode == obj->head){
                obj->head = evictNode->prev;
            }     
            deleteNode(evictNode);
            obj->hashtable[evictNode->key] = NULL;
            obj->curr_size--;
        }
        // if doesn't exceeds the capacity after adding the new key-value pair
        Node *newNode = (Node *)malloc(sizeof(Node));
        assert(newNode != NULL);
        newNode->prev = NULL;
        newNode->next = NULL;
        newNode->key  = key;
        newNode->val  = value;
        obj->hashtable[key] = newNode;
        obj->curr_size++;
        // for the initial condition of empty cache
        if(obj->head == NULL){
            obj->head = newNode;
            obj->tail = newNode;
        }
        else{
            addprevNode(obj->head, newNode);
            obj->head = newNode;
        }
    }
    printf("Key-value pair : %d-%d is inserted into the cache \n", key, value);
    printCache(obj);
    //printf("Key-value pair : %d-%d is evicted from the hashtable!\n", evictNode->key, evictNode->val);
}

void lRUCacheFree(LRUCache* obj){
    assert(obj != NULL);
    assert(obj->capacity > 0);
    assert(obj->hashtable != NULL);
    Node *currNode = obj->head;
    
    while(currNode){
        Node *tempNode = currNode;
        // Why is freeing here causing heap use-after-free?
        // Because currNode and tempNode points to the same segment in memory
        // free(tempNode); 
        printf("Key-value pair : %d-%d in the cache is freed! \n", tempNode->key, tempNode->val);
        currNode = currNode->next;
        free(tempNode);
    }
    free(obj->hashtable);
    free(obj);
    printf("Cache freed successfully! \n");
    return;
}

int main(){
    LRUCache* obj = lRUCacheCreate(2);
    int param_1;
    lRUCachePut(obj, 1, 1);
    lRUCachePut(obj, 2, 2);
    lRUCachePut(obj, 3, 3);
    param_1 = lRUCacheGet(obj, 2);
    lRUCacheFree(obj);
    return 0;    
}