On 4/8/2019 4:48 PM, Barry Scott 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.
I think that this is an argument for a SortedList class. If
.key_function is changes, the list is resorted by the new key function.
To make it thread-safer, access might be locked for the duration.
--
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/
