Some changes to be more compatible with Python 3 in the future
[joel/kofoto.git] / src / packages / kofoto / iodict.py
1 # Copyright (c) 2006 Joel Rosdahl
2 # All rights reserved.
3 #
4 # Redistribution and use in source and binary forms, with or without
5 # modification, are permitted provided that the following conditions
6 # are met:
7 #
8 #     * Redistributions of source code must retain the above copyright
9 #       notice, this list of conditions and the following disclaimer.
10 #     * Redistributions in binary form must reproduce the above
11 #       copyright notice, this list of conditions and the following
12 #       disclaimer in the documentation and/or other materials
13 #       provided with the distribution.
14 #     * Neither the name of the copyright holders nor the names of
15 #       contributors may be used to endorse or promote products
16 #       derived from this software without specific prior written
17 #       permission.
18 #
19 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22 # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23 # COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
24 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
25 # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
26 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
27 # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
29 # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 # POSSIBILITY OF SUCH DAMAGE.
31
32 """iodict -- An insertion-ordered dictionary.
33
34 This module contains a class called InsertionOrderedDict, which
35 implements a dictionary that keeping the keys in insertion order.
36 """
37
38
39 __all__ = ["InsertionOrderedDict"]
40
41
42 class InsertionOrderedDict:
43     """A mapping datatype with keys kept in insertion order.
44
45     An ordinary dict insertion operation (d[k] = v) inserts the
46     key-value pair first in the dictionary, so the oldest insertion
47     appears last in the key list.
48
49     Apart from the standard mapping interface, the class has some
50     extra methods:
51
52     insert_after  -- insert a key-value pair after a given existing key
53     insert_before -- insert a key-value pair before a given existing key
54     insert_first  -- insert a key-value pair first in the dictionary
55     insert_last   -- insert a key-value pair last in the dictionary
56     reviteritems  -- return a backward iterator over (key, value) pairs
57     reviterkeys   -- return a backward iterator over the dictionary's keys
58     revitervalues -- return a backward iterator over the dictionary's values
59
60     The class keeps keys in a linked list, which means that insertion
61     and deletion are asymptotically efficient; insertion and deletion
62     are (amortized) O(1). For small dictionaries, this approach will
63     be slower than using an ordinary arrayish Python list, though.
64     """
65
66     def __init__(self, items=None):
67         self._map = {} # key --> (keylistnode, value)
68         self._keylist_head = _KeyListNode()
69         self._keylist_tail = _KeyListNode()
70         self._keylist_tail.insert_after(self._keylist_head)
71         if items is not None:
72             self.update(items)
73
74     def __cmp__(self, other):
75         snode = self._keylist_head.next
76         onode = other._keylist_head.next
77         while True:
78             if snode is self._keylist_tail:
79                 if onode is other._keylist_tail:
80                     return 0
81                 else:
82                     return -1
83             elif onode is other._keylist_tail:
84                 return 1
85             elif snode.key != onode.key:
86                 return cmp(snode.key, onode.key)
87             else:
88                 sval = self._map[snode.key][1]
89                 oval = other._map[onode.key][1]
90                 cmpval = cmp(sval, oval)
91                 if cmpval != 0:
92                     return cmpval
93             snode = snode.next
94             onode = onode.next
95
96     def __contains__(self, key):
97         return key in self._map
98
99     def __delitem__(self, key):
100         self._map[key][0].unlink()
101         del self._map[key]
102
103     def __getitem__(self, key):
104         return self._map[key][1]
105
106     def __iter__(self):
107         return self.iterkeys()
108
109     def __len__(self):
110         return len(self._map)
111
112     def __repr__(self):
113         return "InsertionOrderedDict(%r)" % self.items()
114
115     def __setitem__(self, key, value):
116         if key in self._map:
117             node = self._map[key][0]
118             node.unlink()
119         else:
120             node = _KeyListNode(key)
121         self._map[key] = (node, value)
122         node.insert_after(self._keylist_head)
123
124     def clear(self):
125         self._map.clear()
126
127         # Break reference cycles:
128         node = self._keylist_head
129         while node is not None:
130             node.prev = None
131             node = node.next
132         self._keylist_head.unlink()
133         self._keylist_tail.unlink()
134         self._keylist_tail.insert_after(self._keylist_head)
135
136     def copy(self):
137         return InsertionOrderedDict(self.reviteritems())
138
139     def get(self, key, default=None):
140         if key in self._map:
141             return self._map[key][1]
142         else:
143             return default
144
145     def has_key(self, key):
146         return self._map.has_key(key)
147
148     def insert_after(self, refkey, key, value):
149         """Insert a key-value pair after a given existing key.
150
151         Arguments:
152
153         refkey -- Reference key after which to insert the key-value pair.
154         key    -- The key to insert.
155         value  -- The value to insert.
156         """
157         self._insert_after_or_before(refkey, key, value, True)
158
159     def insert_before(self, refkey, key, value):
160         """Insert a key-value pair before an given existing key.
161
162         Arguments:
163
164         refkey -- Reference key before which to insert the key-value pair.
165         key    -- The key to insert.
166         value  -- The value to insert.
167         """
168         self._insert_after_or_before(refkey, key, value, False)
169
170     def insert_first(self, key, value):
171         """Insert a key-value pair first in the dictionary.
172
173         Arguments:
174
175         key    -- The key to insert.
176         value  -- The value to insert.
177         """
178         self[key] = value
179
180     def insert_last(self, key, value):
181         """Insert a key-value pair last in the dictionary.
182
183         Arguments:
184
185         key    -- The key to insert.
186         value  -- The value to insert.
187         """
188         if key in self._map:
189             node = self._map[key][0]
190             node.unlink()
191         else:
192             node = _KeyListNode(key)
193         self._map[key] = (node, value)
194         node.insert_before(self._keylist_tail)
195
196     def items(self):
197         return self.items()
198
199     def iteritems(self):
200         node = self._keylist_head.next
201         while node is not self._keylist_tail:
202             yield (node.key, self._map[node.key][1])
203             node = node.next
204
205     def iterkeys(self):
206         node = self._keylist_head.next
207         while node is not self._keylist_tail:
208             yield node.key
209             node = node.next
210
211     def itervalues(self):
212         node = self._keylist_head.next
213         while node is not self._keylist_tail:
214             yield self._map[node.key][1]
215             node = node.next
216
217     def keys(self):
218         return self.keys()
219
220     def pop(self, key, default=None):
221         if key in self._map:
222             value = self[key]
223             del self[key]
224             return value
225         else:
226             if default is None:
227                 raise KeyError(key)
228             else:
229                 return default
230
231     def popitem(self):
232         if len(self) == 0:
233             raise KeyError
234         else:
235             key = self._keylist_head.next.key
236             value = self.pop(key)
237             return (key, value)
238
239     def reviteritems(self):
240         node = self._keylist_tail.prev
241         while node is not self._keylist_head:
242             yield (node.key, self._map[node.key][1])
243             node = node.prev
244
245     def reviterkeys(self):
246         node = self._keylist_tail.prev
247         while node is not self._keylist_head:
248             yield node.key
249             node = node.prev
250
251     def revitervalues(self):
252         node = self._keylist_tail.prev
253         while node is not self._keylist_head:
254             yield self._map[node.key][1]
255             node = node.prev
256
257     def setdefault(self, key, value=None):
258         if key in self._map:
259             return self[key]
260         else:
261             self[key] = value
262             return value
263
264     def update(self, items):
265         for key, value in items:
266             self[key] = value
267
268     def values(self):
269         return self.values()
270
271     def _insert_after_or_before(self, refkey, key, value, after):
272         refnode = self._map[refkey][0]
273         if refkey == key:
274             self._map[refkey] = (refnode, value)
275         else:
276             if key in self._map:
277                 del self[key]
278             node = _KeyListNode(key)
279             self._map[key] = (node, value)
280             if after:
281                 node.insert_after(refnode)
282             else:
283                 node.insert_before(refnode)
284
285
286 class _KeyListNode:
287     def __init__(self, key=None):
288         self.key = key
289         self.prev = None
290         self.next = None
291
292     def insert_after(self, node):
293         if node.next is not None:
294             node.next.prev = self
295             self.next = node.next
296         self.prev = node
297         node.next = self
298
299     def insert_before(self, node):
300         if node.prev is not None:
301             node.prev.next = self
302             self.prev = node.prev
303         self.next = node
304         node.prev = self
305
306     def unlink(self):
307         if self.prev is not None:
308             self.prev.next = self.next
309         if self.next is not None:
310             self.next.prev = self.prev
311         self.prev = None
312         self.next = None