sampo.schemas.sorted_list#

Overview#

Classes#

ExtendedSortedList

Sorted-key list is a subtype of sorted list.

Classes#

class sampo.schemas.sorted_list.ExtendedSortedList(iterable=None, key=identity)#

Bases: sortedcontainers.SortedKeyList, abc.ABC

Sorted-key list is a subtype of sorted list.

The sorted-key list maintains values in comparison order based on the result of a key function applied to every value.

All the same methods that are available in SortedList are also available in SortedKeyList.

Additional methods provided:

  • SortedKeyList.key

  • SortedKeyList.bisect_key_left()

  • SortedKeyList.bisect_key_right()

  • SortedKeyList.irange_key()

Some examples below use:

>>> from operator import neg
>>> neg
<built-in function neg>
>>> neg(1)
-1
__setitem__(idx, value)#

This should just set the item by internal index WITHOUT modifying the key

Parameters:

  • idx – the index

  • value – value. Should have tha same key even the old value reverenced by idx

merge(old, value, merger)#

Merges value and old and places the result to the place of old in sorted list. This should NOT modify key of object.

Runtime complexity: O(log(n)) – approximate.

Parameters:

  • merger – a function that takes old and new value and merges it into new one

  • value – value to merge