On 26 Sep, 16:20, Paul Hankin <[EMAIL PROTECTED]> wrote:
> On Sep 26, 3:24 pm, Mark Summerfield <[EMAIL PROTECTED]>
> wrote:
>
> > On 26 Sep, 14:59, Paul Hankin <[EMAIL PROTECTED]> wrote:
>
> > > On Sep 26, 2:46 pm, Duncan Booth <[EMAIL PROTECTED]> wrote:
>
> > > > Paul Hankin <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
