3215a702a6813b2be4d04871576da3960666e477
[joel/kofoto.git] / src / packages / kofoto / insertionorderedmapping.py
1 """This module contains the InsertionOrderedMapping class."""
2
3 __all__ = ["InsertionOrderedMapping"]
4
5 class _KeyListNode:
6     def __init__(self, key=None):
7         self.key = key
8         self.prev = None
9         self.next = None
10
11     def insert_after(self, node):
12         assert self.prev is None
13         assert self.next is None
14         if node.next:
15             node.next.prev = self
16             self.next = node.next
17         self.prev = node
18         node.next = self
19
20     def insert_before(self, node):
21         assert self.prev is None
22         assert self.next is None
23         if node.prev:
24             node.prev.next = self
25             self.prev = node.prev
26         self.next = node
27         node.prev = self
28
29     def unlink(self):
30         if self.prev:
31             self.prev.next = self.next
32         if self.next:
33             self.next.prev = self.prev
34         self.prev = None
35         self.next = None
36
37 class InsertionOrderedMapping:
38     """A mapping datatype with keys sorted in insertion order.
39
40     The newest insertion appears first in the key list and the oldest
41     last.
42     """
43
44     def __init__(self, items=None):
45         self._map = {} # key --> (keylistnode, value)
46         self._keylist_head = _KeyListNode()
47         self._keylist_tail = _KeyListNode()
48         self._keylist_tail.insert_after(self._keylist_head)
49         if items is not None:
50             self.update(items)
51
52     def __cmp__(self, other):
53         snode = self._keylist_head.next
54         onode = other._keylist_head.next
55         while True:
56             if snode is self._keylist_tail:
57                 if onode is other._keylist_tail:
58                     return 0
59                 else:
60                     return -1
61             elif onode is other._keylist_tail:
62                 return 1
63             elif snode.key != onode.key:
64                 return cmp(snode.key, onode.key)
65             else:
66                 sval = self._map[snode.key][1]
67                 oval = other._map[onode.key][1]
68                 if sval != oval:
69                     return cmp(sval, oval)
70             snode = snode.next
71             onode = onode.next
72
73     def __contains__(self, key):
74         return key in self._map
75
76     def __delitem__(self, key):
77         self._map[key][0].unlink()
78         del self._map[key]
79
80     def __getitem__(self, key):
81         return self._map[key][1]
82
83     def __iter__(self):
84         return self.iterkeys()
85
86     def __len__(self):
87         return len(self._map)
88
89     def __repr__(self):
90         return "InsertionOrderedMapping(%r)" % self.items()
91
92     def __setitem__(self, key, value):
93         if key in self._map:
94             node = self._map[key][0]
95             node.unlink()
96         else:
97             node = _KeyListNode(key)
98         self._map[key] = (node, value)
99         node.insert_after(self._keylist_head)
100
101     def clear(self):
102         self._map.clear()
103
104         # Break reference cycles:
105         node = self._keylist_head
106         while node is not None:
107             node.prev = None
108             node = node.next
109         self._keylist_head.unlink()
110         self._keylist_tail.unlink()
111         self._keylist_tail.insert_after(self._keylist_head)
112
113     def copy(self):
114         return InsertionOrderedMapping(self.reviteritems())
115
116     def get(self, key, default=None):
117         if key in self._map:
118             return self._map[key][1]
119         else:
120             return default
121
122     def has_key(self, key):
123         return self._map.has_key(key)
124
125     def items(self):
126         return list(self.iteritems())
127
128     def iteritems(self):
129         node = self._keylist_head.next
130         while node is not self._keylist_tail:
131             yield (node.key, self._map[node.key][1])
132             node = node.next
133
134     def iterkeys(self):
135         node = self._keylist_head.next
136         while node is not self._keylist_tail:
137             yield node.key
138             node = node.next
139
140     def itervalues(self):
141         node = self._keylist_head.next
142         while node is not self._keylist_tail:
143             yield self._map[node.key][1]
144             node = node.next
145
146     def keys(self):
147         return list(self.iterkeys())
148
149     def pop(self, key, default=None):
150         if key in self._map:
151             value = self[key]
152             del self[key]
153             return value
154         else:
155             if default is None:
156                 raise KeyError(key)
157             else:
158                 return default
159
160     def popitem(self):
161         if len(self) == 0:
162             raise KeyError
163         else:
164             key = self._keylist_head.next.key
165             value = self.pop(key)
166             return (key, value)
167
168     def reviteritems(self):
169         node = self._keylist_tail.prev
170         while node is not self._keylist_head:
171             yield (node.key, self._map[node.key][1])
172             node = node.prev
173
174     def reviterkeys(self):
175         node = self._keylist_tail.prev
176         while node is not self._keylist_head:
177             yield node.key
178             node = node.prev
179
180     def revitervalues(self):
181         node = self._keylist_tail.prev
182         while node is not self._keylist_head:
183             yield self._map[node.key][1]
184             node = node.prev
185
186     def setdefault(self, key, value=None):
187         if key in self._map:
188             return self[key]
189         else:
190             self[key] = value
191             return value
192
193     def update(self, items):
194         for key, value in items:
195             self[key] = value
196
197     def values(self):
198         return list(self.itervalues())