sorteddict PEP proposal [started off as orderedict]

[Mark Summerfield]

On 25 Sep, 22:33, Paul Hankin <paul.han... at gmail.com> wrote:
> On Sep 25, 9:55 pm, Mark Summerfield <m.n.summerfi... at googlemail.com>
> wrote:
>
> > ...
> > class sorteddict(dict):
>
> > ...
> >         if self.__keys is None:
> >             self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
> >                                  key=self.__key,
> > reverse=self.__reverse)
>
> You'd be better defining __keys like this:
>
> def __getkeys(self):
>   if self.__keycache is None:
>      self.__keycache = dict.keys(self)
>      self.__keycache.sort(cmp=...)
>   return self.__keycache
>
> __keys = property(__getkeys)
>
> and where you have 'self.__keys = None', either replace with
> 'self.__keycache = None' or more cleanly with a call to:
>
> def __invalidate_key_cache(self):
>     self.__keycache = None
>
> to improve the code quality.

Yes, that's much better.

As you've no doubt realised, this particular implementation gives best
performance when the pattern of use is: lots of edits, lots of
lookups, ..., and gives worst performance when the pattern of use is:
edit, lookup, edit, lookup (in which case using a dict and sorted() is
probably better).

So there is lots of scope for someone to do a version that has good
performance for all patterns of use:-)

I've put a full version with doctests & docstrings on PyPI:
http://pypi.python.org/pypi/sorteddict

Here's the stripped version (just 92 lines):

class sorteddict(dict):

    def __init__(self, iterable=None, cmp=None, key=None,
reverse=False):
        if iterable is None:
            iterable = []
        dict.__init__(self, iterable)
        self.__cmp = cmp
        self.__key = key
        self.__reverse = reverse
        self.__keycache = None

    @property
    def __keys(self):
        if self.__keycache is None:
            self.__keycache = dict.keys(self)
            self.__keycache.sort(cmp=self.__cmp, key=self.__key,
                                 reverse=self.__reverse)
        return self.__keycache

    def __invalidate_key_cache(self):
        self.__keycache = None

    def update(self, *args, **kwargs):
        self.__invalidate_key_cache()
        dict.update(self, *args, **kwargs)

    @classmethod
    def fromkeys(cls, iterable, value=None):
        dictionary = cls()
        for key in iterable:
            dictionary[key] = value
        return dictionary

    def copy(self):
        return sorteddict(dict.copy(self), cmp=self.__cmp,
                          key=self.__key, reverse=self.__reverse)

    def clear(self):
        self.__invalidate_key_cache()
        dict.clear(self)

    def setdefault(self, key, value):
        self.__invalidate_key_cache()
        return dict.setdefault(self, key, value)

    def pop(self, key, value=None):
        if key not in self:
            return value
        self.__invalidate_key_cache()
        return dict.pop(self, key, value)

    def popitem(self):
        self.__invalidate_key_cache()
        return dict.popitem(self)

    def keys(self):
        return self.__keys[:]

    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):
        self.__invalidate_key_cache()
        dict.__delitem__(self, key)

    def __setitem__(self, key, value):
        self.__invalidate_key_cache()
        dict.__setitem__(self, key, value)

    def __repr__(self):
        raise NotImplementedError()

    def __str__(self):
        return "{%s}" % ", ".join(
               ["%r: %r" % (key, self[key]) for key in self.__keys])