code.js

// Import visualization library
const {
  Array1DTracer,
  LogTracer,
  Layout,
  Tracer,
} = require("algorithm-visualizer");

/**
 * Node class for doubly-linked list
 */
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

/**
 * LRU (Least Recently Used) Cache Implementation
 *
 * This cache maintains a fixed capacity and automatically evicts
 * the least recently used item when capacity is exceeded.
 *
 * Time Complexity: O(1) for both get and put operations
 * Space Complexity: O(capacity)
 */
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.size = 0;
    this.head = null;
    this.map = new Map();
  }

  /**
   * Get value by key. Marks the key as recently used.
   * Returns -1 if key doesn't exist.
   */
  get(key) {
    if (!this.map.has(key)) return -1;
    this.moveToFront(key);
    return this.map.get(key).value;
  }

  /**
   * Insert or update a key-value pair.
   * If cache is full, evicts the least recently used item.
   */
  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.value = value;
      this.moveToFront(key);
      return;
    }

    const newNode = new Node(key, value);
    this.map.set(key, newNode);
    this.insertAtFront(newNode);

    if (this.size > this.capacity) {
      this.removeLast();
    }
  }

  /**
   * Get current cache state as array
   */
  getState() {
    const result = [];
    let current = this.head;

    while (current) {
      result.push({ key: current.key, value: current.value });
      current = current.next;
      if (current === this.head) break;
    }

    return result;
  }

  insertAtFront(node) {
    if (!this.head) {
      node.next = node;
      node.prev = node;
      this.head = node;
    } else {
      const last = this.head.prev;
      node.next = this.head;
      node.prev = last;
      last.next = node;
      this.head.prev = node;
      this.head = node;
    }
    this.size++;
  }

  removeLast() {
    if (!this.head) return;
    const last = this.head.prev;
    this.map.delete(last.key);
    this.size--;

    if (this.head === last) {
      this.head = null;
      return;
    }

    last.prev.next = this.head;
    this.head.prev = last.prev;
  }

  moveToFront(key) {
    const node = this.map.get(key);
    if (node === this.head) return;

    node.prev.next = node.next;
    node.next.prev = node.prev;

    const last = this.head.prev;
    node.next = this.head;
    node.prev = last;
    last.next = node;
    this.head.prev = node;
    this.head = node;
  }
}

// Visualization Setup
const logger = new LogTracer("Operation Log");
const cacheTracer = new Array1DTracer(
  "LRU Cache State (Most Recent → Least Recent)"
);

// Helper function to update visualization
function updateVisualization(cache, message) {
  const state = cache.getState();
  const keys = state.map((item) => `${item.key}:${item.value}`);

  if (keys.length > 0) {
    cacheTracer.set(keys);
    cacheTracer.patch(0); // Highlight most recently used
  }
  logger.println(message);
  Tracer.delay();
}

// Set up layout
Layout.setRoot(cacheTracer);
Tracer.delay();

// Demo: LRU Cache Operations
logger.println("=== LRU Cache Demonstration ===");
logger.println(`Creating cache with capacity 4`);
Tracer.delay();

const cache = new LRUCache(4);

// Operation 1: Insert items
logger.println("\n--- Inserting Items ---");
Tracer.delay();

cache.put(1, 100);
updateVisualization(cache, "PUT(1, 100): Added first item");

cache.put(2, 200);
updateVisualization(cache, "PUT(2, 200): Added second item");

cache.put(3, 300);
updateVisualization(cache, "PUT(3, 300): Added third item");

cache.put(4, 400);
updateVisualization(cache, "PUT(4, 400): Cache is now full");

// Operation 2: Access an item (makes it most recently used)
logger.println("\n--- Accessing Items ---");
Tracer.delay();

const value1 = cache.get(1);
updateVisualization(cache, `GET(1): Retrieved value ${value1}, moved to front`);

const value2 = cache.get(3);
updateVisualization(cache, `GET(3): Retrieved value ${value2}, moved to front`);

// Operation 3: Insert new item (will evict least recently used)
logger.println("\n--- Eviction Demonstration ---");
Tracer.delay();

cache.put(5, 500);
updateVisualization(cache, "PUT(5, 500): Added new item, evicted key 2 (LRU)");

// Try to access evicted item
const evicted = cache.get(2);
logger.println(`GET(2): Returns ${evicted} (not found - was evicted)`);
Tracer.delay();

// Operation 4: Update existing item
logger.println("\n--- Updating Items ---");
Tracer.delay();

cache.put(1, 150);
updateVisualization(
  cache,
  "PUT(1, 150): Updated value of key 1, moved to front"
);

// Operation 5: More operations to show LRU behavior
logger.println("\n--- Complex Access Pattern ---");
Tracer.delay();

cache.get(4);
updateVisualization(cache, "GET(4): Accessed key 4, moved to front");

cache.put(6, 600);
updateVisualization(cache, "PUT(6, 600): Added new item, evicted key 5 (LRU)");

cache.get(1);
updateVisualization(cache, "GET(1): Accessed key 1, moved to front");

cache.put(7, 700);
updateVisualization(cache, "PUT(7, 700): Added new item, evicted key 3 (LRU)");

// Final state
logger.println("\n--- Final Cache State ---");
Tracer.delay();
const finalState = cache.getState();
logger.println("Cache contents (Most Recent → Least Recent):");
finalState.forEach((item, index) => {
  logger.println(`  ${index + 1}. Key: ${item.key}, Value: ${item.value}`);
});
Tracer.delay();

logger.println("\n=== Demonstration Complete ===");
logger.println("\nKey Observations:");
logger.println("1. Most recently accessed items stay at the front");
logger.println("2. When cache is full, least recently used item is evicted");
logger.println("3. Both GET and PUT operations update recency");
logger.println("4. All operations run in O(1) time complexity");
Tracer.delay();