other.lfu_cache
===============

.. py:module:: other.lfu_cache


Attributes
----------

.. autoapisummary::

   other.lfu_cache.T
   other.lfu_cache.U


Classes
-------

.. autoapisummary::

   other.lfu_cache.DoubleLinkedList
   other.lfu_cache.DoubleLinkedListNode
   other.lfu_cache.LFUCache


Module Contents
---------------

.. py:class:: DoubleLinkedList

   Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ , :py:obj:`U`\ ]


   Double Linked List built specifically for LFU Cache

   >>> dll: DoubleLinkedList = DoubleLinkedList()
   >>> dll
   DoubleLinkedList,
       Node: key: None, val: None, freq: 0, has next: True, has prev: False,
       Node: key: None, val: None, freq: 0, has next: False, has prev: True

   >>> first_node = DoubleLinkedListNode(1,10)
   >>> first_node
   Node: key: 1, val: 10, freq: 0, has next: False, has prev: False


   >>> dll.add(first_node)
   >>> dll
   DoubleLinkedList,
       Node: key: None, val: None, freq: 0, has next: True, has prev: False,
       Node: key: 1, val: 10, freq: 1, has next: True, has prev: True,
       Node: key: None, val: None, freq: 0, has next: False, has prev: True

   >>> # node is mutated
   >>> first_node
   Node: key: 1, val: 10, freq: 1, has next: True, has prev: True

   >>> second_node = DoubleLinkedListNode(2,20)
   >>> second_node
   Node: key: 2, val: 20, freq: 0, has next: False, has prev: False

   >>> dll.add(second_node)
   >>> dll
   DoubleLinkedList,
       Node: key: None, val: None, freq: 0, has next: True, has prev: False,
       Node: key: 1, val: 10, freq: 1, has next: True, has prev: True,
       Node: key: 2, val: 20, freq: 1, has next: True, has prev: True,
       Node: key: None, val: None, freq: 0, has next: False, has prev: True

   >>> removed_node = dll.remove(first_node)
   >>> assert removed_node == first_node
   >>> dll
   DoubleLinkedList,
       Node: key: None, val: None, freq: 0, has next: True, has prev: False,
       Node: key: 2, val: 20, freq: 1, has next: True, has prev: True,
       Node: key: None, val: None, freq: 0, 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, freq: 0, 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, freq: 0, has next: False, has prev: True
   >>> dll.remove(dll.rear) is None
   True




   .. py:method:: __repr__() -> str


   .. py:method:: _position_node(node: DoubleLinkedListNode[T, U]) -> None

      Moves node forward to maintain invariant of sort by freq value



   .. py:method:: add(node: DoubleLinkedListNode[T, U]) -> None

      Adds the given node at the tail of the list and shifting it to proper position



   .. 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 LFU Cache

   >>> node = DoubleLinkedListNode(1,1)
   >>> node
   Node: key: 1, val: 1, freq: 0, has next: False, has prev: False


   .. py:method:: __repr__() -> str


   .. py:attribute:: freq
      :type:  int
      :value: 0



   .. 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:: LFUCache(capacity: int)

   Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ , :py:obj:`U`\ ]


   LFU Cache to store a given capacity of data. Can be used as a stand-alone object
   or as a function decorator.

   >>> cache = LFUCache(2)
   >>> cache.put(1, 1)
   >>> cache.put(2, 2)
   >>> cache.get(1)
   1
   >>> cache.put(3, 3)
   >>> 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)
   >>> @LFUCache.decorator(100)
   ... def fib(num):
   ...     if num in (1, 2):
   ...         return 1
   ...     return fib(num - 1) + fib(num - 2)

   >>> for i in range(1, 101):
   ...     res = fib(i)

   >>> fib.cache_info()
   CacheInfo(hits=196, misses=100, capacity=100, current_size=100)


   .. py:method:: __contains__(key: T) -> bool

      >>> cache = LFUCache(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 LFU 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
      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