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
|
class lastused: #Implementation of a length-limited O(1) LRU cache
class Node:
def __init__(self, prev, me):
self.prev = prev
self.me = me
self.next = None
def __init__(self, count, lst=[]):
self.count = max(count, 2)
self.d = {}
self.first = None
self.last = None
for key, value in lst:
self[key] = value
def __contains__(self, obj):
return obj in self.d
def __getitem__(self, obj):
return self.d[obj].me[1]
def __setitem__(self, obj, val):
if obj in self.d:
del self[obj]
nobj = self.Node(self.last, (obj, val))
if self.first is None:
self.first = nobj
if self.last:
self.last.next = nobj
self.last = nobj
self.d[obj] = nobj
if len(self.d) > self.count:
if self.first == self.last:
self.first = None
self.last = None
return
a = self.first
a.next.prev = None
self.first = a.next
a.next = None
del self.d[a.me[0]]
del a
def __delitem__(self, obj):
nobj = self.d[obj]
if nobj.prev:
nobj.prev.next = nobj.next
else:
self.first = nobj.next
if nobj.next:
nobj.next.prev = nobj.prev
else:
self.last = nobj.prev
del self.d[obj]
def __iter__(self):
cur = self.first
while cur != None:
cur2 = cur.next
yield cur.me[1]
cur = cur2
raise StopIteration
def iteritems(self):
cur = self.first
while cur != None:
cur2 = cur.next
yield cur.me
cur = cur2
raise StopIteration
def iterkeys(self):
return iter(self.d)
def itervalues(self):
for i,j in self.iteritems():
yield j
def keys(self):
return [i for i,j in self.iteritems()]
def values(self):
return [j for i,j in self.iteritems()]
def items(self):
return [i for i in self.iteritems()]
|
