|
| __init__ (self, iterable=None, key=identity) |
| __new__ (cls, iterable=None, key=identity) |
| key (self) |
| clear (self) |
None | add (self, Any value) |
| update (self, iterable) |
| __contains__ (self, value) |
| discard (self, value) |
None | remove (self, Any value) |
| irange (self, minimum=None, maximum=None, inclusive=(True, True), reverse=False) |
| irange_key (self, min_key=None, max_key=None, inclusive=(True, True), reverse=False) |
| bisect_left (self, value) |
| bisect_right (self, value) |
| bisect_key_left (self, key) |
| bisect_key_right (self, key) |
| count (self, value) |
| copy (self) |
| index (self, value, start=None, stop=None) |
| __add__ (self, other) |
| __mul__ (self, num) |
| __repr__ (self) |
| __init__ (self, iterable=None, key=None) |
| __new__ (cls, iterable=None, key=None) |
| __contains__ (self, value) |
| __delitem__ (self, index) |
| __getitem__ (self, index) |
| __setitem__ (self, index, value) |
| __iter__ (self) |
| __reversed__ (self) |
| reverse (self) |
| islice (self, start=None, stop=None, reverse=False) |
| __len__ (self) |
| append (self, value) |
| extend (self, values) |
| insert (self, index, value) |
| pop (self, index=-1) |
| __add__ (self, other) |
| __iadd__ (self, other) |
| __mul__ (self, num) |
| __imul__ (self, num) |
| __repr__ (self) |
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 :class:`SortedList` are also
available in :class:`SortedKeyList`.
Additional methods provided:
* :attr:`SortedKeyList.key`
* :func:`SortedKeyList.bisect_key_left`
* :func:`SortedKeyList.bisect_key_right`
* :func:`SortedKeyList.irange_key`
Some examples below use:
>>> from operator import neg
>>> neg
<built-in function neg>
>>> neg(1)
-1
UM.SortedList.SortedKeyList.__init__ |
( |
| self, |
|
|
| iterable = None, |
|
|
| key = identity ) |
Initialize sorted-key list instance.
Optional `iterable` argument provides an initial iterable of values to
initialize the sorted-key list.
Optional `key` argument defines a callable that, like the `key`
argument to Python's `sorted` function, extracts a comparison key from
each value. The default is the identity function.
Runtime complexity: `O(n*log(n))`
>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl
SortedKeyList([], key=<built-in function neg>)
>>> skl = SortedKeyList([3, 1, 2], key=neg)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
:param iterable: initial values (optional)
:param key: function used to extract comparison key (optional)
UM.SortedList.SortedKeyList.__add__ |
( |
| self, |
|
|
| other ) |
Return new sorted-key list containing all values in both sequences.
``skl.__add__(other)`` <==> ``skl + other``
Values in `other` do not need to be in sorted-key order.
Runtime complexity: `O(n*log(n))`
>>> from operator import neg
>>> skl1 = SortedKeyList([5, 4, 3], key=neg)
>>> skl2 = SortedKeyList([2, 1, 0], key=neg)
>>> skl1 + skl2
SortedKeyList([5, 4, 3, 2, 1, 0], key=<built-in function neg>)
:param other: other iterable
:return: new sorted-key list
UM.SortedList.SortedKeyList.__contains__ |
( |
| self, |
|
|
| value ) |
Return true if `value` is an element of the sorted-key list.
``skl.__contains__(value)`` <==> ``value in skl``
Runtime complexity: `O(log(n))`
>>> from operator import neg
>>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
>>> 3 in skl
True
:param value: search for value in sorted-key list
:return: true if `value` in sorted-key list
UM.SortedList.SortedKeyList.__mul__ |
( |
| self, |
|
|
| num ) |
Return new sorted-key list with `num` shallow copies of values.
``skl.__mul__(num)`` <==> ``skl * num``
Runtime complexity: `O(n*log(n))`
>>> from operator import neg
>>> skl = SortedKeyList([3, 2, 1], key=neg)
>>> skl * 2
SortedKeyList([3, 3, 2, 2, 1, 1], key=<built-in function neg>)
:param int num: count of shallow copies
:return: new sorted-key list
UM.SortedList.SortedKeyList.bisect_key_left |
( |
| self, |
|
|
| key ) |
Return an index to insert `key` in the sorted-key list.
If the `key` is already present, the insertion point will be before (to
the left of) any existing keys.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_left(-1)
4
:param key: insertion index of key in sorted-key list
:return: index
UM.SortedList.SortedKeyList.bisect_key_right |
( |
| self, |
|
|
| key ) |
Return an index to insert `key` in the sorted-key list.
Similar to `bisect_key_left`, but if `key` is already present, the
insertion point with be after (to the right of) any existing keys.
Similar to the `bisect` module in the standard library.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_right(-1)
5
:param key: insertion index of key in sorted-key list
:return: index
UM.SortedList.SortedKeyList.bisect_left |
( |
| self, |
|
|
| value ) |
Return an index to insert `value` in the sorted-key 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.
>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_left(1)
4
:param value: insertion index of value in sorted-key list
:return: index
Reimplemented from UM.SortedList.SortedList.
UM.SortedList.SortedKeyList.bisect_right |
( |
| self, |
|
|
| value ) |
Return an index to insert `value` in the sorted-key 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.
>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_right(1)
5
:param value: insertion index of value in sorted-key list
:return: index
Reimplemented from UM.SortedList.SortedList.
UM.SortedList.SortedKeyList.count |
( |
| self, |
|
|
| value ) |
Return number of occurrences of `value` in the sorted-key list.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([4, 4, 4, 4, 3, 3, 3, 2, 2, 1], key=neg)
>>> skl.count(2)
2
:param value: value to count in sorted-key list
:return: count
Reimplemented from UM.SortedList.SortedList.
UM.SortedList.SortedKeyList.discard |
( |
| self, |
|
|
| value ) |
Remove `value` from sorted-key list if it is a member.
If `value` is not a member, do nothing.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.discard(1)
>>> skl.discard(0)
>>> skl == [5, 4, 3, 2]
True
:param value: `value` to discard from sorted-key list
Reimplemented from UM.SortedList.SortedList.
UM.SortedList.SortedKeyList.index |
( |
| self, |
|
|
| value, |
|
|
| start = None, |
|
|
| stop = None ) |
Return first index of value in sorted-key list.
Raise ValueError if `value` is not present.
Index must be between `start` and `stop` for the `value` to be
considered present. The default value, None, for `start` and `stop`
indicate the beginning and end of the sorted-key list.
Negative indices are supported.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.index(2)
3
>>> skl.index(0)
Traceback (most recent call last):
...
ValueError: 0 is not in list
:param value: value in sorted-key list
:param int start: start index (default None, start of sorted-key list)
:param int stop: stop index (default None, end of sorted-key list)
:return: index of value
:raises ValueError: if value is not present
Reimplemented from UM.SortedList.SortedList.
UM.SortedList.SortedKeyList.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-key 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`.
>>> from operator import neg
>>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
>>> it = skl.irange(14.5, 11.5)
>>> list(it)
[14, 13, 12]
: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
Reimplemented from UM.SortedList.SortedList.
UM.SortedList.SortedKeyList.irange_key |
( |
| self, |
|
|
| min_key = None, |
|
|
| max_key = None, |
|
|
| inclusive = (True, True), |
|
|
| reverse = False ) |
Create an iterator of values between `min_key` and `max_key`.
Both `min_key` and `max_key` default to `None` which is automatically
inclusive of the beginning and end of the sorted-key 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`.
>>> from operator import neg
>>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
>>> it = skl.irange_key(-14, -12)
>>> list(it)
[14, 13, 12]
:param min_key: minimum key to start iterating
:param max_key: maximum key to stop iterating
:param inclusive: pair of booleans
:param bool reverse: yield values in reverse order
:return: iterator
None UM.SortedList.SortedKeyList.remove |
( |
| self, |
|
|
Any | value ) |
Remove `value` from sorted-key list; `value` must be a member.
If `value` is not a member, raise ValueError.
Runtime complexity: `O(log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
>>> skl.remove(5)
>>> skl == [4, 3, 2, 1]
True
>>> skl.remove(0)
Traceback (most recent call last):
...
ValueError: 0 not in list
:param value: `value` to remove from sorted-key list
:raises ValueError: if `value` is not in sorted-key list
Reimplemented from UM.SortedList.SortedList.
UM.SortedList.SortedKeyList.update |
( |
| self, |
|
|
| iterable ) |
Update sorted-key list by adding all values from `iterable`.
Runtime complexity: `O(k*log(n))` -- approximate.
>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl.update([3, 1, 2])
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
:param iterable: iterable of values to add
Reimplemented from UM.SortedList.SortedList.