osqa/forum/utils/odict.py

   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