Added insert_after, insert_before, insert_first and insert_last
[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 insert_after(self, refkey, key, value):
126         self._insert_after_or_before(refkey, key, value, True)
127
128     def insert_before(self, refkey, key, value):
129         self._insert_after_or_before(refkey, key, value, False)
130
131     def insert_first(self, key, value):
132         self[key] = value
133
134     def insert_last(self, key, value):
135         if key in self._map:
136             node = self._map[key][0]
137             node.unlink()
138         else:
139             node = _KeyListNode(key)
140         self._map[key] = (node, value)
141         node.insert_before(self._keylist_tail)
142
143     def items(self):
144         return list(self.iteritems())
145
146     def iteritems(self):
147         node = self._keylist_head.next
148         while node is not self._keylist_tail:
149             yield (node.key, self._map[node.key][1])
150             node = node.next
151
152     def iterkeys(self):
153         node = self._keylist_head.next
154         while node is not self._keylist_tail:
155             yield node.key
156             node = node.next
157
158     def itervalues(self):
159         node = self._keylist_head.next
160         while node is not self._keylist_tail:
161             yield self._map[node.key][1]
162             node = node.next
163
164     def keys(self):
165         return list(self.iterkeys())
166
167     def pop(self, key, default=None):
168         if key in self._map:
169             value = self[key]
170             del self[key]
171             return value
172         else:
173             if default is None:
174                 raise KeyError(key)
175             else:
176                 return default
177
178     def popitem(self):
179         if len(self) == 0:
180             raise KeyError
181         else:
182             key = self._keylist_head.next.key
183             value = self.pop(key)
184             return (key, value)
185
186     def reviteritems(self):
187         node = self._keylist_tail.prev
188         while node is not self._keylist_head:
189             yield (node.key, self._map[node.key][1])
190             node = node.prev
191
192     def reviterkeys(self):
193         node = self._keylist_tail.prev
194         while node is not self._keylist_head:
195             yield node.key
196             node = node.prev
197
198     def revitervalues(self):
199         node = self._keylist_tail.prev
200         while node is not self._keylist_head:
201             yield self._map[node.key][1]
202             node = node.prev
203
204     def setdefault(self, key, value=None):
205         if key in self._map:
206             return self[key]
207         else:
208             self[key] = value
209             return value
210
211     def update(self, items):
212         for key, value in items:
213             self[key] = value
214
215     def values(self):
216         return list(self.itervalues())
217
218     def _insert_after_or_before(self, refkey, key, value, after):
219         refnode = self._map[refkey][0]
220         if refkey == key:
221             self._map[refkey] = (refnode, value)
222         else:
223             if key in self._map:
224                 del self[key]
225             node = _KeyListNode(key)
226             self._map[key] = (node, value)
227             if after:
228                 node.insert_after(refnode)
229             else:
230                 node.insert_before(refnode)