Make the least-recently-used cache O(1)

// Implement here: Explain why the full predicate is captured before insertion.

class LRUNode;
  int key;
  LRUNode prev;
  LRUNode next;

  function new(int key);
    this.key = key;
  endfunction
endclass

class LRUCacheO1;
  int capacity;
  int value_by_key[int];
  LRUNode node_by_key[int];
  LRUNode head;
  LRUNode tail;

  function new(int capacity);
    this.capacity = (capacity > 0) ? capacity : 0;
  endfunction

  function void unlink(LRUNode node);
    // Implement here: detach this node while preserving head and tail.
  endfunction

  function void append_mru(LRUNode node);
    // Implement here: append this detached node as MRU.
  endfunction

  function void touch(int key);
    LRUNode node;
    // Implement here: move this existing key to MRU.
  endfunction

  function bit get(int key, output int value);
    // Implement here: report a hit and return its value while updating recency.
  endfunction

  function void put(int key, int value);
    LRUNode node;
    int evict_key;
    bit full_before_insert;
    // Implement here: insert or update and enforce capacity.
  endfunction
endclass