On Mon, 8 Apr 2019 at 22:07, Barry Scott <ba...@barrys-emacs.org> wrote: > > > > > On 8 Apr 2019, at 19:37, Terry Reedy <tjre...@udel.edu> wrote: > > > > On 4/8/2019 5:40 AM, Steven D'Aprano wrote: > >> On Mon, Apr 08, 2019 at 07:44:41AM +0100, Alex Chamberlain wrote: > >>> I think a better abstraction for a sorted list is a new class, which > >>> implements the Sequence protocol (and hence can be used in a lot of > >>> existing list contexts), but only exposed mutation methods that can > >>> guarantee that sorted order can be maintained > >> Perhaps that's a better idea. > >>> (and hence is _not_ a MutableSequence). > >> Right, but it can still be mutable, so long as the mutation methods can > >> maintain the invariant. That means: > >> - the SortedList needs to know the sort direction; > >> - and the key used for sorting; > >> - no slice or item assignment; > > > > Item assignment could be allowed if it checked the new value against > > neighbors and raised ValueError if it would 'unsort' the list. > >> - insertions are okay, since the SortedList can put them in > >> the correct place; > >> - but not append; > >> - deletions are okay, since they won't change the sort invariant > >> (at least not for items with a total order). > > > How do you handle a list of objects that after insertion and being sorted > change their sort key and thus make the list unsorted. > From the point of view of the list nothing changed, but its not sorted now. > > Think if a list of file stat info objects that are sorted by size. > As the files are written to the size changes. > I can loop over the objects and tell them to update the stats. > Now the __is_sorted__ property is wrong. > > Barry > > > > > > > > -- > > Terry Jan Reedy > > > > _______________________________________________ > > Python-ideas mailing list > > Python-ideas@python.org > > https://mail.python.org/mailman/listinfo/python-ideas > > Code of Conduct: http://python.org/psf/codeofconduct/ > > > > _______________________________________________ > Python-ideas mailing list > Python-ideas@python.org > https://mail.python.org/mailman/listinfo/python-ideas > Code of Conduct: http://python.org/psf/codeofconduct/
Evening Barry, I think you're right to recognise that as a risk, but I consider it similar to the risk of someone defining `__hash__` on a mutable object, putting it in a `set` then mutating it. We'd have to make the contract of `SortedList` clear, but I think it would be very difficult to stop the determined user from breaking the contract if they so wished. To be clear, that contract would be that although storing mutable objects is supported, once in the SortedList, a mutable object must not be changed in such a way as to change its key. Alex _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/
