LRUCache.js

// @flow strict

class Node<K> {
  key: K
  next: Node<K> | null
  prev: Node<K> | null

  constructor(key: K) {
    this.key = key
  }
}

class LRUCache<K, V> {
  max: number
  head: Node<K> | null
  tail: Node<K> | null
  values: Map<K, V> = new Map()
  nodes: Map<K, Node<K>> = new Map()
  length: number = 0

  constructor(max: number = 1000) {
    this.max = max
  }

  touch(key: K) {
    const node = this.nodes.get(key)

    if (node != null && node !== this.head) {
      const prevNode = node.prev
      const nextNode = node.next

      if (prevNode != null && nextNode != null) {
        prevNode.next = nextNode
        nextNode.prev = prevNode
      }

      if (this.head != null) {
        this.head.prev = node
        node.next = this.head
      }

      this.head = node
    }
  }

  set(key: K, value: V) {
    if (this.values.has(key)) {
      this.touch(key)
    } else {
      const head = new Node(key)

      if (this.head == null && this.tail == null) {
        this.head = head
        this.tail = head

        this.head.next = this.tail
        this.tail.prev = this.head
      } else {
        if (this.head != null) {
          this.head.prev = head
          head.next = this.head
        }

        this.head = head
      }

      this.nodes.set(key, head)

      this.length += 1

      if (this.length > this.max) {
        const tail = this.tail

        if (tail != null) {
          if (tail.prev != null) {
            this.tail = tail.prev
          }

          this.length -= 1

          this.values.delete(tail.key)
          this.nodes.delete(tail.key)
        }
      }
    }

    this.values.set(key, value)
  }

  get(key: K): V | void {
    if (this.values.has(key)) {
      this.touch(key)

      return this.values.get(key)
    }

    return undefined
  }
}

export default LRUCache
export { Node }