I forgot one item in the proposed API:
ordereddict.delete(index : int)
Also, the API for keys() should be
ordereddict.keys(firstindex : int = None, secondindex : int = None)
If called with no args, returns list of all keys (in key order of
course); if one arg is given, returns keys with indexes in range(0,
firstindex); if two args are given, returns keys with indexes in
range(firstindex, secondindex).
Below is a stripped-down implementation in pure python that is just 84
lines long.
(I have a proper version with blank lines and doctests which is 482
lines but I thought that was a bit long to post.)
It should work as a drop-in replacement for dict (apart from
performance), but with the keys ordered by <, so that every list or
iterator that it returns is always in key order.
The get(), has_key(), __contains__(), len(), and __getitem__() methods
are not reimplemented because the base class versions work fine.
I'm only posting it to give a better feel for the API---if someone did
a better (faster) implementation (e.g., in C), that'd be great, but
best to get consensus on an API first I think (if consensus is
possible at all!).
import bisect
class ordereddict(dict):
def __init__(self, *args, **kwargs):
dict.__init__(self, *args, **kwargs)
self.__keys = sorted(dict.keys(self))
def update(self, *args, **kwargs):
dict.update(self, *args, **kwargs)
self.__keys = sorted(dict.keys(self))
@classmethod
def fromkeys(cls, iterable, value=None):
dictionary = cls()
for key in iterable:
dictionary[key] = value
return dictionary
def key(self, index):
return self.__keys[index]
def item(self, index):
key = self.__keys[index]
return key, self[key]
def value(self, index):
return self[self.__keys[index]]
def set_value(self, index, value):
self[self.__keys[index]] = value
def delete(self, index):
key = self.__keys[index]
del self.__keys[index]
dict.__delitem__(self, key)
def copy(self):
dictionary = ordereddict(dict.copy(self))
dictionary.__keys = self.__keys[:]
return dictionary
def clear(self):
self.__keys = []
dict.clear(self)
def setdefault(self, key, value):
if key not in self:
bisect.insort_left(self.__keys, key)
return dict.setdefault(self, key, value)
def pop(self, key, value=None):
if key not in self:
return value
i = bisect.bisect_left(self.__keys, key)
del self.__keys[i]
return dict.pop(self, key, value)
def popitem(self):
item = dict.popitem(self)
i = bisect.bisect_left(self.__keys, item[0])
del self.__keys[i]
return item
def keys(self, firstindex=None, secondindex=None):
if firstindex is not None and secondindex is None:
secondindex = firstindex
firstindex = 0
else:
if firstindex is None:
firstindex = 0
if secondindex is None:
secondindex = len(self)
return self.__keys[firstindex:secondindex]
def values(self):
return [self[key] for key in self.__keys]
def items(self):
return [(key, self[key]) for key in self.__keys]
def __iter__(self):
return iter(self.__keys)
def iterkeys(self):
return iter(self.__keys)
def itervalues(self):
for key in self.__keys:
yield self[key]
def iteritems(self):
for key in self.__keys:
yield key, self[key]
def __delitem__(self, key):
i = bisect.bisect_left(self.__keys, key)
del self.__keys[i]
dict.__delitem__(self, key)
def __setitem__(self, key, value):
if key not in self:
bisect.insort_left(self.__keys, key)
dict.__setitem__(self, key, value)
def __repr__(self):
return "ordereddict({%s})" % ", ".join(
["%r: %r" % (key, self[key]) for key in self.__keys])
--
http://mail.python.org/mailman/listinfo/python-list
