Uranium
Application Framework
UM.SortedList.SortedList Class Reference
Inheritance diagram for UM.SortedList.SortedList:
UM.SortedList.SortedKeyList

Public Member Functions

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)
 

Static Public Attributes

int DEFAULT_LOAD_FACTOR = 1000
 
def bisect = bisect_right
 

Detailed Description

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.

Constructor & Destructor Documentation

◆ __init__()

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)

Member Function Documentation

◆ __add__()

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

◆ __contains__()

def UM.SortedList.SortedList.__contains__ (   self,
  value 
)
Return true if `value` is an element of the sorted list.

``sl.__contains__(value)`` <==> ``value in sl``

Runtime complexity: `O(log(n))`

>>> sl = SortedList([1, 2, 3, 4, 5])
>>> 3 in sl
True

:param value: search for value in sorted list
:return: true if `value` in sorted list

◆ __delitem__()

def UM.SortedList.SortedList.__delitem__ (   self,
  index 
)
Remove value at `index` from sorted list.

``sl.__delitem__(index)`` <==> ``del sl[index]``

Supports slicing.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList('abcde')
>>> del sl[2]
>>> sl
SortedList(['a', 'b', 'd', 'e'])
>>> del sl[:2]
>>> sl
SortedList(['d', 'e'])

:param index: integer or slice for indexing
:raises IndexError: if index out of range

◆ __getitem__()

def UM.SortedList.SortedList.__getitem__ (   self,
  index 
)
Lookup value at `index` in sorted list.

``sl.__getitem__(index)`` <==> ``sl[index]``

Supports slicing.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList('abcde')
>>> sl[1]
'b'
>>> sl[-1]
'e'
>>> sl[2:5]
['c', 'd', 'e']

:param index: integer or slice for indexing
:return: value or list of values
:raises IndexError: if index out of range

◆ __iadd__()

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

◆ __imul__()

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

◆ __iter__()

def UM.SortedList.SortedList.__iter__ (   self)
Return an iterator over the sorted list.

``sl.__iter__()`` <==> ``iter(sl)``

Iterating the sorted list while adding or deleting values may raise a
:exc:`RuntimeError` or fail to iterate over all values.

◆ __len__()

def UM.SortedList.SortedList.__len__ (   self)
Return the size of the sorted list.

``sl.__len__()`` <==> ``len(sl)``

:return: size of sorted list

◆ __mul__()

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

◆ __new__()

def UM.SortedList.SortedList.__new__ (   cls,
  iterable = None,
  key = None 
)
Create new sorted list or sorted-key list instance.

Optional `key`-function argument will return an instance of subtype
:class:`SortedKeyList`.

>>> sl = SortedList()
>>> isinstance(sl, SortedList)
True
>>> sl = SortedList(key=lambda x: -x)
>>> isinstance(sl, SortedList)
True
>>> isinstance(sl, SortedKeyList)
True

:param iterable: initial values (optional)
:param key: function used to extract comparison key (optional)
:return: sorted list or sorted-key list instance

◆ __repr__()

def UM.SortedList.SortedList.__repr__ (   self)
Return string representation of sorted list.

``sl.__repr__()`` <==> ``repr(sl)``

:return: string representation

◆ __reversed__()

def UM.SortedList.SortedList.__reversed__ (   self)
Return a reverse iterator over the sorted list.

``sl.__reversed__()`` <==> ``reversed(sl)``

Iterating the sorted list while adding or deleting values may raise a
:exc:`RuntimeError` or fail to iterate over all values.

◆ __setitem__()

def UM.SortedList.SortedList.__setitem__ (   self,
  index,
  value 
)
Raise not-implemented error.

``sl.__setitem__(index, value)`` <==> ``sl[index] = value``

:raises NotImplementedError: use ``del sl[index]`` and
    ``sl.add(value)`` instead

◆ add()

def UM.SortedList.SortedList.add (   self,
  value 
)
Add `value` to sorted list.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList()
>>> sl.add(3)
>>> sl.add(1)
>>> sl.add(2)
>>> sl
SortedList([1, 2, 3])

:param value: value to add to sorted list

◆ append()

def UM.SortedList.SortedList.append (   self,
  value 
)
Raise not-implemented error.

Implemented to override `MutableSequence.append` which provides an
erroneous default implementation.

:raises NotImplementedError: use ``sl.add(value)`` instead

◆ bisect_left()

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

◆ bisect_right()

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

◆ clear()

def UM.SortedList.SortedList.clear (   self)
Remove all values from sorted list.

Runtime complexity: `O(n)`

◆ copy()

def UM.SortedList.SortedList.copy (   self)
Return a shallow copy of the sorted list.

Runtime complexity: `O(n)`

:return: new sorted list

◆ count()

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

◆ discard()

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

◆ extend()

def UM.SortedList.SortedList.extend (   self,
  values 
)
Raise not-implemented error.

Implemented to override `MutableSequence.extend` which provides an
erroneous default implementation.

:raises NotImplementedError: use ``sl.update(values)`` instead

◆ index()

def UM.SortedList.SortedList.index (   self,
  value,
  start = None,
  stop = None 
)
Return first index of value in sorted 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 list.

Negative indices are supported.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList('abcde')
>>> sl.index('d')
3
>>> sl.index('z')
Traceback (most recent call last):
  ...
ValueError: 'z' is not in list

:param value: value in sorted list
:param int start: start index (default None, start of sorted list)
:param int stop: stop index (default None, end of sorted list)
:return: index of value
:raises ValueError: if value is not present

◆ insert()

def UM.SortedList.SortedList.insert (   self,
  index,
  value 
)
Raise not-implemented error.

:raises NotImplementedError: use ``sl.add(value)`` instead

◆ irange()

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

◆ islice()

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

◆ key()

def UM.SortedList.SortedList.key (   self)
Function used to extract comparison key from values.

Sorted list compares values directly so the key function is none.

◆ pop()

def UM.SortedList.SortedList.pop (   self,
  index = -1 
)
Remove and return value at `index` in sorted list.

Raise :exc:`IndexError` if the sorted list is empty or index is out of
range.

Negative indices are supported.

Runtime complexity: `O(log(n))` -- approximate.

>>> sl = SortedList('abcde')
>>> sl.pop()
'e'
>>> sl.pop(2)
'c'
>>> sl
SortedList(['a', 'b', 'd'])

:param int index: index of value (default -1)
:return: value
:raises IndexError: if index is out of range

◆ remove()

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

◆ reverse()

def UM.SortedList.SortedList.reverse (   self)
Raise not-implemented error.

Sorted list maintains values in ascending sort order. Values may not be
reversed in-place.

Use ``reversed(sl)`` for an iterator over values in descending sort
order.

Implemented to override `MutableSequence.reverse` which provides an
erroneous default implementation.

:raises NotImplementedError: use ``reversed(sl)`` instead

◆ update()

def UM.SortedList.SortedList.update (   self,
  iterable 
)
Update sorted list by adding all values from `iterable`.

Runtime complexity: `O(k*log(n))` -- approximate.

>>> sl = SortedList()
>>> sl.update([3, 1, 2])
>>> sl
SortedList([1, 2, 3])

:param iterable: iterable of values to add

The documentation for this class was generated from the following file: