Design an LRU Cache

from __future__ import annotations

import threading
from collections.abc import Callable


class Node[K, V]:
    """One entry in the recency list."""
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key: K | None = None, val: V | None = None):
        self.key, self.val = key, val
        self.prev: Node[K, V] | None = None
        self.next: Node[K, V] | None = None


class Cache[K, V]:
    """Fixed-size LRU cache. get and put are O(1). Not thread-safe: see Safe.
    (collections.OrderedDict can do this in a few lines; we build the list by hand to see how.)"""

    def __init__(self, capacity: int, on_evict: Callable[[K, V], None] | None = None):
        if capacity <= 0:
            raise ValueError(f"capacity must be positive, got {capacity}")
        self.cap, self.on_evict = capacity, on_evict
        self.items: dict[K, Node[K, V]] = {}
        self.head: Node[K, V] = Node()  # sentinel: head.next is the most recently used
        self.tail: Node[K, V] = Node()  # sentinel: tail.prev is the least recently used
        self.head.next, self.tail.prev = self.tail, self.head
        self.hits = self.misses = 0

    def get(self, key: K) -> V | None:
        n = self.items.get(key)
        if n is None:
            self.misses += 1
            return None
        self.hits += 1
        self._move_to_front(n)
        return n.val

    def put(self, key: K, val: V) -> None:
        n = self.items.get(key)
        if n is not None:
            n.val = val
            self._move_to_front(n)
            return
        if len(self.items) == self.cap:
            lru = self.tail.prev
            assert lru is not None
            self._unlink(lru)
            del self.items[lru.key]  # type: ignore[arg-type]
            if self.on_evict:
                self.on_evict(lru.key, lru.val)  # type: ignore[arg-type]
        n = Node(key, val)
        self.items[key] = n
        self._push_front(n)

    def delete(self, key: K) -> bool:
        n = self.items.pop(key, None)
        if n is not None:
            self._unlink(n)
        return n is not None

    def __len__(self) -> int:
        return len(self.items)

    def keys(self) -> list[K]:
        """Most to least recently used. O(n), for tests and debugging."""
        out, n = [], self.head.next
        while n is not self.tail:
            out.append(n.key)
            n = n.next
        return out

    # The three list moves. Thanks to the sentinels there are no None checks.
    def _unlink(self, n: Node[K, V]) -> None:
        n.prev.next, n.next.prev = n.next, n.prev  # type: ignore[union-attr]
        n.prev = n.next = None

    def _push_front(self, n: Node[K, V]) -> None:
        n.prev, n.next = self.head, self.head.next
        self.head.next.prev = n  # type: ignore[union-attr]
        self.head.next = n

    def _move_to_front(self, n: Node[K, V]) -> None:
        self._unlink(n)
        self._push_front(n)


class Safe[K, V]:
    """Wraps a Cache with a lock. get moves an entry, so even a read needs the lock."""

    def __init__(self, capacity: int, on_evict: Callable[[K, V], None] | None = None):
        self._c: Cache[K, V] = Cache(capacity, on_evict)
        self._lock = threading.Lock()

    def get(self, key: K) -> V | None:
        with self._lock:
            return self._c.get(key)

    def put(self, key: K, val: V) -> None:
        with self._lock:
            self._c.put(key, val)

    def delete(self, key: K) -> bool:
        with self._lock:
            return self._c.delete(key)

    def keys(self) -> list[K]:
        with self._lock:
            return self._c.keys()


def main() -> None:
    evicted = [""]

    def remember(k: str, _: str) -> None:
        evicted[0] = k

    c: Cache[str, str] = Cache(3, remember)
    print("profile cache, capacity 3, keys from most to least recent")

    def show(action: str) -> None:
        note = f"   evicted {evicted[0]}" if evicted[0] else ""
        evicted[0] = ""
        print(f"{action:<26} [{' '.join(c.keys())}]{note}")

    def put(k: str, v: str) -> None:
        c.put(k, v)
        show(f"put {k} = {v}")

    def get(k: str) -> None:
        v = c.get(k)
        show(f"get {k} -> {v if v is not None else 'miss'}")

    put("rahim", "Mirpur")
    put("nadia", "Dhanmondi")
    put("tania", "Banani")
    get("rahim")
    put("sabbir", "Uttara")
    get("nadia")
    get("tania")
    put("karim", "Gulshan")
    put("sabbir", "Bashundhara")
    print(f"hits {c.hits}, misses {c.misses}, size {len(c)}")


if __name__ == "__main__":
    main()

// A JS Map remembers insertion order, so delete + set can fake LRU in a few lines.
// We build the list by hand to see how it works. (The names are LruCache and Entry
// because browsers already have global Cache and Node types.)

class Entry<K, V> {
  key: K; val: V;
  prev: Entry<K, V> | null = null;
  next: Entry<K, V> | null = null;
  constructor(key: K, val: V) { this.key = key; this.val = val; }
}

/** Fixed-size LRU cache. get and put are O(1). */
class LruCache<K, V> {
  private items = new Map<K, Entry<K, V>>();
  private head: Entry<K, V>; // sentinel: head.next is the most recently used
  private tail: Entry<K, V>; // sentinel: tail.prev is the least recently used
  private cap: number;
  private onEvict?: (k: K, v: V) => void;
  hits = 0;
  misses = 0;

  constructor(capacity: number, onEvict?: (k: K, v: V) => void) {
    if (capacity <= 0) throw new Error(`capacity must be positive, got ${capacity}`);
    this.cap = capacity;
    this.onEvict = onEvict;
    this.head = new Entry<K, V>(undefined as K, undefined as V);
    this.tail = new Entry<K, V>(undefined as K, undefined as V);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: K): V | undefined {
    const n = this.items.get(key);
    if (!n) { this.misses++; return undefined; }
    this.hits++;
    this.moveToFront(n);
    return n.val;
  }

  put(key: K, val: V): void {
    const found = this.items.get(key);
    if (found) { found.val = val; this.moveToFront(found); return; }
    if (this.items.size === this.cap) {
      const lru = this.tail.prev!;
      this.unlink(lru);
      this.items.delete(lru.key);
      this.onEvict?.(lru.key, lru.val);
    }
    const n = new Entry(key, val);
    this.items.set(key, n);
    this.pushFront(n);
  }

  delete(key: K): boolean {
    const n = this.items.get(key);
    if (!n) return false;
    this.unlink(n);
    this.items.delete(key);
    return true;
  }

  get size(): number { return this.items.size; }

  /** Most to least recently used. O(n), for tests and debugging. */
  keys(): K[] {
    const out: K[] = [];
    for (let n = this.head.next!; n !== this.tail; n = n.next!) out.push(n.key);
    return out;
  }

  // The three list moves. Thanks to the sentinels there are no null checks.
  private unlink(n: Entry<K, V>): void {
    n.prev!.next = n.next;
    n.next!.prev = n.prev;
    n.prev = n.next = null;
  }
  private pushFront(n: Entry<K, V>): void {
    n.prev = this.head;
    n.next = this.head.next;
    this.head.next!.prev = n;
    this.head.next = n;
  }
  private moveToFront(n: Entry<K, V>): void { this.unlink(n); this.pushFront(n); }
}

// One thread runs JavaScript, so there's no Safe wrapper: a method can't be interrupted halfway.

function main(): void {
  let evicted = "";
  const c = new LruCache<string, string>(3, (k) => { evicted = k; });
  console.log("profile cache, capacity 3, keys from most to least recent");

  const show = (action: string) => {
    const note = evicted ? `   evicted ${evicted}` : "";
    evicted = "";
    console.log(`${action.padEnd(26)} [${c.keys().join(" ")}]${note}`);
  };
  const put = (k: string, v: string) => { c.put(k, v); show(`put ${k} = ${v}`); };
  const get = (k: string) => { const v = c.get(k); show(`get ${k} -> ${v ?? "miss"}`); };

  put("rahim", "Mirpur");
  put("nadia", "Dhanmondi");
  put("tania", "Banani");
  get("rahim");
  put("sabbir", "Uttara");
  get("nadia");
  get("tania");
  put("karim", "Gulshan");
  put("sabbir", "Bashundhara");
  console.log(`hits ${c.hits}, misses ${c.misses}, size ${c.size}`);
}

main();

use std::collections::HashMap;
use std::hash::Hash;
use std::sync::Mutex;

// A doubly linked list with pointers both ways fights Rust's ownership rules. So the nodes
// live in a Vec and point to each other by index. Slot 0 is the head sentinel, slot 1 the tail.
const HEAD: usize = 0;
const TAIL: usize = 1;

struct Node<K, V> {
    key: Option<K>, // None only for the two sentinels
    val: Option<V>,
    prev: usize,
    next: usize,
}

/// Fixed-size LRU cache. get and put are O(1). Not thread-safe on its own: see Safe.
struct Cache<K, V> {
    cap: usize,
    items: HashMap<K, usize>, // key -> slot in `nodes`
    nodes: Vec<Node<K, V>>,
    free: Vec<usize>, // slots freed by delete, reused by put
    hits: u32,
    misses: u32,
}

impl<K: Hash + Eq + Clone, V: Clone> Cache<K, V> {
    fn new(cap: usize) -> Result<Self, String> {
        if cap == 0 {
            return Err("capacity must be positive, got 0".into());
        }
        let nodes = vec![
            Node { key: None, val: None, prev: HEAD, next: TAIL },
            Node { key: None, val: None, prev: HEAD, next: TAIL },
        ];
        Ok(Cache { cap, items: HashMap::new(), nodes, free: vec![], hits: 0, misses: 0 })
    }

    fn get(&mut self, key: &K) -> Option<V> {
        let Some(&i) = self.items.get(key) else {
            self.misses += 1;
            return None;
        };
        self.hits += 1;
        self.unlink(i);
        self.push_front(i);
        self.nodes[i].val.clone()
    }

    /// Adds or updates. Returns the evicted entry, if the cache was full.
    fn put(&mut self, key: K, val: V) -> Option<(K, V)> {
        if let Some(&i) = self.items.get(&key) {
            self.nodes[i].val = Some(val);
            self.unlink(i);
            self.push_front(i);
            return None;
        }
        let mut evicted = None;
        if self.items.len() == self.cap {
            let lru = self.nodes[TAIL].prev;
            self.unlink(lru);
            let (k, v) = (self.nodes[lru].key.take().unwrap(), self.nodes[lru].val.take().unwrap());
            self.items.remove(&k);
            self.free.push(lru);
            evicted = Some((k, v));
        }
        let node = Node { key: Some(key.clone()), val: Some(val), prev: HEAD, next: TAIL };
        let i = match self.free.pop() {
            Some(i) => {
                self.nodes[i] = node;
                i
            }
            None => {
                self.nodes.push(node);
                self.nodes.len() - 1
            }
        };
        self.items.insert(key, i);
        self.push_front(i);
        evicted
    }

    #[allow(dead_code)]
    fn delete(&mut self, key: &K) -> bool {
        let Some(i) = self.items.remove(key) else { return false };
        self.unlink(i);
        self.nodes[i].key = None;
        self.nodes[i].val = None;
        self.free.push(i);
        true
    }

    fn len(&self) -> usize {
        self.items.len()
    }

    /// Most to least recently used. O(n), for tests and debugging.
    fn keys(&self) -> Vec<K> {
        let mut out = vec![];
        let mut i = self.nodes[HEAD].next;
        while i != TAIL {
            out.push(self.nodes[i].key.clone().unwrap());
            i = self.nodes[i].next;
        }
        out
    }

    // The two list moves, with indices instead of pointers.
    fn unlink(&mut self, i: usize) {
        let (p, n) = (self.nodes[i].prev, self.nodes[i].next);
        self.nodes[p].next = n;
        self.nodes[n].prev = p;
    }

    fn push_front(&mut self, i: usize) {
        let first = self.nodes[HEAD].next;
        self.nodes[i].prev = HEAD;
        self.nodes[i].next = first;
        self.nodes[first].prev = i;
        self.nodes[HEAD].next = i;
    }
}

/// Shares a Cache between threads. get moves an entry, so even a read takes the lock
/// (and Rust won't let you call get through a shared reference without one).
#[allow(dead_code)]
struct Safe<K, V>(Mutex<Cache<K, V>>);

#[allow(dead_code)]
impl<K: Hash + Eq + Clone, V: Clone> Safe<K, V> {
    fn get(&self, key: &K) -> Option<V> {
        self.0.lock().unwrap().get(key)
    }
    fn put(&self, key: K, val: V) -> Option<(K, V)> {
        self.0.lock().unwrap().put(key, val)
    }
}

fn main() {
    let mut c: Cache<String, String> = Cache::new(3).unwrap();
    println!("profile cache, capacity 3, keys from most to least recent");

    fn show(c: &Cache<String, String>, action: String, evicted: Option<(String, String)>) {
        let note = evicted.map(|(k, _)| format!("   evicted {k}")).unwrap_or_default();
        println!("{action:<26} [{}]{note}", c.keys().join(" "));
    }
    let put = |c: &mut Cache<String, String>, k: &str, v: &str| {
        let ev = c.put(k.to_string(), v.to_string());
        show(c, format!("put {k} = {v}"), ev);
    };
    let get = |c: &mut Cache<String, String>, k: &str| {
        let v = c.get(&k.to_string()).unwrap_or("miss".into());
        show(c, format!("get {k} -> {v}"), None);
    };

    put(&mut c, "rahim", "Mirpur");
    put(&mut c, "nadia", "Dhanmondi");
    put(&mut c, "tania", "Banani");
    get(&mut c, "rahim");
    put(&mut c, "sabbir", "Uttara");
    get(&mut c, "nadia");
    get(&mut c, "tania");
    put(&mut c, "karim", "Gulshan");
    put(&mut c, "sabbir", "Bashundhara");
    println!("hits {}, misses {}, size {}", c.hits, c.misses, c.len());
}

import java.util.*;
import java.util.function.BiConsumer;

// java.util.LinkedHashMap(cap, 0.75f, true) with removeEldestEntry is a ready-made LRU.
// We build the list by hand to see how it works.
public class Main {
    static final class Node<K, V> {
        K key;
        V val;
        Node<K, V> prev, next;
        Node(K key, V val) { this.key = key; this.val = val; }
    }

    /** Fixed-size LRU cache. get and put are O(1). Not thread-safe: see Safe. */
    static class Cache<K, V> {
        private final int cap;
        private final Map<K, Node<K, V>> items = new HashMap<>();
        private final Node<K, V> head = new Node<>(null, null); // head.next = most recently used
        private final Node<K, V> tail = new Node<>(null, null); // tail.prev = least recently used
        private final BiConsumer<K, V> onEvict;
        int hits, misses;

        Cache(int capacity, BiConsumer<K, V> onEvict) {
            if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive, got " + capacity);
            this.cap = capacity;
            this.onEvict = onEvict;
            head.next = tail;
            tail.prev = head;
        }

        Optional<V> get(K key) {
            Node<K, V> n = items.get(key);
            if (n == null) { misses++; return Optional.empty(); }
            hits++;
            moveToFront(n);
            return Optional.of(n.val);
        }

        void put(K key, V val) {
            Node<K, V> n = items.get(key);
            if (n != null) { n.val = val; moveToFront(n); return; }
            if (items.size() == cap) {
                Node<K, V> lru = tail.prev;
                unlink(lru);
                items.remove(lru.key);
                if (onEvict != null) onEvict.accept(lru.key, lru.val);
            }
            n = new Node<>(key, val);
            items.put(key, n);
            pushFront(n);
        }

        boolean delete(K key) {
            Node<K, V> n = items.remove(key);
            if (n != null) unlink(n);
            return n != null;
        }

        int size() { return items.size(); }

        /** Most to least recently used. O(n), for tests and debugging. */
        List<K> keys() {
            List<K> out = new ArrayList<>();
            for (Node<K, V> n = head.next; n != tail; n = n.next) out.add(n.key);
            return out;
        }

        // The three list moves. Thanks to the sentinels there are no null checks.
        private void unlink(Node<K, V> n) {
            n.prev.next = n.next;
            n.next.prev = n.prev;
            n.prev = n.next = null;
        }

        private void pushFront(Node<K, V> n) {
            n.prev = head;
            n.next = head.next;
            head.next.prev = n;
            head.next = n;
        }

        private void moveToFront(Node<K, V> n) { unlink(n); pushFront(n); }
    }

    /** Wraps a Cache with a lock. get moves an entry, so even a read is synchronized. */
    static final class Safe<K, V> {
        private final Cache<K, V> c;
        Safe(int capacity, BiConsumer<K, V> onEvict) { c = new Cache<>(capacity, onEvict); }
        synchronized Optional<V> get(K key) { return c.get(key); }
        synchronized void put(K key, V val) { c.put(key, val); }
        synchronized boolean delete(K key) { return c.delete(key); }
        synchronized List<K> keys() { return c.keys(); }
    }

    static String evicted = "";
    static Cache<String, String> c;

    static void show(String action) {
        String note = evicted.isEmpty() ? "" : "   evicted " + evicted;
        evicted = "";
        System.out.printf("%-26s [%s]%s%n", action, String.join(" ", c.keys()), note);
    }

    static void put(String k, String v) { c.put(k, v); show("put " + k + " = " + v); }

    static void get(String k) { show("get " + k + " -> " + c.get(k).orElse("miss")); }

    public static void main(String[] args) {
        c = new Cache<>(3, (k, v) -> evicted = k);
        System.out.println("profile cache, capacity 3, keys from most to least recent");
        put("rahim", "Mirpur");
        put("nadia", "Dhanmondi");
        put("tania", "Banani");
        get("rahim");
        put("sabbir", "Uttara");
        get("nadia");
        get("tania");
        put("karim", "Gulshan");
        put("sabbir", "Bashundhara");
        System.out.printf("hits %d, misses %d, size %d%n", c.hits, c.misses, c.size());
    }
}

#include <cstdio>
#include <functional>
#include <list>
#include <mutex>
#include <optional>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

// Fixed-size LRU cache. get and put are O(1). Not thread-safe: see Safe.
// std::list is already a doubly linked list, and splice moves a node to the front in O(1)
// without copying it, so the map can keep iterators into the list.
template <typename K, typename V>
class Cache {
   public:
    using OnEvict = std::function<void(const K&, const V&)>;

    explicit Cache(int capacity, OnEvict onEvict = nullptr) : cap_(capacity), onEvict_(std::move(onEvict)) {
        if (capacity <= 0) throw std::invalid_argument("capacity must be positive, got " + std::to_string(capacity));
    }

    std::optional<V> get(const K& key) {
        auto it = items_.find(key);
        if (it == items_.end()) {
            misses++;
            return std::nullopt;
        }
        hits++;
        order_.splice(order_.begin(), order_, it->second);  // move to front
        return it->second->second;
    }

    void put(const K& key, V val) {
        if (auto it = items_.find(key); it != items_.end()) {
            it->second->second = std::move(val);
            order_.splice(order_.begin(), order_, it->second);
            return;
        }
        if (static_cast<int>(items_.size()) == cap_) {
            auto& [k, v] = order_.back();  // least recently used
            if (onEvict_) onEvict_(k, v);
            items_.erase(k);
            order_.pop_back();
        }
        order_.emplace_front(key, std::move(val));
        items_[key] = order_.begin();
    }

    bool remove(const K& key) {
        auto it = items_.find(key);
        if (it == items_.end()) return false;
        order_.erase(it->second);
        items_.erase(it);
        return true;
    }

    size_t size() const { return items_.size(); }

    // Most to least recently used. O(n), for tests and debugging.
    std::vector<K> keys() const {
        std::vector<K> out;
        for (auto& [k, _] : order_) out.push_back(k);
        return out;
    }

    int hits = 0, misses = 0;

   private:
    int cap_;
    OnEvict onEvict_;
    std::list<std::pair<K, V>> order_;  // front = most recently used
    std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> items_;
};

// Wraps a Cache with a mutex. get moves an entry, so even a read takes the lock
// (a shared_mutex with shared_lock in get would be a data race).
template <typename K, typename V>
class Safe {
   public:
    explicit Safe(int capacity) : c_(capacity) {}
    std::optional<V> get(const K& key) {
        std::lock_guard lock(mu_);
        return c_.get(key);
    }
    void put(const K& key, V val) {
        std::lock_guard lock(mu_);
        c_.put(key, std::move(val));
    }

   private:
    std::mutex mu_;
    Cache<K, V> c_;
};

std::string join(const std::vector<std::string>& v) {
    std::string out;
    for (size_t i = 0; i < v.size(); i++) out += (i ? " " : "") + v[i];
    return out;
}

int main() {
    std::string evicted;
    Cache<std::string, std::string> c(3, [&](const std::string& k, const std::string&) { evicted = k; });
    std::printf("profile cache, capacity 3, keys from most to least recent\n");

    auto show = [&](const std::string& action) {
        std::string note = evicted.empty() ? "" : "   evicted " + evicted;
        evicted.clear();
        std::printf("%-26s [%s]%s\n", action.c_str(), join(c.keys()).c_str(), note.c_str());
    };
    auto put = [&](const std::string& k, const std::string& v) {
        c.put(k, v);
        show("put " + k + " = " + v);
    };
    auto get = [&](const std::string& k) {
        auto v = c.get(k);
        show("get " + k + " -> " + v.value_or("miss"));
    };

    put("rahim", "Mirpur");
    put("nadia", "Dhanmondi");
    put("tania", "Banani");
    get("rahim");
    put("sabbir", "Uttara");
    get("nadia");
    get("tania");
    put("karim", "Gulshan");
    put("sabbir", "Bashundhara");
    std::printf("hits %d, misses %d, size %zu\n", c.hits, c.misses, c.size());
}