1 | class DoubleLinkedList
|
2 | constructor: ->
|
3 | @headNode = @tailNode = null
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
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 |
|
35 | class 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]?
|