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

Public Member Functions

 __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)
 
- Public Member Functions inherited from UM.SortedList.SortedList
 __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)
 

Static Public Attributes

 bisect_key = bisect_key_right
 
- Static Public Attributes inherited from UM.SortedList.SortedList
int DEFAULT_LOAD_FACTOR = 1000
 
 bisect = bisect_right
 

Protected Member Functions

 _expand (self, pos)
 
 _delete (self, pos, idx)
 
 _check (self)
 
- Protected Member Functions inherited from UM.SortedList.SortedList
 _reset (self, load)
 
 _loc (self, pos, idx)
 
 _pos (self, idx)
 
 _build_index (self)
 
 _islice (self, min_pos, min_idx, max_pos, max_idx, reverse)
 

Protected Attributes

 _key = key
 
list _keys = []
 
- Protected Attributes inherited from UM.SortedList.SortedList
int _len = 0
 
int _load = self.DEFAULT_LOAD_FACTOR
 
list _lists = []
 
list _maxes = []
 
list _index = []
 
int _offset = 0
 

Static Protected Attributes

 _irange_key = irange_key
 
 _bisect_key_left = bisect_key_left
 
 _bisect_key_right = bisect_key_right
 
- Static Protected Attributes inherited from UM.SortedList.SortedList
 _clear = clear
 
 _update = update
 
 _getitem = __getitem__
 
 _bisect_right = bisect_right
 

Detailed Description

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

Constructor & Destructor Documentation

◆ __init__()

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)

Member Function Documentation

◆ __add__()

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

◆ __contains__()

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

◆ __mul__()

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

◆ __repr__()

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

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

:return: string representation

◆ _check()

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

Runtime complexity: `O(n)`

Reimplemented from UM.SortedList.SortedList.

◆ _delete()

UM.SortedList.SortedKeyList._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 from UM.SortedList.SortedList.

◆ _expand()

UM.SortedList.SortedKeyList._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 from UM.SortedList.SortedList.

◆ add()

None UM.SortedList.SortedKeyList.add ( self,
Any value )
Add `value` to sorted-key list.

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

>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl.add(3)
>>> skl.add(1)
>>> skl.add(2)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)

:param value: value to add to sorted-key list

Reimplemented from UM.SortedList.SortedList.

◆ bisect_key_left()

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

◆ bisect_key_right()

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

◆ bisect_left()

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.

◆ bisect_right()

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.

◆ clear()

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

Runtime complexity: `O(n)`

Reimplemented from UM.SortedList.SortedList.

◆ copy()

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

Runtime complexity: `O(n)`

:return: new sorted-key list

Reimplemented from UM.SortedList.SortedList.

◆ count()

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.

◆ discard()

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.

◆ index()

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.

◆ irange()

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.

◆ irange_key()

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

◆ key()

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

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

Reimplemented from UM.SortedList.SortedList.

◆ remove()

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.

◆ update()

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.


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