Eviction LRU

cache.ts

import LruPolicy from './lru';
import { IEvictionPolicy } from './types';

class Cache {
  private _evictionPolicy: IEvictionPolicy;

  constructor(evictionPolicy: IEvictionPolicy) {
    this._evictionPolicy = evictionPolicy;
  }

  set(key: string, value: unknown): void {
    return this._evictionPolicy.set(key, value);
  }

  get(key: string): unknown | null {
    return this._evictionPolicy.get(key);
  }

  delete(key: string): void {
    return this._evictionPolicy.delete(key);
  }

  update(key: string, value: unknown): void {
    return this._evictionPolicy.update(key, value);
  }
}

export default Cache;

lru.ts

import { IEvictionPolicy } from './types';

class DoublyLinkedList {
  _key: string;
  _prev: DoublyLinkedList | null;
  _next: DoublyLinkedList | null;

  constructor(
    key: string,
    prev: DoublyLinkedList | null,
    next: DoublyLinkedList | null
  ) {
    this._key = key;
    this._prev = prev;
    this._next = next;
  }
}

class LruPolicy implements IEvictionPolicy {
  _size: number;
  private _map: Map<string, unknown>;
  private _head: DoublyLinkedList | null;

  constructor(size: number) {
    this._size = size;
    this._map = new Map();
    this._head = null;
  }

  private deleteNode(node: DoublyLinkedList) {
    if (node._prev) {
      node._prev._next = null;
    }
    node._prev = null;
    node._next = null;
    this._map.delete(node._key);
  }

  private deleteEnd() {
    if (this._head === null) {
      return;
    }

    if (this._map.size > this._size) {
      let node = this._head;
      while (node._next !== null) {
        node = node._next;
      }

      this.deleteNode(node);
    }
  }

  private pushToFront(node: DoublyLinkedList) {
    if (node._prev) {
      node._prev._next = node._next;
    }
    if (node._next) {
      node._next._prev = node._prev;
    }
    node._prev = null;
    node._next = this._head;
    if (this._head) {
      this._head._prev = node;
    }
    this._head = node;
  }

  private findNode(key: string): DoublyLinkedList | null {
    let node = this._head;
    while (node !== null && node._key !== key) {
      node = node._next;
    }
    return node;
  }

  set(key: string, value: unknown): void {
    if (this._map.has(key)) {
      this.update(key, value);
      return;
    }

    this._map.set(key, value);
    const newNode = new DoublyLinkedList(key, null, null);
    this.pushToFront(newNode);
    this.deleteEnd();
  }

  get(key: string): unknown | null {
    if (this._map.has(key)) {
      const node = this.findNode(key);
      if (node === null) {
        throw new Error(`${key} doesn't exist with get()`);
      }

      this.pushToFront(node);
      return this._map.get(key);
    }

    return null;
  }

  delete(key: string): void {
    if (!this._map.has(key)) {
      throw new Error(`${key} doesn't exist`);
    }

    this._map.delete(key);
    const node = this.findNode(key);
    if (node === null) {
      throw new Error(`${key} doesn't exist with delete()`);
    }
    this.deleteNode(node);
  }

  update(key: string, value: unknown): void {
    if (!this._map.has(key)) {
      throw new Error(`${key} doesn't exist`);
    }

    this._map.set(key, value);
    const node = this.findNode(key);
    if (node === null) {
      throw new Error(`${key} doesn't exist with update()`);
    }
    this.pushToFront(node);
  }
}

export default LruPolicy;

script.ts

import LruPolicy from './lru';
import { IEvictionPolicy } from './types';
import Cache from './cache';

function main() {
  const evict: IEvictionPolicy = new LruPolicy(3);

  const cache = new Cache(evict);
  cache.set('key_1', 'value_1');
  cache.set('key_2', 'value_2');
  cache.update('key_1', 'new_value_1');
  cache.set('key_3', 'value_3');
  cache.set('key_4', 'value_4');

  console.log(cache.get('key_1'));
  console.log(cache.get('key_2'));
}

main();

types.ts

export interface IEvictionPolicy {
  _size: number;
  set(key: string, value: unknown): void;
  get(key: string): unknown | null;
  delete(key: string): void;
  update(key: string, value: unknown): void;
}