SIEVE patological case

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.head = None
        self.tail = None
        self.hand = None
        self.size = 0
        self.acc = 0
        self.hit = 0
        self.wrap = 0

    def _add_to_head(self, node):
        node.next = self.head
        node.prev = None
        if self.head:
            self.head.prev = node
        self.head = node
        if self.tail is None:
            self.tail = node

    def _remove_node(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def _evict(self):
        if not self.hand:
            print("self.tail")
            self.wrap += 1
        obj = self.hand if self.hand else self.tail
        while obj and obj.visited:
            print(f"unvisit {obj.value}")
            obj.visited = False
            obj = obj.prev if obj.prev else self.tail
        self.hand = obj.prev if obj.prev else None
        print(f"evict {obj.value}")
        del self.cache[obj.value]
        self._remove_node(obj)
        self.size -= 1

    def access(self, x):
        self.acc += 1
        if x in self.cache:  # Cache Hit
            print(f"access {x} hit")
            node = self.cache[x]
            node.visited = True
            self.hit += 1
        else:  # Cache Miss
            if self.size == self.capacity:  # Cache Full
                self._evict()  # Eviction
            new_node = Node(x)
            self._add_to_head(new_node)
            print(f"access {x} miss")
            self.cache[x] = new_node
            self.size += 1
            new_node.visited = False  # Insertion

    def show_cache(self):
        current = self.head
        print(f"cache access: {self.acc}")
        print(f"cache hit: {self.hit}")
        print(f"cache hit ratio: {self.hit/self.acc:.3f}")
        print(f"cache wrap: {self.wrap}")
        while current:
            print(f'{current.value} (Visited: {current.visited})', end=' -> ' if current.next else '\n')
            current = current.next

# Example usage
def history(N):
    for i in range(10, N, 2):
        for j in range(-10, -1):
            yield i+j
        yield i
        yield i+1

cache = SieveCache(10)
for item in history(1000):
    cache.access(item)
cache.show_cache()