146. LRU Cache

LRUCache cache = new LRUCache(2);   // capacity = 2
cache.put(1, 1);   // cache: {1=1}
cache.put(2, 2);   // cache: {1=1, 2=2}
cache.get(1);      // returns 1     -> now 1 is most recent
cache.put(3, 3);   // capacity full, evict LRU (key 2) -> {1=1, 3=3}
cache.get(2);      // returns -1 (evicted)
cache.put(4, 4);   // evict LRU (key 1) -> {3=3, 4=4}
cache.get(1);      // returns -1
cache.get(3);      // returns 3
cache.get(4);      // returns 4

// 演算法 / 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
}

// 演算法 / Algorithm:
//   unordered_map(雜湊表) + list(標準庫的雙向鏈結串列)。
//   unordered_map + std::list (the standard doubly-linked list).
//   list 頭=最新、尾=最舊；map 把 key 對應到 list 中的迭代器，
//   讓我們能 O(1) 找到並用 splice 移動節點。
//   The list keeps head=newest/tail=oldest; the map maps key to a list iterator,
//   so we can find and splice a node in O(1).

#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
private:
    int cap;   // 容量 / capacity
    // list 每個元素是一對 {key, value}；pair.first=key, pair.second=value
    // Each list element is a pair {key, value}.
    list<pair<int,int>> items;
    // map: key -> 指向 list 中對應元素的迭代器(iterator，可想成「位置憑證」)
    // map: key -> an iterator (a handle to the element's position in the list)
    unordered_map<int, list<pair<int,int>>::iterator> pos;

public:
    LRUCache(int capacity) : cap(capacity) {}   // 成員初始化列表設定容量 / init capacity

    int get(int key) {
        auto it = pos.find(key);        // 在 map 中找 key / look up key in the map
        if (it == pos.end()) return -1; // 找不到就回傳 -1 / not found -> -1
        // splice 把節點從原位置搬到 items 的最前面，指標不失效、O(1)。
        // splice moves the node to the front of items in O(1) without invalidating iterators.
        // it->second 是那個節點的迭代器 / it->second is the node's iterator
        items.splice(items.begin(), items, it->second);
        return it->second->second;      // 迭代器指向 pair，.second 就是 value / the value
    }

    void put(int key, int value) {
        auto it = pos.find(key);        // 先看 key 在不在 / check existence
        if (it != pos.end()) {          // 已存在 / exists
            it->second->second = value; // 更新 value / update value
            items.splice(items.begin(), items, it->second);  // 移到最前 / move to front
            return;
        }
        if ((int)items.size() == cap) { // 滿了才淘汰(先淘汰再插入也可) / full -> evict LRU first
            auto &oldest = items.back();  // list 尾端是最舊的 / back of list is least recently used
            pos.erase(oldest.first);      // 用它的 key 從 map 移除 / erase from map by its key
            items.pop_back();             // 從 list 移除尾端 / remove it from the list
        }
        // emplace_front 直接在最前面就地建立 {key,value}，比 push_front 少一次複製
        // emplace_front constructs {key,value} in place at the front (fewer copies than push_front)
        items.emplace_front(key, value);
        pos[key] = items.begin();       // 登記新節點的迭代器 / record the new node's iterator
    }
};

/**
 * 你的 LRUCache 會被這樣使用 / Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */