// 演算法 / Algorithm:
//   雜湊表(以 key 為索引的陣列) + 雙向鏈結串列。
//   Hash table (an array indexed by key) + doubly-linked list.
//   鏈結串列維持「頭=最新、尾=最舊」的順序；查找靠雜湊表 O(1)，
//   移動與淘汰靠鏈結串列 O(1)。The list keeps head=newest, tail=oldest;
//   the hash table gives O(1) lookup, the list gives O(1) move/evict.

#include <stdlib.h>   // malloc / free / calloc

// 鏈結串列的節點 / a node of the doubly-linked list
typedef struct Node {
    int key;                 // 存 key，淘汰時要用它從雜湊表移除 / needed to erase from the map on eviction
    int value;               // 這個 key 對應的值 / the value for this key
    struct Node *prev;       // 指向前一個節點 / pointer to previous node
    struct Node *next;       // 指向後一個節點 / pointer to next node
} Node;

// 因為 0 <= key <= 10^4，直接開一個大小 10001 的陣列當雜湊表最簡單
// Since 0 <= key <= 10^4, the simplest hash table is a plain array of size 10001.
#define KEY_RANGE 10001

typedef struct {
    int capacity;            // 最多能放幾個 key / max number of keys allowed
    int size;                // 目前放了幾個 key / current number of keys
    Node **map;              // map[key] = 指向該 key 節點的指標，沒有則為 NULL / pointer to that key's node, or NULL
    Node *head;              // 虛擬頭節點(不存資料) / dummy head (no real data)
    Node *tail;              // 虛擬尾節點(不存資料) / dummy tail (no real data)
} LRUCache;

// 把節點 n 從串列中「拆掉」：讓它的前後互相牽手，跳過 n
// Unlink node n from the list: connect its neighbours to each other, skipping n.
static void unlink_node(Node *n) {
    n->prev->next = n->next;   // 前一個的 next 直接指向後一個 / previous now points to next
    n->next->prev = n->prev;   // 後一個的 prev 直接指回前一個 / next now points back to previous
}

// 把節點 n 插到緊接在虛擬頭之後(即成為最新) / insert n right after dummy head (becomes most recent)
static void insert_front(LRUCache *c, Node *n) {
    n->prev = c->head;             // n 的前面是 head / n's previous is head
    n->next = c->head->next;       // n 的後面是原本 head 後面的那個 / n's next is the old first real node
    c->head->next->prev = n;       // 原第一個節點回頭指向 n / old first node points back to n
    c->head->next = n;             // head 現在指向 n / head now points to n
}

// 移到最前 = 先拆掉再插到最前 / move to front = unlink then insert at front
static void move_front(LRUCache *c, Node *n) {
    unlink_node(n);
    insert_front(c, n);
}

LRUCache *lRUCacheCreate(int capacity) {
    LRUCache *c = (LRUCache *)malloc(sizeof(LRUCache));   // 配置快取本體 / allocate the cache struct
    c->capacity = capacity;
    c->size = 0;
    // calloc 會把所有格子初始化為 0(即 NULL)，表示一開始每個 key 都沒有節點
    // calloc zero-initializes every slot to NULL, meaning no key has a node yet.
    c->map = (Node **)calloc(KEY_RANGE, sizeof(Node *));
    c->head = (Node *)malloc(sizeof(Node));   // 建立虛擬頭 / create dummy head
    c->tail = (Node *)malloc(sizeof(Node));   // 建立虛擬尾 / create dummy tail
    c->head->prev = NULL;
    c->head->next = c->tail;   // 一開始 head 直接接 tail(串列為空) / initially head links straight to tail (empty)
    c->tail->prev = c->head;
    c->tail->next = NULL;
    return c;
}

int lRUCacheGet(LRUCache *c, int key) {
    Node *n = c->map[key];          // O(1) 用陣列索引查節點 / O(1) lookup by array index
    if (n == NULL) return -1;       // 不存在就回傳 -1 / not found -> -1
    move_front(c, n);               // 用過了，變成最新 / touched, so make it most recent
    return n->value;                // 回傳它的值 / return its value
}

void lRUCachePut(LRUCache *c, int key, int value) {
    Node *n = c->map[key];          // 先看 key 在不在 / check if key already exists
    if (n != NULL) {                // 已存在：更新值並移到最前 / exists: update value, move to front
        n->value = value;
        move_front(c, n);
        return;
    }
    // 不存在：建立新節點 / does not exist: create a new node
    Node *fresh = (Node *)malloc(sizeof(Node));
    fresh->key = key;
    fresh->value = value;
    insert_front(c, fresh);         // 新的一定是最新，插到最前 / new entry is most recent
    c->map[key] = fresh;            // 在雜湊表登記 / register in the hash table
    c->size++;                      // 數量加一 / one more key stored

    if (c->size > c->capacity) {    // 超出容量就要淘汰 / over capacity -> evict
        Node *lru = c->tail->prev;  // 尾巴前一個就是最舊的真實節點 / node before tail is the LRU
        unlink_node(lru);           // 從串列拆掉 / unlink from list
        c->map[lru->key] = NULL;    // 從雜湊表移除(用 key 定位) / erase from map using its key
        free(lru);                  // 釋放記憶體，避免洩漏 / free memory to avoid a leak
        c->size--;                  // 數量減一 / one fewer key
    }
}

void lRUCacheFree(LRUCache *c) {
    Node *cur = c->head;            // 從頭開始逐一釋放 / free every node starting from head
    while (cur != NULL) {
        Node *nxt = cur->next;      // 先記住下一個，否則 free 後就找不到了 / save next before freeing
        free(cur);
        cur = nxt;
    }
    free(c->map);                   // 釋放雜湊表陣列 / free the hash table array
    free(c);                        // 釋放快取本體 / free the cache struct
}