diff options
Diffstat (limited to 'h-client/odict.py')
| -rw-r--r-- | h-client/odict.py | 1399 |
1 files changed, 0 insertions, 1399 deletions
diff --git a/h-client/odict.py b/h-client/odict.py deleted file mode 100644 index 2c8391d..0000000 --- a/h-client/odict.py +++ /dev/null @@ -1,1399 +0,0 @@ -# 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) - |