UNPKG

2.32 kBtext/coffeescriptView Raw
1class DoubleLinkedList
2 constructor: ->
3 @headNode = @tailNode = null
4
5 # removes the last element. Since
6 # we move used elements to head, the last
7 # element is *probably* a relatively
8 # unused one.
9 remove: (node) ->
10 if node.pre
11 node.pre.next = node.next
12 else
13 @headNode = node.next
14
15 if node.next
16 node.next.pre = node.pre
17 else
18 @tailNode = node.pre
19
20 insertBeginning: (node) ->
21 if @headNode
22 node.next = @headNode
23 @headNode.pre = node
24 @headNode = node
25 else
26 @headNode = @tailNode = node
27
28 moveToHead: (node) ->
29 @remove node
30 @insertBeginning node
31
32 clear: ->
33 @headNode = @tailNode = null
34
35class LRUCache
36 constructor: (@capacity = 10, @maxAge = 60000) ->
37 @_linkList = new DoubleLinkedList()
38 @reset()
39 @hitCount = @missCount = 0
40
41 resetHitMissCount: ->
42 @hitCount = @missCount = 0
43
44 keys: ->
45 return Object.keys @_hash
46
47 values: ->
48 values = @keys().map (key) =>
49 @get key
50 return values.filter (v) -> v isnt undefined
51
52 remove: (key) ->
53 if @_hash[key]?
54 node = @_hash[key]
55 @_linkList.remove node
56 delete @_hash[key]
57 if node.data.onDispose then node.data.onDispose.call this, node.data.key, node.data.value
58 @size--
59
60 reset: ->
61 @_hash = {}
62 @size = 0
63 @resetHitMissCount()
64 @_linkList.clear()
65
66 set: (key, value, onDispose) ->
67 node = @_hash[key]
68 if node
69 node.data.value = value
70 node.data.onDispose = onDispose
71 @_refreshNode node
72 else
73 if @size is @capacity then @remove @_linkList.tailNode.data.key
74
75 createNode = (data, pre, next) -> {data, pre, next}
76
77 node = createNode {key, value, onDispose}
78 node.data.lastVisitTime = Date.now()
79 @_linkList.insertBeginning node
80 @_hash[key] = node
81 @size++
82 return
83
84 get: (key) ->
85 node = @_hash[key]
86 if !node
87 @missCount++
88 return undefined
89 if @_isExpiredNode node
90 @remove key
91 @missCount++
92 return undefined
93 @_refreshNode node
94 @hitCount++
95 return node.data.value
96
97 _refreshNode: (node) ->
98 node.data.lastVisitTime = Date.now()
99 @_linkList.moveToHead node
100
101 _isExpiredNode: (node) ->
102 return Date.now() - node.data.lastVisitTime > @maxAge
103
104 has: (key) -> return @_hash[key]?