sorteddict PEP proposal [started off as orderedict]

[Mark Summerfield]

On 26 Sep, 16:20, Paul Hankin <paul.han... at gmail.com> wrote:
> On Sep 26, 3:24 pm, Mark Summerfield <m.n.summerfi... at googlemail.com>
> wrote:
>
> > On 26 Sep, 14:59, Paul Hankin <paul.han... at gmail.com> wrote:
>
> > > On Sep 26, 2:46 pm, Duncan Booth <duncan.bo... at invalid.invalid> wrote:
>
> > > > Paul Hankin <paul.han... at gmail.com> wrote:
> > > > > More flexibly, keep a set of inserted keys that haven't yet been
> > > > > included in the sorted list, and a set of deleted keys that haven't
> > > > > yet been removed from the sorted list. The cache is invalid if either
> > > > > of these sets are empty - and to make it valid you can choose what to
> > > > > do based on the sizes of the two sets (and the sorted list). For
> > > > > instance, if there's just been one insertion you're probably better
> > > > > doing an insertion rather than a full resort. Of course, there's a few
> > > > > nasty cases here but it's always possible to just throw away the
> > > > > sorted list and reconstruct it from the dict keys when things get too
> > > > > hairy (eg, the user deletes a key that's in the inserted-but-not-yet-
> > > > > sorted set).
>
> > > > Yes that sounds good. Did you mean 'The cache is invalid if either of
> > > > these sets is not empty'?
>
> > > Yes :)
>
> > > > If you delete a key which is in the inserted set you can simply delete
> > > > it from the inserted set.
>
> > > No, in case it was already in the sorted list before the insert. You
> > > have to remove it from the inserted set AND add it to the deleted set.
>
> > > --
> > > Paul Hankin
>
> > So should Duncan's
>
> >     def __removekey(self, key):
> >         if key in self.__addkeys:
> >             del self.__addkeys[key]
> >         else:
> >             self.__delkeys.add(key)
>
> > be changed to:
>
> >     def __removekey(self, key):
> >         if key in self.__addkeys:
> >             del self.__addkeys[key]
> >         self.__delkeys.add(key)
>
> Yes, and the same in __addkey: if it's in __delkeys it should be
> removed from there, and added to __addkeys. There's an invariant: any
> key is in at most one of __addkeys and __delkeys.

OK, I have changed both:

    def __addkey(self, key):
        if key in self.__delkeys:
            del self.__delkeys[key]
        self.__addkeys.add(key)


    def __removekey(self, key):
        if key in self.__addkeys:
            del self.__addkeys[key]
        self.__delkeys.add(key)

> > (BTW I'm happy to put up a new version on PyPI, but I'm v. conscious
> > of the fact that the key ideas and code have come from you and Duncan,
> > so if either of you would like to adopt it, I will gladly step aside.
> > I just want a sorteddict in Python, and I don't mind who does it:-)
>
> Speaking for myself, I'm happy to have helped out, but you should
> carry on.

OK, I will if Duncan doesn't want it:-)

> --
> Paul Hankin