"""Least-recently-used (LRU) cache with O(1) average get/put.

The cache is backed by an ``OrderedDict``, which keeps keys in insertion /
use order and supports moving an existing key to either end in O(1) average
time. The most-recently-used key is kept at the right end of the ordering and
the least-recently-used key at the left end, so eviction is a constant-time
``popitem(last=False)``.
"""

from collections import OrderedDict


class LRUCache:
    """A fixed-capacity cache that evicts the least recently used key.

    Parameters
    ----------
    capacity:
        Maximum number of keys the cache may hold. Must be a non-negative
        integer. A capacity of 0 stores nothing.
    """

    def __init__(self, capacity):
        if capacity < 0:
            raise ValueError("capacity must be a non-negative integer")
        self.capacity = capacity
        self._store = OrderedDict()

    def get(self, key):
        """Return the value for ``key``, or -1 if it is not present.

        A successful lookup marks ``key`` as the most recently used.
        """
        if key not in self._store:
            return -1
        # Refresh recency: move to the most-recently-used (right) end.
        self._store.move_to_end(key)
        return self._store[key]

    def put(self, key, value):
        """Insert or update ``value`` for ``key`` as the most recently used.

        Updating an existing key refreshes its recency without growing the
        cache. Inserting a new key may evict the least recently used key if
        the cache is at capacity. With a capacity of 0 this is a no-op.
        """
        if self.capacity == 0:
            return
        if key in self._store:
            # Existing key: update value and refresh recency in place.
            self._store[key] = value
            self._store.move_to_end(key)
            return
        # New key: insert as most recently used, then evict if over capacity.
        self._store[key] = value
        if len(self._store) > self.capacity:
            self._store.popitem(last=False)