blob: 333f66a4436ec436b714d6c6725f1d9900c25012 (
plain)
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
|
module.exports = function(size) {
return new LruCache(size)
}
function LruCache(size) {
this.capacity = size | 0
this.map = Object.create(null)
this.list = new DoublyLinkedList()
}
LruCache.prototype.get = function(key) {
var node = this.map[key]
if (node == null) return undefined
this.used(node)
return node.val
}
LruCache.prototype.set = function(key, val) {
var node = this.map[key]
if (node != null) {
node.val = val
} else {
if (!this.capacity) this.prune()
if (!this.capacity) return false
node = new DoublyLinkedNode(key, val)
this.map[key] = node
this.capacity--
}
this.used(node)
return true
}
LruCache.prototype.used = function(node) {
this.list.moveToFront(node)
}
LruCache.prototype.prune = function() {
var node = this.list.pop()
if (node != null) {
delete this.map[node.key]
this.capacity++
}
}
function DoublyLinkedList() {
this.firstNode = null
this.lastNode = null
}
DoublyLinkedList.prototype.moveToFront = function(node) {
if (this.firstNode == node) return
this.remove(node)
if (this.firstNode == null) {
this.firstNode = node
this.lastNode = node
node.prev = null
node.next = null
} else {
node.prev = null
node.next = this.firstNode
node.next.prev = node
this.firstNode = node
}
}
DoublyLinkedList.prototype.pop = function() {
var lastNode = this.lastNode
if (lastNode != null) {
this.remove(lastNode)
}
return lastNode
}
DoublyLinkedList.prototype.remove = function(node) {
if (this.firstNode == node) {
this.firstNode = node.next
} else if (node.prev != null) {
node.prev.next = node.next
}
if (this.lastNode == node) {
this.lastNode = node.prev
} else if (node.next != null) {
node.next.prev = node.prev
}
}
function DoublyLinkedNode(key, val) {
this.key = key
this.val = val
this.prev = null
this.next = null
}
|
