On 25 Sep, 20:28, Paul Hankin <paul.han...@gmail.com> wrote:
> On Sep 25, 7:58 pm, Steven Bethard <steven.beth...@gmail.com> wrote:
>
>
>
> > > Paul Hankin wrote:
> > > ...
> > > class sorteddict(dict):
> > > "A sorted dictionary"
> > > def __init__(self, arg=None, cmp=None, key=None, reverse=False):
> > > if arg:
> > > ...
>
> > With this is the implementation, I'm definitely -1. Not because it's a
> > bad implementation, but because if the iteration is always doing a sort,
> > then there's no reason for a separate data structure. Just use sorted()
> > directly on a regular dict. That has the advantage of being much more
> > obvious about where the expensive operations are::
>
> > for key in sorted(d, ...):
> > ... whatever you want to do ...
>
> > IMHO, the only reason to introduce a sorteddict() is if it minimizes the
> > cost of sorting the keys.
>
> I disagree with your reason for introducing a sorteddict - the main
> reason should be if it makes code that uses it simpler and more
> readable, with efficiency (within reasonable limits) being of
> secondary importance. Unfortunately for sorteddict, your code is
> simpler and more explicit for most obvious use cases.
>
> But, with Bill's cached sorted key list it'll be reasonably efficient,
> and it's likely possible to update the sorted cache more efficiently
> than resorting if there's only been a small number of insertions since
> the last sort, but I haven't the time to do a thorough job.
>
> --
> Paul Hankin

I think that keeping a sorted list of keys is worthwhile, but because
the key or cmp functions could access keys or values or both you have
to invalidate whenever a key or value is added or changed. Here's my
version (v. similar to yours of course, but sorting when necessary):

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.__keys = None

def update(self, *args, **kwargs):
dict.update(self, *args, **kwargs)
self.__keys = None

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

def copy(self):
dictionary = sorteddict(dict.copy(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
dictionary.__keys = None if self.__keys is None else
self.__keys[:]
return dictionary

def clear(self):
self.__keys = None
dict.clear(self)

def setdefault(self, key, value):
self.__keys = None
return dict.setdefault(self, key, value)

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

def popitem(self):
self.__keys = None
return dict.popitem(self)

def keys(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return self.__keys[:]

def values(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return [self[key] for key in self.__keys]

def items(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return [(key, self[key]) for key in self.__keys]

def __iter__(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return iter(self.__keys)

def iterkeys(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return iter(self.__keys)

def itervalues(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
for key in self.__keys:
yield self[key]

def iteritems(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
for key in self.__keys:
yield key, self[key]

def __delitem__(self, key):
self.__keys = None
dict.__delitem__(self, key)

def __setitem__(self, key, value):
self.__keys = None
dict.__setitem__(self, key, value)

def __repr__(self):
return str(self)

def __str__(self):
if self.__keys is None:
self.__keys = sorted(dict.keys(self), cmp=self.__cmp,
key=self.__key,
reverse=self.__reverse)
return "{%s}" % ", ".join(
["%r: %r" % (key, self[key]) for key in self.__keys])