Uranium
Application Framework
Loading...
Searching...
No Matches
UM.SortedList.SortedList Class Reference
Inheritance diagram for UM.SortedList.SortedList:
UM.SortedList.SortedKeyList

Public Member Functions

 __init__ (self, iterable=None, key=None)
 __new__ (cls, iterable=None, key=None)
 key (self)
 clear (self)
 add (self, value)
 update (self, iterable)
 __contains__ (self, value)
 discard (self, value)
 remove (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)
 irange (self, minimum=None, maximum=None, inclusive=(True, True), reverse=False)
 __len__ (self)
 bisect_left (self, value)
 bisect_right (self, value)
 count (self, value)
 copy (self)
 append (self, value)
 extend (self, values)
 insert (self, index, value)
 pop (self, index=-1)
 index (self, value, start=None, stop=None)
 __add__ (self, other)
 __iadd__ (self, other)
 __mul__ (self, num)
 __imul__ (self, num)
 __repr__ (self)

Static Public Attributes

int DEFAULT_LOAD_FACTOR = 1000
 bisect = bisect_right

Protected Member Functions

 _reset (self, load)
 _expand (self, pos)
 _delete (self, pos, idx)
 _loc (self, pos, idx)
 _pos (self, idx)
 _build_index (self)
 _islice (self, min_pos, min_idx, max_pos, max_idx, reverse)
 _check (self)

Protected Attributes

int _len = 0
int _load = self.DEFAULT_LOAD_FACTOR
list _lists = []
list _maxes = []
list _index = []
int _offset = 0

Static Protected Attributes

 _clear = clear
 _update = update
 _getitem = __getitem__
 _bisect_right = 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__()

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__()

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__()

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__()

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__()

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__()

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__()

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__()

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__()

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

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

:return: size of sorted list

◆ __mul__()

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__()

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__()

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

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

:return: string representation

◆ __reversed__()

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__()

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

◆ _build_index()

UM.SortedList.SortedList._build_index ( self)
protected
Build a positional index for indexing the sorted list.

Indexes are represented as binary trees in a dense array notation
similar to a binary heap.

For example, given a lists representation storing integers::

    0: [1, 2, 3]
    1: [4, 5]
    2: [6, 7, 8, 9]
    3: [10, 11, 12, 13, 14]

The first transformation maps the sub-lists by their length. The
first row of the index is the length of the sub-lists::

    0: [3, 2, 4, 5]

Each row after that is the sum of consecutive pairs of the previous
row::

    1: [5, 9]
    2: [14]

Finally, the index is built by concatenating these lists together::

    _index = [14, 5, 9, 3, 2, 4, 5]

An offset storing the start of the first row is also stored::

    _offset = 3

When built, the index can be used for efficient indexing into the list.
See the comment and notes on ``SortedList._pos`` for details.

◆ _check()

UM.SortedList.SortedList._check ( self)
protected
Check invariants of sorted list.

Runtime complexity: `O(n)`

Reimplemented in UM.SortedList.SortedKeyList.

◆ _delete()

UM.SortedList.SortedList._delete ( self,
pos,
idx )
protected
Delete value at the given `(pos, idx)`.

Combines lists that are less than half the load level.

Updates the index when the sublist length is more than half the load
level. This requires decrementing the nodes in a traversal from the
leaf node to the root. For an example traversal see
``SortedList._loc``.

:param int pos: lists index
:param int idx: sublist index

Reimplemented in UM.SortedList.SortedKeyList.

◆ _expand()

UM.SortedList.SortedList._expand ( self,
pos )
protected
Split sublists with length greater than double the load-factor.

Updates the index when the sublist length is less than double the load
level. This requires incrementing the nodes in a traversal from the
leaf node to the root. For an example traversal see
``SortedList._loc``.

Reimplemented in UM.SortedList.SortedKeyList.

◆ _islice()

UM.SortedList.SortedList._islice ( self,
min_pos,
min_idx,
max_pos,
max_idx,
reverse )
protected
Return an iterator that slices sorted list using two index pairs.

The index pairs are (min_pos, min_idx) and (max_pos, max_idx), the
first inclusive and the latter exclusive. See `_pos` for details on how
an index is converted to an index pair.

When `reverse` is `True`, values are yielded from the iterator in
reverse order.

◆ _loc()

UM.SortedList.SortedList._loc ( self,
pos,
idx )
protected
Convert an index pair (lists index, sublist index) into a single
index number that corresponds to the position of the value in the
sorted list.

Many queries require the index be built. Details of the index are
described in ``SortedList._build_index``.

Indexing requires traversing the tree from a leaf node to the root. The
parent of each node is easily computable at ``(pos - 1) // 2``.

Left-child nodes are always at odd indices and right-child nodes are
always at even indices.

When traversing up from a right-child node, increment the total by the
left-child node.

The final index is the sum from traversal and the index in the sublist.

For example, using the index from ``SortedList._build_index``::

    _index = 14 5 9 3 2 4 5
    _offset = 3

Tree::

         14
      5      9
    3   2  4   5

Converting an index pair (2, 3) into a single index involves iterating
like so:

1. Starting at the leaf node: offset + alpha = 3 + 2 = 5. We identify
   the node as a left-child node. At such nodes, we simply traverse to
   the parent.

2. At node 9, position 2, we recognize the node as a right-child node
   and accumulate the left-child in our total. Total is now 5 and we
   traverse to the parent at position 0.

3. Iteration ends at the root.

The index is then the sum of the total and sublist index: 5 + 3 = 8.

:param int pos: lists index
:param int idx: sublist index
:return: index in sorted list

◆ _pos()

UM.SortedList.SortedList._pos ( self,
idx )
protected
Convert an index into an index pair (lists index, sublist index)
that can be used to access the corresponding lists position.

Many queries require the index be built. Details of the index are
described in ``SortedList._build_index``.

Indexing requires traversing the tree to a leaf node. Each node has two
children which are easily computable. Given an index, pos, the
left-child is at ``pos * 2 + 1`` and the right-child is at ``pos * 2 +
2``.

When the index is less than the left-child, traversal moves to the
left sub-tree. Otherwise, the index is decremented by the left-child
and traversal moves to the right sub-tree.

At a child node, the indexing pair is computed from the relative
position of the child node as compared with the offset and the remaining
index.

For example, using the index from ``SortedList._build_index``::

    _index = 14 5 9 3 2 4 5
    _offset = 3

Tree::

         14
      5      9
    3   2  4   5

Indexing position 8 involves iterating like so:

1. Starting at the root, position 0, 8 is compared with the left-child
   node (5) which it is greater than. When greater the index is
   decremented and the position is updated to the right child node.

2. At node 9 with index 3, we again compare the index to the left-child
   node with value 4. Because the index is the less than the left-child
   node, we simply traverse to the left.

3. At node 4 with index 3, we recognize that we are at a leaf node and
   stop iterating.

4. To compute the sublist index, we subtract the offset from the index
   of the leaf node: 5 - 3 = 2. To compute the index in the sublist, we
   simply use the index remaining from iteration. In this case, 3.

The final index pair from our example is (2, 3) which corresponds to
index 8 in the sorted list.

:param int idx: index in sorted list
:return: (lists index, sublist index) pair

◆ _reset()

UM.SortedList.SortedList._reset ( self,
load )
protected
Reset sorted list load factor.

The `load` specifies the load-factor of the list. The default load
factor of 1000 works well for lists from tens to tens-of-millions of
values. Good practice is to use a value that is the cube root of the
list size. With billions of elements, the best load factor depends on
your usage. It's best to leave the load factor at the default until you
start benchmarking.

See :doc:`implementation` and :doc:`performance-scale` for more
information.

Runtime complexity: `O(n)`

:param int load: load-factor for sorted list sublists

◆ add()

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ append()

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

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ bisect_right()

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ clear()

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

Runtime complexity: `O(n)`

Reimplemented in UM.SortedList.SortedKeyList.

◆ copy()

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

Runtime complexity: `O(n)`

:return: new sorted list

Reimplemented in UM.SortedList.SortedKeyList.

◆ count()

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ discard()

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ extend()

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

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ insert()

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

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

◆ irange()

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ islice()

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

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

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ pop()

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

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

Reimplemented in UM.SortedList.SortedKeyList.

◆ reverse()

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

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

Reimplemented in UM.SortedList.SortedKeyList.


The documentation for this class was generated from the following file:
  • UM/SortedList.py