diff options
Diffstat (limited to 'lib/dodai/tools/odict.py')
-rw-r--r-- | lib/dodai/tools/odict.py | 1399 |
1 files changed, 1399 insertions, 0 deletions
diff --git a/lib/dodai/tools/odict.py b/lib/dodai/tools/odict.py new file mode 100644 index 0000000..2c8391d --- /dev/null +++ b/lib/dodai/tools/odict.py | |||
@@ -0,0 +1,1399 @@ | |||
1 | # odict.py | ||
2 | # An Ordered Dictionary object | ||
3 | # Copyright (C) 2005 Nicola Larosa, Michael Foord | ||
4 | # E-mail: nico AT tekNico DOT net, fuzzyman AT voidspace DOT org DOT uk | ||
5 | |||
6 | # This software is licensed under the terms of the BSD license. | ||
7 | # http://www.voidspace.org.uk/python/license.shtml | ||
8 | # Basically you're free to copy, modify, distribute and relicense it, | ||
9 | # So long as you keep a copy of the license with it. | ||
10 | |||
11 | # Documentation at http://www.voidspace.org.uk/python/odict.html | ||
12 | # For information about bugfixes, updates and support, please join the | ||
13 | # Pythonutils mailing list: | ||
14 | # http://groups.google.com/group/pythonutils/ | ||
15 | # Comments, suggestions and bug reports welcome. | ||
16 | |||
17 | """A dict that keeps keys in insertion order""" | ||
18 | from __future__ import generators | ||
19 | |||
20 | __author__ = ('Nicola Larosa <nico-NoSp@m-tekNico.net>,' | ||
21 | 'Michael Foord <fuzzyman AT voidspace DOT org DOT uk>') | ||
22 | |||
23 | __docformat__ = "restructuredtext en" | ||
24 | |||
25 | __revision__ = '$Id: odict.py 129 2005-09-12 18:15:28Z teknico $' | ||
26 | |||
27 | __version__ = '0.2.2' | ||
28 | |||
29 | __all__ = ['OrderedDict', 'SequenceOrderedDict'] | ||
30 | |||
31 | import sys | ||
32 | INTP_VER = sys.version_info[:2] | ||
33 | if INTP_VER < (2, 2): | ||
34 | raise RuntimeError("Python v.2.2 or later required") | ||
35 | |||
36 | import types, warnings | ||
37 | |||
38 | class OrderedDict(dict): | ||
39 | """ | ||
40 | A class of dictionary that keeps the insertion order of keys. | ||
41 | |||
42 | All appropriate methods return keys, items, or values in an ordered way. | ||
43 | |||
44 | All normal dictionary methods are available. Update and comparison is | ||
45 | restricted to other OrderedDict objects. | ||
46 | |||
47 | Various sequence methods are available, including the ability to explicitly | ||
48 | mutate the key ordering. | ||
49 | |||
50 | __contains__ tests: | ||
51 | |||
52 | >>> d = OrderedDict(((1, 3),)) | ||
53 | >>> 1 in d | ||
54 | 1 | ||
55 | >>> 4 in d | ||
56 | 0 | ||
57 | |||
58 | __getitem__ tests: | ||
59 | |||
60 | >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[2] | ||
61 | 1 | ||
62 | >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[4] | ||
63 | Traceback (most recent call last): | ||
64 | KeyError: 4 | ||
65 | |||
66 | __len__ tests: | ||
67 | |||
68 | >>> len(OrderedDict()) | ||
69 | 0 | ||
70 | >>> len(OrderedDict(((1, 3), (3, 2), (2, 1)))) | ||
71 | 3 | ||
72 | |||
73 | get tests: | ||
74 | |||
75 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
76 | >>> d.get(1) | ||
77 | 3 | ||
78 | >>> d.get(4) is None | ||
79 | 1 | ||
80 | >>> d.get(4, 5) | ||
81 | 5 | ||
82 | >>> d | ||
83 | OrderedDict([(1, 3), (3, 2), (2, 1)]) | ||
84 | |||
85 | has_key tests: | ||
86 | |||
87 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
88 | >>> d.has_key(1) | ||
89 | 1 | ||
90 | >>> d.has_key(4) | ||
91 | 0 | ||
92 | """ | ||
93 | |||
94 | def __init__(self, init_val=(), strict=False): | ||
95 | """ | ||
96 | Create a new ordered dictionary. Cannot init from a normal dict, | ||
97 | nor from kwargs, since items order is undefined in those cases. | ||
98 | |||
99 | If the ``strict`` keyword argument is ``True`` (``False`` is the | ||
100 | default) then when doing slice assignment - the ``OrderedDict`` you are | ||
101 | assigning from *must not* contain any keys in the remaining dict. | ||
102 | |||
103 | >>> OrderedDict() | ||
104 | OrderedDict([]) | ||
105 | >>> OrderedDict({1: 1}) | ||
106 | Traceback (most recent call last): | ||
107 | TypeError: undefined order, cannot get items from dict | ||
108 | >>> OrderedDict({1: 1}.items()) | ||
109 | OrderedDict([(1, 1)]) | ||
110 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
111 | >>> d | ||
112 | OrderedDict([(1, 3), (3, 2), (2, 1)]) | ||
113 | >>> OrderedDict(d) | ||
114 | OrderedDict([(1, 3), (3, 2), (2, 1)]) | ||
115 | """ | ||
116 | self.strict = strict | ||
117 | dict.__init__(self) | ||
118 | if isinstance(init_val, OrderedDict): | ||
119 | self._sequence = init_val.keys() | ||
120 | dict.update(self, init_val) | ||
121 | elif isinstance(init_val, dict): | ||
122 | # we lose compatibility with other ordered dict types this way | ||
123 | raise TypeError('undefined order, cannot get items from dict') | ||
124 | else: | ||
125 | self._sequence = [] | ||
126 | self.update(init_val) | ||
127 | |||
128 | ### Special methods ### | ||
129 | |||
130 | def __delitem__(self, key): | ||
131 | """ | ||
132 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
133 | >>> del d[3] | ||
134 | >>> d | ||
135 | OrderedDict([(1, 3), (2, 1)]) | ||
136 | >>> del d[3] | ||
137 | Traceback (most recent call last): | ||
138 | KeyError: 3 | ||
139 | >>> d[3] = 2 | ||
140 | >>> d | ||
141 | OrderedDict([(1, 3), (2, 1), (3, 2)]) | ||
142 | >>> del d[0:1] | ||
143 | >>> d | ||
144 | OrderedDict([(2, 1), (3, 2)]) | ||
145 | """ | ||
146 | if isinstance(key, types.SliceType): | ||
147 | # FIXME: efficiency? | ||
148 | keys = self._sequence[key] | ||
149 | for entry in keys: | ||
150 | dict.__delitem__(self, entry) | ||
151 | del self._sequence[key] | ||
152 | else: | ||
153 | # do the dict.__delitem__ *first* as it raises | ||
154 | # the more appropriate error | ||
155 | dict.__delitem__(self, key) | ||
156 | self._sequence.remove(key) | ||
157 | |||
158 | def __eq__(self, other): | ||
159 | """ | ||
160 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
161 | >>> d == OrderedDict(d) | ||
162 | True | ||
163 | >>> d == OrderedDict(((1, 3), (2, 1), (3, 2))) | ||
164 | False | ||
165 | >>> d == OrderedDict(((1, 0), (3, 2), (2, 1))) | ||
166 | False | ||
167 | >>> d == OrderedDict(((0, 3), (3, 2), (2, 1))) | ||
168 | False | ||
169 | >>> d == dict(d) | ||
170 | False | ||
171 | >>> d == False | ||
172 | False | ||
173 | """ | ||
174 | if isinstance(other, OrderedDict): | ||
175 | # FIXME: efficiency? | ||
176 | # Generate both item lists for each compare | ||
177 | return (self.items() == other.items()) | ||
178 | else: | ||
179 | return False | ||
180 | |||
181 | def __lt__(self, other): | ||
182 | """ | ||
183 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
184 | >>> c = OrderedDict(((0, 3), (3, 2), (2, 1))) | ||
185 | >>> c < d | ||
186 | True | ||
187 | >>> d < c | ||
188 | False | ||
189 | >>> d < dict(c) | ||
190 | Traceback (most recent call last): | ||
191 | TypeError: Can only compare with other OrderedDicts | ||
192 | """ | ||
193 | if not isinstance(other, OrderedDict): | ||
194 | raise TypeError('Can only compare with other OrderedDicts') | ||
195 | # FIXME: efficiency? | ||
196 | # Generate both item lists for each compare | ||
197 | return (self.items() < other.items()) | ||
198 | |||
199 | def __le__(self, other): | ||
200 | """ | ||
201 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
202 | >>> c = OrderedDict(((0, 3), (3, 2), (2, 1))) | ||
203 | >>> e = OrderedDict(d) | ||
204 | >>> c <= d | ||
205 | True | ||
206 | >>> d <= c | ||
207 | False | ||
208 | >>> d <= dict(c) | ||
209 | Traceback (most recent call last): | ||
210 | TypeError: Can only compare with other OrderedDicts | ||
211 | >>> d <= e | ||
212 | True | ||
213 | """ | ||
214 | if not isinstance(other, OrderedDict): | ||
215 | raise TypeError('Can only compare with other OrderedDicts') | ||
216 | # FIXME: efficiency? | ||
217 | # Generate both item lists for each compare | ||
218 | return (self.items() <= other.items()) | ||
219 | |||
220 | def __ne__(self, other): | ||
221 | """ | ||
222 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
223 | >>> d != OrderedDict(d) | ||
224 | False | ||
225 | >>> d != OrderedDict(((1, 3), (2, 1), (3, 2))) | ||
226 | True | ||
227 | >>> d != OrderedDict(((1, 0), (3, 2), (2, 1))) | ||
228 | True | ||
229 | >>> d == OrderedDict(((0, 3), (3, 2), (2, 1))) | ||
230 | False | ||
231 | >>> d != dict(d) | ||
232 | True | ||
233 | >>> d != False | ||
234 | True | ||
235 | """ | ||
236 | if isinstance(other, OrderedDict): | ||
237 | # FIXME: efficiency? | ||
238 | # Generate both item lists for each compare | ||
239 | return not (self.items() == other.items()) | ||
240 | else: | ||
241 | return True | ||
242 | |||
243 | def __gt__(self, other): | ||
244 | """ | ||
245 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
246 | >>> c = OrderedDict(((0, 3), (3, 2), (2, 1))) | ||
247 | >>> d > c | ||
248 | True | ||
249 | >>> c > d | ||
250 | False | ||
251 | >>> d > dict(c) | ||
252 | Traceback (most recent call last): | ||
253 | TypeError: Can only compare with other OrderedDicts | ||
254 | """ | ||
255 | if not isinstance(other, OrderedDict): | ||
256 | raise TypeError('Can only compare with other OrderedDicts') | ||
257 | # FIXME: efficiency? | ||
258 | # Generate both item lists for each compare | ||
259 | return (self.items() > other.items()) | ||
260 | |||
261 | def __ge__(self, other): | ||
262 | """ | ||
263 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
264 | >>> c = OrderedDict(((0, 3), (3, 2), (2, 1))) | ||
265 | >>> e = OrderedDict(d) | ||
266 | >>> c >= d | ||
267 | False | ||
268 | >>> d >= c | ||
269 | True | ||
270 | >>> d >= dict(c) | ||
271 | Traceback (most recent call last): | ||
272 | TypeError: Can only compare with other OrderedDicts | ||
273 | >>> e >= d | ||
274 | True | ||
275 | """ | ||
276 | if not isinstance(other, OrderedDict): | ||
277 | raise TypeError('Can only compare with other OrderedDicts') | ||
278 | # FIXME: efficiency? | ||
279 | # Generate both item lists for each compare | ||
280 | return (self.items() >= other.items()) | ||
281 | |||
282 | def __repr__(self): | ||
283 | """ | ||
284 | Used for __repr__ and __str__ | ||
285 | |||
286 | >>> r1 = repr(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f')))) | ||
287 | >>> r1 | ||
288 | "OrderedDict([('a', 'b'), ('c', 'd'), ('e', 'f')])" | ||
289 | >>> r2 = repr(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd')))) | ||
290 | >>> r2 | ||
291 | "OrderedDict([('a', 'b'), ('e', 'f'), ('c', 'd')])" | ||
292 | >>> r1 == str(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f')))) | ||
293 | True | ||
294 | >>> r2 == str(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd')))) | ||
295 | True | ||
296 | """ | ||
297 | return '%s([%s])' % (self.__class__.__name__, ', '.join( | ||
298 | ['(%r, %r)' % (key, self[key]) for key in self._sequence])) | ||
299 | |||
300 | def __setitem__(self, key, val): | ||
301 | """ | ||
302 | Allows slice assignment, so long as the slice is an OrderedDict | ||
303 | >>> d = OrderedDict() | ||
304 | >>> d['a'] = 'b' | ||
305 | >>> d['b'] = 'a' | ||
306 | >>> d[3] = 12 | ||
307 | >>> d | ||
308 | OrderedDict([('a', 'b'), ('b', 'a'), (3, 12)]) | ||
309 | >>> d[:] = OrderedDict(((1, 2), (2, 3), (3, 4))) | ||
310 | >>> d | ||
311 | OrderedDict([(1, 2), (2, 3), (3, 4)]) | ||
312 | >>> d[::2] = OrderedDict(((7, 8), (9, 10))) | ||
313 | >>> d | ||
314 | OrderedDict([(7, 8), (2, 3), (9, 10)]) | ||
315 | >>> d = OrderedDict(((0, 1), (1, 2), (2, 3), (3, 4))) | ||
316 | >>> d[1:3] = OrderedDict(((1, 2), (5, 6), (7, 8))) | ||
317 | >>> d | ||
318 | OrderedDict([(0, 1), (1, 2), (5, 6), (7, 8), (3, 4)]) | ||
319 | >>> d = OrderedDict(((0, 1), (1, 2), (2, 3), (3, 4)), strict=True) | ||
320 | >>> d[1:3] = OrderedDict(((1, 2), (5, 6), (7, 8))) | ||
321 | >>> d | ||
322 | OrderedDict([(0, 1), (1, 2), (5, 6), (7, 8), (3, 4)]) | ||
323 | |||
324 | >>> a = OrderedDict(((0, 1), (1, 2), (2, 3)), strict=True) | ||
325 | >>> a[3] = 4 | ||
326 | >>> a | ||
327 | OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
328 | >>> a[::1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
329 | >>> a | ||
330 | OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
331 | >>> a[:2] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]) | ||
332 | Traceback (most recent call last): | ||
333 | ValueError: slice assignment must be from unique keys | ||
334 | >>> a = OrderedDict(((0, 1), (1, 2), (2, 3))) | ||
335 | >>> a[3] = 4 | ||
336 | >>> a | ||
337 | OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
338 | >>> a[::1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
339 | >>> a | ||
340 | OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
341 | >>> a[:2] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
342 | >>> a | ||
343 | OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
344 | >>> a[::-1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
345 | >>> a | ||
346 | OrderedDict([(3, 4), (2, 3), (1, 2), (0, 1)]) | ||
347 | |||
348 | >>> d = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
349 | >>> d[:1] = 3 | ||
350 | Traceback (most recent call last): | ||
351 | TypeError: slice assignment requires an OrderedDict | ||
352 | |||
353 | >>> d = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) | ||
354 | >>> d[:1] = OrderedDict([(9, 8)]) | ||
355 | >>> d | ||
356 | OrderedDict([(9, 8), (1, 2), (2, 3), (3, 4)]) | ||
357 | """ | ||
358 | if isinstance(key, types.SliceType): | ||
359 | if not isinstance(val, OrderedDict): | ||
360 | # FIXME: allow a list of tuples? | ||
361 | raise TypeError('slice assignment requires an OrderedDict') | ||
362 | keys = self._sequence[key] | ||
363 | # NOTE: Could use ``range(*key.indices(len(self._sequence)))`` | ||
364 | indexes = range(len(self._sequence))[key] | ||
365 | if key.step is None: | ||
366 | # NOTE: new slice may not be the same size as the one being | ||
367 | # overwritten ! | ||
368 | # NOTE: What is the algorithm for an impossible slice? | ||
369 | # e.g. d[5:3] | ||
370 | pos = key.start or 0 | ||
371 | del self[key] | ||
372 | newkeys = val.keys() | ||
373 | for k in newkeys: | ||
374 | if k in self: | ||
375 | if self.strict: | ||
376 | raise ValueError('slice assignment must be from ' | ||
377 | 'unique keys') | ||
378 | else: | ||
379 | # NOTE: This removes duplicate keys *first* | ||
380 | # so start position might have changed? | ||
381 | del self[k] | ||
382 | self._sequence = (self._sequence[:pos] + newkeys + | ||
383 | self._sequence[pos:]) | ||
384 | dict.update(self, val) | ||
385 | else: | ||
386 | # extended slice - length of new slice must be the same | ||
387 | # as the one being replaced | ||
388 | if len(keys) != len(val): | ||
389 | raise ValueError('attempt to assign sequence of size %s ' | ||
390 | 'to extended slice of size %s' % (len(val), len(keys))) | ||
391 | # FIXME: efficiency? | ||
392 | del self[key] | ||
393 | item_list = zip(indexes, val.items()) | ||
394 | # smallest indexes first - higher indexes not guaranteed to | ||
395 | # exist | ||
396 | item_list.sort() | ||
397 | for pos, (newkey, newval) in item_list: | ||
398 | if self.strict and newkey in self: | ||
399 | raise ValueError('slice assignment must be from unique' | ||
400 | ' keys') | ||
401 | self.insert(pos, newkey, newval) | ||
402 | else: | ||
403 | if key not in self: | ||
404 | self._sequence.append(key) | ||
405 | dict.__setitem__(self, key, val) | ||
406 | |||
407 | def __getitem__(self, key): | ||
408 | """ | ||
409 | Allows slicing. Returns an OrderedDict if you slice. | ||
410 | >>> b = OrderedDict([(7, 0), (6, 1), (5, 2), (4, 3), (3, 4), (2, 5), (1, 6)]) | ||
411 | >>> b[::-1] | ||
412 | OrderedDict([(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)]) | ||
413 | >>> b[2:5] | ||
414 | OrderedDict([(5, 2), (4, 3), (3, 4)]) | ||
415 | >>> type(b[2:4]) | ||
416 | <class '__main__.OrderedDict'> | ||
417 | """ | ||
418 | if isinstance(key, types.SliceType): | ||
419 | # FIXME: does this raise the error we want? | ||
420 | keys = self._sequence[key] | ||
421 | # FIXME: efficiency? | ||
422 | return OrderedDict([(entry, self[entry]) for entry in keys]) | ||
423 | else: | ||
424 | return dict.__getitem__(self, key) | ||
425 | |||
426 | __str__ = __repr__ | ||
427 | |||
428 | def __setattr__(self, name, value): | ||
429 | """ | ||
430 | Implemented so that accesses to ``sequence`` raise a warning and are | ||
431 | diverted to the new ``setkeys`` method. | ||
432 | """ | ||
433 | if name == 'sequence': | ||
434 | warnings.warn('Use of the sequence attribute is deprecated.' | ||
435 | ' Use the keys method instead.', DeprecationWarning) | ||
436 | # NOTE: doesn't return anything | ||
437 | self.setkeys(value) | ||
438 | else: | ||
439 | # FIXME: do we want to allow arbitrary setting of attributes? | ||
440 | # Or do we want to manage it? | ||
441 | object.__setattr__(self, name, value) | ||
442 | |||
443 | def __getattr__(self, name): | ||
444 | """ | ||
445 | Implemented so that access to ``sequence`` raises a warning. | ||
446 | |||
447 | >>> d = OrderedDict() | ||
448 | >>> d.sequence | ||
449 | [] | ||
450 | """ | ||
451 | if name == 'sequence': | ||
452 | warnings.warn('Use of the sequence attribute is deprecated.' | ||
453 | ' Use the keys method instead.', DeprecationWarning) | ||
454 | # NOTE: Still (currently) returns a direct reference. Need to | ||
455 | # because code that uses sequence will expect to be able to | ||
456 | # mutate it in place. | ||
457 | return self._sequence | ||
458 | else: | ||
459 | # raise the appropriate error | ||
460 | raise AttributeError("OrderedDict has no '%s' attribute" % name) | ||
461 | |||
462 | def __deepcopy__(self, memo): | ||
463 | """ | ||
464 | To allow deepcopy to work with OrderedDict. | ||
465 | |||
466 | >>> from copy import deepcopy | ||
467 | >>> a = OrderedDict([(1, 1), (2, 2), (3, 3)]) | ||
468 | >>> a['test'] = {} | ||
469 | >>> b = deepcopy(a) | ||
470 | >>> b == a | ||
471 | True | ||
472 | >>> b is a | ||
473 | False | ||
474 | >>> a['test'] is b['test'] | ||
475 | False | ||
476 | """ | ||
477 | from copy import deepcopy | ||
478 | return self.__class__(deepcopy(self.items(), memo), self.strict) | ||
479 | |||
480 | |||
481 | ### Read-only methods ### | ||
482 | |||
483 | def copy(self): | ||
484 | """ | ||
485 | >>> OrderedDict(((1, 3), (3, 2), (2, 1))).copy() | ||
486 | OrderedDict([(1, 3), (3, 2), (2, 1)]) | ||
487 | """ | ||
488 | return OrderedDict(self) | ||
489 | |||
490 | def items(self): | ||
491 | """ | ||
492 | ``items`` returns a list of tuples representing all the | ||
493 | ``(key, value)`` pairs in the dictionary. | ||
494 | |||
495 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
496 | >>> d.items() | ||
497 | [(1, 3), (3, 2), (2, 1)] | ||
498 | >>> d.clear() | ||
499 | >>> d.items() | ||
500 | [] | ||
501 | """ | ||
502 | return zip(self._sequence, self.values()) | ||
503 | |||
504 | def keys(self): | ||
505 | """ | ||
506 | Return a list of keys in the ``OrderedDict``. | ||
507 | |||
508 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
509 | >>> d.keys() | ||
510 | [1, 3, 2] | ||
511 | """ | ||
512 | return self._sequence[:] | ||
513 | |||
514 | def values(self, values=None): | ||
515 | """ | ||
516 | Return a list of all the values in the OrderedDict. | ||
517 | |||
518 | Optionally you can pass in a list of values, which will replace the | ||
519 | current list. The value list must be the same len as the OrderedDict. | ||
520 | |||
521 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
522 | >>> d.values() | ||
523 | [3, 2, 1] | ||
524 | """ | ||
525 | return [self[key] for key in self._sequence] | ||
526 | |||
527 | def iteritems(self): | ||
528 | """ | ||
529 | >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iteritems() | ||
530 | >>> ii.next() | ||
531 | (1, 3) | ||
532 | >>> ii.next() | ||
533 | (3, 2) | ||
534 | >>> ii.next() | ||
535 | (2, 1) | ||
536 | >>> ii.next() | ||
537 | Traceback (most recent call last): | ||
538 | StopIteration | ||
539 | """ | ||
540 | def make_iter(self=self): | ||
541 | keys = self.iterkeys() | ||
542 | while True: | ||
543 | key = keys.next() | ||
544 | yield (key, self[key]) | ||
545 | return make_iter() | ||
546 | |||
547 | def iterkeys(self): | ||
548 | """ | ||
549 | >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iterkeys() | ||
550 | >>> ii.next() | ||
551 | 1 | ||
552 | >>> ii.next() | ||
553 | 3 | ||
554 | >>> ii.next() | ||
555 | 2 | ||
556 | >>> ii.next() | ||
557 | Traceback (most recent call last): | ||
558 | StopIteration | ||
559 | """ | ||
560 | return iter(self._sequence) | ||
561 | |||
562 | __iter__ = iterkeys | ||
563 | |||
564 | def itervalues(self): | ||
565 | """ | ||
566 | >>> iv = OrderedDict(((1, 3), (3, 2), (2, 1))).itervalues() | ||
567 | >>> iv.next() | ||
568 | 3 | ||
569 | >>> iv.next() | ||
570 | 2 | ||
571 | >>> iv.next() | ||
572 | 1 | ||
573 | >>> iv.next() | ||
574 | Traceback (most recent call last): | ||
575 | StopIteration | ||
576 | """ | ||
577 | def make_iter(self=self): | ||
578 | keys = self.iterkeys() | ||
579 | while True: | ||
580 | yield self[keys.next()] | ||
581 | return make_iter() | ||
582 | |||
583 | ### Read-write methods ### | ||
584 | |||
585 | def clear(self): | ||
586 | """ | ||
587 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
588 | >>> d.clear() | ||
589 | >>> d | ||
590 | OrderedDict([]) | ||
591 | """ | ||
592 | dict.clear(self) | ||
593 | self._sequence = [] | ||
594 | |||
595 | def pop(self, key, *args): | ||
596 | """ | ||
597 | No dict.pop in Python 2.2, gotta reimplement it | ||
598 | |||
599 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
600 | >>> d.pop(3) | ||
601 | 2 | ||
602 | >>> d | ||
603 | OrderedDict([(1, 3), (2, 1)]) | ||
604 | >>> d.pop(4) | ||
605 | Traceback (most recent call last): | ||
606 | KeyError: 4 | ||
607 | >>> d.pop(4, 0) | ||
608 | 0 | ||
609 | >>> d.pop(4, 0, 1) | ||
610 | Traceback (most recent call last): | ||
611 | TypeError: pop expected at most 2 arguments, got 3 | ||
612 | """ | ||
613 | if len(args) > 1: | ||
614 | raise TypeError, ('pop expected at most 2 arguments, got %s' % | ||
615 | (len(args) + 1)) | ||
616 | if key in self: | ||
617 | val = self[key] | ||
618 | del self[key] | ||
619 | else: | ||
620 | try: | ||
621 | val = args[0] | ||
622 | except IndexError: | ||
623 | raise KeyError(key) | ||
624 | return val | ||
625 | |||
626 | def popitem(self, i=-1): | ||
627 | """ | ||
628 | Delete and return an item specified by index, not a random one as in | ||
629 | dict. The index is -1 by default (the last item). | ||
630 | |||
631 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
632 | >>> d.popitem() | ||
633 | (2, 1) | ||
634 | >>> d | ||
635 | OrderedDict([(1, 3), (3, 2)]) | ||
636 | >>> d.popitem(0) | ||
637 | (1, 3) | ||
638 | >>> OrderedDict().popitem() | ||
639 | Traceback (most recent call last): | ||
640 | KeyError: 'popitem(): dictionary is empty' | ||
641 | >>> d.popitem(2) | ||
642 | Traceback (most recent call last): | ||
643 | IndexError: popitem(): index 2 not valid | ||
644 | """ | ||
645 | if not self._sequence: | ||
646 | raise KeyError('popitem(): dictionary is empty') | ||
647 | try: | ||
648 | key = self._sequence[i] | ||
649 | except IndexError: | ||
650 | raise IndexError('popitem(): index %s not valid' % i) | ||
651 | return (key, self.pop(key)) | ||
652 | |||
653 | def setdefault(self, key, defval = None): | ||
654 | """ | ||
655 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
656 | >>> d.setdefault(1) | ||
657 | 3 | ||
658 | >>> d.setdefault(4) is None | ||
659 | True | ||
660 | >>> d | ||
661 | OrderedDict([(1, 3), (3, 2), (2, 1), (4, None)]) | ||
662 | >>> d.setdefault(5, 0) | ||
663 | 0 | ||
664 | >>> d | ||
665 | OrderedDict([(1, 3), (3, 2), (2, 1), (4, None), (5, 0)]) | ||
666 | """ | ||
667 | if key in self: | ||
668 | return self[key] | ||
669 | else: | ||
670 | self[key] = defval | ||
671 | return defval | ||
672 | |||
673 | def update(self, from_od): | ||
674 | """ | ||
675 | Update from another OrderedDict or sequence of (key, value) pairs | ||
676 | |||
677 | >>> d = OrderedDict(((1, 0), (0, 1))) | ||
678 | >>> d.update(OrderedDict(((1, 3), (3, 2), (2, 1)))) | ||
679 | >>> d | ||
680 | OrderedDict([(1, 3), (0, 1), (3, 2), (2, 1)]) | ||
681 | >>> d.update({4: 4}) | ||
682 | Traceback (most recent call last): | ||
683 | TypeError: undefined order, cannot get items from dict | ||
684 | >>> d.update((4, 4)) | ||
685 | Traceback (most recent call last): | ||
686 | TypeError: cannot convert dictionary update sequence element "4" to a 2-item sequence | ||
687 | """ | ||
688 | if isinstance(from_od, OrderedDict): | ||
689 | for key, val in from_od.items(): | ||
690 | self[key] = val | ||
691 | elif isinstance(from_od, dict): | ||
692 | # we lose compatibility with other ordered dict types this way | ||
693 | raise TypeError('undefined order, cannot get items from dict') | ||
694 | else: | ||
695 | # FIXME: efficiency? | ||
696 | # sequence of 2-item sequences, or error | ||
697 | for item in from_od: | ||
698 | try: | ||
699 | key, val = item | ||
700 | except TypeError: | ||
701 | raise TypeError('cannot convert dictionary update' | ||
702 | ' sequence element "%s" to a 2-item sequence' % item) | ||
703 | self[key] = val | ||
704 | |||
705 | def rename(self, old_key, new_key): | ||
706 | """ | ||
707 | Rename the key for a given value, without modifying sequence order. | ||
708 | |||
709 | For the case where new_key already exists this raise an exception, | ||
710 | since if new_key exists, it is ambiguous as to what happens to the | ||
711 | associated values, and the position of new_key in the sequence. | ||
712 | |||
713 | >>> od = OrderedDict() | ||
714 | >>> od['a'] = 1 | ||
715 | >>> od['b'] = 2 | ||
716 | >>> od.items() | ||
717 | [('a', 1), ('b', 2)] | ||
718 | >>> od.rename('b', 'c') | ||
719 | >>> od.items() | ||
720 | [('a', 1), ('c', 2)] | ||
721 | >>> od.rename('c', 'a') | ||
722 | Traceback (most recent call last): | ||
723 | ValueError: New key already exists: 'a' | ||
724 | >>> od.rename('d', 'b') | ||
725 | Traceback (most recent call last): | ||
726 | KeyError: 'd' | ||
727 | """ | ||
728 | if new_key == old_key: | ||
729 | # no-op | ||
730 | return | ||
731 | if new_key in self: | ||
732 | raise ValueError("New key already exists: %r" % new_key) | ||
733 | # rename sequence entry | ||
734 | value = self[old_key] | ||
735 | old_idx = self._sequence.index(old_key) | ||
736 | self._sequence[old_idx] = new_key | ||
737 | # rename internal dict entry | ||
738 | dict.__delitem__(self, old_key) | ||
739 | dict.__setitem__(self, new_key, value) | ||
740 | |||
741 | def setitems(self, items): | ||
742 | """ | ||
743 | This method allows you to set the items in the dict. | ||
744 | |||
745 | It takes a list of tuples - of the same sort returned by the ``items`` | ||
746 | method. | ||
747 | |||
748 | >>> d = OrderedDict() | ||
749 | >>> d.setitems(((3, 1), (2, 3), (1, 2))) | ||
750 | >>> d | ||
751 | OrderedDict([(3, 1), (2, 3), (1, 2)]) | ||
752 | """ | ||
753 | self.clear() | ||
754 | # FIXME: this allows you to pass in an OrderedDict as well :-) | ||
755 | self.update(items) | ||
756 | |||
757 | def setkeys(self, keys): | ||
758 | """ | ||
759 | ``setkeys`` all ows you to pass in a new list of keys which will | ||
760 | replace the current set. This must contain the same set of keys, but | ||
761 | need not be in the same order. | ||
762 | |||
763 | If you pass in new keys that don't match, a ``KeyError`` will be | ||
764 | raised. | ||
765 | |||
766 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
767 | >>> d.keys() | ||
768 | [1, 3, 2] | ||
769 | >>> d.setkeys((1, 2, 3)) | ||
770 | >>> d | ||
771 | OrderedDict([(1, 3), (2, 1), (3, 2)]) | ||
772 | >>> d.setkeys(['a', 'b', 'c']) | ||
773 | Traceback (most recent call last): | ||
774 | KeyError: 'Keylist is not the same as current keylist.' | ||
775 | """ | ||
776 | # FIXME: Efficiency? (use set for Python 2.4 :-) | ||
777 | # NOTE: list(keys) rather than keys[:] because keys[:] returns | ||
778 | # a tuple, if keys is a tuple. | ||
779 | kcopy = list(keys) | ||
780 | kcopy.sort() | ||
781 | self._sequence.sort() | ||
782 | if kcopy != self._sequence: | ||
783 | raise KeyError('Keylist is not the same as current keylist.') | ||
784 | # NOTE: This makes the _sequence attribute a new object, instead | ||
785 | # of changing it in place. | ||
786 | # FIXME: efficiency? | ||
787 | self._sequence = list(keys) | ||
788 | |||
789 | def setvalues(self, values): | ||
790 | """ | ||
791 | You can pass in a list of values, which will replace the | ||
792 | current list. The value list must be the same len as the OrderedDict. | ||
793 | |||
794 | (Or a ``ValueError`` is raised.) | ||
795 | |||
796 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
797 | >>> d.setvalues((1, 2, 3)) | ||
798 | >>> d | ||
799 | OrderedDict([(1, 1), (3, 2), (2, 3)]) | ||
800 | >>> d.setvalues([6]) | ||
801 | Traceback (most recent call last): | ||
802 | ValueError: Value list is not the same length as the OrderedDict. | ||
803 | """ | ||
804 | if len(values) != len(self): | ||
805 | # FIXME: correct error to raise? | ||
806 | raise ValueError('Value list is not the same length as the ' | ||
807 | 'OrderedDict.') | ||
808 | self.update(zip(self, values)) | ||
809 | |||
810 | ### Sequence Methods ### | ||
811 | |||
812 | def index(self, key): | ||
813 | """ | ||
814 | Return the position of the specified key in the OrderedDict. | ||
815 | |||
816 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
817 | >>> d.index(3) | ||
818 | 1 | ||
819 | >>> d.index(4) | ||
820 | Traceback (most recent call last): | ||
821 | ValueError: list.index(x): x not in list | ||
822 | """ | ||
823 | return self._sequence.index(key) | ||
824 | |||
825 | def insert(self, index, key, value): | ||
826 | """ | ||
827 | Takes ``index``, ``key``, and ``value`` as arguments. | ||
828 | |||
829 | Sets ``key`` to ``value``, so that ``key`` is at position ``index`` in | ||
830 | the OrderedDict. | ||
831 | |||
832 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
833 | >>> d.insert(0, 4, 0) | ||
834 | >>> d | ||
835 | OrderedDict([(4, 0), (1, 3), (3, 2), (2, 1)]) | ||
836 | >>> d.insert(0, 2, 1) | ||
837 | >>> d | ||
838 | OrderedDict([(2, 1), (4, 0), (1, 3), (3, 2)]) | ||
839 | >>> d.insert(8, 8, 1) | ||
840 | >>> d | ||
841 | OrderedDict([(2, 1), (4, 0), (1, 3), (3, 2), (8, 1)]) | ||
842 | """ | ||
843 | if key in self: | ||
844 | # FIXME: efficiency? | ||
845 | del self[key] | ||
846 | self._sequence.insert(index, key) | ||
847 | dict.__setitem__(self, key, value) | ||
848 | |||
849 | def reverse(self): | ||
850 | """ | ||
851 | Reverse the order of the OrderedDict. | ||
852 | |||
853 | >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) | ||
854 | >>> d.reverse() | ||
855 | >>> d | ||
856 | OrderedDict([(2, 1), (3, 2), (1, 3)]) | ||
857 | """ | ||
858 | self._sequence.reverse() | ||
859 | |||
860 | def sort(self, *args, **kwargs): | ||
861 | """ | ||
862 | Sort the key order in the OrderedDict. | ||
863 | |||
864 | This method takes the same arguments as the ``list.sort`` method on | ||
865 | your version of Python. | ||
866 | |||
867 | >>> d = OrderedDict(((4, 1), (2, 2), (3, 3), (1, 4))) | ||
868 | >>> d.sort() | ||
869 | >>> d | ||
870 | OrderedDict([(1, 4), (2, 2), (3, 3), (4, 1)]) | ||
871 | """ | ||
872 | self._sequence.sort(*args, **kwargs) | ||
873 | |||
874 | class Keys(object): | ||
875 | # FIXME: should this object be a subclass of list? | ||
876 | """ | ||
877 | Custom object for accessing the keys of an OrderedDict. | ||
878 | |||
879 | Can be called like the normal ``OrderedDict.keys`` method, but also | ||
880 | supports indexing and sequence methods. | ||
881 | """ | ||
882 | |||
883 | def __init__(self, main): | ||
884 | self._main = main | ||
885 | |||
886 | def __call__(self): | ||
887 | """Pretend to be the keys method.""" | ||
888 | return self._main._keys() | ||
889 | |||
890 | def __getitem__(self, index): | ||
891 | """Fetch the key at position i.""" | ||
892 | # NOTE: this automatically supports slicing :-) | ||
893 | return self._main._sequence[index] | ||
894 | |||
895 | def __setitem__(self, index, name): | ||
896 | """ | ||
897 | You cannot assign to keys, but you can do slice assignment to re-order | ||
898 | them. | ||
899 | |||
900 | You can only do slice assignment if the new set of keys is a reordering | ||
901 | of the original set. | ||
902 | """ | ||
903 | if isinstance(index, types.SliceType): | ||
904 | # FIXME: efficiency? | ||
905 | # check length is the same | ||
906 | indexes = range(len(self._main._sequence))[index] | ||
907 | if len(indexes) != len(name): | ||
908 | raise ValueError('attempt to assign sequence of size %s ' | ||
909 | 'to slice of size %s' % (len(name), len(indexes))) | ||
910 | # check they are the same keys | ||
911 | # FIXME: Use set | ||
912 | old_keys = self._main._sequence[index] | ||
913 | new_keys = list(name) | ||
914 | old_keys.sort() | ||
915 | new_keys.sort() | ||
916 | if old_keys != new_keys: | ||
917 | raise KeyError('Keylist is not the same as current keylist.') | ||
918 | orig_vals = [self._main[k] for k in name] | ||
919 | del self._main[index] | ||
920 | vals = zip(indexes, name, orig_vals) | ||
921 | vals.sort() | ||
922 | for i, k, v in vals: | ||
923 | if self._main.strict and k in self._main: | ||
924 | raise ValueError('slice assignment must be from ' | ||
925 | 'unique keys') | ||
926 | self._main.insert(i, k, v) | ||
927 | else: | ||
928 | raise ValueError('Cannot assign to keys') | ||
929 | |||
930 | ### following methods pinched from UserList and adapted ### | ||
931 | def __repr__(self): return repr(self._main._sequence) | ||
932 | |||
933 | # FIXME: do we need to check if we are comparing with another ``Keys`` | ||
934 | # object? (like the __cast method of UserList) | ||
935 | def __lt__(self, other): return self._main._sequence < other | ||
936 | def __le__(self, other): return self._main._sequence <= other | ||
937 | def __eq__(self, other): return self._main._sequence == other | ||
938 | def __ne__(self, other): return self._main._sequence != other | ||
939 | def __gt__(self, other): return self._main._sequence > other | ||
940 | def __ge__(self, other): return self._main._sequence >= other | ||
941 | # FIXME: do we need __cmp__ as well as rich comparisons? | ||
942 | def __cmp__(self, other): return cmp(self._main._sequence, other) | ||
943 | |||
944 | def __contains__(self, item): return item in self._main._sequence | ||
945 | def __len__(self): return len(self._main._sequence) | ||
946 | def __iter__(self): return self._main.iterkeys() | ||
947 | def count(self, item): return self._main._sequence.count(item) | ||
948 | def index(self, item, *args): return self._main._sequence.index(item, *args) | ||
949 | def reverse(self): self._main._sequence.reverse() | ||
950 | def sort(self, *args, **kwds): self._main._sequence.sort(*args, **kwds) | ||
951 | def __mul__(self, n): return self._main._sequence*n | ||
952 | __rmul__ = __mul__ | ||
953 | def __add__(self, other): return self._main._sequence + other | ||
954 | def __radd__(self, other): return other + self._main._sequence | ||
955 | |||
956 | ## following methods not implemented for keys ## | ||
957 | def __delitem__(self, i): raise TypeError('Can\'t delete items from keys') | ||
958 | def __iadd__(self, other): raise TypeError('Can\'t add in place to keys') | ||
959 | def __imul__(self, n): raise TypeError('Can\'t multiply keys in place') | ||
960 | def append(self, item): raise TypeError('Can\'t append items to keys') | ||
961 | def insert(self, i, item): raise TypeError('Can\'t insert items into keys') | ||
962 | def pop(self, i=-1): raise TypeError('Can\'t pop items from keys') | ||
963 | def remove(self, item): raise TypeError('Can\'t remove items from keys') | ||
964 | def extend(self, other): raise TypeError('Can\'t extend keys') | ||
965 | |||
966 | class Items(object): | ||
967 | """ | ||
968 | Custom object for accessing the items of an OrderedDict. | ||
969 | |||
970 | Can be called like the normal ``OrderedDict.items`` method, but also | ||
971 | supports indexing and sequence methods. | ||
972 | """ | ||
973 | |||
974 | def __init__(self, main): | ||
975 | self._main = main | ||
976 | |||
977 | def __call__(self): | ||
978 | """Pretend to be the items method.""" | ||
979 | return self._main._items() | ||
980 | |||
981 | def __getitem__(self, index): | ||
982 | """Fetch the item at position i.""" | ||
983 | if isinstance(index, types.SliceType): | ||
984 | # fetching a slice returns an OrderedDict | ||
985 | return self._main[index].items() | ||
986 | key = self._main._sequence[index] | ||
987 | return (key, self._main[key]) | ||
988 | |||
989 | def __setitem__(self, index, item): | ||
990 | """Set item at position i to item.""" | ||
991 | if isinstance(index, types.SliceType): | ||
992 | # NOTE: item must be an iterable (list of tuples) | ||
993 | self._main[index] = OrderedDict(item) | ||
994 | else: | ||
995 | # FIXME: Does this raise a sensible error? | ||
996 | orig = self._main.keys[index] | ||
997 | key, value = item | ||
998 | if self._main.strict and key in self and (key != orig): | ||
999 | raise ValueError('slice assignment must be from ' | ||
1000 | 'unique keys') | ||
1001 | # delete the current one | ||
1002 | del self._main[self._main._sequence[index]] | ||
1003 | self._main.insert(index, key, value) | ||
1004 | |||
1005 | def __delitem__(self, i): | ||
1006 | """Delete the item at position i.""" | ||
1007 | key = self._main._sequence[i] | ||
1008 | if isinstance(i, types.SliceType): | ||
1009 | for k in key: | ||
1010 | # FIXME: efficiency? | ||
1011 | del self._main[k] | ||
1012 | else: | ||
1013 | del self._main[key] | ||
1014 | |||
1015 | ### following methods pinched from UserList and adapted ### | ||
1016 | def __repr__(self): return repr(self._main.items()) | ||
1017 | |||
1018 | # FIXME: do we need to check if we are comparing with another ``Items`` | ||
1019 | # object? (like the __cast method of UserList) | ||
1020 | def __lt__(self, other): return self._main.items() < other | ||
1021 | def __le__(self, other): return self._main.items() <= other | ||
1022 | def __eq__(self, other): return self._main.items() == other | ||
1023 | def __ne__(self, other): return self._main.items() != other | ||
1024 | def __gt__(self, other): return self._main.items() > other | ||
1025 | def __ge__(self, other): return self._main.items() >= other | ||
1026 | def __cmp__(self, other): return cmp(self._main.items(), other) | ||
1027 | |||
1028 | def __contains__(self, item): return item in self._main.items() | ||
1029 | def __len__(self): return len(self._main._sequence) # easier :-) | ||
1030 | def __iter__(self): return self._main.iteritems() | ||
1031 | def count(self, item): return self._main.items().count(item) | ||
1032 | def index(self, item, *args): return self._main.items().index(item, *args) | ||
1033 | def reverse(self): self._main.reverse() | ||
1034 | def sort(self, *args, **kwds): self._main.sort(*args, **kwds) | ||
1035 | def __mul__(self, n): return self._main.items()*n | ||
1036 | __rmul__ = __mul__ | ||
1037 | def __add__(self, other): return self._main.items() + other | ||
1038 | def __radd__(self, other): return other + self._main.items() | ||
1039 | |||
1040 | def append(self, item): | ||
1041 | """Add an item to the end.""" | ||
1042 | # FIXME: this is only append if the key isn't already present | ||
1043 | key, value = item | ||
1044 | self._main[key] = value | ||
1045 | |||
1046 | def insert(self, i, item): | ||
1047 | key, value = item | ||
1048 | self._main.insert(i, key, value) | ||
1049 | |||
1050 | def pop(self, i=-1): | ||
1051 | key = self._main._sequence[i] | ||
1052 | return (key, self._main.pop(key)) | ||
1053 | |||
1054 | def remove(self, item): | ||
1055 | key, value = item | ||
1056 | try: | ||
1057 | assert value == self._main[key] | ||
1058 | except (KeyError, AssertionError): | ||
1059 | raise ValueError('ValueError: list.remove(x): x not in list') | ||
1060 | else: | ||
1061 | del self._main[key] | ||
1062 | |||
1063 | def extend(self, other): | ||
1064 | # FIXME: is only a true extend if none of the keys already present | ||
1065 | for item in other: | ||
1066 | key, value = item | ||
1067 | self._main[key] = value | ||
1068 | |||
1069 | def __iadd__(self, other): | ||
1070 | self.extend(other) | ||
1071 | |||
1072 | ## following methods not implemented for items ## | ||
1073 | |||
1074 | def __imul__(self, n): raise TypeError('Can\'t multiply items in place') | ||
1075 | |||
1076 | class Values(object): | ||
1077 | """ | ||
1078 | Custom object for accessing the values of an OrderedDict. | ||
1079 | |||
1080 | Can be called like the normal ``OrderedDict.values`` method, but also | ||
1081 | supports indexing and sequence methods. | ||
1082 | """ | ||
1083 | |||
1084 | def __init__(self, main): | ||
1085 | self._main = main | ||
1086 | |||
1087 | def __call__(self): | ||
1088 | """Pretend to be the values method.""" | ||
1089 | return self._main._values() | ||
1090 | |||
1091 | def __getitem__(self, index): | ||
1092 | """Fetch the value at position i.""" | ||
1093 | if isinstance(index, types.SliceType): | ||
1094 | return [self._main[key] for key in self._main._sequence[index]] | ||
1095 | else: | ||
1096 | return self._main[self._main._sequence[index]] | ||
1097 | |||
1098 | def __setitem__(self, index, value): | ||
1099 | """ | ||
1100 | Set the value at position i to value. | ||
1101 | |||
1102 | You can only do slice assignment to values if you supply a sequence of | ||
1103 | equal length to the slice you are replacing. | ||
1104 | """ | ||
1105 | if isinstance(index, types.SliceType): | ||
1106 | keys = self._main._sequence[index] | ||
1107 | if len(keys) != len(value): | ||
1108 | raise ValueError('attempt to assign sequence of size %s ' | ||
1109 | 'to slice of size %s' % (len(name), len(keys))) | ||
1110 | # FIXME: efficiency? Would be better to calculate the indexes | ||
1111 | # directly from the slice object | ||
1112 | # NOTE: the new keys can collide with existing keys (or even | ||
1113 | # contain duplicates) - these will overwrite | ||
1114 | for key, val in zip(keys, value): | ||
1115 | self._main[key] = val | ||
1116 | else: | ||
1117 | self._main[self._main._sequence[index]] = value | ||
1118 | |||
1119 | ### following methods pinched from UserList and adapted ### | ||
1120 | def __repr__(self): return repr(self._main.values()) | ||
1121 | |||
1122 | # FIXME: do we need to check if we are comparing with another ``Values`` | ||
1123 | # object? (like the __cast method of UserList) | ||
1124 | def __lt__(self, other): return self._main.values() < other | ||
1125 | def __le__(self, other): return self._main.values() <= other | ||
1126 | def __eq__(self, other): return self._main.values() == other | ||
1127 | def __ne__(self, other): return self._main.values() != other | ||
1128 | def __gt__(self, other): return self._main.values() > other | ||
1129 | def __ge__(self, other): return self._main.values() >= other | ||
1130 | def __cmp__(self, other): return cmp(self._main.values(), other) | ||
1131 | |||
1132 | def __contains__(self, item): return item in self._main.values() | ||
1133 | def __len__(self): return len(self._main._sequence) # easier :-) | ||
1134 | def __iter__(self): return self._main.itervalues() | ||
1135 | def count(self, item): return self._main.values().count(item) | ||
1136 | def index(self, item, *args): return self._main.values().index(item, *args) | ||
1137 | |||
1138 | def reverse(self): | ||
1139 | """Reverse the values""" | ||
1140 | vals = self._main.values() | ||
1141 | vals.reverse() | ||
1142 | # FIXME: efficiency | ||
1143 | self[:] = vals | ||
1144 | |||
1145 | def sort(self, *args, **kwds): | ||
1146 | """Sort the values.""" | ||
1147 | vals = self._main.values() | ||
1148 | vals.sort(*args, **kwds) | ||
1149 | self[:] = vals | ||
1150 | |||
1151 | def __mul__(self, n): return self._main.values()*n | ||
1152 | __rmul__ = __mul__ | ||
1153 | def __add__(self, other): return self._main.values() + other | ||
1154 | def __radd__(self, other): return other + self._main.values() | ||
1155 | |||
1156 | ## following methods not implemented for values ## | ||
1157 | def __delitem__(self, i): raise TypeError('Can\'t delete items from values') | ||
1158 | def __iadd__(self, other): raise TypeError('Can\'t add in place to values') | ||
1159 | def __imul__(self, n): raise TypeError('Can\'t multiply values in place') | ||
1160 | def append(self, item): raise TypeError('Can\'t append items to values') | ||
1161 | def insert(self, i, item): raise TypeError('Can\'t insert items into values') | ||
1162 | def pop(self, i=-1): raise TypeError('Can\'t pop items from values') | ||
1163 | def remove(self, item): raise TypeError('Can\'t remove items from values') | ||
1164 | def extend(self, other): raise TypeError('Can\'t extend values') | ||
1165 | |||
1166 | class SequenceOrderedDict(OrderedDict): | ||
1167 | """ | ||
1168 | Experimental version of OrderedDict that has a custom object for ``keys``, | ||
1169 | ``values``, and ``items``. | ||
1170 | |||
1171 | These are callable sequence objects that work as methods, or can be | ||
1172 | manipulated directly as sequences. | ||
1173 | |||
1174 | Test for ``keys``, ``items`` and ``values``. | ||
1175 | |||
1176 | >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4))) | ||
1177 | >>> d | ||
1178 | SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) | ||
1179 | >>> d.keys | ||
1180 | [1, 2, 3] | ||
1181 | >>> d.keys() | ||
1182 | [1, 2, 3] | ||
1183 | >>> d.setkeys((3, 2, 1)) | ||
1184 | >>> d | ||
1185 | SequenceOrderedDict([(3, 4), (2, 3), (1, 2)]) | ||
1186 | >>> d.setkeys((1, 2, 3)) | ||
1187 | >>> d.keys[0] | ||
1188 | 1 | ||
1189 | >>> d.keys[:] | ||
1190 | [1, 2, 3] | ||
1191 | >>> d.keys[-1] | ||
1192 | 3 | ||
1193 | >>> d.keys[-2] | ||
1194 | 2 | ||
1195 | >>> d.keys[0:2] = [2, 1] | ||
1196 | >>> d | ||
1197 | SequenceOrderedDict([(2, 3), (1, 2), (3, 4)]) | ||
1198 | >>> d.keys.reverse() | ||
1199 | >>> d.keys | ||
1200 | [3, 1, 2] | ||
1201 | >>> d.keys = [1, 2, 3] | ||
1202 | >>> d | ||
1203 | SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) | ||
1204 | >>> d.keys = [3, 1, 2] | ||
1205 | >>> d | ||
1206 | SequenceOrderedDict([(3, 4), (1, 2), (2, 3)]) | ||
1207 | >>> a = SequenceOrderedDict() | ||
1208 | >>> b = SequenceOrderedDict() | ||
1209 | >>> a.keys == b.keys | ||
1210 | 1 | ||
1211 | >>> a['a'] = 3 | ||
1212 | >>> a.keys == b.keys | ||
1213 | 0 | ||
1214 | >>> b['a'] = 3 | ||
1215 | >>> a.keys == b.keys | ||
1216 | 1 | ||
1217 | >>> b['b'] = 3 | ||
1218 | >>> a.keys == b.keys | ||
1219 | 0 | ||
1220 | >>> a.keys > b.keys | ||
1221 | 0 | ||
1222 | >>> a.keys < b.keys | ||
1223 | 1 | ||
1224 | >>> 'a' in a.keys | ||
1225 | 1 | ||
1226 | >>> len(b.keys) | ||
1227 | 2 | ||
1228 | >>> 'c' in d.keys | ||
1229 | 0 | ||
1230 | >>> 1 in d.keys | ||
1231 | 1 | ||
1232 | >>> [v for v in d.keys] | ||
1233 | [3, 1, 2] | ||
1234 | >>> d.keys.sort() | ||
1235 | >>> d.keys | ||
1236 | [1, 2, 3] | ||
1237 | >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)), strict=True) | ||
1238 | >>> d.keys[::-1] = [1, 2, 3] | ||
1239 | >>> d | ||
1240 | SequenceOrderedDict([(3, 4), (2, 3), (1, 2)]) | ||
1241 | >>> d.keys[:2] | ||
1242 | [3, 2] | ||
1243 | >>> d.keys[:2] = [1, 3] | ||
1244 | Traceback (most recent call last): | ||
1245 | KeyError: 'Keylist is not the same as current keylist.' | ||
1246 | |||
1247 | >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4))) | ||
1248 | >>> d | ||
1249 | SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) | ||
1250 | >>> d.values | ||
1251 | [2, 3, 4] | ||
1252 | >>> d.values() | ||
1253 | [2, 3, 4] | ||
1254 | >>> d.setvalues((4, 3, 2)) | ||
1255 | >>> d | ||
1256 | SequenceOrderedDict([(1, 4), (2, 3), (3, 2)]) | ||
1257 | >>> d.values[::-1] | ||
1258 | [2, 3, 4] | ||
1259 | >>> d.values[0] | ||
1260 | 4 | ||
1261 | >>> d.values[-2] | ||
1262 | 3 | ||
1263 | >>> del d.values[0] | ||
1264 | Traceback (most recent call last): | ||
1265 | TypeError: Can't delete items from values | ||
1266 | >>> d.values[::2] = [2, 4] | ||
1267 | >>> d | ||
1268 | SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) | ||
1269 | >>> 7 in d.values | ||
1270 | 0 | ||
1271 | >>> len(d.values) | ||
1272 | 3 | ||
1273 | >>> [val for val in d.values] | ||
1274 | [2, 3, 4] | ||
1275 | >>> d.values[-1] = 2 | ||
1276 | >>> d.values.count(2) | ||
1277 | 2 | ||
1278 | >>> d.values.index(2) | ||
1279 | 0 | ||
1280 | >>> d.values[-1] = 7 | ||
1281 | >>> d.values | ||
1282 | [2, 3, 7] | ||
1283 | >>> d.values.reverse() | ||
1284 | >>> d.values | ||
1285 | [7, 3, 2] | ||
1286 | >>> d.values.sort() | ||
1287 | >>> d.values | ||
1288 | [2, 3, 7] | ||
1289 | >>> d.values.append('anything') | ||
1290 | Traceback (most recent call last): | ||
1291 | TypeError: Can't append items to values | ||
1292 | >>> d.values = (1, 2, 3) | ||
1293 | >>> d | ||
1294 | SequenceOrderedDict([(1, 1), (2, 2), (3, 3)]) | ||
1295 | |||
1296 | >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4))) | ||
1297 | >>> d | ||
1298 | SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) | ||
1299 | >>> d.items() | ||
1300 | [(1, 2), (2, 3), (3, 4)] | ||
1301 | >>> d.setitems([(3, 4), (2 ,3), (1, 2)]) | ||
1302 | >>> d | ||
1303 | SequenceOrderedDict([(3, 4), (2, 3), (1, 2)]) | ||
1304 | >>> d.items[0] | ||
1305 | (3, 4) | ||
1306 | >>> d.items[:-1] | ||
1307 | [(3, 4), (2, 3)] | ||
1308 | >>> d.items[1] = (6, 3) | ||
1309 | >>> d.items | ||
1310 | [(3, 4), (6, 3), (1, 2)] | ||
1311 | >>> d.items[1:2] = [(9, 9)] | ||
1312 | >>> d | ||
1313 | SequenceOrderedDict([(3, 4), (9, 9), (1, 2)]) | ||
1314 | >>> del d.items[1:2] | ||
1315 | >>> d | ||
1316 | SequenceOrderedDict([(3, 4), (1, 2)]) | ||
1317 | >>> (3, 4) in d.items | ||
1318 | 1 | ||
1319 | >>> (4, 3) in d.items | ||
1320 | 0 | ||
1321 | >>> len(d.items) | ||
1322 | 2 | ||
1323 | >>> [v for v in d.items] | ||
1324 | [(3, 4), (1, 2)] | ||
1325 | >>> d.items.count((3, 4)) | ||
1326 | 1 | ||
1327 | >>> d.items.index((1, 2)) | ||
1328 | 1 | ||
1329 | >>> d.items.index((2, 1)) | ||
1330 | Traceback (most recent call last): | ||
1331 | ValueError: list.index(x): x not in list | ||
1332 | >>> d.items.reverse() | ||
1333 | >>> d.items | ||
1334 | [(1, 2), (3, 4)] | ||
1335 | >>> d.items.reverse() | ||
1336 | >>> d.items.sort() | ||
1337 | >>> d.items | ||
1338 | [(1, 2), (3, 4)] | ||
1339 | >>> d.items.append((5, 6)) | ||
1340 | >>> d.items | ||
1341 | [(1, 2), (3, 4), (5, 6)] | ||
1342 | >>> d.items.insert(0, (0, 0)) | ||
1343 | >>> d.items | ||
1344 | [(0, 0), (1, 2), (3, 4), (5, 6)] | ||
1345 | >>> d.items.insert(-1, (7, 8)) | ||
1346 | >>> d.items | ||
1347 | [(0, 0), (1, 2), (3, 4), (7, 8), (5, 6)] | ||
1348 | >>> d.items.pop() | ||
1349 | (5, 6) | ||
1350 | >>> d.items | ||
1351 | [(0, 0), (1, 2), (3, 4), (7, 8)] | ||
1352 | >>> d.items.remove((1, 2)) | ||
1353 | >>> d.items | ||
1354 | [(0, 0), (3, 4), (7, 8)] | ||
1355 | >>> d.items.extend([(1, 2), (5, 6)]) | ||
1356 | >>> d.items | ||
1357 | [(0, 0), (3, 4), (7, 8), (1, 2), (5, 6)] | ||
1358 | """ | ||
1359 | |||
1360 | def __init__(self, init_val=(), strict=True): | ||
1361 | OrderedDict.__init__(self, init_val, strict=strict) | ||
1362 | self._keys = self.keys | ||
1363 | self._values = self.values | ||
1364 | self._items = self.items | ||
1365 | self.keys = Keys(self) | ||
1366 | self.values = Values(self) | ||
1367 | self.items = Items(self) | ||
1368 | self._att_dict = { | ||
1369 | 'keys': self.setkeys, | ||
1370 | 'items': self.setitems, | ||
1371 | 'values': self.setvalues, | ||
1372 | } | ||
1373 | |||
1374 | def __setattr__(self, name, value): | ||
1375 | """Protect keys, items, and values.""" | ||
1376 | if not '_att_dict' in self.__dict__: | ||
1377 | object.__setattr__(self, name, value) | ||
1378 | else: | ||
1379 | try: | ||
1380 | fun = self._att_dict[name] | ||
1381 | except KeyError: | ||
1382 | OrderedDict.__setattr__(self, name, value) | ||
1383 | else: | ||
1384 | fun(value) | ||
1385 | |||
1386 | if __name__ == '__main__': | ||
1387 | if INTP_VER < (2, 3): | ||
1388 | raise RuntimeError("Tests require Python v.2.3 or later") | ||
1389 | # turn off warnings for tests | ||
1390 | warnings.filterwarnings('ignore') | ||
1391 | # run the code tests in doctest format | ||
1392 | import doctest | ||
1393 | m = sys.modules.get('__main__') | ||
1394 | globs = m.__dict__.copy() | ||
1395 | globs.update({ | ||
1396 | 'INTP_VER': INTP_VER, | ||
1397 | }) | ||
1398 | doctest.testmod(m, globs=globs) | ||
1399 | |||