other.lru_cache =============== .. py:module:: other.lru_cache Attributes ---------- .. autoapisummary:: other.lru_cache.T other.lru_cache.U Classes ------- .. autoapisummary:: other.lru_cache.DoubleLinkedList other.lru_cache.DoubleLinkedListNode other.lru_cache.LRUCache Module Contents --------------- .. py:class:: DoubleLinkedList Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ , :py:obj:`U`\ ] Double Linked List built specifically for LRU Cache >>> dll: DoubleLinkedList = DoubleLinkedList() >>> dll DoubleLinkedList, Node: key: None, val: None, has next: True, has prev: False, Node: key: None, val: None, has next: False, has prev: True >>> first_node = DoubleLinkedListNode(1,10) >>> first_node Node: key: 1, val: 10, has next: False, has prev: False >>> dll.add(first_node) >>> dll DoubleLinkedList, Node: key: None, val: None, has next: True, has prev: False, Node: key: 1, val: 10, has next: True, has prev: True, Node: key: None, val: None, has next: False, has prev: True >>> # node is mutated >>> first_node Node: key: 1, val: 10, has next: True, has prev: True >>> second_node = DoubleLinkedListNode(2,20) >>> second_node Node: key: 2, val: 20, has next: False, has prev: False >>> dll.add(second_node) >>> dll DoubleLinkedList, Node: key: None, val: None, has next: True, has prev: False, Node: key: 1, val: 10, has next: True, has prev: True, Node: key: 2, val: 20, has next: True, has prev: True, Node: key: None, val: None, has next: False, has prev: True >>> removed_node = dll.remove(first_node) >>> assert removed_node == first_node >>> dll DoubleLinkedList, Node: key: None, val: None, has next: True, has prev: False, Node: key: 2, val: 20, has next: True, has prev: True, Node: key: None, val: None, has next: False, has prev: True >>> # Attempt to remove node not on list >>> removed_node = dll.remove(first_node) >>> removed_node is None True >>> # Attempt to remove head or rear >>> dll.head Node: key: None, val: None, has next: True, has prev: False >>> dll.remove(dll.head) is None True >>> # Attempt to remove head or rear >>> dll.rear Node: key: None, val: None, has next: False, has prev: True >>> dll.remove(dll.rear) is None True .. py:method:: __repr__() -> str .. py:method:: add(node: DoubleLinkedListNode[T, U]) -> None Adds the given node to the end of the list (before rear) .. py:method:: remove(node: DoubleLinkedListNode[T, U]) -> DoubleLinkedListNode[T, U] | None Removes and returns the given node from the list Returns None if node.prev or node.next is None .. py:attribute:: head :type: DoubleLinkedListNode[T, U] .. py:attribute:: rear :type: DoubleLinkedListNode[T, U] .. py:class:: DoubleLinkedListNode(key: T | None, val: U | None) Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ , :py:obj:`U`\ ] Double Linked List Node built specifically for LRU Cache >>> DoubleLinkedListNode(1,1) Node: key: 1, val: 1, has next: False, has prev: False .. py:method:: __repr__() -> str .. py:attribute:: key .. py:attribute:: next :type: DoubleLinkedListNode[T, U] | None :value: None .. py:attribute:: prev :type: DoubleLinkedListNode[T, U] | None :value: None .. py:attribute:: val .. py:class:: LRUCache(capacity: int) Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ , :py:obj:`U`\ ] LRU Cache to store a given capacity of data. Can be used as a stand-alone object or as a function decorator. >>> cache = LRUCache(2) >>> cache.put(1, 1) >>> cache.put(2, 2) >>> cache.get(1) 1 >>> cache.list DoubleLinkedList, Node: key: None, val: None, has next: True, has prev: False, Node: key: 2, val: 2, has next: True, has prev: True, Node: key: 1, val: 1, has next: True, has prev: True, Node: key: None, val: None, has next: False, has prev: True >>> cache.cache # doctest: +NORMALIZE_WHITESPACE {1: Node: key: 1, val: 1, has next: True, has prev: True, 2: Node: key: 2, val: 2, has next: True, has prev: True} >>> cache.put(3, 3) >>> cache.list DoubleLinkedList, Node: key: None, val: None, has next: True, has prev: False, Node: key: 1, val: 1, has next: True, has prev: True, Node: key: 3, val: 3, has next: True, has prev: True, Node: key: None, val: None, has next: False, has prev: True >>> cache.cache # doctest: +NORMALIZE_WHITESPACE {1: Node: key: 1, val: 1, has next: True, has prev: True, 3: Node: key: 3, val: 3, has next: True, has prev: True} >>> cache.get(2) is None True >>> cache.put(4, 4) >>> cache.get(1) is None True >>> cache.get(3) 3 >>> cache.get(4) 4 >>> cache CacheInfo(hits=3, misses=2, capacity=2, current size=2) >>> @LRUCache.decorator(100) ... def fib(num): ... if num in (1, 2): ... return 1 ... return fib(num - 1) + fib(num - 2) >>> for i in range(1, 100): ... res = fib(i) >>> fib.cache_info() CacheInfo(hits=194, misses=99, capacity=100, current size=99) .. py:method:: __contains__(key: T) -> bool >>> cache = LRUCache(1) >>> 1 in cache False >>> cache.put(1, 1) >>> 1 in cache True .. py:method:: __repr__() -> str Return the details for the cache instance [hits, misses, capacity, current_size] .. py:method:: decorator(size: int = 128) -> collections.abc.Callable[[collections.abc.Callable[[T], U]], collections.abc.Callable[Ellipsis, U]] :classmethod: Decorator version of LRU Cache Decorated function must be function of T -> U .. py:method:: get(key: T) -> U | None Returns the value for the input key and updates the Double Linked List. Returns None if key is not present in cache .. py:method:: put(key: T, value: U) -> None Sets the value for the input key and updates the Double Linked List .. py:attribute:: cache :type: dict[T, DoubleLinkedListNode[T, U]] .. py:attribute:: capacity .. py:attribute:: hits :value: 0 .. py:attribute:: list :type: DoubleLinkedList[T, U] .. py:attribute:: miss :value: 0 .. py:attribute:: num_keys :value: 0 .. py:data:: T .. py:data:: U