00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 """A dict that keeps keys in insertion order"""
00018
00019 __author__ = ('Nicola Larosa <nico-NoSp@m-tekNico.net>,'
00020 'Michael Foord <fuzzyman AT voidspace DOT org DOT uk>')
00021
00022 __docformat__ = "restructuredtext en"
00023
00024 __revision__ = '$Id: odict.py 129 2005-09-12 18:15:28Z teknico $'
00025
00026 __version__ = '0.2.1'
00027
00028 __all__ = ['OrderedDict', 'SequenceOrderedDict']
00029
00030 from __future__ import generators
00031 from warnings import warn
00032 from types import SliceType
00033
00034 import sys
00035 INTP_VER = sys.version_info[:2]
00036 if INTP_VER < (2, 2):
00037 raise RuntimeError("Python v.2.2 or later needed")
00038
00039 class OrderedDict(dict):
00040 """
00041 A class of dictionary that keeps the insertion order of keys.
00042
00043 All appropriate methods return keys, items, or values in an ordered way.
00044
00045 All normal dictionary methods are available. Update and comparison is
00046 restricted to other OrderedDict objects.
00047
00048 Various sequence methods are available, including the ability to explicitly
00049 mutate the key ordering.
00050
00051 __contains__ tests:
00052
00053 >>> d = OrderedDict(((1, 3),))
00054 >>> 1 in d
00055 1
00056 >>> 4 in d
00057 0
00058
00059 __getitem__ tests:
00060
00061 >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[2]
00062 1
00063 >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[4]
00064 Traceback (most recent call last):
00065 KeyError: 4
00066
00067 __len__ tests:
00068
00069 >>> len(OrderedDict())
00070 0
00071 >>> len(OrderedDict(((1, 3), (3, 2), (2, 1))))
00072 3
00073
00074 get tests:
00075
00076 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00077 >>> d.get(1)
00078 3
00079 >>> d.get(4) is None
00080 1
00081 >>> d.get(4, 5)
00082 5
00083 >>> d
00084 OrderedDict([(1, 3), (3, 2), (2, 1)])
00085
00086 has_key tests:
00087
00088 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00089 >>> d.has_key(1)
00090 1
00091 >>> d.has_key(4)
00092 0
00093 """
00094
00095 def __init__(self, init_val=(), strict=False):
00096 """
00097 Create a new ordered dictionary. Cannot init from a normal dict,
00098 nor from kwargs, since items order is undefined in those cases.
00099
00100 If the ``strict`` keyword argument is ``True`` (``False`` is the
00101 default) then when doing slice assignment - the ``OrderedDict`` you are
00102 assigning from *must not* contain any keys in the remaining dict.
00103
00104 >>> OrderedDict()
00105 OrderedDict([])
00106 >>> OrderedDict({1: 1})
00107 Traceback (most recent call last):
00108 TypeError: undefined order, cannot get items from dict
00109 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00110 >>> d
00111 OrderedDict([(1, 3), (3, 2), (2, 1)])
00112 >>> OrderedDict(d)
00113 OrderedDict([(1, 3), (3, 2), (2, 1)])
00114 """
00115 self.strict = strict
00116 dict.__init__(self)
00117 if isinstance(init_val, OrderedDict):
00118 self._sequence = init_val.keys()
00119 dict.update(self, init_val)
00120 elif isinstance(init_val, dict):
00121
00122 raise TypeError('undefined order, cannot get items from dict')
00123 else:
00124 self._sequence = []
00125
00126
00127
00128
00129 idx = 0
00130
00131 for item in init_val:
00132 try:
00133 key, val = item
00134 except TypeError:
00135 raise TypeError('cannot convert dictionary update'
00136 ' sequence element #%d to a sequence' % idx)
00137 self[key] = val
00138 idx += 1
00139
00140
00141
00142 def __delitem__(self, key):
00143 """
00144 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00145 >>> del d[3]
00146 >>> d
00147 OrderedDict([(1, 3), (2, 1)])
00148 >>> del d[3]
00149 Traceback (most recent call last):
00150 KeyError: 3
00151 >>> d[3] = 2
00152 >>> d
00153 OrderedDict([(1, 3), (2, 1), (3, 2)])
00154 >>> del d[0:1]
00155 >>> d
00156 OrderedDict([(2, 1), (3, 2)])
00157 """
00158 if isinstance(key, SliceType):
00159
00160 keys = self._sequence[key]
00161 for entry in keys:
00162 dict.__delitem__(self, entry)
00163 del self._sequence[key]
00164 else:
00165
00166
00167 dict.__delitem__(self, key)
00168 self._sequence.remove(key)
00169
00170 def __eq__(self, other):
00171 """
00172 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00173 >>> d == OrderedDict(d)
00174 1
00175 >>> d == OrderedDict(((1, 3), (2, 1), (3, 2)))
00176 0
00177 >>> d == OrderedDict(((1, 0), (3, 2), (2, 1)))
00178 0
00179 >>> d == OrderedDict(((0, 3), (3, 2), (2, 1)))
00180 0
00181 >>> d == dict(d)
00182 Traceback (most recent call last):
00183 TypeError: Equality undefined for OrderedDicts and dictionaries
00184 >>> d == False
00185 0
00186 """
00187 if isinstance(other, dict):
00188 if not isinstance(other, OrderedDict):
00189 raise TypeError('Equality undefined for OrderedDicts and '
00190 'dictionaries')
00191
00192
00193 return (self.items() == other.items())
00194 else:
00195 return False
00196
00197 def __lt__(self, other):
00198 """
00199 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00200 >>> c = OrderedDict(((0, 3), (3, 2), (2, 1)))
00201 >>> c < d
00202 1
00203 >>> d < c
00204 0
00205 >>> d < dict(c)
00206 Traceback (most recent call last):
00207 TypeError: Can only compare with other OrderedDicts
00208 """
00209 if not isinstance(other, OrderedDict):
00210 raise TypeError('Can only compare with other OrderedDicts')
00211
00212
00213 return (self.items() < other.items())
00214
00215 def __le__(self, other):
00216 """
00217 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00218 >>> c = OrderedDict(((0, 3), (3, 2), (2, 1)))
00219 >>> e = OrderedDict(d)
00220 >>> c <= d
00221 1
00222 >>> d <= c
00223 0
00224 >>> d <= dict(c)
00225 Traceback (most recent call last):
00226 TypeError: Can only compare with other OrderedDicts
00227 >>> d <= e
00228 1
00229 """
00230 if not isinstance(other, OrderedDict):
00231 raise TypeError('Can only compare with other OrderedDicts')
00232
00233
00234 return (self.items() <= other.items())
00235
00236 def __ne__(self, other):
00237 """
00238 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00239 >>> d != OrderedDict(d)
00240 0
00241 >>> d != OrderedDict(((1, 3), (2, 1), (3, 2)))
00242 1
00243 >>> d != OrderedDict(((1, 0), (3, 2), (2, 1)))
00244 1
00245 >>> d == OrderedDict(((0, 3), (3, 2), (2, 1)))
00246 0
00247 >>> d != dict(d)
00248 Traceback (most recent call last):
00249 TypeError: Inequality undefined for OrderedDicts and dictionaries
00250 >>> d != False
00251 1
00252 """
00253 if isinstance(other, dict):
00254 if not isinstance(other, OrderedDict):
00255 raise TypeError('Inequality undefined for OrderedDicts and '
00256 'dictionaries')
00257
00258
00259 return not (self.items() == other.items())
00260 else:
00261 return True
00262
00263 def __gt__(self, other):
00264 """
00265 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00266 >>> c = OrderedDict(((0, 3), (3, 2), (2, 1)))
00267 >>> d > c
00268 1
00269 >>> c > d
00270 0
00271 >>> d > dict(c)
00272 Traceback (most recent call last):
00273 TypeError: Can only compare with other OrderedDicts
00274 """
00275 if not isinstance(other, OrderedDict):
00276 raise TypeError('Can only compare with other OrderedDicts')
00277
00278
00279 return (self.items() > other.items())
00280
00281 def __ge__(self, other):
00282 """
00283 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00284 >>> c = OrderedDict(((0, 3), (3, 2), (2, 1)))
00285 >>> e = OrderedDict(d)
00286 >>> c >= d
00287 0
00288 >>> d >= c
00289 1
00290 >>> d >= dict(c)
00291 Traceback (most recent call last):
00292 TypeError: Can only compare with other OrderedDicts
00293 >>> e >= d
00294 1
00295 """
00296 if not isinstance(other, OrderedDict):
00297 raise TypeError('Can only compare with other OrderedDicts')
00298
00299
00300 return (self.items() >= other.items())
00301
00302 def __repr__(self):
00303 """
00304 Used for __repr__ and __str__
00305
00306 >>> r1 = repr(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f'))))
00307 >>> r1
00308 "OrderedDict([('a', 'b'), ('c', 'd'), ('e', 'f')])"
00309 >>> r2 = repr(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd'))))
00310 >>> r2
00311 "OrderedDict([('a', 'b'), ('e', 'f'), ('c', 'd')])"
00312 >>> r1 == str(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f'))))
00313 1
00314 >>> r2 == str(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd'))))
00315 1
00316 """
00317 return '%s([%s])' % (self.__class__.__name__, ', '.join(
00318 ['(%r, %r)' % (key, self[key]) for key in self._sequence]))
00319
00320 def __setitem__(self, key, val):
00321 """
00322 Allows slice assignment, so long as the slice is an OrderedDict
00323 >>> d = OrderedDict()
00324 >>> d['a'] = 'b'
00325 >>> d['b'] = 'a'
00326 >>> d[3] = 12
00327 >>> d
00328 OrderedDict([('a', 'b'), ('b', 'a'), (3, 12)])
00329 >>> d[:] = OrderedDict(((1, 2), (2, 3), (3, 4)))
00330 >>> d
00331 OrderedDict([(1, 2), (2, 3), (3, 4)])
00332 >>> d[::2] = OrderedDict(((7, 8), (9, 10)))
00333 >>> d
00334 OrderedDict([(7, 8), (2, 3), (9, 10)])
00335 >>> d = OrderedDict(((0, 1), (1, 2), (2, 3), (3, 4)))
00336 >>> d[1:3] = OrderedDict(((1, 2), (5, 6), (7, 8)))
00337 >>> d
00338 OrderedDict([(0, 1), (1, 2), (5, 6), (7, 8), (3, 4)])
00339 >>> d = OrderedDict(((0, 1), (1, 2), (2, 3), (3, 4)), strict=True)
00340 >>> d[1:3] = OrderedDict(((1, 2), (5, 6), (7, 8)))
00341 >>> d
00342 OrderedDict([(0, 1), (1, 2), (5, 6), (7, 8), (3, 4)])
00343
00344 >>> a = OrderedDict(((0, 1), (1, 2), (2, 3)), strict=True)
00345 >>> a[3] = 4
00346 >>> a
00347 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00348 >>> a[::1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00349 >>> a
00350 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00351 >>> a[:2] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)])
00352 Traceback (most recent call last):
00353 ValueError: slice assignment must be from unique keys
00354 >>> a = OrderedDict(((0, 1), (1, 2), (2, 3)))
00355 >>> a[3] = 4
00356 >>> a
00357 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00358 >>> a[::1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00359 >>> a
00360 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00361 >>> a[:2] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00362 >>> a
00363 OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00364 >>> a[::-1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00365 >>> a
00366 OrderedDict([(3, 4), (2, 3), (1, 2), (0, 1)])
00367
00368 >>> d = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00369 >>> d[:1] = 3
00370 Traceback (most recent call last):
00371 TypeError: slice assignment requires an OrderedDict
00372
00373 >>> d = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)])
00374 >>> d[:1] = OrderedDict([(9, 8)])
00375 >>> d
00376 OrderedDict([(9, 8), (1, 2), (2, 3), (3, 4)])
00377 """
00378 if isinstance(key, SliceType):
00379 if not isinstance(val, OrderedDict):
00380
00381 raise TypeError('slice assignment requires an OrderedDict')
00382 keys = self._sequence[key]
00383 indexes = range(len(self._sequence))[key]
00384 if key.step is None:
00385
00386
00387
00388
00389 pos = key.start or 0
00390 del self[key]
00391 newkeys = val.keys()
00392 for k in newkeys:
00393 if k in self:
00394 if self.strict:
00395 raise ValueError('slice assignment must be from '
00396 'unique keys')
00397 else:
00398
00399
00400 del self[k]
00401 self._sequence = (self._sequence[:pos] + newkeys +
00402 self._sequence[pos:])
00403 dict.update(self, val)
00404 else:
00405
00406
00407
00408 if len(keys) != len(val):
00409 raise ValueError('attempt to assign sequence of size %s '
00410 'to extended slice of size %s' % (len(val), len(keys)))
00411
00412 del self[key]
00413 item_list = zip(indexes, val.items())
00414
00415
00416 item_list.sort()
00417 for pos, (newkey, newval) in item_list:
00418 if self.strict and newkey in self:
00419 raise ValueError('slice assignment must be from unique'
00420 ' keys')
00421 self.insert(pos, newkey, newval)
00422 else:
00423 if not self.has_key(key):
00424 self._sequence.append(key)
00425 dict.__setitem__(self, key, val)
00426
00427 def __getitem__(self, key):
00428 """
00429 Allows slicing. Returns an OrderedDict if you slice.
00430 >>> b = OrderedDict([(7, 0), (6, 1), (5, 2), (4, 3), (3, 4), (2, 5), (1, 6)])
00431 >>> b[::-1]
00432 OrderedDict([(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)])
00433 >>> b[2:5]
00434 OrderedDict([(5, 2), (4, 3), (3, 4)])
00435 >>> type(b[2:4])
00436 <class '__main__.OrderedDict'>
00437 """
00438 if isinstance(key, SliceType):
00439
00440 keys = self._sequence[key]
00441
00442 return OrderedDict([(entry, self[entry]) for entry in keys])
00443 else:
00444 return dict.__getitem__(self, key)
00445
00446 __str__ = __repr__
00447
00448 def __setattr__(self, name, value):
00449 """
00450 Implemented so that accesses to ``sequence`` raise a warning and are
00451 diverted to the new ``setkeys`` method.
00452 """
00453 if name == 'sequence':
00454 warn('use of sequence attribute is deprecated. Use keys method '
00455 'instead.', DeprecationWarning)
00456
00457 self.setkeys(value)
00458 else:
00459
00460
00461 object.__setattr__(self, name, value)
00462
00463 def __getattr__(self, name):
00464 """
00465 Implemented so that access to ``sequence`` raises a warning.
00466
00467 >>> d = OrderedDict()
00468 >>> d.sequence
00469 []
00470 """
00471 if name == 'sequence':
00472 warn('use of sequence attribute is deprecated. Use keys method '
00473 'instead.', DeprecationWarning)
00474
00475
00476
00477 return self._sequence
00478 else:
00479
00480 raise AttributeError("OrderedDict has no attribute '%s'" % name)
00481
00482 def __deepcopy__(self, memo):
00483 """
00484 To allow deepcopy to work with OrderedDict.
00485
00486 >>> from copy import deepcopy
00487 >>> a = OrderedDict([(1, 1), (2, 2), (3, 3)])
00488 >>> a['test'] = {}
00489 >>> b = deepcopy(a)
00490 >>> b == a
00491 1
00492 >>> b is a
00493 0
00494 >>> a['test'] is b['test']
00495 0
00496 """
00497 from copy import deepcopy
00498 return self.__class__(deepcopy(self.items(), memo), self.strict)
00499
00500
00501
00502
00503 def copy(self):
00504 """
00505 >>> OrderedDict(((1, 3), (3, 2), (2, 1))).copy()
00506 OrderedDict([(1, 3), (3, 2), (2, 1)])
00507 """
00508 return OrderedDict(self)
00509
00510 def items(self):
00511 """
00512 ``items`` returns a list of tuples representing all the
00513 ``(key, value)`` pairs in the dictionary.
00514
00515 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00516 >>> d.items()
00517 [(1, 3), (3, 2), (2, 1)]
00518 >>> d.clear()
00519 >>> d.items()
00520 []
00521 """
00522 return zip(self._sequence, self.values())
00523
00524 def keys(self):
00525 """
00526 Return a list of keys in the ``OrderedDict``.
00527
00528 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00529 >>> d.keys()
00530 [1, 3, 2]
00531 """
00532 return self._sequence[:]
00533
00534 def values(self, values=None):
00535 """
00536 Return a list of all the values in the OrderedDict.
00537
00538 Optionally you can pass in a list of values, which will replace the
00539 current list. The value list must be the same len as the OrderedDict.
00540
00541 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00542 >>> d.values()
00543 [3, 2, 1]
00544 """
00545 return [self[key] for key in self._sequence]
00546
00547 def iteritems(self):
00548 """
00549 >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iteritems()
00550 >>> ii.next()
00551 (1, 3)
00552 >>> ii.next()
00553 (3, 2)
00554 >>> ii.next()
00555 (2, 1)
00556 >>> ii.next()
00557 Traceback (most recent call last):
00558 StopIteration
00559 """
00560 def make_iter(self=self):
00561 keys = self.iterkeys()
00562 while True:
00563 key = keys.next()
00564 yield (key, self[key])
00565 return make_iter()
00566
00567 def iterkeys(self):
00568 """
00569 >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iterkeys()
00570 >>> ii.next()
00571 1
00572 >>> ii.next()
00573 3
00574 >>> ii.next()
00575 2
00576 >>> ii.next()
00577 Traceback (most recent call last):
00578 StopIteration
00579 """
00580 return iter(self._sequence)
00581
00582 __iter__ = iterkeys
00583
00584 def itervalues(self):
00585 """
00586 >>> iv = OrderedDict(((1, 3), (3, 2), (2, 1))).itervalues()
00587 >>> iv.next()
00588 3
00589 >>> iv.next()
00590 2
00591 >>> iv.next()
00592 1
00593 >>> iv.next()
00594 Traceback (most recent call last):
00595 StopIteration
00596 """
00597 def make_iter(self=self):
00598 keys = self.iterkeys()
00599 while True:
00600 yield self[keys.next()]
00601 return make_iter()
00602
00603
00604
00605 def clear(self):
00606 """
00607 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00608 >>> d.clear()
00609 >>> d
00610 OrderedDict([])
00611 """
00612 dict.clear(self)
00613 self._sequence = []
00614
00615 def pop(self, key, *args):
00616 """
00617 No dict.pop in Python 2.2, gotta reimplement it
00618
00619 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00620 >>> d.pop(3)
00621 2
00622 >>> d
00623 OrderedDict([(1, 3), (2, 1)])
00624 >>> d.pop(4)
00625 Traceback (most recent call last):
00626 KeyError: 4
00627 >>> d.pop(4, 0)
00628 0
00629 >>> d.pop(4, 0, 1)
00630 Traceback (most recent call last):
00631 TypeError: pop expected at most 2 arguments, got 3
00632 """
00633 if len(args) > 1:
00634 raise TypeError, ('pop expected at most 2 arguments, got %s' %
00635 (len(args) + 1))
00636 if key in self:
00637 val = self[key]
00638 del self[key]
00639 else:
00640 try:
00641 val = args[0]
00642 except IndexError:
00643 raise KeyError(key)
00644 return val
00645
00646 def popitem(self, i=-1):
00647 """
00648 Delete and return an item specified by index, not a random one as in
00649 dict. The index is -1 by default (the last item).
00650
00651 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00652 >>> d.popitem()
00653 (2, 1)
00654 >>> d
00655 OrderedDict([(1, 3), (3, 2)])
00656 >>> d.popitem(0)
00657 (1, 3)
00658 >>> OrderedDict().popitem()
00659 Traceback (most recent call last):
00660 KeyError: 'popitem(): dictionary is empty'
00661 >>> d.popitem(2)
00662 Traceback (most recent call last):
00663 IndexError: popitem(): index 2 not valid
00664 """
00665 if not self._sequence:
00666 raise KeyError('popitem(): dictionary is empty')
00667 try:
00668 key = self._sequence[i]
00669 except IndexError:
00670 raise IndexError('popitem(): index %s not valid' % i)
00671 return (key, self.pop(key))
00672
00673 def setdefault(self, key, defval = None):
00674 """
00675 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00676 >>> d.setdefault(1)
00677 3
00678 >>> d.setdefault(4) is None
00679 1
00680 >>> d
00681 OrderedDict([(1, 3), (3, 2), (2, 1), (4, None)])
00682 >>> d.setdefault(5, 0)
00683 0
00684 >>> d
00685 OrderedDict([(1, 3), (3, 2), (2, 1), (4, None), (5, 0)])
00686 """
00687 if key in self:
00688 return self[key]
00689 else:
00690 self[key] = defval
00691 return defval
00692
00693 def update(self, from_od):
00694 """
00695 Update from another OrderedDict or sequence of (key, value) pairs
00696
00697 >>> d = OrderedDict()
00698 >>> d.update(OrderedDict(((1, 3), (3, 2), (2, 1))))
00699 >>> d
00700 OrderedDict([(1, 3), (3, 2), (2, 1)])
00701 >>> d.update({4: 4})
00702 Traceback (most recent call last):
00703 TypeError: undefined order, cannot get items from dict
00704 >>> d.update((4, 4))
00705 Traceback (most recent call last):
00706 TypeError: cannot convert dictionary update sequence element #0 to a sequence
00707 """
00708 if isinstance(from_od, OrderedDict):
00709 for key, val in from_od.items():
00710 self[key] = val
00711 elif isinstance(from_od, dict):
00712
00713 raise TypeError('undefined order, cannot get items from dict')
00714 else:
00715 idx = 0
00716
00717 for item in from_od:
00718 try:
00719 key, val = item
00720 except TypeError:
00721 raise TypeError('cannot convert dictionary update'
00722 ' sequence element #%d to a sequence' % idx)
00723 self[key] = val
00724 idx += 1
00725
00726 def setitems(self, items):
00727 """
00728 This method allows you to set the items in the dict.
00729
00730 It takes a list of tuples - of the same sort returned by the ``items``
00731 method.
00732
00733 >>> d = OrderedDict()
00734 >>> d.setitems(((3, 1), (2, 3), (1, 2)))
00735 >>> d
00736 OrderedDict([(3, 1), (2, 3), (1, 2)])
00737 """
00738 self.clear()
00739
00740 self.update(items)
00741
00742 def setkeys(self, keys):
00743 """
00744 ``setkeys`` all ows you to pass in a new list of keys which will
00745 replace the current set. This must contain the same set of keys, but
00746 need not be in the same order.
00747
00748 If you pass in new keys that don't match, a ``KeyError`` will be
00749 raised.
00750
00751 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00752 >>> d.keys()
00753 [1, 3, 2]
00754 >>> d.setkeys((1, 2, 3))
00755 >>> d
00756 OrderedDict([(1, 3), (2, 1), (3, 2)])
00757 >>> d.setkeys(['a', 'b', 'c'])
00758 Traceback (most recent call last):
00759 KeyError: 'Keylist is not the same as current keylist.'
00760 """
00761
00762
00763
00764 kcopy = list(keys)
00765 kcopy.sort()
00766 self._sequence.sort()
00767 if kcopy != self._sequence:
00768 raise KeyError('Keylist is not the same as current keylist.')
00769
00770
00771
00772 self._sequence = list(keys)
00773
00774 def setvalues(self, values):
00775 """
00776 You can pass in a list of values, which will replace the
00777 current list. The value list must be the same len as the OrderedDict.
00778
00779 (Or a ``ValueError`` is raised.)
00780
00781 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00782 >>> d.setvalues((1, 2, 3))
00783 >>> d
00784 OrderedDict([(1, 1), (3, 2), (2, 3)])
00785 >>> d.setvalues([6])
00786 Traceback (most recent call last):
00787 ValueError: Value list is not the same length as the OrderedDict.
00788 """
00789 if len(values) != len(self):
00790
00791 raise ValueError('Value list is not the same length as the '
00792 'OrderedDict.')
00793 self.update(zip(self, values))
00794
00795
00796
00797 def index(self, key):
00798 """
00799 Return the position of the specified key in the OrderedDict.
00800
00801 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00802 >>> d.index(3)
00803 1
00804 >>> d.index(4)
00805 Traceback (most recent call last):
00806 ValueError: list.index(x): x not in list
00807 """
00808 return self._sequence.index(key)
00809
00810 def insert(self, index, key, value):
00811 """
00812 Takes ``index``, ``key``, and ``value`` as arguments.
00813
00814 Sets ``key`` to ``value``, so that ``key`` is at position ``index`` in
00815 the OrderedDict.
00816
00817 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00818 >>> d.insert(0, 4, 0)
00819 >>> d
00820 OrderedDict([(4, 0), (1, 3), (3, 2), (2, 1)])
00821 >>> d.insert(0, 2, 1)
00822 >>> d
00823 OrderedDict([(2, 1), (4, 0), (1, 3), (3, 2)])
00824 >>> d.insert(8, 8, 1)
00825 >>> d
00826 OrderedDict([(2, 1), (4, 0), (1, 3), (3, 2), (8, 1)])
00827 """
00828 if key in self:
00829
00830 del self[key]
00831 self._sequence.insert(index, key)
00832 dict.__setitem__(self, key, value)
00833
00834 def reverse(self):
00835 """
00836 Reverse the order of the OrderedDict.
00837
00838 >>> d = OrderedDict(((1, 3), (3, 2), (2, 1)))
00839 >>> d.reverse()
00840 >>> d
00841 OrderedDict([(2, 1), (3, 2), (1, 3)])
00842 """
00843 self._sequence.reverse()
00844
00845 def sort(self, *args, **kwargs):
00846 """
00847 Sort the key order in the OrderedDict.
00848
00849 This method takes the same arguments as the ``list.sort`` method on
00850 your version of Python.
00851
00852 >>> d = OrderedDict(((4, 1), (2, 2), (3, 3), (1, 4)))
00853 >>> d.sort()
00854 >>> d
00855 OrderedDict([(1, 4), (2, 2), (3, 3), (4, 1)])
00856 """
00857 self._sequence.sort(*args, **kwargs)
00858
00859 class _keys(object):
00860
00861 """
00862 Custom object for accessing the keys of an OrderedDict.
00863
00864 Can be called like the normal ``OrderedDict.keys`` method, but also
00865 supports indexing and sequence methods.
00866 """
00867
00868 def __init__(self, main):
00869 self._main = main
00870
00871 def __call__(self):
00872 """Pretend to be the keys method."""
00873 return self._main._keys()
00874
00875 def __getitem__(self, index):
00876 """Fetch the key at position i."""
00877
00878 return self._main._sequence[index]
00879
00880 def __setitem__(self, index, name):
00881 """
00882 You cannot assign to keys, but you can do slice assignment to re-order
00883 them.
00884
00885 You can only do slice assignment if the new set of keys is a reordering
00886 of the original set.
00887 """
00888 if isinstance(index, SliceType):
00889
00890
00891 indexes = range(len(self._main._sequence))[index]
00892 if len(indexes) != len(name):
00893 raise ValueError('attempt to assign sequence of size %s '
00894 'to slice of size %s' % (len(name), len(indexes)))
00895
00896
00897 old_keys = self._main._sequence[index]
00898 new_keys = list(name)
00899 old_keys.sort()
00900 new_keys.sort()
00901 if old_keys != new_keys:
00902 raise KeyError('Keylist is not the same as current keylist.')
00903 orig_vals = [self._main[k] for k in name]
00904 del self._main[index]
00905 vals = zip(indexes, name, orig_vals)
00906 vals.sort()
00907 for i, k, v in vals:
00908 if self._main.strict and k in self._main:
00909 raise ValueError('slice assignment must be from '
00910 'unique keys')
00911 self._main.insert(i, k, v)
00912 else:
00913 raise ValueError('Cannot assign to keys')
00914
00915
00916 def __repr__(self): return repr(self._main._sequence)
00917
00918
00919
00920 def __lt__(self, other): return self._main._sequence < other
00921 def __le__(self, other): return self._main._sequence <= other
00922 def __eq__(self, other): return self._main._sequence == other
00923 def __ne__(self, other): return self._main._sequence != other
00924 def __gt__(self, other): return self._main._sequence > other
00925 def __ge__(self, other): return self._main._sequence >= other
00926
00927 def __cmp__(self, other): return cmp(self._main._sequence, other)
00928
00929 def __contains__(self, item): return item in self._main._sequence
00930 def __len__(self): return len(self._main._sequence)
00931 def __iter__(self): return self._main.iterkeys()
00932 def count(self, item): return self._main._sequence.count(item)
00933 def index(self, item, *args): return self._main._sequence.index(item, *args)
00934 def reverse(self): self._main._sequence.reverse()
00935 def sort(self, *args, **kwds): self._main._sequence.sort(*args, **kwds)
00936 def __mul__(self, n): return self._main._sequence*n
00937 __rmul__ = __mul__
00938 def __add__(self, other): return self._main._sequence + other
00939 def __radd__(self, other): return other + self._main._sequence
00940
00941
00942 def __delitem__(self, i): raise TypeError('Can\'t delete items from keys')
00943 def __iadd__(self, other): raise TypeError('Can\'t add in place to keys')
00944 def __imul__(self, n): raise TypeError('Can\'t multiply keys in place')
00945 def append(self, item): raise TypeError('Can\'t append items to keys')
00946 def insert(self, i, item): raise TypeError('Can\'t insert items into keys')
00947 def pop(self, i=-1): raise TypeError('Can\'t pop items from keys')
00948 def remove(self, item): raise TypeError('Can\'t remove items from keys')
00949 def extend(self, other): raise TypeError('Can\'t extend keys')
00950
00951 class _items(object):
00952 """
00953 Custom object for accessing the items of an OrderedDict.
00954
00955 Can be called like the normal ``OrderedDict.items`` method, but also
00956 supports indexing and sequence methods.
00957 """
00958
00959 def __init__(self, main):
00960 self._main = main
00961
00962 def __call__(self):
00963 """Pretend to be the items method."""
00964 return self._main._items()
00965
00966 def __getitem__(self, index):
00967 """Fetch the item at position i."""
00968 if isinstance(index, SliceType):
00969
00970 return self._main[index].items()
00971 key = self._main._sequence[index]
00972 return (key, self._main[key])
00973
00974 def __setitem__(self, index, item):
00975 """Set item at position i to item."""
00976 if isinstance(index, SliceType):
00977
00978 self._main[index] = OrderedDict(item)
00979 else:
00980
00981 orig = self._main.keys[index]
00982 key, value = item
00983 if self._main.strict and key in self and (key != orig):
00984 raise ValueError('slice assignment must be from '
00985 'unique keys')
00986
00987 del self._main[self._main._sequence[index]]
00988 self._main.insert(index, key, value)
00989
00990 def __delitem__(self, i):
00991 """Delete the item at position i."""
00992 key = self._main._sequence[i]
00993 if isinstance(i, SliceType):
00994 for k in key:
00995
00996 del self._main[k]
00997 else:
00998 del self._main[key]
00999
01000
01001 def __repr__(self): return repr(self._main.items())
01002
01003
01004
01005 def __lt__(self, other): return self._main.items() < other
01006 def __le__(self, other): return self._main.items() <= other
01007 def __eq__(self, other): return self._main.items() == other
01008 def __ne__(self, other): return self._main.items() != other
01009 def __gt__(self, other): return self._main.items() > other
01010 def __ge__(self, other): return self._main.items() >= other
01011 def __cmp__(self, other): return cmp(self._main.items(), other)
01012
01013 def __contains__(self, item): return item in self._main.items()
01014 def __len__(self): return len(self._main._sequence)
01015 def __iter__(self): return self._main.iteritems()
01016 def count(self, item): return self._main.items().count(item)
01017 def index(self, item, *args): return self._main.items().index(item, *args)
01018 def reverse(self): self._main.reverse()
01019 def sort(self, *args, **kwds): self._main.sort(*args, **kwds)
01020 def __mul__(self, n): return self._main.items()*n
01021 __rmul__ = __mul__
01022 def __add__(self, other): return self._main.items() + other
01023 def __radd__(self, other): return other + self._main.items()
01024
01025 def append(self, item):
01026 """Add an item to the end."""
01027
01028 key, value = item
01029 self._main[key] = value
01030
01031 def insert(self, i, item):
01032 key, value = item
01033 self._main.insert(i, key, value)
01034
01035 def pop(self, i=-1):
01036 key = self._main._sequence[i]
01037 return (key, self._main.pop(key))
01038
01039 def remove(self, item):
01040 key, value = item
01041 try:
01042 assert value == self._main[key]
01043 except (KeyError, AssertionError):
01044 raise ValueError('ValueError: list.remove(x): x not in list')
01045 else:
01046 del self._main[key]
01047
01048 def extend(self, other):
01049
01050 for item in other:
01051 key, value = item
01052 self._main[key] = value
01053
01054 def __iadd__(self, other):
01055 self.extend(other)
01056
01057
01058
01059 def __imul__(self, n): raise TypeError('Can\'t multiply items in place')
01060
01061
01062 class _values(object):
01063 """
01064 Custom object for accessing the values of an OrderedDict.
01065
01066 Can be called like the normal ``OrderedDict.values`` method, but also
01067 supports indexing and sequence methods.
01068 """
01069
01070 def __init__(self, main):
01071 self._main = main
01072
01073 def __call__(self):
01074 """Pretend to be the values method."""
01075 return self._main._values()
01076
01077 def __getitem__(self, index):
01078 """Fetch the value at position i."""
01079 if isinstance(index, SliceType):
01080 return [self._main[key] for key in self._main._sequence[index]]
01081 else:
01082 return self._main[self._main._sequence[index]]
01083
01084 def __setitem__(self, index, value):
01085 """
01086 Set the value at position i to value.
01087
01088 You can only do slice assignment to values if you supply a sequence of
01089 equal length to the slice you are replacing.
01090 """
01091 if isinstance(index, SliceType):
01092 keys = self._main._sequence[index]
01093 if len(keys) != len(value):
01094 raise ValueError('attempt to assign sequence of size %s '
01095 'to slice of size %s' % (len(name), len(keys)))
01096
01097
01098
01099
01100 for key, val in zip(keys, value):
01101 self._main[key] = val
01102 else:
01103 self._main[self._main._sequence[index]] = value
01104
01105
01106 def __repr__(self): return repr(self._main.values())
01107
01108
01109
01110 def __lt__(self, other): return self._main.values() < other
01111 def __le__(self, other): return self._main.values() <= other
01112 def __eq__(self, other): return self._main.values() == other
01113 def __ne__(self, other): return self._main.values() != other
01114 def __gt__(self, other): return self._main.values() > other
01115 def __ge__(self, other): return self._main.values() >= other
01116 def __cmp__(self, other): return cmp(self._main.values(), other)
01117
01118 def __contains__(self, item): return item in self._main.values()
01119 def __len__(self): return len(self._main._sequence)
01120 def __iter__(self): return self._main.itervalues()
01121 def count(self, item): return self._main.values().count(item)
01122 def index(self, item, *args): return self._main.values().index(item, *args)
01123
01124 def reverse(self):
01125 """Reverse the values"""
01126 vals = self._main.values()
01127 vals.reverse()
01128
01129 self[:] = vals
01130
01131 def sort(self, *args, **kwds):
01132 """Sort the values."""
01133 vals = self._main.values()
01134 vals.sort(*args, **kwds)
01135 self[:] = vals
01136
01137 def __mul__(self, n): return self._main.values()*n
01138 __rmul__ = __mul__
01139 def __add__(self, other): return self._main.values() + other
01140 def __radd__(self, other): return other + self._main.values()
01141
01142
01143 def __delitem__(self, i): raise TypeError('Can\'t delete items from values')
01144 def __iadd__(self, other): raise TypeError('Can\'t add in place to values')
01145 def __imul__(self, n): raise TypeError('Can\'t multiply values in place')
01146 def append(self, item): raise TypeError('Can\'t append items to values')
01147 def insert(self, i, item): raise TypeError('Can\'t insert items into values')
01148 def pop(self, i=-1): raise TypeError('Can\'t pop items from values')
01149 def remove(self, item): raise TypeError('Can\'t remove items from values')
01150 def extend(self, other): raise TypeError('Can\'t extend values')
01151
01152
01153 class SequenceOrderedDict(OrderedDict):
01154 """
01155 Experimental version of OrderedDict that has a custom object for ``keys``,
01156 ``values``, and ``items``.
01157
01158 These are callable sequence objects that work as methods, or can be
01159 manipulated directly as sequences.
01160
01161 Test for ``keys``, ``items`` and ``values``.
01162
01163 >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)))
01164 >>> d
01165 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
01166 >>> d.keys
01167 [1, 2, 3]
01168 >>> d.keys()
01169 [1, 2, 3]
01170 >>> d.setkeys((3, 2, 1))
01171 >>> d
01172 SequenceOrderedDict([(3, 4), (2, 3), (1, 2)])
01173 >>> d.setkeys((1, 2, 3))
01174 >>> d.keys[0]
01175 1
01176 >>> d.keys[:]
01177 [1, 2, 3]
01178 >>> d.keys[-1]
01179 3
01180 >>> d.keys[-2]
01181 2
01182 >>> d.keys[0:2] = [2, 1]
01183 >>> d
01184 SequenceOrderedDict([(2, 3), (1, 2), (3, 4)])
01185 >>> d.keys.reverse()
01186 >>> d.keys
01187 [3, 1, 2]
01188 >>> d.keys = [1, 2, 3]
01189 >>> d
01190 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
01191 >>> d.keys = [3, 1, 2]
01192 >>> d
01193 SequenceOrderedDict([(3, 4), (1, 2), (2, 3)])
01194 >>> a = SequenceOrderedDict()
01195 >>> b = SequenceOrderedDict()
01196 >>> a.keys == b.keys
01197 1
01198 >>> a['a'] = 3
01199 >>> a.keys == b.keys
01200 0
01201 >>> b['a'] = 3
01202 >>> a.keys == b.keys
01203 1
01204 >>> b['b'] = 3
01205 >>> a.keys == b.keys
01206 0
01207 >>> a.keys > b.keys
01208 0
01209 >>> a.keys < b.keys
01210 1
01211 >>> 'a' in a.keys
01212 1
01213 >>> len(b.keys)
01214 2
01215 >>> 'c' in d.keys
01216 0
01217 >>> 1 in d.keys
01218 1
01219 >>> [v for v in d.keys]
01220 [3, 1, 2]
01221 >>> d.keys.sort()
01222 >>> d.keys
01223 [1, 2, 3]
01224 >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)), strict=True)
01225 >>> d.keys[::-1] = [1, 2, 3]
01226 >>> d
01227 SequenceOrderedDict([(3, 4), (2, 3), (1, 2)])
01228 >>> d.keys[:2]
01229 [3, 2]
01230 >>> d.keys[:2] = [1, 3]
01231 Traceback (most recent call last):
01232 KeyError: 'Keylist is not the same as current keylist.'
01233
01234 >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)))
01235 >>> d
01236 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
01237 >>> d.values
01238 [2, 3, 4]
01239 >>> d.values()
01240 [2, 3, 4]
01241 >>> d.setvalues((4, 3, 2))
01242 >>> d
01243 SequenceOrderedDict([(1, 4), (2, 3), (3, 2)])
01244 >>> d.values[::-1]
01245 [2, 3, 4]
01246 >>> d.values[0]
01247 4
01248 >>> d.values[-2]
01249 3
01250 >>> del d.values[0]
01251 Traceback (most recent call last):
01252 TypeError: Can't delete items from values
01253 >>> d.values[::2] = [2, 4]
01254 >>> d
01255 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
01256 >>> 7 in d.values
01257 0
01258 >>> len(d.values)
01259 3
01260 >>> [val for val in d.values]
01261 [2, 3, 4]
01262 >>> d.values[-1] = 2
01263 >>> d.values.count(2)
01264 2
01265 >>> d.values.index(2)
01266 0
01267 >>> d.values[-1] = 7
01268 >>> d.values
01269 [2, 3, 7]
01270 >>> d.values.reverse()
01271 >>> d.values
01272 [7, 3, 2]
01273 >>> d.values.sort()
01274 >>> d.values
01275 [2, 3, 7]
01276 >>> d.values.append('anything')
01277 Traceback (most recent call last):
01278 TypeError: Can't append items to values
01279 >>> d.values = (1, 2, 3)
01280 >>> d
01281 SequenceOrderedDict([(1, 1), (2, 2), (3, 3)])
01282
01283 >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)))
01284 >>> d
01285 SequenceOrderedDict([(1, 2), (2, 3), (3, 4)])
01286 >>> d.items()
01287 [(1, 2), (2, 3), (3, 4)]
01288 >>> d.setitems([(3, 4), (2 ,3), (1, 2)])
01289 >>> d
01290 SequenceOrderedDict([(3, 4), (2, 3), (1, 2)])
01291 >>> d.items[0]
01292 (3, 4)
01293 >>> d.items[:-1]
01294 [(3, 4), (2, 3)]
01295 >>> d.items[1] = (6, 3)
01296 >>> d.items
01297 [(3, 4), (6, 3), (1, 2)]
01298 >>> d.items[1:2] = [(9, 9)]
01299 >>> d
01300 SequenceOrderedDict([(3, 4), (9, 9), (1, 2)])
01301 >>> del d.items[1:2]
01302 >>> d
01303 SequenceOrderedDict([(3, 4), (1, 2)])
01304 >>> (3, 4) in d.items
01305 1
01306 >>> (4, 3) in d.items
01307 0
01308 >>> len(d.items)
01309 2
01310 >>> [v for v in d.items]
01311 [(3, 4), (1, 2)]
01312 >>> d.items.count((3, 4))
01313 1
01314 >>> d.items.index((1, 2))
01315 1
01316 >>> d.items.index((2, 1))
01317 Traceback (most recent call last):
01318 ValueError: list.index(x): x not in list
01319 >>> d.items.reverse()
01320 >>> d.items
01321 [(1, 2), (3, 4)]
01322 >>> d.items.reverse()
01323 >>> d.items.sort()
01324 >>> d.items
01325 [(1, 2), (3, 4)]
01326 >>> d.items.append((5, 6))
01327 >>> d.items
01328 [(1, 2), (3, 4), (5, 6)]
01329 >>> d.items.insert(0, (0, 0))
01330 >>> d.items
01331 [(0, 0), (1, 2), (3, 4), (5, 6)]
01332 >>> d.items.insert(-1, (7, 8))
01333 >>> d.items
01334 [(0, 0), (1, 2), (3, 4), (7, 8), (5, 6)]
01335 >>> d.items.pop()
01336 (5, 6)
01337 >>> d.items
01338 [(0, 0), (1, 2), (3, 4), (7, 8)]
01339 >>> d.items.remove((1, 2))
01340 >>> d.items
01341 [(0, 0), (3, 4), (7, 8)]
01342 >>> d.items.extend([(1, 2), (5, 6)])
01343 >>> d.items
01344 [(0, 0), (3, 4), (7, 8), (1, 2), (5, 6)]
01345 """
01346
01347 def __init__(self, init_val=(), strict=True):
01348 OrderedDict.__init__(self, init_val, strict=strict)
01349 self._keys = self.keys
01350 self._values = self.values
01351 self._items = self.items
01352 self.keys = _keys(self)
01353 self.values = _values(self)
01354 self.items = _items(self)
01355 self._att_dict = {'keys': self.setkeys,
01356 'items': self.setitems,
01357 'values': self.setvalues
01358 }
01359
01360 def __setattr__(self, name, value):
01361 """Protect keys, items, and values."""
01362 if not '_att_dict' in self.__dict__:
01363 object.__setattr__(self, name, value)
01364 else:
01365 try:
01366 fun = self._att_dict[name]
01367 except KeyError:
01368 OrderedDict.__setattr__(self, name, value)
01369 else:
01370 fun(value)
01371
01372 if __name__ == '__main__':
01373
01374 import doctest
01375 m = sys.modules.get('__main__')
01376 globs = m.__dict__.copy()
01377 globs.update({
01378 'INTP_VER': INTP_VER,
01379 })
01380 doctest.testmod(m, globs=globs)
01381
01382 """
01383 ISSUES
01384 ======
01385
01386 Slicing doesn't work in Python 2.2. This is because in 2.2, you can't index
01387 a sequence with a slice object. Could be implemented with ``operator``
01388 slicing functions (which don't support extended slices).
01389
01390 TODO
01391 ====
01392
01393 Addition (``__add__``) ? (This would just be syntactic sugar for
01394 ``update``)
01395
01396 Implement the Python 2.4 arguments (``key`` and ``reverse``) for ``sort``
01397 for Python 2.2 and 2.3 ? (So the interface is stable)
01398
01399 Add sequence methods ``move`` and ``rename`` ? (To change the name of a key
01400 at a specific index, and change the index of a key from one position to
01401 another)
01402
01403 Allow assignment to keys (in ``SequenceOrderedDict``) to rename a key ?
01404
01405 Do I *need* to implement ``__cmp__`` - I don't *think* so ?
01406
01407 Allow slice assignment to ``OrderedDict`` (and `possibly
01408 ``SequenceOrderedDict.items``) from list of tuples as well as from an
01409 ``OrderedDict`` ?
01410
01411 CHANGELOG
01412 =========
01413
01414 2005/12/17
01415 ----------
01416
01417 You can now test for equality and inequality with objects (except for
01418 dictionaries for which it is undefined). This allows you to do tests like :
01419 ::
01420
01421 OrderedDict() == False
01422
01423 Added the ``strict`` keyword, which raises a ``ValueError`` if you do slice
01424 assignment with keys that are already in the dictionary.
01425
01426 Assignment to ``keys`` in ``SequenceOrderedDict`` is now only for
01427 re-ordering the keys.
01428
01429 Fixed bug where slice assignment to ``keys`` could lose information. (and
01430 optimised by slicing ranges to get the indexes we are assigning to instead
01431 of indexing each key).
01432
01433 You change keys, items, and values through new methods ``setkeys``,
01434 ``setitems``, and ``setvalues`` methods.
01435
01436 Minor changes, thanks to Christoph Zwerschke for suggestions.
01437
01438 Added ``__deepcopy__`` method (previously deepcopy failed).
01439
01440 CHanged use of ``slice`` to ``types.SliceType`` for Python 2.2.
01441
01442 0.2.1
01443
01444
01445 2005/12/02
01446 ----------
01447
01448 Fixed bugs in ``__getattr__`` and ``popitem``
01449
01450 Optimisation in ``OrderedDict.__init__`` when creating an instance from an
01451 ``OrderedDict``
01452
01453 Changed ``FancyODict`` to ``SequenceOrderedDict``
01454
01455 Implemented new ``__repr__``
01456
01457 0.2.0
01458
01459 2005/12/01
01460 ----------
01461
01462 Added index to ``OrderedDict.popitem``
01463
01464 2005/11/30
01465 ----------
01466
01467 Implemented ``FancyODict``, which has ``keys``, ``items``, ``values`` as
01468 custom, callable, sequence objects.
01469
01470 2005/11/26
01471 ----------
01472
01473 By Michael Foord - from suggestions on comp.lang.python
01474
01475 Hidden the ``sequence`` attribute
01476
01477 ``items``, ``keys``, ``values`` can now take a list to replace the current
01478 keys, values, or items
01479
01480 Implemented slicing (including deleting a slice and assigning to a slice)
01481
01482 Implemented sequence methods ``sort``, ``reverse``, ``insert``, ``index``
01483
01484 2005/09/10
01485 ----------
01486
01487 By Nicola Larosa, based on code from Tim Wegener
01488 <twegener AT radlogic DOT com DOT au>
01489
01490 Create itervalues and iteritems without creating the list up-front
01491
01492 Added doctests for iter methods, and others.
01493
01494 Optimized __setitem__ to be O(1) rather than O(N)
01495
01496 Removed redefined methods that did not alter dict method behaviour,
01497 related doctests moved to the class docstring
01498
01499 Added support for sequences of (key, value) pairs to update
01500
01501 Removed redundant condition from __eq__
01502
01503 Removed incorrect implementation of __str__
01504
01505 2005/08/28
01506 ----------
01507
01508 By Michael Foord
01509
01510 Added __all__
01511
01512 More than two arguments to ``pop`` now raises an error
01513
01514 Version 0.1.0 finalised
01515
01516 2005/08/13
01517 ----------
01518
01519 By Nicola Larosa
01520
01521 Added doctests everywhere, fixed much part of implementation
01522
01523 Added comments at top, other doc vars
01524
01525 2005/08/01
01526 ----------
01527
01528 By Michael Foord
01529
01530 Type tests changed to isinstance
01531
01532 _keys changed to sequence attribute
01533
01534 Allowed creating a dictionary by passing keyword arguments
01535
01536 Shortened __repr__
01537
01538 Fixed bug in popitem
01539
01540 Other minor changes
01541 """