lru_cache.py

gistfile1.txt

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

class LRUCache:
    def __init__(self, k):
        self.k = k
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.storage = {}

    def get(self, key):
        if key in self.storage:
            node = self.storage[key]
            # Move the node to beginning
            self._move_node_to_front(node)
            return node.value
        return None  # Key not found 
   
    def _remove_the_node(self, node):
        node.next.prev = node.prev 
        node.prev.next = node.next
    
    def _add_node_to_front(self, node):
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node 
        node.prev = self.head 

    def _move_node_to_front(self, node):
        # Remove the node from current position 
        self._remove_the_node(node)
        self._add_node_to_front(node)

    def set(self, key, value):
        if key in self.storage:
            # Update value
            node = self.storage[key]
            node.value = value 
            # Move the node to the front
            self._move_node_to_front(node)
        else:
            new_node = Node(key, value)
            # Insert node at the beginning
            self._add_node_to_front(new_node)
            self.storage[key] = new_node
            if len(self.storage) > self.k:  # Fixed: was using 'k' instead of 'self.k'
                # Remove the tail node
                tail_node = self.tail.prev
                self._remove_the_node(tail_node)
                # Delete the element from self.storage using the correct key
                del self.storage[tail_node.key]  # Fixed: was using 'key' instead of 'tail_node.key'

    def display_cache(self):
        current = self.head.next
        cache_order = []
        while current != self.tail:
            cache_order.append(f"({current.key}: {current.value})")
            current = current.next
        return " -> ".join(cache_order)

def main():
    print("Testing LRU Cache Implementation")
    print("=" * 40)
    
    # Test 1: Basic functionality
    print("\nTest 1: Basic Operations")
    cache = LRUCache(3)
    
    cache.set(1, "one")
    cache.set(2, "two")
    cache.set(3, "three")
    print(f"After adding (1,one), (2,two), (3,three): {cache.display_cache()}")
    
    # Test 2: Get operation (should move to front)
    print(f"\nGet key 1: {cache.get(1)}")
    print(f"Cache after get(1): {cache.display_cache()}")
    
    # Test 3: LRU eviction
    print(f"\nAdding (4,four) - should evict least recently used")
    cache.set(4, "four")
    print(f"Cache after adding (4,four): {cache.display_cache()}")
    print(f"Try to get evicted key 2: {cache.get(2)}")
    
    # Test 4: Update existing key
    print(f"\nUpdating key 1 to 'ONE'")
    cache.set(1, "ONE")
    print(f"Cache after update: {cache.display_cache()}")
    
    # Test 5: Edge cases
    print(f"\nEdge case: Get non-existent key: {cache.get(99)}")
    
    # Test 6: Capacity of 1
    print(f"\nTest with capacity 1:")
    small_cache = LRUCache(1)
    small_cache.set(1, "first")
    print(f"After adding (1,first): {small_cache.display_cache()}")
    small_cache.set(2, "second")
    print(f"After adding (2,second): {small_cache.display_cache()}")
    print(f"Try to get evicted key 1: {small_cache.get(1)}")
    
    print("\n" + "=" * 40)
    print("All tests completed!")

if __name__ == "__main__":
    main()