[Python-ideas] Sorted lists

[Barry Scott]

> On 8 Apr 2019, at 19:37, Terry Reedy <tjreedy at 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 at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>