1 from __future__ import division
5 from twisted.internet import reactor
8 def __init__(self, contents, prev=None, next=None):
9 self.contents, self.prev, self.next = contents, prev, next
11 def insert_before(self, contents):
12 self.prev.next = self.prev = node = Node(contents, self.prev, self)
15 def insert_after(self, contents):
16 self.next.prev = self.next = node = Node(contents, self, self.next)
20 def connect(prev, next):
21 if prev.next is not None or next.prev is not None:
22 raise ValueError('node already connected')
23 prev.next, next.prev = next, prev
25 def replace(self, contents):
26 self.contents = contents
29 if self.prev.next is None or self.next.prev is None:
30 raise ValueError('node not connected')
31 self.prev.next, self.next.prev = self.next, self.prev
32 self.next = self.prev = None
35 class LinkedList(object):
36 def __init__(self, iterable=[]):
37 self.start, self.end = Node(None), Node(None)
38 Node.connect(self.start, self.end)
44 return 'LinkedList(%r)' % (list(self),)
47 return sum(1 for x in self)
51 while cur is not self.end:
54 yield cur2 # in case cur is deleted, but items inserted after are ignored
56 def __reversed__(self):
58 while cur is not self.start:
63 def __getitem__(self, index):
64 # odd one out - probably should return Node instance instead of its contents
67 for i in xrange(-index):
70 raise IndexError('index out of range')
73 for i in xrange(index + 1):
76 raise IndexError('index out of range')
79 def appendleft(self, item):
80 return self.start.insert_after(item)
82 def append(self, item):
83 return self.end.insert_before(item)
86 node = self.start.next
88 raise IndexError('popleft from empty')
94 if node is self.start:
95 raise IndexError('pop from empty')
100 class ExpiringDict(object):
101 def __init__(self, expiry_time=100, get_touches=True):
102 self.expiry_time = expiry_time
103 self.get_touches = get_touches
105 self.expiry_deque = LinkedList()
106 self.d = dict() # key -> node, value
109 reactor.callLater(0, self.expire)
110 return 'ExpiringDict' + repr(self.__dict__)
113 reactor.callLater(0, self.expire)
117 def touch(self, key, value=_nothing):
118 'Updates expiry node, optionally replacing value, returning new value'
119 if value is self._nothing or key in self.d:
120 node, old_value = self.d[key]
123 new_value = old_value if value is self._nothing else value
124 self.d[key] = self.expiry_deque.append((time.time(), key)), new_value
128 for node in self.expiry_deque:
129 timestamp, key = node.contents
130 if timestamp + self.expiry_time > time.time():
135 def __contains__(self, key):
138 def __getitem__(self, key):
140 value = self.touch(key)
142 node, value = self.d[key]
143 reactor.callLater(0, self.expire)
146 def __setitem__(self, key, value):
147 self.touch(key, value)
148 reactor.callLater(0, self.expire)
150 def __delitem__(self, key):
151 node, value = self.d.pop(key)
153 reactor.callLater(0, self.expire)
155 def get(self, key, default_value=None):
160 reactor.callLater(0, self.expire)
163 def setdefault(self, key, default_value):
167 self[key] = default_value
174 return [value for node, value in self.d.itervalues()]
176 def itervalues(self):
177 for node, value in self.d.itervalues():
180 if __name__ == '__main__':