1var assert = require('assert');
2
3class Cache {
4  constructor(capacity) {
5    this.count = 0;
6    this.capacity = capacity;
7    this.cache = {};
8    this.head = new DLinkedNode();
9    this.head.pre = null;
10    this.tail = new DLinkedNode();
11    this.tail.next = null;
12    this.head.next = this.tail;
13    this.tail.pre = this.head;
14  }
15
16  get(key) {
17    const node = this.cache[key];
18    if (!node) {
19      return -1;
20    }
21    this.moveToHead(node);
22    return node.val;
23  }
24
25  put(key, value) {
26    const node = this.cache[key];
27    if (!node) {
28      const newNode = new DLinkedNode(key, value, null, null);
29      this.cache[key] = newNode;
30      this.addNode(newNode);
31      this.count++;
32      if (this.count > this.capacity) {
33        const tail = this.popTail();
34        delete this.cache[tail.key];
35        this.count--;
36      }
37    } else {
38      node.val = value;
39      this.moveToHead(node);
40    }
41  }
42
43  addNode(node) {
44    node.pre = this.head;
45    node.next = this.head.next;
46    this.head.next.pre = node;
47    this.head.next = node;
48  }
49
50  removeNode(node) {
51    const pre = node.pre;
52    const next = node.next;
53    pre.next = next;
54    next.pre = pre;
55  }
56
57  moveToHead(node) {
58    this.removeNode(node);
59    this.addNode(node);
60  }
61
62  popTail(node) {
63    const pre = this.tail.pre;
64    this.removeNode(pre);
65    return pre;
66  }
67}
68
69class DLinkedNode {
70  constructor(key, val, pre, next) {
71    this.key = key;
72    this.val = val;
73    this.pre = pre;
74    this.next = next;
75  }
76}
77
78try {
79  var cache = new Cache(3);
80  cache.put(1, 1);
81  cache.put(2, 4);
82  cache.put(3, 9);
83  assert.equal(cache.get(1), 1);
84
85  console.log(
86    'PASSED: Initialize a cache of size 3, and run `cache.put(1, 1); cache.put(2, 4); cache.put(3, 9);`. `cache.get(1)` should return 1'
87  );
88} catch (err) {
89  console.log(err);
90}
91
92try {
93  cache.put(4, 16);
94  assert.equal(cache.get(2), -1);
95
96  console.log('PASSED: ' + '`cache.put(4, 16);` should evict key `2`');
97} catch (err) {
98  console.log(err);
99}