LRU Cache

lru_cache.tests.ts

import { DoublyLinkedList, ListNode, LRUCache } from '../lru_cache';

describe('DoublyLinkedList', () => {
  test('keys', () => {
    const dll = new DoublyLinkedList<string, number>();

    const head: ListNode<string, number> = {
      key: 'one',
      value: 0,
      prev: undefined,
      next: undefined,
    };
    const prev: ListNode<string, number> = {
      key: 'two',
      value: 0,
      prev: undefined,
      next: head,
    };
    head.prev = prev;

    dll.head = head;
    expect(dll.keys()).toEqual(['one', 'two']);
  });

  test('prepend', () => {
    const dll = new DoublyLinkedList<string, string>();
    dll.prepend('one', 'value');

    expect(dll.keys()).toEqual(['one']);
    expect(dll.head).toBe(dll.tail);

    dll.prepend('two', 'value');
    expect(dll.keys()).toEqual(['two', 'one']);
  });

  test('append', () => {
    const dll = new DoublyLinkedList<string, string>();
    dll.append('one', 'value');

    expect(dll.keys()).toEqual(['one']);
    expect(dll.head).toBe(dll.tail);

    dll.append('two', 'value');
    expect(dll.keys()).toEqual(['one', 'two']);
  });

  test('remove', () => {
    const dll = new DoublyLinkedList<string, string>();
    dll.append('one', 'value'); 
    dll.append('two', 'value'); 
    dll.append('three', 'value'); 
    dll.append('four', 'value');

    let removed = dll.remove('not-in-list');
    expect(removed).toBeUndefined();
    
    // item with next + prev
    removed = dll.remove('two');
    expect(removed).not.toBeUndefined();
    expect(removed!.key).toBe('two');
    expect(removed!.value).toBe('value');
    expect(dll.keys()).toEqual(['one', 'three', 'four']);

    // item with only prev
    removed = dll.remove('one');
    expect(removed).not.toBeUndefined();
    expect(removed!.key).toBe('one');
    expect(removed!.value).toBe('value');
    expect(dll.keys()).toEqual(['three', 'four']);

    // item with only next
    removed = dll.remove('four');
    expect(removed).not.toBeUndefined();
    expect(removed!.key).toBe('four');
    expect(removed!.value).toBe('value');
    expect(dll.keys()).toEqual(['three']);

    // item with no prev or next
    removed = dll.remove('three');
    expect(removed).not.toBeUndefined();
    expect(removed!.key).toBe('three');
    expect(removed!.value).toBe('value');
    expect(dll.keys()).toEqual([]);
  });
});

describe('LRUCache', () => {
  test('size = 1', () => {
    const cache = new LRUCache<string, number>(1);
    expect(cache.get('one')).toBeUndefined();
    
    cache.set('one', 1);
    expect(cache.get('one')).toBe(1);

    cache.set('two', 2);
    expect(cache.get('one')).toBeUndefined();
    expect(cache.get('two')).toBe(2);
  });

  test('size = 2', () => {
    const cache = new LRUCache<string, number>(2);

    cache.set('one', 1);
    cache.set('two', 2);
    cache.set('three', 3);
    
    expect(cache.get('one')).toBeUndefined();
    expect(cache.get('two')).toBe(2);
    expect(cache.get('three')).toBe(3);
  });
});

lru_cache.ts

import { Preconditions } from 'base/preconditions';

export type ListNode<K, V> = {
  next: ListNode<K, V> | undefined;
  prev: ListNode<K, V> | undefined;
  key: K;
  value: V;
};

export class DoublyLinkedList<K, V> {
  head: ListNode<K, V> | undefined;
  tail: ListNode<K, V> | undefined;
  size = 0;

  prepend(key: K, value: V) {
    const currentHead = this.head;
    const node = { key, value, prev: currentHead, next: undefined };

    if (currentHead == null && this.tail == null) { // first insert
      this.head = this.tail = node;
    } else {
      Preconditions.checkExists(currentHead).next = node;
      this.head = node;
    }
    this.size++;
  }

  append(key: K, value: V) {
    const currentTail = this.tail;
    const node = { key, value, prev: undefined, next: currentTail };

    if (this.head == null && currentTail == null) { // first insert
      this.head = this.tail = node;
    } else {
      Preconditions.checkExists(currentTail).prev = node;
      this.tail = node;
    }
    this.size++;
  }

  remove(key: K): ListNode<K, V> | undefined {
    const matchingNode = this.find(key);
    if (matchingNode == null) {
      return undefined;
    }

    if (matchingNode.next == null) {
      if (matchingNode.prev == null) { // no next, no prev
        this.head = this.tail = undefined;
      } else { // no next, has prev
        this.head = matchingNode.prev;
        this.head.next = undefined;
      }
    } else {
      if (matchingNode.prev == null) { // has next, no prev
        matchingNode.next.prev = undefined;
      } else { // has prev & next
        matchingNode.next.prev = matchingNode.prev;
        matchingNode.prev.next = matchingNode.next;
      }
    }

    matchingNode.next = undefined;
    matchingNode.prev = undefined;

    return matchingNode;
  }

  find(key: K): ListNode<K, V> | undefined {
    let currentNode = this.head;
    while (currentNode != null && currentNode.key !== key) {
      currentNode = currentNode.prev;
    }

    return currentNode;
  }

  keys(): K[] {
    const keys: K[] = [];
    let currentNode = this.head;
    while (currentNode != null) {
      keys.push(currentNode.key);
      currentNode = currentNode.prev;
    }
    return keys;
  }
}

export class LRUCache<K, V> {
  private queue: DoublyLinkedList<K, V> = new DoublyLinkedList();

  private map: Map<K, V> = new Map();

  constructor(
      private limit: number,
  ) {}

  get(key: K): V | undefined {
    if (this.map.has(key)) {
      const value = Preconditions.checkExists(this.map.get(key));
      const node = Preconditions.checkExists(this.queue.remove(key));
      this.queue.prepend(node.key, node.value);
      return value;
    }
  }

  set(key: K, value: V) {
    this.map.set(key, value);
    this.queue.prepend(key, value);
    if (this.queue.size > this.limit) {
      const tail = Preconditions.checkExists(this.queue.tail);
      this.queue.remove(tail.key);
      this.map.delete(tail.key);
    }
  }
}