-
Notifications
You must be signed in to change notification settings - Fork 0
/
LRU_cache.js
125 lines (104 loc) · 2.85 KB
/
LRU_cache.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// /**
// @param {number} capacity
// */
// use a doubly linked list and hash map
// doubly linked list node key is key to hash map
// hashmap stores the node; ensures 0(1) access of any node
class Node {
constructor(key, val) {
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
};
};
var LRUCache = function (capacity) {
this.capacity = capacity;
this.length = 0;
this.myHash = {};
this.head = new Node('head',null);
this.tail = new Node('tail', null);
this.head.next = this.tail;
this.tail.prev = this.head;
};
LRUCache.prototype.moveFront = function(key){
// if already at front, return
if (key === this.head.next.key) return;
// movingNode = node moving to front
// prevFirst = previous first in line
let prevFirst = this.head.next;
let movingNode = this.myHash[key];
// cut out the moving node first
let movePrev = movingNode.prev;
let moveNext = movingNode.next;
movePrev.next = moveNext;
moveNext.prev = movePrev;
// insert moving at front
this.head.next = movingNode;
movingNode.prev = this.head;
movingNode.next = prevFirst;
prevFirst.prev = movingNode;
return;
};
LRUCache.prototype.deleteLast = function(){
let prevLast = this.tail.prev;
let newLast = prevLast.prev;
// cut prevLast
newLast.next = this.tail;
this.tail.prev = newLast;
prevLast.next = null;
prevLast.prev = null;
this.myHash[prevLast.key] = null;
return;
};
LRUCache.prototype.insertFront = function (newNode){
let prevFirst = this.head.next;
// cut previous first
this.head.next = newNode;
prevFirst.prev = newNode;
newNode.prev = this.head;
newNode.next = prevFirst;
return;
};
LRUCache.prototype.get = function (key) {
// get operation accesses the hash and returns hash[key]
// also need to move the node to be next to head
// use helper function moveFront
// if its already at front then return the val
// not at front, move to front function and return val
if (this.myHash[key]){
this.moveFront(key);
return this.myHash[key].val;
} else {
return -1;
};
};
LRUCache.prototype.put = function (key, value) {
// if key exists, move to front, rewrite value
// else, insert new key value pair at front
// also, check if length of the LRU cache is at limit
if(this.myHash[key]){
// move to front function then rewrite the value
this.moveFront(key);
this.myHash[key].val = value;
} else {
// insert new node at front
let newNode = new Node(key, value);
this.myHash[key] = newNode;
this.insertFront(newNode);
this.length++;
// check if max length reached and delete accordingly
if(this.length > this.capacity){
this.deleteLast();
this.length--;
}
};
return;
};
let cache = new LRUCache(2);
cache.put(2,1);
cache.put(2, 2);
console.log(cache.get(2));
cache.put(1, 1);
cache.put(4, 1);
cache.get(2);