bd028579
 易尊强
2/28
|
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
|
var Entry = (function () {
function Entry(val) {
this.value = val;
}
return Entry;
}());
export { Entry };
var LinkedList = (function () {
function LinkedList() {
this._len = 0;
}
LinkedList.prototype.insert = function (val) {
var entry = new Entry(val);
this.insertEntry(entry);
return entry;
};
LinkedList.prototype.insertEntry = function (entry) {
if (!this.head) {
this.head = this.tail = entry;
}
else {
this.tail.next = entry;
entry.prev = this.tail;
entry.next = null;
this.tail = entry;
}
this._len++;
};
LinkedList.prototype.remove = function (entry) {
var prev = entry.prev;
var next = entry.next;
if (prev) {
prev.next = next;
}
else {
this.head = next;
}
if (next) {
next.prev = prev;
}
else {
this.tail = prev;
}
entry.next = entry.prev = null;
this._len--;
};
LinkedList.prototype.len = function () {
return this._len;
};
LinkedList.prototype.clear = function () {
this.head = this.tail = null;
this._len = 0;
};
return LinkedList;
}());
export { LinkedList };
var LRU = (function () {
function LRU(maxSize) {
this._list = new LinkedList();
this._maxSize = 10;
this._map = {};
this._maxSize = maxSize;
}
LRU.prototype.put = function (key, value) {
var list = this._list;
var map = this._map;
var removed = null;
if (map[key] == null) {
var len = list.len();
var entry = this._lastRemovedEntry;
if (len >= this._maxSize && len > 0) {
var leastUsedEntry = list.head;
list.remove(leastUsedEntry);
delete map[leastUsedEntry.key];
removed = leastUsedEntry.value;
this._lastRemovedEntry = leastUsedEntry;
}
if (entry) {
entry.value = value;
}
else {
entry = new Entry(value);
}
entry.key = key;
list.insertEntry(entry);
map[key] = entry;
}
return removed;
};
LRU.prototype.get = function (key) {
var entry = this._map[key];
var list = this._list;
if (entry != null) {
if (entry !== list.tail) {
list.remove(entry);
list.insertEntry(entry);
}
return entry.value;
}
};
LRU.prototype.clear = function () {
this._list.clear();
this._map = {};
};
LRU.prototype.len = function () {
return this._list.len();
};
return LRU;
}());
export default LRU;
|
