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. > (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. -- Paul Hankin -- http://mail.python.org/mailman/listinfo/python-list
