1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 """A dict that keeps keys in insertion order"""
18
19 __author__ = ('Nicola Larosa <nico-NoSp@m-tekNico.net>,'
20 'Michael Foord <fuzzyman AT voidspace DOT org DOT uk>')
21
22 __docformat__ = "restructuredtext en"
23
24 __revision__ = '$Id: odict.py 129 2005-09-12 18:15:28Z teknico $'
25
26 __version__ = '0.2.1'
27
28 __all__ = ['OrderedDict', 'SequenceOrderedDict']
29
30 from __future__ import generators
31 from warnings import warn
32 from types import SliceType
33
34 import sys
35 INTP_VER = sys.version_info[:2]
36 if INTP_VER < (2, 2):
37 raise RuntimeError("Python v.2.2 or later needed")
38
40 """
41 A class of dictionary that keeps the insertion order of keys.
42
43 All appropriate methods return keys, items, or values in an ordered way.
44
45 All normal dictionary methods are available. Update and comparison is
46 restricted to other OrderedDict objects.
47
48 Various sequence methods are available, including the ability to explicitly
49 mutate the key ordering.
50
51 __contains__ tests:
52
53 >>> d = OrderedDict(((1, 3),))
54 >>> 1 in d
55 1
56 >>> 4 in d
57 0
58
59 __getitem__ tests:
60
61 >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[2]
62 1
63 >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[4]
64 Traceback (most recent call last):
65 KeyError: 4
66
67 __len__ tests:
68
69 >>> len(OrderedDict())
70 0
71 >>> len(OrderedDict(((1, 3), (3, 2), (2, 1))))
72 3
73
74 get tests:
75
76 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
77 >>> d.get(1)
78 3
79 >>> d.get(4) is None
80 1
81 >>> d.get(4, 5)
82 5
83 >>> d
84 OrderedDict([(1, 3), (3, 2), (2, 1)])
85
86 has_key tests:
87
88 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
89 >>> d.has_key(1)
90 1
91 >>> d.has_key(4)
92 0
93 """
94
95 - def __init__(self, init_val=(), strict=False):
96 """
97 Create a new ordered dictionary. Cannot init from a normal dict,
98 nor from kwargs, since items order is undefined in those cases.
99
100 If the ``strict`` keyword argument is ``True`` (``False`` is the
101 default) then when doing slice assignment - the ``OrderedDict`` you are
102 assigning from *must not* contain any keys in the remaining dict.
103
104 >>> OrderedDict()
105 OrderedDict([])
106 >>> OrderedDict({1: 1})
107 Traceback (most recent call last):
108 TypeError: undefined order, cannot get items from dict
109 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
110 >>> d
111 OrderedDict([(1, 3), (3, 2), (2, 1)])
112 >>> OrderedDict(d)
113 OrderedDict([(1, 3), (3, 2), (2, 1)])
114 """
115 self.strict = strict
116 dict.__init__(self)
117 if isinstance(init_val, OrderedDict):
118 self._sequence = init_val.keys()
119 dict.update(self, init_val)
120 elif isinstance(init_val, dict):
121
122 raise TypeError('undefined order, cannot get items from dict')
123 else:
124 self._sequence = []
125
126
127
128
129 idx = 0
130
131 for item in init_val:
132 try:
133 key, val = item
134 except TypeError:
135 raise TypeError('cannot convert dictionary update'
136 ' sequence element #%d to a sequence' % idx)
137 self[key] = val
138 idx += 1
139
140
141
143 """
144 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
145 >>> del d[3]
146 >>> d
147 OrderedDict([(1, 3), (2, 1)])
148 >>> del d[3]
149 Traceback (most recent call last):
150 KeyError: 3
151 >>> d[3] = 2
152 >>> d
153 OrderedDict([(1, 3), (2, 1), (3, 2)])
154 >>> del d[0:1]
155 >>> d
156 OrderedDict([(2, 1), (3, 2)])
157 """
158 if isinstance(key, SliceType):
159
160 keys = self._sequence[key]
161 for entry in keys:
162 dict.__delitem__(self, entry)
163 del self._sequence[key]
164 else:
165
166
167 dict.__delitem__(self, key)
168 self._sequence.remove(key)
169
171 """
172 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
173 >>> d == OrderedDict(d)
174 1
175 >>> d == OrderedDict(((1, 3), (2, 1), (3, 2)))
176 0
177 >>> d == OrderedDict(((1, 0), (3, 2), (2, 1)))
178 0
179 >>> d == OrderedDict(((0, 3), (3, 2), (2, 1)))
180 0
181 >>> d == dict(d)
182 Traceback (most recent call last):
183 TypeError: Equality undefined for OrderedDicts and dictionaries
184 >>> d == False
185 0
186 """
187 if isinstance(other, dict):
188 if not isinstance(other, OrderedDict):
189 raise TypeError('Equality undefined for OrderedDicts and '
190 'dictionaries')
191
192
193 return (self.items() == other.items())
194 else:
195 return False
196
198 """
199 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
200 >>> c = OrderedDict(((0, 3), (3, 2), (2, 1)))
201 >>> c < d
202 1
203 >>> d < c
204 0
205 >>> d < dict(c)
206 Traceback (most recent call last):
207 TypeError: Can only compare with other OrderedDicts
208 """
209 if not isinstance(other, OrderedDict):
210 raise TypeError('Can only compare with other OrderedDicts')
211
212
213 return (self.items() < other.items())
214
216 """
217 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
218 >>> c = OrderedDict(((0, 3), (3, 2), (2, 1)))
219 >>> e = OrderedDict(d)
220 >>> c <= d
221 1
222 >>> d <= c
223 0
224 >>> d <= dict(c)
225 Traceback (most recent call last):
226 TypeError: Can only compare with other OrderedDicts
227 >>> d <= e
228 1
229 """
230 if not isinstance(other, OrderedDict):
231 raise TypeError('Can only compare with other OrderedDicts')
232
233
234 return (self.items() <= other.items())
235
237 """
238 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
239 >>> d != OrderedDict(d)
240 0
241 >>> d != OrderedDict(((1, 3), (2, 1), (3, 2)))
242 1
243 >>> d != OrderedDict(((1, 0), (3, 2), (2, 1)))
244 1
245 >>> d == OrderedDict(((0, 3), (3, 2), (2, 1)))
246 0
247 >>> d != dict(d)
248 Traceback (most recent call last):
249 TypeError: Inequality undefined for OrderedDicts and dictionaries
250 >>> d != False
251 1
252 """
253 if isinstance(other, dict):
254 if not isinstance(other, OrderedDict):
255 raise TypeError('Inequality undefined for OrderedDicts and '
256 'dictionaries')
257
258
259 return not (self.items() == other.items())
260 else:
261 return True
262
264 """
265 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
266 >>> c = OrderedDict(((0, 3), (3, 2), (2, 1)))
267 >>> d > c
268 1
269 >>> c > d
270 0
271 >>> d > dict(c)
272 Traceback (most recent call last):
273 TypeError: Can only compare with other OrderedDicts
274 """
275 if not isinstance(other, OrderedDict):
276 raise TypeError('Can only compare with other OrderedDicts')
277
278
279 return (self.items() > other.items())
280
282 """
283 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
284 >>> c = OrderedDict(((0, 3), (3, 2), (2, 1)))
285 >>> e = OrderedDict(d)
286 >>> c >= d
287 0
288 >>> d >= c
289 1
290 >>> d >= dict(c)
291 Traceback (most recent call last):
292 TypeError: Can only compare with other OrderedDicts
293 >>> e >= d
294 1
295 """
296 if not isinstance(other, OrderedDict):
297 raise TypeError('Can only compare with other OrderedDicts')
298
299
300 return (self.items() >= other.items())
301
303 """
304 Used for __repr__ and __str__
305
306 >>> r1 = repr(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f'))))
307 >>> r1
308 "OrderedDict([('a', 'b'), ('c', 'd'), ('e', 'f')])"
309 >>> r2 = repr(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd'))))
310 >>> r2
311 "OrderedDict([('a', 'b'), ('e', 'f'), ('c', 'd')])"
312 >>> r1 == str(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f'))))
313 1
314 >>> r2 == str(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd'))))
315 1
316 """
317 return '%s([%s])' % (self.__class__.__name__, ', '.join(
318 ['(%r, %r)' % (key, self[key]) for key in self._sequence]))
319
321 """
322 Allows slice assignment, so long as the slice is an OrderedDict
323 >>> d = OrderedDict()
324 >>> d['a'] = 'b'
325 >>> d['b'] = 'a'
326 >>> d[3] = 12
327 >>> d
328 OrderedDict([('a', 'b'), ('b', 'a'), (3, 12)])
329 >>> d[:] = OrderedDict(((1, 2), (2, 3), (3, 4)))
330 >>> d
331 OrderedDict([(1, 2), (2, 3), (3, 4)])
332 >>> d[::2] = OrderedDict(((7, 8), (9, 10)))
333 >>> d
334 OrderedDict([(7, 8), (2, 3), (9, 10)])
335 >>> d = OrderedDict(((0, 1), (1, 2), (2, 3), (3, 4)))
336 >>> d[1:3] = OrderedDict(((1, 2), (5, 6), (7, 8)))
337 >>> d
338 OrderedDict([(0, 1), (1, 2), (5, 6), (7, 8), (3, 4)])
339 >>> d = OrderedDict(((0, 1), (1, 2), (2, 3), (3, 4)), strict=True)
340 >>> d[1:3] = OrderedDict(((1, 2), (5, 6), (7, 8)))
341 >>> d
342 OrderedDict([(0, 1), (1, 2), (5, 6), (7, 8), (3, 4)])
343
344 >>> a = OrderedDict(((0, 1), (1, 2), (2, 3)), strict=True)
345 >>> a[3] = 4
346 >>> a
347 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
348 >>> a[::1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
349 >>> a
350 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
351 >>> a[:2] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)])
352 Traceback (most recent call last):
353 ValueError: slice assignment must be from unique keys
354 >>> a = OrderedDict(((0, 1), (1, 2), (2, 3)))
355 >>> a[3] = 4
356 >>> a
357 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
358 >>> a[::1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
359 >>> a
360 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
361 >>> a[:2] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
362 >>> a
363 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
364 >>> a[::-1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
365 >>> a
366 OrderedDict([(3, 4), (2, 3), (1, 2), (0, 1)])
367
368 >>> d = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
369 >>> d[:1] = 3
370 Traceback (most recent call last):
371 TypeError: slice assignment requires an OrderedDict
372
373 >>> d = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
374 >>> d[:1] = OrderedDict([(9, 8)])
375 >>> d
376 OrderedDict([(9, 8), (1, 2), (2, 3), (3, 4)])
377 """
378 if isinstance(key, SliceType):
379 if not isinstance(val, OrderedDict):
380
381 raise TypeError('slice assignment requires an OrderedDict')
382 keys = self._sequence[key]
383
384 indexes = range(len(self._sequence))[key]
385 if key.step is None:
386
387
388
389
390 pos = key.start or 0
391 del self[key]
392 newkeys = val.keys()
393 for k in newkeys:
394 if k in self:
395 if self.strict:
396 raise ValueError('slice assignment must be from '
397 'unique keys')
398 else:
399
400
401 del self[k]
402 self._sequence = (self._sequence[:pos] + newkeys +
403 self._sequence[pos:])
404 dict.update(self, val)
405 else:
406
407
408
409 if len(keys) != len(val):
410 raise ValueError('attempt to assign sequence of size %s '
411 'to extended slice of size %s' % (len(val), len(keys)))
412
413 del self[key]
414 item_list = zip(indexes, val.items())
415
416
417 item_list.sort()
418 for pos, (newkey, newval) in item_list:
419 if self.strict and newkey in self:
420 raise ValueError('slice assignment must be from unique'
421 ' keys')
422 self.insert(pos, newkey, newval)
423 else:
424 if not self.has_key(key):
425 self._sequence.append(key)
426 dict.__setitem__(self, key, val)
427
429 """
430 Allows slicing. Returns an OrderedDict if you slice.
431 >>> b = OrderedDict([(7, 0), (6, 1), (5, 2), (4, 3), (3, 4), (2, 5), (1, 6)])
432 >>> b[::-1]
433 OrderedDict([(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)])
434 >>> b[2:5]
435 OrderedDict([(5, 2), (4, 3), (3, 4)])
436 >>> type(b[2:4])
437 <class '__main__.OrderedDict'>
438 """
439 if isinstance(key, SliceType):
440
441 keys = self._sequence[key]
442
443 return OrderedDict([(entry, self[entry]) for entry in keys])
444 else:
445 return dict.__getitem__(self, key)
446
447 __str__ = __repr__
448
450 """
451 Implemented so that accesses to ``sequence`` raise a warning and are
452 diverted to the new ``setkeys`` method.
453 """
454 if name == 'sequence':
455 warn('use of sequence attribute is deprecated. Use keys method '
456 'instead.', DeprecationWarning)
457
458 self.setkeys(value)
459 else:
460
461
462 object.__setattr__(self, name, value)
463
465 """
466 Implemented so that access to ``sequence`` raises a warning.
467
468 >>> d = OrderedDict()
469 >>> d.sequence
470 []
471 """
472 if name == 'sequence':
473 warn('use of sequence attribute is deprecated. Use keys method '
474 'instead.', DeprecationWarning)
475
476
477
478 return self._sequence
479 else:
480
481 raise AttributeError("OrderedDict has no attribute '%s'" % name)
482
484 """
485 To allow deepcopy to work with OrderedDict.
486
487 >>> from copy import deepcopy
488 >>> a = OrderedDict([(1, 1), (2, 2), (3, 3)])
489 >>> a['test'] = {}
490 >>> b = deepcopy(a)
491 >>> b == a
492 1
493 >>> b is a
494 0
495 >>> a['test'] is b['test']
496 0
497 """
498 from copy import deepcopy
499 return self.__class__(deepcopy(self.items(), memo), self.strict)
500
501
502
503
505 """
506 >>> OrderedDict(((1, 3), (3, 2), (2, 1))).copy()
507 OrderedDict([(1, 3), (3, 2), (2, 1)])
508 """
509 return OrderedDict(self)
510
512 """
513 ``items`` returns a list of tuples representing all the
514 ``(key, value)`` pairs in the dictionary.
515
516 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
517 >>> d.items()
518 [(1, 3), (3, 2), (2, 1)]
519 >>> d.clear()
520 >>> d.items()
521 []
522 """
523 return zip(self._sequence, self.values())
524
526 """
527 Return a list of keys in the ``OrderedDict``.
528
529 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
530 >>> d.keys()
531 [1, 3, 2]
532 """
533 return self._sequence[:]
534
535 - def values(self, values=None):
536 """
537 Return a list of all the values in the OrderedDict.
538
539 Optionally you can pass in a list of values, which will replace the
540 current list. The value list must be the same len as the OrderedDict.
541
542 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
543 >>> d.values()
544 [3, 2, 1]
545 """
546 return [self[key] for key in self._sequence]
547
549 """
550 >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iteritems()
551 >>> ii.next()
552 (1, 3)
553 >>> ii.next()
554 (3, 2)
555 >>> ii.next()
556 (2, 1)
557 >>> ii.next()
558 Traceback (most recent call last):
559 StopIteration
560 """
562 keys = self.iterkeys()
563 while True:
564 key = keys.next()
565 yield (key, self[key])
566 return make_iter()
567
569 """
570 >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iterkeys()
571 >>> ii.next()
572 1
573 >>> ii.next()
574 3
575 >>> ii.next()
576 2
577 >>> ii.next()
578 Traceback (most recent call last):
579 StopIteration
580 """
581 return iter(self._sequence)
582
583 __iter__ = iterkeys
584
586 """
587 >>> iv = OrderedDict(((1, 3), (3, 2), (2, 1))).itervalues()
588 >>> iv.next()
589 3
590 >>> iv.next()
591 2
592 >>> iv.next()
593 1
594 >>> iv.next()
595 Traceback (most recent call last):
596 StopIteration
597 """
602 return make_iter()
603
604
605
607 """
608 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
609 >>> d.clear()
610 >>> d
611 OrderedDict([])
612 """
613 dict.clear(self)
614 self._sequence = []
615
616 - def pop(self, key, *args):
617 """
618 No dict.pop in Python 2.2, gotta reimplement it
619
620 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
621 >>> d.pop(3)
622 2
623 >>> d
624 OrderedDict([(1, 3), (2, 1)])
625 >>> d.pop(4)
626 Traceback (most recent call last):
627 KeyError: 4
628 >>> d.pop(4, 0)
629 0
630 >>> d.pop(4, 0, 1)
631 Traceback (most recent call last):
632 TypeError: pop expected at most 2 arguments, got 3
633 """
634 if len(args) > 1:
635 raise TypeError, ('pop expected at most 2 arguments, got %s' %
636 (len(args) + 1))
637 if key in self:
638 val = self[key]
639 del self[key]
640 else:
641 try:
642 val = args[0]
643 except IndexError:
644 raise KeyError(key)
645 return val
646
648 """
649 Delete and return an item specified by index, not a random one as in
650 dict. The index is -1 by default (the last item).
651
652 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
653 >>> d.popitem()
654 (2, 1)
655 >>> d
656 OrderedDict([(1, 3), (3, 2)])
657 >>> d.popitem(0)
658 (1, 3)
659 >>> OrderedDict().popitem()
660 Traceback (most recent call last):
661 KeyError: 'popitem(): dictionary is empty'
662 >>> d.popitem(2)
663 Traceback (most recent call last):
664 IndexError: popitem(): index 2 not valid
665 """
666 if not self._sequence:
667 raise KeyError('popitem(): dictionary is empty')
668 try:
669 key = self._sequence[i]
670 except IndexError:
671 raise IndexError('popitem(): index %s not valid' % i)
672 return (key, self.pop(key))
673
675 """
676 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
677 >>> d.setdefault(1)
678 3
679 >>> d.setdefault(4) is None
680 1
681 >>> d
682 OrderedDict([(1, 3), (3, 2), (2, 1), (4, None)])
683 >>> d.setdefault(5, 0)
684 0
685 >>> d
686 OrderedDict([(1, 3), (3, 2), (2, 1), (4, None), (5, 0)])
687 """
688 if key in self:
689 return self[key]
690 else:
691 self[key] = defval
692 return defval
693
695 """
696 Update from another OrderedDict or sequence of (key, value) pairs
697
698 >>> d = OrderedDict()
699 >>> d.update(OrderedDict(((1, 3), (3, 2), (2, 1))))
700 >>> d
701 OrderedDict([(1, 3), (3, 2), (2, 1)])
702 >>> d.update({4: 4})
703 Traceback (most recent call last):
704 TypeError: undefined order, cannot get items from dict
705 >>> d.update((4, 4))
706 Traceback (most recent call last):
707 TypeError: cannot convert dictionary update sequence element #0 to a sequence
708 """
709 if isinstance(from_od, OrderedDict):
710 for key, val in from_od.items():
711 self[key] = val
712 elif isinstance(from_od, dict):
713
714 raise TypeError('undefined order, cannot get items from dict')
715 else:
716 idx = 0
717
718 for item in from_od:
719 try:
720 key, val = item
721 except TypeError:
722 raise TypeError('cannot convert dictionary update'
723 ' sequence element #%d to a sequence' % idx)
724 self[key] = val
725 idx += 1
726
728 """
729 This method allows you to set the items in the dict.
730
731 It takes a list of tuples - of the same sort returned by the ``items``
732 method.
733
734 >>> d = OrderedDict()
735 >>> d.setitems(((3, 1), (2, 3), (1, 2)))
736 >>> d
737 OrderedDict([(3, 1), (2, 3), (1, 2)])
738 """
739 self.clear()
740
741 self.update(items)
742
744 """
745 ``setkeys`` all ows you to pass in a new list of keys which will
746 replace the current set. This must contain the same set of keys, but
747 need not be in the same order.
748
749 If you pass in new keys that don't match, a ``KeyError`` will be
750 raised.
751
752 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
753 >>> d.keys()
754 [1, 3, 2]
755 >>> d.setkeys((1, 2, 3))
756 >>> d
757 OrderedDict([(1, 3), (2, 1), (3, 2)])
758 >>> d.setkeys(['a', 'b', 'c'])
759 Traceback (most recent call last):
760 KeyError: 'Keylist is not the same as current keylist.'
761 """
762
763
764
765 kcopy = list(keys)
766 kcopy.sort()
767 self._sequence.sort()
768 if kcopy != self._sequence:
769 raise KeyError('Keylist is not the same as current keylist.')
770
771
772
773 self._sequence = list(keys)
774
776 """
777 You can pass in a list of values, which will replace the
778 current list. The value list must be the same len as the OrderedDict.
779
780 (Or a ``ValueError`` is raised.)
781
782 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
783 >>> d.setvalues((1, 2, 3))
784 >>> d
785 OrderedDict([(1, 1), (3, 2), (2, 3)])
786 >>> d.setvalues([6])
787 Traceback (most recent call last):
788 ValueError: Value list is not the same length as the OrderedDict.
789 """
790 if len(values) != len(self):
791
792 raise ValueError('Value list is not the same length as the '
793 'OrderedDict.')
794 self.update(zip(self, values))
795
796
797
799 """
800 Return the position of the specified key in the OrderedDict.
801
802 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
803 >>> d.index(3)
804 1
805 >>> d.index(4)
806 Traceback (most recent call last):
807 ValueError: list.index(x): x not in list
808 """
809 return self._sequence.index(key)
810
811 - def insert(self, index, key, value):
812 """
813 Takes ``index``, ``key``, and ``value`` as arguments.
814
815 Sets ``key`` to ``value``, so that ``key`` is at position ``index`` in
816 the OrderedDict.
817
818 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
819 >>> d.insert(0, 4, 0)
820 >>> d
821 OrderedDict([(4, 0), (1, 3), (3, 2), (2, 1)])
822 >>> d.insert(0, 2, 1)
823 >>> d
824 OrderedDict([(2, 1), (4, 0), (1, 3), (3, 2)])
825 >>> d.insert(8, 8, 1)
826 >>> d
827 OrderedDict([(2, 1), (4, 0), (1, 3), (3, 2), (8, 1)])
828 """
829 if key in self:
830
831 del self[key]
832 self._sequence.insert(index, key)
833 dict.__setitem__(self, key, value)
834
836 """
837 Reverse the order of the OrderedDict.
838
839 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
840 >>> d.reverse()
841 >>> d
842 OrderedDict([(2, 1), (3, 2), (1, 3)])
843 """
844 self._sequence.reverse()
845
846 - def sort(self, *args, **kwargs):
847 """
848 Sort the key order in the OrderedDict.
849
850 This method takes the same arguments as the ``list.sort`` method on
851 your version of Python.
852
853 >>> d = OrderedDict(((4, 1), (2, 2), (3, 3), (1, 4)))
854 >>> d.sort()
855 >>> d
856 OrderedDict([(1, 4), (2, 2), (3, 3), (4, 1)])
857 """
858 self._sequence.sort(*args, **kwargs)
859
861
862 """
863 Custom object for accessing the keys of an OrderedDict.
864
865 Can be called like the normal ``OrderedDict.keys`` method, but also
866 supports indexing and sequence methods.
867 """
868
870 self._main = main
871
873 """Pretend to be the keys method."""
874 return self._main._keys()
875
877 """Fetch the key at position i."""
878
879 return self._main._sequence[index]
880
882 """
883 You cannot assign to keys, but you can do slice assignment to re-order
884 them.
885
886 You can only do slice assignment if the new set of keys is a reordering
887 of the original set.
888 """
889 if isinstance(index, SliceType):
890
891
892 indexes = range(len(self._main._sequence))[index]
893 if len(indexes) != len(name):
894 raise ValueError('attempt to assign sequence of size %s '
895 'to slice of size %s' % (len(name), len(indexes)))
896
897
898 old_keys = self._main._sequence[index]
899 new_keys = list(name)
900 old_keys.sort()
901 new_keys.sort()
902 if old_keys != new_keys:
903 raise KeyError('Keylist is not the same as current keylist.')
904 orig_vals = [self._main[k] for k in name]
905 del self._main[index]
906 vals = zip(indexes, name, orig_vals)
907 vals.sort()
908 for i, k, v in vals:
909 if self._main.strict and k in self._main:
910 raise ValueError('slice assignment must be from '
911 'unique keys')
912 self._main.insert(i, k, v)
913 else:
914 raise ValueError('Cannot assign to keys')
915
916
917 - def __repr__(self): return repr(self._main._sequence)
918
919
920
921 - def __lt__(self, other): return self._main._sequence < other
922 - def __le__(self, other): return self._main._sequence <= other
923 - def __eq__(self, other): return self._main._sequence == other
924 - def __ne__(self, other): return self._main._sequence != other
925 - def __gt__(self, other): return self._main._sequence > other
926 - def __ge__(self, other): return self._main._sequence >= other
927
928 - def __cmp__(self, other): return cmp(self._main._sequence, other)
929
930 - def __contains__(self, item): return item in self._main._sequence
931 - def __len__(self): return len(self._main._sequence)
933 - def count(self, item): return self._main._sequence.count(item)
934 - def index(self, item, *args): return self._main._sequence.index(item, *args)
936 - def sort(self, *args, **kwds): self._main._sequence.sort(*args, **kwds)
937 - def __mul__(self, n): return self._main._sequence*n
938 __rmul__ = __mul__
939 - def __add__(self, other): return self._main._sequence + other
940 - def __radd__(self, other): return other + self._main._sequence
941
942
943 - def __delitem__(self, i): raise TypeError('Can\'t delete items from keys')
944 - def __iadd__(self, other): raise TypeError('Can\'t add in place to keys')
945 - def __imul__(self, n): raise TypeError('Can\'t multiply keys in place')
946 - def append(self, item): raise TypeError('Can\'t append items to keys')
947 - def insert(self, i, item): raise TypeError('Can\'t insert items into keys')
948 - def pop(self, i=-1): raise TypeError('Can\'t pop items from keys')
949 - def remove(self, item): raise TypeError('Can\'t remove items from keys')
950 - def extend(self, other): raise TypeError('Can\'t extend keys')
951
953 """
954 Custom object for accessing the items of an OrderedDict.
955
956 Can be called like the normal ``OrderedDict.items`` method, but also
957 supports indexing and sequence methods.
958 """
959
961 self._main = main
962
964 """Pretend to be the items method."""
965 return self._main._items()
966
968 """Fetch the item at position i."""
969 if isinstance(index, SliceType):
970
971 return self._main[index].items()
972 key = self._main._sequence[index]
973 return (key, self._main[key])
974
976 """Set item at position i to item."""
977 if isinstance(index, SliceType):
978
979 self._main[index] = OrderedDict(item)
980 else:
981
982 orig = self._main.keys[index]
983 key, value = item
984 if self._main.strict and key in self and (key != orig):
985 raise ValueError('slice assignment must be from '
986 'unique keys')
987
988 del self._main[self._main._sequence[index]]
989 self._main.insert(index, key, value)
990
992 """Delete the item at position i."""
993 key = self._main._sequence[i]
994 if isinstance(i, SliceType):
995 for k in key:
996
997 del self._main[k]
998 else:
999 del self._main[key]
1000
1001
1003
1004
1005
1006 - def __lt__(self, other): return self._main.items() < other
1007 - def __le__(self, other): return self._main.items() <= other
1008 - def __eq__(self, other): return self._main.items() == other
1009 - def __ne__(self, other): return self._main.items() != other
1010 - def __gt__(self, other): return self._main.items() > other
1011 - def __ge__(self, other): return self._main.items() >= other
1012 - def __cmp__(self, other): return cmp(self._main.items(), other)
1013
1015 - def __len__(self): return len(self._main._sequence)
1018 - def index(self, item, *args): return self._main.items().index(item, *args)
1020 - def sort(self, *args, **kwds): self._main.sort(*args, **kwds)
1022 __rmul__ = __mul__
1023 - def __add__(self, other): return self._main.items() + other
1025
1027 """Add an item to the end."""
1028
1029 key, value = item
1030 self._main[key] = value
1031
1033 key, value = item
1034 self._main.insert(i, key, value)
1035
1036 - def pop(self, i=-1):
1037 key = self._main._sequence[i]
1038 return (key, self._main.pop(key))
1039
1041 key, value = item
1042 try:
1043 assert value == self._main[key]
1044 except (KeyError, AssertionError):
1045 raise ValueError('ValueError: list.remove(x): x not in list')
1046 else:
1047 del self._main[key]
1048
1050
1051 for item in other:
1052 key, value = item
1053 self._main[key] = value
1054
1057
1058
1059
1060 - def __imul__(self, n): raise TypeError('Can\'t multiply items in place')
1061
1062
1064 """
1065 Custom object for accessing the values of an OrderedDict.
1066
1067 Can be called like the normal ``OrderedDict.values`` method, but also
1068 supports indexing and sequence methods.
1069 """
1070
1072 self._main = main
1073
1075 """Pretend to be the values method."""
1076 return self._main._values()
1077
1079 """Fetch the value at position i."""
1080 if isinstance(index, SliceType):
1081 return [self._main[key] for key in self._main._sequence[index]]
1082 else:
1083 return self._main[self._main._sequence[index]]
1084
1086 """
1087 Set the value at position i to value.
1088
1089 You can only do slice assignment to values if you supply a sequence of
1090 equal length to the slice you are replacing.
1091 """
1092 if isinstance(index, SliceType):
1093 keys = self._main._sequence[index]
1094 if len(keys) != len(value):
1095 raise ValueError('attempt to assign sequence of size %s '
1096 'to slice of size %s' % (len(name), len(keys)))
1097
1098
1099
1100
1101 for key, val in zip(keys, value):
1102 self._main[key] = val
1103 else:
1104 self._main[self._main._sequence[index]] = value
1105
1106
1108
1109
1110
1111 - def __lt__(self, other): return self._main.values() < other
1112 - def __le__(self, other): return self._main.values() <= other
1113 - def __eq__(self, other): return self._main.values() == other
1114 - def __ne__(self, other): return self._main.values() != other
1115 - def __gt__(self, other): return self._main.values() > other
1116 - def __ge__(self, other): return self._main.values() >= other
1117 - def __cmp__(self, other): return cmp(self._main.values(), other)
1118
1120 - def __len__(self): return len(self._main._sequence)
1124
1126 """Reverse the values"""
1127 vals = self._main.values()
1128 vals.reverse()
1129
1130 self[:] = vals
1131
1132 - def sort(self, *args, **kwds):
1133 """Sort the values."""
1134 vals = self._main.values()
1135 vals.sort(*args, **kwds)
1136 self[:] = vals
1137
1139 __rmul__ = __mul__
1142
1143
1144 - def __delitem__(self, i): raise TypeError('Can\'t delete items from values')
1145 - def __iadd__(self, other): raise TypeError('Can\'t add in place to values')
1146 - def __imul__(self, n): raise TypeError('Can\'t multiply values in place')
1147 - def append(self, item): raise TypeError('Can\'t append items to values')
1148 - def insert(self, i, item): raise TypeError('Can\'t insert items into values')
1149 - def pop(self, i=-1): raise TypeError('Can\'t pop items from values')
1150 - def remove(self, item): raise TypeError('Can\'t remove items from values')
1151 - def extend(self, other): raise TypeError('Can\'t extend values')
1152
1153
1155 """
1156 Experimental version of OrderedDict that has a custom object for ``keys``,
1157 ``values``, and ``items``.
1158
1159 These are callable sequence objects that work as methods, or can be
1160 manipulated directly as sequences.
1161
1162 Test for ``keys``, ``items`` and ``values``.
1163
1164 >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)))
1165 >>> d
1166 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
1167 >>> d.keys
1168 [1, 2, 3]
1169 >>> d.keys()
1170 [1, 2, 3]
1171 >>> d.setkeys((3, 2, 1))
1172 >>> d
1173 SequenceOrderedDict([(3, 4), (2, 3), (1, 2)])
1174 >>> d.setkeys((1, 2, 3))
1175 >>> d.keys[0]
1176 1
1177 >>> d.keys[:]
1178 [1, 2, 3]
1179 >>> d.keys[-1]
1180 3
1181 >>> d.keys[-2]
1182 2
1183 >>> d.keys[0:2] = [2, 1]
1184 >>> d
1185 SequenceOrderedDict([(2, 3), (1, 2), (3, 4)])
1186 >>> d.keys.reverse()
1187 >>> d.keys
1188 [3, 1, 2]
1189 >>> d.keys = [1, 2, 3]
1190 >>> d
1191 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
1192 >>> d.keys = [3, 1, 2]
1193 >>> d
1194 SequenceOrderedDict([(3, 4), (1, 2), (2, 3)])
1195 >>> a = SequenceOrderedDict()
1196 >>> b = SequenceOrderedDict()
1197 >>> a.keys == b.keys
1198 1
1199 >>> a['a'] = 3
1200 >>> a.keys == b.keys
1201 0
1202 >>> b['a'] = 3
1203 >>> a.keys == b.keys
1204 1
1205 >>> b['b'] = 3
1206 >>> a.keys == b.keys
1207 0
1208 >>> a.keys > b.keys
1209 0
1210 >>> a.keys < b.keys
1211 1
1212 >>> 'a' in a.keys
1213 1
1214 >>> len(b.keys)
1215 2
1216 >>> 'c' in d.keys
1217 0
1218 >>> 1 in d.keys
1219 1
1220 >>> [v for v in d.keys]
1221 [3, 1, 2]
1222 >>> d.keys.sort()
1223 >>> d.keys
1224 [1, 2, 3]
1225 >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)), strict=True)
1226 >>> d.keys[::-1] = [1, 2, 3]
1227 >>> d
1228 SequenceOrderedDict([(3, 4), (2, 3), (1, 2)])
1229 >>> d.keys[:2]
1230 [3, 2]
1231 >>> d.keys[:2] = [1, 3]
1232 Traceback (most recent call last):
1233 KeyError: 'Keylist is not the same as current keylist.'
1234
1235 >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)))
1236 >>> d
1237 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
1238 >>> d.values
1239 [2, 3, 4]
1240 >>> d.values()
1241 [2, 3, 4]
1242 >>> d.setvalues((4, 3, 2))
1243 >>> d
1244 SequenceOrderedDict([(1, 4), (2, 3), (3, 2)])
1245 >>> d.values[::-1]
1246 [2, 3, 4]
1247 >>> d.values[0]
1248 4
1249 >>> d.values[-2]
1250 3
1251 >>> del d.values[0]
1252 Traceback (most recent call last):
1253 TypeError: Can't delete items from values
1254 >>> d.values[::2] = [2, 4]
1255 >>> d
1256 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
1257 >>> 7 in d.values
1258 0
1259 >>> len(d.values)
1260 3
1261 >>> [val for val in d.values]
1262 [2, 3, 4]
1263 >>> d.values[-1] = 2
1264 >>> d.values.count(2)
1265 2
1266 >>> d.values.index(2)
1267 0
1268 >>> d.values[-1] = 7
1269 >>> d.values
1270 [2, 3, 7]
1271 >>> d.values.reverse()
1272 >>> d.values
1273 [7, 3, 2]
1274 >>> d.values.sort()
1275 >>> d.values
1276 [2, 3, 7]
1277 >>> d.values.append('anything')
1278 Traceback (most recent call last):
1279 TypeError: Can't append items to values
1280 >>> d.values = (1, 2, 3)
1281 >>> d
1282 SequenceOrderedDict([(1, 1), (2, 2), (3, 3)])
1283
1284 >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)))
1285 >>> d
1286 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
1287 >>> d.items()
1288 [(1, 2), (2, 3), (3, 4)]
1289 >>> d.setitems([(3, 4), (2 ,3), (1, 2)])
1290 >>> d
1291 SequenceOrderedDict([(3, 4), (2, 3), (1, 2)])
1292 >>> d.items[0]
1293 (3, 4)
1294 >>> d.items[:-1]
1295 [(3, 4), (2, 3)]
1296 >>> d.items[1] = (6, 3)
1297 >>> d.items
1298 [(3, 4), (6, 3), (1, 2)]
1299 >>> d.items[1:2] = [(9, 9)]
1300 >>> d
1301 SequenceOrderedDict([(3, 4), (9, 9), (1, 2)])
1302 >>> del d.items[1:2]
1303 >>> d
1304 SequenceOrderedDict([(3, 4), (1, 2)])
1305 >>> (3, 4) in d.items
1306 1
1307 >>> (4, 3) in d.items
1308 0
1309 >>> len(d.items)
1310 2
1311 >>> [v for v in d.items]
1312 [(3, 4), (1, 2)]
1313 >>> d.items.count((3, 4))
1314 1
1315 >>> d.items.index((1, 2))
1316 1
1317 >>> d.items.index((2, 1))
1318 Traceback (most recent call last):
1319 ValueError: list.index(x): x not in list
1320 >>> d.items.reverse()
1321 >>> d.items
1322 [(1, 2), (3, 4)]
1323 >>> d.items.reverse()
1324 >>> d.items.sort()
1325 >>> d.items
1326 [(1, 2), (3, 4)]
1327 >>> d.items.append((5, 6))
1328 >>> d.items
1329 [(1, 2), (3, 4), (5, 6)]
1330 >>> d.items.insert(0, (0, 0))
1331 >>> d.items
1332 [(0, 0), (1, 2), (3, 4), (5, 6)]
1333 >>> d.items.insert(-1, (7, 8))
1334 >>> d.items
1335 [(0, 0), (1, 2), (3, 4), (7, 8), (5, 6)]
1336 >>> d.items.pop()
1337 (5, 6)
1338 >>> d.items
1339 [(0, 0), (1, 2), (3, 4), (7, 8)]
1340 >>> d.items.remove((1, 2))
1341 >>> d.items
1342 [(0, 0), (3, 4), (7, 8)]
1343 >>> d.items.extend([(1, 2), (5, 6)])
1344 >>> d.items
1345 [(0, 0), (3, 4), (7, 8), (1, 2), (5, 6)]
1346 """
1347
1348 - def __init__(self, init_val=(), strict=True):
1360
1362 """Protect keys, items, and values."""
1363 if not '_att_dict' in self.__dict__:
1364 object.__setattr__(self, name, value)
1365 else:
1366 try:
1367 fun = self._att_dict[name]
1368 except KeyError:
1369 OrderedDict.__setattr__(self, name, value)
1370 else:
1371 fun(value)
1372
1373 if __name__ == '__main__':
1374
1375 import doctest
1376 m = sys.modules.get('__main__')
1377 globs = m.__dict__.copy()
1378 globs.update({
1379 'INTP_VER': INTP_VER,
1380 })
1381 doctest.testmod(m, globs=globs)
1382
1383 """
1384 ISSUES
1385 ======
1386
1387 Slicing doesn't work in Python 2.2. This is because in 2.2, you can't index
1388 a sequence with a slice object. Could be implemented with ``operator``
1389 slicing functions (which don't support extended slices).
1390
1391 TODO
1392 ====
1393
1394 Addition (``__add__``) ? (This would just be syntactic sugar for
1395 ``update``)
1396
1397 Implement the Python 2.4 arguments (``key`` and ``reverse``) for ``sort``
1398 for Python 2.2 and 2.3 ? (So the interface is stable)
1399
1400 Add sequence methods ``move`` and ``rename`` ? (To change the name of a key
1401 at a specific index, and change the index of a key from one position to
1402 another)
1403
1404 Allow assignment to keys (in ``SequenceOrderedDict``) to rename a key ?
1405
1406 Do I *need* to implement ``__cmp__`` - I don't *think* so ?
1407
1408 Allow slice assignment to ``OrderedDict`` (and `possibly
1409 ``SequenceOrderedDict.items``) from list of tuples as well as from an
1410 ``OrderedDict`` ?
1411
1412 CHANGELOG
1413 =========
1414
1415 2005/12/17
1416 ----------
1417
1418 You can now test for equality and inequality with objects (except for
1419 dictionaries for which it is undefined). This allows you to do tests like :
1420 ::
1421
1422 OrderedDict() == False
1423
1424 Added the ``strict`` keyword, which raises a ``ValueError`` if you do slice
1425 assignment with keys that are already in the dictionary.
1426
1427 Assignment to ``keys`` in ``SequenceOrderedDict`` is now only for
1428 re-ordering the keys.
1429
1430 Fixed bug where slice assignment to ``keys`` could lose information. (and
1431 optimised by slicing ranges to get the indexes we are assigning to instead
1432 of indexing each key).
1433
1434 You change keys, items, and values through new methods ``setkeys``,
1435 ``setitems``, and ``setvalues`` methods.
1436
1437 Minor changes, thanks to Christoph Zwerschke for suggestions.
1438
1439 Added ``__deepcopy__`` method (previously deepcopy failed).
1440
1441 CHanged use of ``slice`` to ``types.SliceType`` for Python 2.2.
1442
1443 0.2.1
1444
1445
1446 2005/12/02
1447 ----------
1448
1449 Fixed bugs in ``__getattr__`` and ``popitem``
1450
1451 Optimisation in ``OrderedDict.__init__`` when creating an instance from an
1452 ``OrderedDict``
1453
1454 Changed ``FancyODict`` to ``SequenceOrderedDict``
1455
1456 Implemented new ``__repr__``
1457
1458 0.2.0
1459
1460 2005/12/01
1461 ----------
1462
1463 Added index to ``OrderedDict.popitem``
1464
1465 2005/11/30
1466 ----------
1467
1468 Implemented ``FancyODict``, which has ``keys``, ``items``, ``values`` as
1469 custom, callable, sequence objects.
1470
1471 2005/11/26
1472 ----------
1473
1474 By Michael Foord - from suggestions on comp.lang.python
1475
1476 Hidden the ``sequence`` attribute
1477
1478 ``items``, ``keys``, ``values`` can now take a list to replace the current
1479 keys, values, or items
1480
1481 Implemented slicing (including deleting a slice and assigning to a slice)
1482
1483 Implemented sequence methods ``sort``, ``reverse``, ``insert``, ``index``
1484
1485 2005/09/10
1486 ----------
1487
1488 By Nicola Larosa, based on code from Tim Wegener
1489 <twegener AT radlogic DOT com DOT au>
1490
1491 Create itervalues and iteritems without creating the list up-front
1492
1493 Added doctests for iter methods, and others.
1494
1495 Optimized __setitem__ to be O(1) rather than O(N)
1496
1497 Removed redefined methods that did not alter dict method behaviour,
1498 related doctests moved to the class docstring
1499
1500 Added support for sequences of (key, value) pairs to update
1501
1502 Removed redundant condition from __eq__
1503
1504 Removed incorrect implementation of __str__
1505
1506 2005/08/28
1507 ----------
1508
1509 By Michael Foord
1510
1511 Added __all__
1512
1513 More than two arguments to ``pop`` now raises an error
1514
1515 Version 0.1.0 finalised
1516
1517 2005/08/13
1518 ----------
1519
1520 By Nicola Larosa
1521
1522 Added doctests everywhere, fixed much part of implementation
1523
1524 Added comments at top, other doc vars
1525
1526 2005/08/01
1527 ----------
1528
1529 By Michael Foord
1530
1531 Type tests changed to isinstance
1532
1533 _keys changed to sequence attribute
1534
1535 Allowed creating a dictionary by passing keyword arguments
1536
1537 Shortened __repr__
1538
1539 Fixed bug in popitem
1540
1541 Other minor changes
1542 """
1543