"""
p101 — LFU Cache (LC 460)

Goal: O(1) get and put. Eviction = least frequently used; tie-break = LRU within that freq.

Design (canonical):
  - key_to_node: dict[key, Node]
  - freq_to_dll: dict[freq, DLL]  (head = MRU within that freq; tail = LRU)
  - min_freq: int, pointer that only increments or resets to 1 on insert

INVARIANT 1: min_freq points to a non-empty bucket OR cache is empty.
INVARIANT 2: On _bump, if old bucket becomes empty AND old_freq == min_freq, min_freq += 1
             (the bumped node itself now lives at min_freq + 1; nothing else has freq < it).
INVARIANT 3: New inserts always have freq=1, so min_freq resets to 1.
"""
from __future__ import annotations
from collections import OrderedDict
from typing import Dict, Optional
import random


# -----------------------------------------------------------------------------
# Canonical: manual DLL per frequency bucket
# -----------------------------------------------------------------------------
class _Node:
    __slots__ = ("key", "val", "freq", "prev", "next")

    def __init__(self, key: int, val: int, freq: int = 1):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev: Optional["_Node"] = None
        self.next: Optional["_Node"] = None


class _DLL:
    """Doubly linked list with sentinel head/tail. Head = MRU; tail = LRU."""

    def __init__(self) -> None:
        self.head = _Node(0, 0)
        self.tail = _Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def push_front(self, node: _Node) -> None:
        nxt = self.head.next
        node.prev = self.head
        node.next = nxt
        self.head.next = node
        nxt.prev = node
        self.size += 1

    def remove(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        self.size -= 1

    def pop_tail(self) -> _Node:
        # Caller must check not empty.
        node = self.tail.prev
        self.remove(node)
        return node

    def empty(self) -> bool:
        return self.size == 0


class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.size = 0
        self.min_freq = 0
        self.key_to_node: Dict[int, _Node] = {}
        self.freq_to_dll: Dict[int, _DLL] = {}

    def _bucket(self, freq: int) -> _DLL:
        dll = self.freq_to_dll.get(freq)
        if dll is None:
            dll = _DLL()
            self.freq_to_dll[freq] = dll
        return dll

    def _bump(self, node: _Node) -> None:
        old = node.freq
        self.freq_to_dll[old].remove(node)
        if self.freq_to_dll[old].empty() and old == self.min_freq:
            # INVARIANT 2: the bumped node now lives at old+1; no other freq < old+1 exists.
            self.min_freq += 1
        node.freq += 1
        self._bucket(node.freq).push_front(node)

    def get(self, key: int) -> int:
        node = self.key_to_node.get(key)
        if node is None:
            return -1
        self._bump(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if self.cap <= 0:
            return
        node = self.key_to_node.get(key)
        if node is not None:
            node.val = value
            self._bump(node)
            return
        if self.size == self.cap:
            victim = self.freq_to_dll[self.min_freq].pop_tail()
            del self.key_to_node[victim.key]
            self.size -= 1
        new_node = _Node(key, value, freq=1)
        self.key_to_node[key] = new_node
        self._bucket(1).push_front(new_node)
        self.min_freq = 1  # INVARIANT 3
        self.size += 1


# -----------------------------------------------------------------------------
# Idiomatic Python: OrderedDict per frequency bucket
# (popitem(last=False) is O(1) LRU pop; move_to_end is O(1) MRU bump.)
# -----------------------------------------------------------------------------
class LFUCacheOrderedDict:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.key_to_val: Dict[int, int] = {}
        self.key_to_freq: Dict[int, int] = {}
        self.freq_to_keys: Dict[int, "OrderedDict[int, None]"] = {}
        self.min_freq = 0

    def _bucket(self, freq: int) -> "OrderedDict[int, None]":
        od = self.freq_to_keys.get(freq)
        if od is None:
            od = OrderedDict()
            self.freq_to_keys[freq] = od
        return od

    def _bump(self, key: int) -> None:
        old = self.key_to_freq[key]
        del self.freq_to_keys[old][key]
        if not self.freq_to_keys[old] and old == self.min_freq:
            self.min_freq += 1
        self.key_to_freq[key] = old + 1
        self._bucket(old + 1)[key] = None

    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._bump(key)
        return self.key_to_val[key]

    def put(self, key: int, value: int) -> None:
        if self.cap <= 0:
            return
        if key in self.key_to_val:
            self.key_to_val[key] = value
            self._bump(key)
            return
        if len(self.key_to_val) == self.cap:
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self._bucket(1)[key] = None
        self.min_freq = 1


# -----------------------------------------------------------------------------
# Brute oracle: O(n) scan on eviction
# -----------------------------------------------------------------------------
class LFUCacheBrute:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.tick = 0
        self.store: Dict[int, list] = {}  # key -> [val, freq, last_tick]

    def _touch(self, key: int) -> None:
        self.tick += 1
        self.store[key][1] += 1
        self.store[key][2] = self.tick

    def get(self, key: int) -> int:
        if key not in self.store:
            return -1
        self._touch(key)
        return self.store[key][0]

    def put(self, key: int, value: int) -> None:
        if self.cap <= 0:
            return
        if key in self.store:
            self.store[key][0] = value
            self._touch(key)
            return
        if len(self.store) == self.cap:
            # Evict by (freq asc, last_tick asc)
            victim = min(self.store, key=lambda k: (self.store[k][1], self.store[k][2]))
            del self.store[victim]
        self.tick += 1
        self.store[key] = [value, 1, self.tick]


# -----------------------------------------------------------------------------
# Edge cases
# -----------------------------------------------------------------------------
def edge_cases() -> None:
    # capacity 0
    c = LFUCache(0)
    c.put(0, 0)
    assert c.get(0) == -1

    # capacity 1
    c = LFUCache(1)
    c.put(1, 1)
    assert c.get(1) == 1
    c.put(2, 2)  # evicts 1
    assert c.get(1) == -1
    assert c.get(2) == 2

    # LFU example
    c = LFUCache(2)
    c.put(1, 1)
    c.put(2, 2)
    assert c.get(1) == 1            # freqs: 1->2, 2->1
    c.put(3, 3)                      # evicts 2 (min freq)
    assert c.get(2) == -1
    assert c.get(3) == 3            # freqs: 1->2, 3->2
    c.put(4, 4)                      # tie, evict LRU among {1,3} -> 1
    assert c.get(1) == -1
    assert c.get(3) == 3
    assert c.get(4) == 4

    # put-of-existing counts as access
    c = LFUCache(2)
    c.put(1, 1)
    c.put(2, 2)
    c.put(1, 10)                     # freq(1) -> 2
    c.put(3, 3)                      # evicts 2
    assert c.get(2) == -1
    assert c.get(1) == 10

    print("edge_cases OK")


# -----------------------------------------------------------------------------
# Stress test
# -----------------------------------------------------------------------------
def stress_test(trials: int = 200, ops_per_trial: int = 300) -> None:
    rng = random.Random(42)
    for t in range(trials):
        cap = rng.randint(0, 6)
        a = LFUCache(cap)
        b = LFUCacheOrderedDict(cap)
        c = LFUCacheBrute(cap)
        for _ in range(ops_per_trial):
            op = rng.choice(["get", "put", "put"])
            key = rng.randint(0, 8)
            if op == "get":
                ra, rb, rc = a.get(key), b.get(key), c.get(key)
                assert ra == rb == rc, (t, cap, op, key, ra, rb, rc)
            else:
                val = rng.randint(0, 100)
                a.put(key, val)
                b.put(key, val)
                c.put(key, val)
    print(f"stress_test OK ({trials} trials, {ops_per_trial} ops each)")


if __name__ == "__main__":
    edge_cases()
    stress_test()