diff options
Diffstat (limited to 'portato')
| -rw-r--r-- | portato/odict.py | 1399 |
1 files changed, 1399 insertions, 0 deletions
diff --git a/portato/odict.py b/portato/odict.py new file mode 100644 index 0000000..2c8391d --- /dev/null +++ b/portato/odict.py @@ -0,0 +1,1399 @@ +# odict.py +# An Ordered Dictionary object +# Copyright (C) 2005 Nicola Larosa, Michael Foord +# E-mail: nico AT tekNico DOT net, fuzzyman AT voidspace DOT org DOT uk + +# This software is licensed under the terms of the BSD license. +# http://www.voidspace.org.uk/python/license.shtml +# Basically you're free to copy, modify, distribute and relicense it, +# So long as you keep a copy of the license with it. + +# Documentation at http://www.voidspace.org.uk/python/odict.html +# For information about bugfixes, updates and support, please join the +# Pythonutils mailing list: +# http://groups.google.com/group/pythonutils/ +# Comments, suggestions and bug reports welcome. + +"""A dict that keeps keys in insertion order""" +from __future__ import generators + +__author__ = ('Nicola Larosa <nico-NoSp@m-tekNico.net>,' + 'Michael Foord <fuzzyman AT voidspace DOT org DOT uk>') + +__docformat__ = "restructuredtext en" + +__revision__ = '$Id: odict.py 129 2005-09-12 18:15:28Z teknico $' + +__version__ = '0.2.2' + +__all__ = ['OrderedDict', 'SequenceOrderedDict'] + +import sys +INTP_VER = sys.version_info[:2] +if INTP_VER < (2, 2): + raise RuntimeError("Python v.2.2 or later required") + +import types, warnings + +class OrderedDict(dict): + """ + A class of dictionary that keeps the insertion order of keys. + + All appropriate methods return keys, items, or values in an ordered way. + + All normal dictionary methods are available. Update and comparison is + restricted to other OrderedDict objects. + + Various sequence methods are available, including the ability to explicitly + mutate the key ordering. + + __contains__ tests: + + >>> d = OrderedDict(((1, 3),)) + >>> 1 in d + 1 + >>> 4 in d + 0 + + __getitem__ tests: + + >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[2] + 1 + >>> OrderedDict(((1, 3), (3, 2), (2, 1)))[4] + Traceback (most recent call last): + KeyError: 4 + + __len__ tests: + + >>> len(OrderedDict()) + 0 + >>> len(OrderedDict(((1, 3), (3, 2), (2, 1)))) + 3 + + get tests: + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.get(1) + 3 + >>> d.get(4) is None + 1 + >>> d.get(4, 5) + 5 + >>> d + OrderedDict([(1, 3), (3, 2), (2, 1)]) + + has_key tests: + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.has_key(1) + 1 + >>> d.has_key(4) + 0 + """ + + def __init__(self, init_val=(), strict=False): + """ + Create a new ordered dictionary. Cannot init from a normal dict, + nor from kwargs, since items order is undefined in those cases. + + If the ``strict`` keyword argument is ``True`` (``False`` is the + default) then when doing slice assignment - the ``OrderedDict`` you are + assigning from *must not* contain any keys in the remaining dict. + + >>> OrderedDict() + OrderedDict([]) + >>> OrderedDict({1: 1}) + Traceback (most recent call last): + TypeError: undefined order, cannot get items from dict + >>> OrderedDict({1: 1}.items()) + OrderedDict([(1, 1)]) + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d + OrderedDict([(1, 3), (3, 2), (2, 1)]) + >>> OrderedDict(d) + OrderedDict([(1, 3), (3, 2), (2, 1)]) + """ + self.strict = strict + dict.__init__(self) + if isinstance(init_val, OrderedDict): + self._sequence = init_val.keys() + dict.update(self, init_val) + elif isinstance(init_val, dict): + # we lose compatibility with other ordered dict types this way + raise TypeError('undefined order, cannot get items from dict') + else: + self._sequence = [] + self.update(init_val) + +### Special methods ### + + def __delitem__(self, key): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> del d[3] + >>> d + OrderedDict([(1, 3), (2, 1)]) + >>> del d[3] + Traceback (most recent call last): + KeyError: 3 + >>> d[3] = 2 + >>> d + OrderedDict([(1, 3), (2, 1), (3, 2)]) + >>> del d[0:1] + >>> d + OrderedDict([(2, 1), (3, 2)]) + """ + if isinstance(key, types.SliceType): + # FIXME: efficiency? + keys = self._sequence[key] + for entry in keys: + dict.__delitem__(self, entry) + del self._sequence[key] + else: + # do the dict.__delitem__ *first* as it raises + # the more appropriate error + dict.__delitem__(self, key) + self._sequence.remove(key) + + def __eq__(self, other): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d == OrderedDict(d) + True + >>> d == OrderedDict(((1, 3), (2, 1), (3, 2))) + False + >>> d == OrderedDict(((1, 0), (3, 2), (2, 1))) + False + >>> d == OrderedDict(((0, 3), (3, 2), (2, 1))) + False + >>> d == dict(d) + False + >>> d == False + False + """ + if isinstance(other, OrderedDict): + # FIXME: efficiency? + # Generate both item lists for each compare + return (self.items() == other.items()) + else: + return False + + def __lt__(self, other): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> c = OrderedDict(((0, 3), (3, 2), (2, 1))) + >>> c < d + True + >>> d < c + False + >>> d < dict(c) + Traceback (most recent call last): + TypeError: Can only compare with other OrderedDicts + """ + if not isinstance(other, OrderedDict): + raise TypeError('Can only compare with other OrderedDicts') + # FIXME: efficiency? + # Generate both item lists for each compare + return (self.items() < other.items()) + + def __le__(self, other): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> c = OrderedDict(((0, 3), (3, 2), (2, 1))) + >>> e = OrderedDict(d) + >>> c <= d + True + >>> d <= c + False + >>> d <= dict(c) + Traceback (most recent call last): + TypeError: Can only compare with other OrderedDicts + >>> d <= e + True + """ + if not isinstance(other, OrderedDict): + raise TypeError('Can only compare with other OrderedDicts') + # FIXME: efficiency? + # Generate both item lists for each compare + return (self.items() <= other.items()) + + def __ne__(self, other): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d != OrderedDict(d) + False + >>> d != OrderedDict(((1, 3), (2, 1), (3, 2))) + True + >>> d != OrderedDict(((1, 0), (3, 2), (2, 1))) + True + >>> d == OrderedDict(((0, 3), (3, 2), (2, 1))) + False + >>> d != dict(d) + True + >>> d != False + True + """ + if isinstance(other, OrderedDict): + # FIXME: efficiency? + # Generate both item lists for each compare + return not (self.items() == other.items()) + else: + return True + + def __gt__(self, other): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> c = OrderedDict(((0, 3), (3, 2), (2, 1))) + >>> d > c + True + >>> c > d + False + >>> d > dict(c) + Traceback (most recent call last): + TypeError: Can only compare with other OrderedDicts + """ + if not isinstance(other, OrderedDict): + raise TypeError('Can only compare with other OrderedDicts') + # FIXME: efficiency? + # Generate both item lists for each compare + return (self.items() > other.items()) + + def __ge__(self, other): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> c = OrderedDict(((0, 3), (3, 2), (2, 1))) + >>> e = OrderedDict(d) + >>> c >= d + False + >>> d >= c + True + >>> d >= dict(c) + Traceback (most recent call last): + TypeError: Can only compare with other OrderedDicts + >>> e >= d + True + """ + if not isinstance(other, OrderedDict): + raise TypeError('Can only compare with other OrderedDicts') + # FIXME: efficiency? + # Generate both item lists for each compare + return (self.items() >= other.items()) + + def __repr__(self): + """ + Used for __repr__ and __str__ + + >>> r1 = repr(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f')))) + >>> r1 + "OrderedDict([('a', 'b'), ('c', 'd'), ('e', 'f')])" + >>> r2 = repr(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd')))) + >>> r2 + "OrderedDict([('a', 'b'), ('e', 'f'), ('c', 'd')])" + >>> r1 == str(OrderedDict((('a', 'b'), ('c', 'd'), ('e', 'f')))) + True + >>> r2 == str(OrderedDict((('a', 'b'), ('e', 'f'), ('c', 'd')))) + True + """ + return '%s([%s])' % (self.__class__.__name__, ', '.join( + ['(%r, %r)' % (key, self[key]) for key in self._sequence])) + + def __setitem__(self, key, val): + """ + Allows slice assignment, so long as the slice is an OrderedDict + >>> d = OrderedDict() + >>> d['a'] = 'b' + >>> d['b'] = 'a' + >>> d[3] = 12 + >>> d + OrderedDict([('a', 'b'), ('b', 'a'), (3, 12)]) + >>> d[:] = OrderedDict(((1, 2), (2, 3), (3, 4))) + >>> d + OrderedDict([(1, 2), (2, 3), (3, 4)]) + >>> d[::2] = OrderedDict(((7, 8), (9, 10))) + >>> d + OrderedDict([(7, 8), (2, 3), (9, 10)]) + >>> d = OrderedDict(((0, 1), (1, 2), (2, 3), (3, 4))) + >>> d[1:3] = OrderedDict(((1, 2), (5, 6), (7, 8))) + >>> d + OrderedDict([(0, 1), (1, 2), (5, 6), (7, 8), (3, 4)]) + >>> d = OrderedDict(((0, 1), (1, 2), (2, 3), (3, 4)), strict=True) + >>> d[1:3] = OrderedDict(((1, 2), (5, 6), (7, 8))) + >>> d + OrderedDict([(0, 1), (1, 2), (5, 6), (7, 8), (3, 4)]) + + >>> a = OrderedDict(((0, 1), (1, 2), (2, 3)), strict=True) + >>> a[3] = 4 + >>> a + OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a[::1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a + OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a[:2] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)]) + Traceback (most recent call last): + ValueError: slice assignment must be from unique keys + >>> a = OrderedDict(((0, 1), (1, 2), (2, 3))) + >>> a[3] = 4 + >>> a + OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a[::1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a + OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a[:2] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a + OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a[::-1] = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> a + OrderedDict([(3, 4), (2, 3), (1, 2), (0, 1)]) + + >>> d = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> d[:1] = 3 + Traceback (most recent call last): + TypeError: slice assignment requires an OrderedDict + + >>> d = OrderedDict([(0, 1), (1, 2), (2, 3), (3, 4)]) + >>> d[:1] = OrderedDict([(9, 8)]) + >>> d + OrderedDict([(9, 8), (1, 2), (2, 3), (3, 4)]) + """ + if isinstance(key, types.SliceType): + if not isinstance(val, OrderedDict): + # FIXME: allow a list of tuples? + raise TypeError('slice assignment requires an OrderedDict') + keys = self._sequence[key] + # NOTE: Could use ``range(*key.indices(len(self._sequence)))`` + indexes = range(len(self._sequence))[key] + if key.step is None: + # NOTE: new slice may not be the same size as the one being + # overwritten ! + # NOTE: What is the algorithm for an impossible slice? + # e.g. d[5:3] + pos = key.start or 0 + del self[key] + newkeys = val.keys() + for k in newkeys: + if k in self: + if self.strict: + raise ValueError('slice assignment must be from ' + 'unique keys') + else: + # NOTE: This removes duplicate keys *first* + # so start position might have changed? + del self[k] + self._sequence = (self._sequence[:pos] + newkeys + + self._sequence[pos:]) + dict.update(self, val) + else: + # extended slice - length of new slice must be the same + # as the one being replaced + if len(keys) != len(val): + raise ValueError('attempt to assign sequence of size %s ' + 'to extended slice of size %s' % (len(val), len(keys))) + # FIXME: efficiency? + del self[key] + item_list = zip(indexes, val.items()) + # smallest indexes first - higher indexes not guaranteed to + # exist + item_list.sort() + for pos, (newkey, newval) in item_list: + if self.strict and newkey in self: + raise ValueError('slice assignment must be from unique' + ' keys') + self.insert(pos, newkey, newval) + else: + if key not in self: + self._sequence.append(key) + dict.__setitem__(self, key, val) + + def __getitem__(self, key): + """ + Allows slicing. Returns an OrderedDict if you slice. + >>> b = OrderedDict([(7, 0), (6, 1), (5, 2), (4, 3), (3, 4), (2, 5), (1, 6)]) + >>> b[::-1] + OrderedDict([(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)]) + >>> b[2:5] + OrderedDict([(5, 2), (4, 3), (3, 4)]) + >>> type(b[2:4]) + <class '__main__.OrderedDict'> + """ + if isinstance(key, types.SliceType): + # FIXME: does this raise the error we want? + keys = self._sequence[key] + # FIXME: efficiency? + return OrderedDict([(entry, self[entry]) for entry in keys]) + else: + return dict.__getitem__(self, key) + + __str__ = __repr__ + + def __setattr__(self, name, value): + """ + Implemented so that accesses to ``sequence`` raise a warning and are + diverted to the new ``setkeys`` method. + """ + if name == 'sequence': + warnings.warn('Use of the sequence attribute is deprecated.' + ' Use the keys method instead.', DeprecationWarning) + # NOTE: doesn't return anything + self.setkeys(value) + else: + # FIXME: do we want to allow arbitrary setting of attributes? + # Or do we want to manage it? + object.__setattr__(self, name, value) + + def __getattr__(self, name): + """ + Implemented so that access to ``sequence`` raises a warning. + + >>> d = OrderedDict() + >>> d.sequence + [] + """ + if name == 'sequence': + warnings.warn('Use of the sequence attribute is deprecated.' + ' Use the keys method instead.', DeprecationWarning) + # NOTE: Still (currently) returns a direct reference. Need to + # because code that uses sequence will expect to be able to + # mutate it in place. + return self._sequence + else: + # raise the appropriate error + raise AttributeError("OrderedDict has no '%s' attribute" % name) + + def __deepcopy__(self, memo): + """ + To allow deepcopy to work with OrderedDict. + + >>> from copy import deepcopy + >>> a = OrderedDict([(1, 1), (2, 2), (3, 3)]) + >>> a['test'] = {} + >>> b = deepcopy(a) + >>> b == a + True + >>> b is a + False + >>> a['test'] is b['test'] + False + """ + from copy import deepcopy + return self.__class__(deepcopy(self.items(), memo), self.strict) + + +### Read-only methods ### + + def copy(self): + """ + >>> OrderedDict(((1, 3), (3, 2), (2, 1))).copy() + OrderedDict([(1, 3), (3, 2), (2, 1)]) + """ + return OrderedDict(self) + + def items(self): + """ + ``items`` returns a list of tuples representing all the + ``(key, value)`` pairs in the dictionary. + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.items() + [(1, 3), (3, 2), (2, 1)] + >>> d.clear() + >>> d.items() + [] + """ + return zip(self._sequence, self.values()) + + def keys(self): + """ + Return a list of keys in the ``OrderedDict``. + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.keys() + [1, 3, 2] + """ + return self._sequence[:] + + def values(self, values=None): + """ + Return a list of all the values in the OrderedDict. + + Optionally you can pass in a list of values, which will replace the + current list. The value list must be the same len as the OrderedDict. + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.values() + [3, 2, 1] + """ + return [self[key] for key in self._sequence] + + def iteritems(self): + """ + >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iteritems() + >>> ii.next() + (1, 3) + >>> ii.next() + (3, 2) + >>> ii.next() + (2, 1) + >>> ii.next() + Traceback (most recent call last): + StopIteration + """ + def make_iter(self=self): + keys = self.iterkeys() + while True: + key = keys.next() + yield (key, self[key]) + return make_iter() + + def iterkeys(self): + """ + >>> ii = OrderedDict(((1, 3), (3, 2), (2, 1))).iterkeys() + >>> ii.next() + 1 + >>> ii.next() + 3 + >>> ii.next() + 2 + >>> ii.next() + Traceback (most recent call last): + StopIteration + """ + return iter(self._sequence) + + __iter__ = iterkeys + + def itervalues(self): + """ + >>> iv = OrderedDict(((1, 3), (3, 2), (2, 1))).itervalues() + >>> iv.next() + 3 + >>> iv.next() + 2 + >>> iv.next() + 1 + >>> iv.next() + Traceback (most recent call last): + StopIteration + """ + def make_iter(self=self): + keys = self.iterkeys() + while True: + yield self[keys.next()] + return make_iter() + +### Read-write methods ### + + def clear(self): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.clear() + >>> d + OrderedDict([]) + """ + dict.clear(self) + self._sequence = [] + + def pop(self, key, *args): + """ + No dict.pop in Python 2.2, gotta reimplement it + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.pop(3) + 2 + >>> d + OrderedDict([(1, 3), (2, 1)]) + >>> d.pop(4) + Traceback (most recent call last): + KeyError: 4 + >>> d.pop(4, 0) + 0 + >>> d.pop(4, 0, 1) + Traceback (most recent call last): + TypeError: pop expected at most 2 arguments, got 3 + """ + if len(args) > 1: + raise TypeError, ('pop expected at most 2 arguments, got %s' % + (len(args) + 1)) + if key in self: + val = self[key] + del self[key] + else: + try: + val = args[0] + except IndexError: + raise KeyError(key) + return val + + def popitem(self, i=-1): + """ + Delete and return an item specified by index, not a random one as in + dict. The index is -1 by default (the last item). + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.popitem() + (2, 1) + >>> d + OrderedDict([(1, 3), (3, 2)]) + >>> d.popitem(0) + (1, 3) + >>> OrderedDict().popitem() + Traceback (most recent call last): + KeyError: 'popitem(): dictionary is empty' + >>> d.popitem(2) + Traceback (most recent call last): + IndexError: popitem(): index 2 not valid + """ + if not self._sequence: + raise KeyError('popitem(): dictionary is empty') + try: + key = self._sequence[i] + except IndexError: + raise IndexError('popitem(): index %s not valid' % i) + return (key, self.pop(key)) + + def setdefault(self, key, defval = None): + """ + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.setdefault(1) + 3 + >>> d.setdefault(4) is None + True + >>> d + OrderedDict([(1, 3), (3, 2), (2, 1), (4, None)]) + >>> d.setdefault(5, 0) + 0 + >>> d + OrderedDict([(1, 3), (3, 2), (2, 1), (4, None), (5, 0)]) + """ + if key in self: + return self[key] + else: + self[key] = defval + return defval + + def update(self, from_od): + """ + Update from another OrderedDict or sequence of (key, value) pairs + + >>> d = OrderedDict(((1, 0), (0, 1))) + >>> d.update(OrderedDict(((1, 3), (3, 2), (2, 1)))) + >>> d + OrderedDict([(1, 3), (0, 1), (3, 2), (2, 1)]) + >>> d.update({4: 4}) + Traceback (most recent call last): + TypeError: undefined order, cannot get items from dict + >>> d.update((4, 4)) + Traceback (most recent call last): + TypeError: cannot convert dictionary update sequence element "4" to a 2-item sequence + """ + if isinstance(from_od, OrderedDict): + for key, val in from_od.items(): + self[key] = val + elif isinstance(from_od, dict): + # we lose compatibility with other ordered dict types this way + raise TypeError('undefined order, cannot get items from dict') + else: + # FIXME: efficiency? + # sequence of 2-item sequences, or error + for item in from_od: + try: + key, val = item + except TypeError: + raise TypeError('cannot convert dictionary update' + ' sequence element "%s" to a 2-item sequence' % item) + self[key] = val + + def rename(self, old_key, new_key): + """ + Rename the key for a given value, without modifying sequence order. + + For the case where new_key already exists this raise an exception, + since if new_key exists, it is ambiguous as to what happens to the + associated values, and the position of new_key in the sequence. + + >>> od = OrderedDict() + >>> od['a'] = 1 + >>> od['b'] = 2 + >>> od.items() + [('a', 1), ('b', 2)] + >>> od.rename('b', 'c') + >>> od.items() + [('a', 1), ('c', 2)] + >>> od.rename('c', 'a') + Traceback (most recent call last): + ValueError: New key already exists: 'a' + >>> od.rename('d', 'b') + Traceback (most recent call last): + KeyError: 'd' + """ + if new_key == old_key: + # no-op + return + if new_key in self: + raise ValueError("New key already exists: %r" % new_key) + # rename sequence entry + value = self[old_key] + old_idx = self._sequence.index(old_key) + self._sequence[old_idx] = new_key + # rename internal dict entry + dict.__delitem__(self, old_key) + dict.__setitem__(self, new_key, value) + + def setitems(self, items): + """ + This method allows you to set the items in the dict. + + It takes a list of tuples - of the same sort returned by the ``items`` + method. + + >>> d = OrderedDict() + >>> d.setitems(((3, 1), (2, 3), (1, 2))) + >>> d + OrderedDict([(3, 1), (2, 3), (1, 2)]) + """ + self.clear() + # FIXME: this allows you to pass in an OrderedDict as well :-) + self.update(items) + + def setkeys(self, keys): + """ + ``setkeys`` all ows you to pass in a new list of keys which will + replace the current set. This must contain the same set of keys, but + need not be in the same order. + + If you pass in new keys that don't match, a ``KeyError`` will be + raised. + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.keys() + [1, 3, 2] + >>> d.setkeys((1, 2, 3)) + >>> d + OrderedDict([(1, 3), (2, 1), (3, 2)]) + >>> d.setkeys(['a', 'b', 'c']) + Traceback (most recent call last): + KeyError: 'Keylist is not the same as current keylist.' + """ + # FIXME: Efficiency? (use set for Python 2.4 :-) + # NOTE: list(keys) rather than keys[:] because keys[:] returns + # a tuple, if keys is a tuple. + kcopy = list(keys) + kcopy.sort() + self._sequence.sort() + if kcopy != self._sequence: + raise KeyError('Keylist is not the same as current keylist.') + # NOTE: This makes the _sequence attribute a new object, instead + # of changing it in place. + # FIXME: efficiency? + self._sequence = list(keys) + + def setvalues(self, values): + """ + You can pass in a list of values, which will replace the + current list. The value list must be the same len as the OrderedDict. + + (Or a ``ValueError`` is raised.) + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.setvalues((1, 2, 3)) + >>> d + OrderedDict([(1, 1), (3, 2), (2, 3)]) + >>> d.setvalues([6]) + Traceback (most recent call last): + ValueError: Value list is not the same length as the OrderedDict. + """ + if len(values) != len(self): + # FIXME: correct error to raise? + raise ValueError('Value list is not the same length as the ' + 'OrderedDict.') + self.update(zip(self, values)) + +### Sequence Methods ### + + def index(self, key): + """ + Return the position of the specified key in the OrderedDict. + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.index(3) + 1 + >>> d.index(4) + Traceback (most recent call last): + ValueError: list.index(x): x not in list + """ + return self._sequence.index(key) + + def insert(self, index, key, value): + """ + Takes ``index``, ``key``, and ``value`` as arguments. + + Sets ``key`` to ``value``, so that ``key`` is at position ``index`` in + the OrderedDict. + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.insert(0, 4, 0) + >>> d + OrderedDict([(4, 0), (1, 3), (3, 2), (2, 1)]) + >>> d.insert(0, 2, 1) + >>> d + OrderedDict([(2, 1), (4, 0), (1, 3), (3, 2)]) + >>> d.insert(8, 8, 1) + >>> d + OrderedDict([(2, 1), (4, 0), (1, 3), (3, 2), (8, 1)]) + """ + if key in self: + # FIXME: efficiency? + del self[key] + self._sequence.insert(index, key) + dict.__setitem__(self, key, value) + + def reverse(self): + """ + Reverse the order of the OrderedDict. + + >>> d = OrderedDict(((1, 3), (3, 2), (2, 1))) + >>> d.reverse() + >>> d + OrderedDict([(2, 1), (3, 2), (1, 3)]) + """ + self._sequence.reverse() + + def sort(self, *args, **kwargs): + """ + Sort the key order in the OrderedDict. + + This method takes the same arguments as the ``list.sort`` method on + your version of Python. + + >>> d = OrderedDict(((4, 1), (2, 2), (3, 3), (1, 4))) + >>> d.sort() + >>> d + OrderedDict([(1, 4), (2, 2), (3, 3), (4, 1)]) + """ + self._sequence.sort(*args, **kwargs) + +class Keys(object): + # FIXME: should this object be a subclass of list? + """ + Custom object for accessing the keys of an OrderedDict. + + Can be called like the normal ``OrderedDict.keys`` method, but also + supports indexing and sequence methods. + """ + + def __init__(self, main): + self._main = main + + def __call__(self): + """Pretend to be the keys method.""" + return self._main._keys() + + def __getitem__(self, index): + """Fetch the key at position i.""" + # NOTE: this automatically supports slicing :-) + return self._main._sequence[index] + + def __setitem__(self, index, name): + """ + You cannot assign to keys, but you can do slice assignment to re-order + them. + + You can only do slice assignment if the new set of keys is a reordering + of the original set. + """ + if isinstance(index, types.SliceType): + # FIXME: efficiency? + # check length is the same + indexes = range(len(self._main._sequence))[index] + if len(indexes) != len(name): + raise ValueError('attempt to assign sequence of size %s ' + 'to slice of size %s' % (len(name), len(indexes))) + # check they are the same keys + # FIXME: Use set + old_keys = self._main._sequence[index] + new_keys = list(name) + old_keys.sort() + new_keys.sort() + if old_keys != new_keys: + raise KeyError('Keylist is not the same as current keylist.') + orig_vals = [self._main[k] for k in name] + del self._main[index] + vals = zip(indexes, name, orig_vals) + vals.sort() + for i, k, v in vals: + if self._main.strict and k in self._main: + raise ValueError('slice assignment must be from ' + 'unique keys') + self._main.insert(i, k, v) + else: + raise ValueError('Cannot assign to keys') + + ### following methods pinched from UserList and adapted ### + def __repr__(self): return repr(self._main._sequence) + + # FIXME: do we need to check if we are comparing with another ``Keys`` + # object? (like the __cast method of UserList) + def __lt__(self, other): return self._main._sequence < other + def __le__(self, other): return self._main._sequence <= other + def __eq__(self, other): return self._main._sequence == other + def __ne__(self, other): return self._main._sequence != other + def __gt__(self, other): return self._main._sequence > other + def __ge__(self, other): return self._main._sequence >= other + # FIXME: do we need __cmp__ as well as rich comparisons? + def __cmp__(self, other): return cmp(self._main._sequence, other) + + def __contains__(self, item): return item in self._main._sequence + def __len__(self): return len(self._main._sequence) + def __iter__(self): return self._main.iterkeys() + def count(self, item): return self._main._sequence.count(item) + def index(self, item, *args): return self._main._sequence.index(item, *args) + def reverse(self): self._main._sequence.reverse() + def sort(self, *args, **kwds): self._main._sequence.sort(*args, **kwds) + def __mul__(self, n): return self._main._sequence*n + __rmul__ = __mul__ + def __add__(self, other): return self._main._sequence + other + def __radd__(self, other): return other + self._main._sequence + + ## following methods not implemented for keys ## + def __delitem__(self, i): raise TypeError('Can\'t delete items from keys') + def __iadd__(self, other): raise TypeError('Can\'t add in place to keys') + def __imul__(self, n): raise TypeError('Can\'t multiply keys in place') + def append(self, item): raise TypeError('Can\'t append items to keys') + def insert(self, i, item): raise TypeError('Can\'t insert items into keys') + def pop(self, i=-1): raise TypeError('Can\'t pop items from keys') + def remove(self, item): raise TypeError('Can\'t remove items from keys') + def extend(self, other): raise TypeError('Can\'t extend keys') + +class Items(object): + """ + Custom object for accessing the items of an OrderedDict. + + Can be called like the normal ``OrderedDict.items`` method, but also + supports indexing and sequence methods. + """ + + def __init__(self, main): + self._main = main + + def __call__(self): + """Pretend to be the items method.""" + return self._main._items() + + def __getitem__(self, index): + """Fetch the item at position i.""" + if isinstance(index, types.SliceType): + # fetching a slice returns an OrderedDict + return self._main[index].items() + key = self._main._sequence[index] + return (key, self._main[key]) + + def __setitem__(self, index, item): + """Set item at position i to item.""" + if isinstance(index, types.SliceType): + # NOTE: item must be an iterable (list of tuples) + self._main[index] = OrderedDict(item) + else: + # FIXME: Does this raise a sensible error? + orig = self._main.keys[index] + key, value = item + if self._main.strict and key in self and (key != orig): + raise ValueError('slice assignment must be from ' + 'unique keys') + # delete the current one + del self._main[self._main._sequence[index]] + self._main.insert(index, key, value) + + def __delitem__(self, i): + """Delete the item at position i.""" + key = self._main._sequence[i] + if isinstance(i, types.SliceType): + for k in key: + # FIXME: efficiency? + del self._main[k] + else: + del self._main[key] + + ### following methods pinched from UserList and adapted ### + def __repr__(self): return repr(self._main.items()) + + # FIXME: do we need to check if we are comparing with another ``Items`` + # object? (like the __cast method of UserList) + def __lt__(self, other): return self._main.items() < other + def __le__(self, other): return self._main.items() <= other + def __eq__(self, other): return self._main.items() == other + def __ne__(self, other): return self._main.items() != other + def __gt__(self, other): return self._main.items() > other + def __ge__(self, other): return self._main.items() >= other + def __cmp__(self, other): return cmp(self._main.items(), other) + + def __contains__(self, item): return item in self._main.items() + def __len__(self): return len(self._main._sequence) # easier :-) + def __iter__(self): return self._main.iteritems() + def count(self, item): return self._main.items().count(item) + def index(self, item, *args): return self._main.items().index(item, *args) + def reverse(self): self._main.reverse() + def sort(self, *args, **kwds): self._main.sort(*args, **kwds) + def __mul__(self, n): return self._main.items()*n + __rmul__ = __mul__ + def __add__(self, other): return self._main.items() + other + def __radd__(self, other): return other + self._main.items() + + def append(self, item): + """Add an item to the end.""" + # FIXME: this is only append if the key isn't already present + key, value = item + self._main[key] = value + + def insert(self, i, item): + key, value = item + self._main.insert(i, key, value) + + def pop(self, i=-1): + key = self._main._sequence[i] + return (key, self._main.pop(key)) + + def remove(self, item): + key, value = item + try: + assert value == self._main[key] + except (KeyError, AssertionError): + raise ValueError('ValueError: list.remove(x): x not in list') + else: + del self._main[key] + + def extend(self, other): + # FIXME: is only a true extend if none of the keys already present + for item in other: + key, value = item + self._main[key] = value + + def __iadd__(self, other): + self.extend(other) + + ## following methods not implemented for items ## + + def __imul__(self, n): raise TypeError('Can\'t multiply items in place') + +class Values(object): + """ + Custom object for accessing the values of an OrderedDict. + + Can be called like the normal ``OrderedDict.values`` method, but also + supports indexing and sequence methods. + """ + + def __init__(self, main): + self._main = main + + def __call__(self): + """Pretend to be the values method.""" + return self._main._values() + + def __getitem__(self, index): + """Fetch the value at position i.""" + if isinstance(index, types.SliceType): + return [self._main[key] for key in self._main._sequence[index]] + else: + return self._main[self._main._sequence[index]] + + def __setitem__(self, index, value): + """ + Set the value at position i to value. + + You can only do slice assignment to values if you supply a sequence of + equal length to the slice you are replacing. + """ + if isinstance(index, types.SliceType): + keys = self._main._sequence[index] + if len(keys) != len(value): + raise ValueError('attempt to assign sequence of size %s ' + 'to slice of size %s' % (len(name), len(keys))) + # FIXME: efficiency? Would be better to calculate the indexes + # directly from the slice object + # NOTE: the new keys can collide with existing keys (or even + # contain duplicates) - these will overwrite + for key, val in zip(keys, value): + self._main[key] = val + else: + self._main[self._main._sequence[index]] = value + + ### following methods pinched from UserList and adapted ### + def __repr__(self): return repr(self._main.values()) + + # FIXME: do we need to check if we are comparing with another ``Values`` + # object? (like the __cast method of UserList) + def __lt__(self, other): return self._main.values() < other + def __le__(self, other): return self._main.values() <= other + def __eq__(self, other): return self._main.values() == other + def __ne__(self, other): return self._main.values() != other + def __gt__(self, other): return self._main.values() > other + def __ge__(self, other): return self._main.values() >= other + def __cmp__(self, other): return cmp(self._main.values(), other) + + def __contains__(self, item): return item in self._main.values() + def __len__(self): return len(self._main._sequence) # easier :-) + def __iter__(self): return self._main.itervalues() + def count(self, item): return self._main.values().count(item) + def index(self, item, *args): return self._main.values().index(item, *args) + + def reverse(self): + """Reverse the values""" + vals = self._main.values() + vals.reverse() + # FIXME: efficiency + self[:] = vals + + def sort(self, *args, **kwds): + """Sort the values.""" + vals = self._main.values() + vals.sort(*args, **kwds) + self[:] = vals + + def __mul__(self, n): return self._main.values()*n + __rmul__ = __mul__ + def __add__(self, other): return self._main.values() + other + def __radd__(self, other): return other + self._main.values() + + ## following methods not implemented for values ## + def __delitem__(self, i): raise TypeError('Can\'t delete items from values') + def __iadd__(self, other): raise TypeError('Can\'t add in place to values') + def __imul__(self, n): raise TypeError('Can\'t multiply values in place') + def append(self, item): raise TypeError('Can\'t append items to values') + def insert(self, i, item): raise TypeError('Can\'t insert items into values') + def pop(self, i=-1): raise TypeError('Can\'t pop items from values') + def remove(self, item): raise TypeError('Can\'t remove items from values') + def extend(self, other): raise TypeError('Can\'t extend values') + +class SequenceOrderedDict(OrderedDict): + """ + Experimental version of OrderedDict that has a custom object for ``keys``, + ``values``, and ``items``. + + These are callable sequence objects that work as methods, or can be + manipulated directly as sequences. + + Test for ``keys``, ``items`` and ``values``. + + >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4))) + >>> d + SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) + >>> d.keys + [1, 2, 3] + >>> d.keys() + [1, 2, 3] + >>> d.setkeys((3, 2, 1)) + >>> d + SequenceOrderedDict([(3, 4), (2, 3), (1, 2)]) + >>> d.setkeys((1, 2, 3)) + >>> d.keys[0] + 1 + >>> d.keys[:] + [1, 2, 3] + >>> d.keys[-1] + 3 + >>> d.keys[-2] + 2 + >>> d.keys[0:2] = [2, 1] + >>> d + SequenceOrderedDict([(2, 3), (1, 2), (3, 4)]) + >>> d.keys.reverse() + >>> d.keys + [3, 1, 2] + >>> d.keys = [1, 2, 3] + >>> d + SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) + >>> d.keys = [3, 1, 2] + >>> d + SequenceOrderedDict([(3, 4), (1, 2), (2, 3)]) + >>> a = SequenceOrderedDict() + >>> b = SequenceOrderedDict() + >>> a.keys == b.keys + 1 + >>> a['a'] = 3 + >>> a.keys == b.keys + 0 + >>> b['a'] = 3 + >>> a.keys == b.keys + 1 + >>> b['b'] = 3 + >>> a.keys == b.keys + 0 + >>> a.keys > b.keys + 0 + >>> a.keys < b.keys + 1 + >>> 'a' in a.keys + 1 + >>> len(b.keys) + 2 + >>> 'c' in d.keys + 0 + >>> 1 in d.keys + 1 + >>> [v for v in d.keys] + [3, 1, 2] + >>> d.keys.sort() + >>> d.keys + [1, 2, 3] + >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4)), strict=True) + >>> d.keys[::-1] = [1, 2, 3] + >>> d + SequenceOrderedDict([(3, 4), (2, 3), (1, 2)]) + >>> d.keys[:2] + [3, 2] + >>> d.keys[:2] = [1, 3] + Traceback (most recent call last): + KeyError: 'Keylist is not the same as current keylist.' + + >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4))) + >>> d + SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) + >>> d.values + [2, 3, 4] + >>> d.values() + [2, 3, 4] + >>> d.setvalues((4, 3, 2)) + >>> d + SequenceOrderedDict([(1, 4), (2, 3), (3, 2)]) + >>> d.values[::-1] + [2, 3, 4] + >>> d.values[0] + 4 + >>> d.values[-2] + 3 + >>> del d.values[0] + Traceback (most recent call last): + TypeError: Can't delete items from values + >>> d.values[::2] = [2, 4] + >>> d + SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) + >>> 7 in d.values + 0 + >>> len(d.values) + 3 + >>> [val for val in d.values] + [2, 3, 4] + >>> d.values[-1] = 2 + >>> d.values.count(2) + 2 + >>> d.values.index(2) + 0 + >>> d.values[-1] = 7 + >>> d.values + [2, 3, 7] + >>> d.values.reverse() + >>> d.values + [7, 3, 2] + >>> d.values.sort() + >>> d.values + [2, 3, 7] + >>> d.values.append('anything') + Traceback (most recent call last): + TypeError: Can't append items to values + >>> d.values = (1, 2, 3) + >>> d + SequenceOrderedDict([(1, 1), (2, 2), (3, 3)]) + + >>> d = SequenceOrderedDict(((1, 2), (2, 3), (3, 4))) + >>> d + SequenceOrderedDict([(1, 2), (2, 3), (3, 4)]) + >>> d.items() + [(1, 2), (2, 3), (3, 4)] + >>> d.setitems([(3, 4), (2 ,3), (1, 2)]) + >>> d + SequenceOrderedDict([(3, 4), (2, 3), (1, 2)]) + >>> d.items[0] + (3, 4) + >>> d.items[:-1] + [(3, 4), (2, 3)] + >>> d.items[1] = (6, 3) + >>> d.items + [(3, 4), (6, 3), (1, 2)] + >>> d.items[1:2] = [(9, 9)] + >>> d + SequenceOrderedDict([(3, 4), (9, 9), (1, 2)]) + >>> del d.items[1:2] + >>> d + SequenceOrderedDict([(3, 4), (1, 2)]) + >>> (3, 4) in d.items + 1 + >>> (4, 3) in d.items + 0 + >>> len(d.items) + 2 + >>> [v for v in d.items] + [(3, 4), (1, 2)] + >>> d.items.count((3, 4)) + 1 + >>> d.items.index((1, 2)) + 1 + >>> d.items.index((2, 1)) + Traceback (most recent call last): + ValueError: list.index(x): x not in list + >>> d.items.reverse() + >>> d.items + [(1, 2), (3, 4)] + >>> d.items.reverse() + >>> d.items.sort() + >>> d.items + [(1, 2), (3, 4)] + >>> d.items.append((5, 6)) + >>> d.items + [(1, 2), (3, 4), (5, 6)] + >>> d.items.insert(0, (0, 0)) + >>> d.items + [(0, 0), (1, 2), (3, 4), (5, 6)] + >>> d.items.insert(-1, (7, 8)) + >>> d.items + [(0, 0), (1, 2), (3, 4), (7, 8), (5, 6)] + >>> d.items.pop() + (5, 6) + >>> d.items + [(0, 0), (1, 2), (3, 4), (7, 8)] + >>> d.items.remove((1, 2)) + >>> d.items + [(0, 0), (3, 4), (7, 8)] + >>> d.items.extend([(1, 2), (5, 6)]) + >>> d.items + [(0, 0), (3, 4), (7, 8), (1, 2), (5, 6)] + """ + + def __init__(self, init_val=(), strict=True): + OrderedDict.__init__(self, init_val, strict=strict) + self._keys = self.keys + self._values = self.values + self._items = self.items + self.keys = Keys(self) + self.values = Values(self) + self.items = Items(self) + self._att_dict = { + 'keys': self.setkeys, + 'items': self.setitems, + 'values': self.setvalues, + } + + def __setattr__(self, name, value): + """Protect keys, items, and values.""" + if not '_att_dict' in self.__dict__: + object.__setattr__(self, name, value) + else: + try: + fun = self._att_dict[name] + except KeyError: + OrderedDict.__setattr__(self, name, value) + else: + fun(value) + +if __name__ == '__main__': + if INTP_VER < (2, 3): + raise RuntimeError("Tests require Python v.2.3 or later") + # turn off warnings for tests + warnings.filterwarnings('ignore') + # run the code tests in doctest format + import doctest + m = sys.modules.get('__main__') + globs = m.__dict__.copy() + globs.update({ + 'INTP_VER': INTP_VER, + }) + doctest.testmod(m, globs=globs) + |