TheAlgorithms-Python

1
from __future__ import annotations
2

3
import sys
4
from collections import deque
5
from typing import Generic, TypeVar
6

7
T = TypeVar("T")
8

9

10
class LRUCache(Generic[T]):
11
    """
12
    Page Replacement Algorithm, Least Recently Used (LRU) Caching.
13

14
    >>> lru_cache: LRUCache[str | int] = LRUCache(4)
15
    >>> lru_cache.refer("A")
16
    >>> lru_cache.refer(2)
17
    >>> lru_cache.refer(3)
18

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

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

26
    >>> lru_cache.refer(4)
27
    >>> lru_cache.refer(5)
28
    >>> lru_cache
29
    LRUCache(4) => [5, 4, 'A', 3]
30

31
    """
32

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

37
    def __init__(self, n: int) -> None:
38
        """Creates an empty store and map for the keys.
39
        The LRUCache is set the size n.
40
        """
41
        self.dq_store = deque()
42
        self.key_reference = set()
43
        if not n:
44
            LRUCache._MAX_CAPACITY = sys.maxsize
45
        elif n < 0:
46
            raise ValueError("n should be an integer greater than 0.")
47
        else:
48
            LRUCache._MAX_CAPACITY = n
49

50
    def refer(self, x: T) -> None:
51
        """
52
        Looks for a page in the cache store and adds reference to the set.
53
        Remove the least recently used key if the store is full.
54
        Update store to reflect recent access.
55
        """
56
        if x not in self.key_reference:
57
            if len(self.dq_store) == LRUCache._MAX_CAPACITY:
58
                last_element = self.dq_store.pop()
59
                self.key_reference.remove(last_element)
60
        else:
61
            self.dq_store.remove(x)
62

63
        self.dq_store.appendleft(x)
64
        self.key_reference.add(x)
65

66
    def display(self) -> None:
67
        """
68
        Prints all the elements in the store.
69
        """
70
        for k in self.dq_store:
71
            print(k)
72

73
    def __repr__(self) -> str:
74
        return f"LRUCache({self._MAX_CAPACITY}) => {list(self.dq_store)}"
75

76

77
if __name__ == "__main__":
78
    import doctest
79

80
    doctest.testmod()
81

82
    lru_cache: LRUCache[str | int] = LRUCache(4)
83
    lru_cache.refer("A")
84
    lru_cache.refer(2)
85
    lru_cache.refer(3)
86
    lru_cache.refer("A")
87
    lru_cache.refer(4)
88
    lru_cache.refer(5)
89
    lru_cache.display()
90

91
    print(lru_cache)
92
    assert str(lru_cache) == "LRUCache(4) => [5, 4, 'A', 3]"
93