[Python-ideas] Sorted lists

[Terry Reedy]

On 4/8/2019 4:48 PM, Barry Scott wrote:
> 
> 
>> 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.

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