"""

def __init__(self, init_val=(), strict=False):

"""

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)

def __delitem__(self, key):

"""

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):

"""

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):

"""

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):

"""

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):

"""

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):

"""

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):

"""

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):

"""

return '%s([%s])' % (self.__class__.__name__, ', '.join(

['(%r, %r)' % (key, self[key]) for key in self._sequence]))

def __setitem__(self, key, val):

"""

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):

"""

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):

"""

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):

"""

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):

"""

from copy import deepcopy

return self.__class__(deepcopy(self.items(), memo), self.strict)

def copy(self):

"""

return OrderedDict(self)

def items(self):

"""

return zip(self._sequence, self.values())

def keys(self):

"""

return self._sequence[:]

def values(self, values=None):

"""

return [self[key] for key in self._sequence]

def iteritems(self):

"""

def make_iter(self=self):

keys = self.iterkeys()

while True:

key = keys.next()

yield (key, self[key])

return make_iter()

def iterkeys(self):

"""

return iter(self._sequence)

__iter__ = iterkeys

def itervalues(self):

"""

def make_iter(self=self):

keys = self.iterkeys()

while True:

yield self[keys.next()]

return make_iter()

def clear(self):

"""

dict.clear(self)

self._sequence = []

def pop(self, key, *args):

"""

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):

"""

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):

"""

if key in self:

return self[key]

else:

self[key] = defval

return defval

def update(self, from_od):

"""

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):

"""

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):

"""

self.clear()

# FIXME: this allows you to pass in an OrderedDict as well :-)

self.update(items)

def setkeys(self, keys):

"""

# 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):

"""

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))

def index(self, key):

"""

return self._sequence.index(key)

def insert(self, index, key, value):

"""

if key in self:

# FIXME: efficiency?

del self[key]

self._sequence.insert(index, key)

dict.__setitem__(self, key, value)

def reverse(self):

"""

self._sequence.reverse()

def sort(self, *args, **kwargs):

"""

# FIXME: should this object be a subclass of list?

"""

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):

"""

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')