least_recently_used.py

from __future__ importannotations

importsys
fromcollectionsimportdeque
fromtypingimportGeneric, TypeVar

T=TypeVar("T")


classLRUCache(Generic[T]):
"""
 Page Replacement Algorithm, Least Recently Used (LRU) Caching.

 >>> lru_cache: LRUCache[str | int] = LRUCache(4)
 >>> lru_cache.refer("A")
 >>> lru_cache.refer(2)
 >>> lru_cache.refer(3)

 >>> lru_cache
 LRUCache(4) => [3, 2, 'A']

 >>> lru_cache.refer("A")
 >>> lru_cache
 LRUCache(4) => ['A', 3, 2]

 >>> lru_cache.refer(4)
 >>> lru_cache.refer(5)
 >>> lru_cache
 LRUCache(4) => [5, 4, 'A', 3]

 """

dq_store: deque[T] # Cache store of keys
key_reference: set[T] # References of the keys in cache
_MAX_CAPACITY: int=10# Maximum capacity of cache

def__init__(self, n: int) ->None:
"""Creates an empty store and map for the keys.
 The LRUCache is set the size n.
 """
self.dq_store=deque()
self.key_reference=set()
ifnotn:
LRUCache._MAX_CAPACITY=sys.maxsize
elifn<0:
raiseValueError("n should be an integer greater than 0.")
else:
LRUCache._MAX_CAPACITY=n

defrefer(self, x: T) ->None:
"""
 Looks for a page in the cache store and adds reference to the set.
 Remove the least recently used key if the store is full.
 Update store to reflect recent access.
 """
ifxnotinself.key_reference:
iflen(self.dq_store) ==LRUCache._MAX_CAPACITY:
last_element=self.dq_store.pop()
self.key_reference.remove(last_element)
else:
self.dq_store.remove(x)

self.dq_store.appendleft(x)
self.key_reference.add(x)

defdisplay(self) ->None:
"""
 Prints all the elements in the store.
 """
forkinself.dq_store:
print(k)

def__repr__(self) ->str:
returnf"LRUCache({self._MAX_CAPACITY}) => {list(self.dq_store)}"


if__name__=="__main__":
importdoctest

doctest.testmod()

lru_cache: LRUCache[str|int] =LRUCache(4)
lru_cache.refer("A")
lru_cache.refer(2)
lru_cache.refer(3)
lru_cache.refer("A")
lru_cache.refer(4)
lru_cache.refer(5)
lru_cache.display()

print(lru_cache)
assertstr(lru_cache) =="LRUCache(4) => [5, 4, 'A', 3]"