loading
open in
index.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class LRUnode {
  constructor (key, value) {
    this.key = key;
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class LRUcache {
  constructor (limit) {
    this.size = 0;
    this.limit = limit || 10;
    this.map = new Map();
    this.head = null;
    this.tail = null;
  }
  makeHead (node) {
    node.next = this.head; // demote current head
    node.prev = null;
    if(this.head !== null){ // is cache not empty
      this.head.prev = node;
    }
    this.head = node;
    if(this.tail === null){ // only when cache has one node are the head and tail the same node
      this.tail = node;
    }
    this.size++;
    this.map.set(node.key, node); // map for lookup
  }
  set (key, value) {
    const node = new LRUnode(key, value);
    if(this.map.get(key)){
      this.map.get(key).value = value;
      this.remove(node.key);
    } else {
      if(this.size >= this.limit){ // cull least recently used
        this.remove(this.tail.key);
      }
    }
    this.makeHead(node); // most recently used; promote to head
  }
  get (key) {
    if(this.map.get(key)){ 
      const value = this.map.get(key).value;
      const node = new LRUnode(key, value);
      this.remove(key);
      this.makeHead(node); // most recently used; promote to head
      return value;
    } else {
      console.log(`Key '${key}' does not exist`);
    }
  }
  remove (key) {
    const node = this.map.get(key);
    if(node.prev !== null){ // is not head
      node.prev.next = node.next;
    } else { // is head
      this.head = node.next; 
    }
    if(node.next !== null) { // is not tail
      node.next.prev = node.prev;
    } else { // is tail
      this.tail = this.tail.prev;
    }
    this.map.delete(key);
    this.size--;
  }
  toArray () {
    const json = [];
    let node = this.head;
    while(node) { // this.tail.next will allways be null
      json.push({key: node.key, value: node.value});
      node = node.next;
    }
    return json;
  }
}

const cache = new LRUcache(3);

cache.set('one', '1');
cache.set('two', '2');
cache.set('three', '3');
console.log(cache.toArray());
cache.set('four', '4');
console.log(cache.toArray());
cache.remove('two');
console.log(cache.tail);
node v10.15.2 linux/amd64