https://cachemon.github.io/SIEVE-website/blog/2023/12/17/sieve-is-simpler-than-lru/#appendix but without the linked list

sieve.py

class Node:
    def __init__(self, value):
        self.value = value
        self.visited = False
        self.prev = None
        self.next = None

class SieveCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # To store cache items as {value: node}
        self.queue = []
        self.hand = 0

    def _evict(self):
        hand = self.hand
        self.hand = 0
        for i, node in enumerate(self.queue[hand:]):
            if not node.visited:
              self.hand = i
              break
            node.visited = False

        del self.cache[self.queue[self.hand].value]
        self.queue.pop(self.hand)

    def access(self, x):
        if x in self.cache:  # Cache Hit
            node = self.cache[x]
            node.visited = True
        else:  # Cache Miss
            if len(self.cache) == self.capacity:  # Cache Full
                self._evict()  # Eviction
            new_node = Node(x)
            self.queue.append(new_node)
            self.cache[x] = new_node
            new_node.visited = False  # Insertion

    def show_cache(self):
        first = True
        for node in self.queue:
            if first: first = False
            else: print(' -> ', end='')
            print(f'{node.value} (Visited: {node.visited})', end='')
        print()

# Example usage
cache = SieveCache(3)
cache.access('A')
cache.access('B')
cache.access('C')
cache.access('D')
cache.access('B')
cache.access('E')
cache.show_cache()