[Python-ideas] Sorted lists

[Terry Reedy]

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).
> 
> 


-- 
Terry Jan Reedy