|
def | __init__ (self, iterable=None, key=None) |
|
def | __new__ (cls, iterable=None, key=None) |
|
def | key (self) |
|
def | clear (self) |
|
def | add (self, value) |
|
def | update (self, iterable) |
|
def | __contains__ (self, value) |
|
def | discard (self, value) |
|
def | remove (self, value) |
|
def | __delitem__ (self, index) |
|
def | __getitem__ (self, index) |
|
def | __setitem__ (self, index, value) |
|
def | __iter__ (self) |
|
def | __reversed__ (self) |
|
def | reverse (self) |
|
def | islice (self, start=None, stop=None, reverse=False) |
|
def | irange (self, minimum=None, maximum=None, inclusive=(True, True), reverse=False) |
|
def | __len__ (self) |
|
def | bisect_left (self, value) |
|
def | bisect_right (self, value) |
|
def | count (self, value) |
|
def | copy (self) |
|
def | append (self, value) |
|
def | extend (self, values) |
|
def | insert (self, index, value) |
|
def | pop (self, index=-1) |
|
def | index (self, value, start=None, stop=None) |
|
def | __add__ (self, other) |
|
def | __iadd__ (self, other) |
|
def | __mul__ (self, num) |
|
def | __imul__ (self, num) |
|
def | __repr__ (self) |
|
Sorted list is a sorted mutable sequence.
Sorted list values are maintained in sorted order.
Sorted list values must be comparable. The total ordering of values must
not change while they are stored in the sorted list.
Methods for adding values:
* :func:`SortedList.add`
* :func:`SortedList.update`
* :func:`SortedList.__add__`
* :func:`SortedList.__iadd__`
* :func:`SortedList.__mul__`
* :func:`SortedList.__imul__`
Methods for removing values:
* :func:`SortedList.clear`
* :func:`SortedList.discard`
* :func:`SortedList.remove`
* :func:`SortedList.pop`
* :func:`SortedList.__delitem__`
Methods for looking up values:
* :func:`SortedList.bisect_left`
* :func:`SortedList.bisect_right`
* :func:`SortedList.count`
* :func:`SortedList.index`
* :func:`SortedList.__contains__`
* :func:`SortedList.__getitem__`
Methods for iterating values:
* :func:`SortedList.irange`
* :func:`SortedList.islice`
* :func:`SortedList.__iter__`
* :func:`SortedList.__reversed__`
Methods for miscellany:
* :func:`SortedList.copy`
* :func:`SortedList.__len__`
* :func:`SortedList.__repr__`
* :func:`SortedList._check`
* :func:`SortedList._reset`
Sorted lists use lexicographical ordering semantics when compared to other
sequences.
Some methods of mutable sequences are not supported and will raise
not-implemented error.
def UM.SortedList.SortedList.__init__ |
( |
|
self, |
|
|
|
iterable = None , |
|
|
|
key = None |
|
) |
| |
Initialize sorted list instance.
Optional `iterable` argument provides an initial iterable of values to
initialize the sorted list.
Runtime complexity: `O(n*log(n))`
>>> sl = SortedList()
>>> sl
SortedList([])
>>> sl = SortedList([3, 1, 2, 5, 4])
>>> sl
SortedList([1, 2, 3, 4, 5])
:param iterable: initial values (optional)
def UM.SortedList.SortedList.__add__ |
( |
|
self, |
|
|
|
other |
|
) |
| |
Return new sorted list containing all values in both sequences.
``sl.__add__(other)`` <==> ``sl + other``
Values in `other` do not need to be in sorted order.
Runtime complexity: `O(n*log(n))`
>>> sl1 = SortedList('bat')
>>> sl2 = SortedList('cat')
>>> sl1 + sl2
SortedList(['a', 'a', 'b', 'c', 't', 't'])
:param other: other iterable
:return: new sorted list
def UM.SortedList.SortedList.__iadd__ |
( |
|
self, |
|
|
|
other |
|
) |
| |
Update sorted list with values from `other`.
``sl.__iadd__(other)`` <==> ``sl += other``
Values in `other` do not need to be in sorted order.
Runtime complexity: `O(k*log(n))` -- approximate.
>>> sl = SortedList('bat')
>>> sl += 'cat'
>>> sl
SortedList(['a', 'a', 'b', 'c', 't', 't'])
:param other: other iterable
:return: existing sorted list
def UM.SortedList.SortedList.__imul__ |
( |
|
self, |
|
|
|
num |
|
) |
| |
Update the sorted list with `num` shallow copies of values.
``sl.__imul__(num)`` <==> ``sl *= num``
Runtime complexity: `O(n*log(n))`
>>> sl = SortedList('abc')
>>> sl *= 3
>>> sl
SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
:param int num: count of shallow copies
:return: existing sorted list
def UM.SortedList.SortedList.__mul__ |
( |
|
self, |
|
|
|
num |
|
) |
| |
Return new sorted list with `num` shallow copies of values.
``sl.__mul__(num)`` <==> ``sl * num``
Runtime complexity: `O(n*log(n))`
>>> sl = SortedList('abc')
>>> sl * 3
SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
:param int num: count of shallow copies
:return: new sorted list
def UM.SortedList.SortedList.bisect_left |
( |
|
self, |
|
|
|
value |
|
) |
| |
Return an index to insert `value` in the sorted list.
If the `value` is already present, the insertion point will be before
(to the left of) any existing values.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList([10, 11, 12, 13, 14])
>>> sl.bisect_left(12)
2
:param value: insertion index of value in sorted list
:return: index
def UM.SortedList.SortedList.bisect_right |
( |
|
self, |
|
|
|
value |
|
) |
| |
Return an index to insert `value` in the sorted list.
Similar to `bisect_left`, but if `value` is already present, the
insertion point with be after (to the right of) any existing values.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList([10, 11, 12, 13, 14])
>>> sl.bisect_right(12)
3
:param value: insertion index of value in sorted list
:return: index
def UM.SortedList.SortedList.count |
( |
|
self, |
|
|
|
value |
|
) |
| |
Return number of occurrences of `value` in the sorted list.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
>>> sl.count(3)
3
:param value: value to count in sorted list
:return: count
def UM.SortedList.SortedList.discard |
( |
|
self, |
|
|
|
value |
|
) |
| |
Remove `value` from sorted list if it is a member.
If `value` is not a member, do nothing.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList([1, 2, 3, 4, 5])
>>> sl.discard(5)
>>> sl.discard(0)
>>> sl == [1, 2, 3, 4]
True
:param value: `value` to discard from sorted list
def UM.SortedList.SortedList.irange |
( |
|
self, |
|
|
|
minimum = None , |
|
|
|
maximum = None , |
|
|
|
inclusive = (True, True) , |
|
|
|
reverse = False |
|
) |
| |
Create an iterator of values between `minimum` and `maximum`.
Both `minimum` and `maximum` default to `None` which is automatically
inclusive of the beginning and end of the sorted list.
The argument `inclusive` is a pair of booleans that indicates whether
the minimum and maximum ought to be included in the range,
respectively. The default is ``(True, True)`` such that the range is
inclusive of both minimum and maximum.
When `reverse` is `True` the values are yielded from the iterator in
reverse order; `reverse` defaults to `False`.
>>> sl = SortedList('abcdefghij')
>>> it = sl.irange('c', 'f')
>>> list(it)
['c', 'd', 'e', 'f']
:param minimum: minimum value to start iterating
:param maximum: maximum value to stop iterating
:param inclusive: pair of booleans
:param bool reverse: yield values in reverse order
:return: iterator
def UM.SortedList.SortedList.islice |
( |
|
self, |
|
|
|
start = None , |
|
|
|
stop = None , |
|
|
|
reverse = False |
|
) |
| |
Return an iterator that slices sorted list from `start` to `stop`.
The `start` and `stop` index are treated inclusive and exclusive,
respectively.
Both `start` and `stop` default to `None` which is automatically
inclusive of the beginning and end of the sorted list.
When `reverse` is `True` the values are yielded from the iterator in
reverse order; `reverse` defaults to `False`.
>>> sl = SortedList('abcdefghij')
>>> it = sl.islice(2, 6)
>>> list(it)
['c', 'd', 'e', 'f']
:param int start: start index (inclusive)
:param int stop: stop index (exclusive)
:param bool reverse: yield values in reverse order
:return: iterator
def UM.SortedList.SortedList.remove |
( |
|
self, |
|
|
|
value |
|
) |
| |
Remove `value` from sorted list; `value` must be a member.
If `value` is not a member, raise ValueError.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList([1, 2, 3, 4, 5])
>>> sl.remove(5)
>>> sl == [1, 2, 3, 4]
True
>>> sl.remove(0)
Traceback (most recent call last):
...
ValueError: 0 not in list
:param value: `value` to remove from sorted list
:raises ValueError: if `value` is not in sorted list