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

Public Member Functions

 __init__ (self, iterable=None, load=1000)
 
 __new__ (cls, iterable=None, key=None, load=1000)
 
 clear (self)
 
 add (self, val)
 
 update (self, iterable)
 
 __contains__ (self, val)
 
 discard (self, val)
 
 remove (self, val)
 
 __delitem__ (self, idx)
 
 __getitem__ (self, idx)
 
 __setitem__ (self, index, value)
 
 __iter__ (self)
 
 __reversed__ (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, val)
 
 bisect_right (self, val)
 
 count (self, val)
 
 copy (self)
 
 append (self, val)
 
 extend (self, values)
 
 insert (self, idx, val)
 
 pop (self, idx=-1)
 
 index (self, val, start=None, stop=None)
 
 __add__ (self, that)
 
 __iadd__ (self, that)
 
 __mul__ (self, that)
 
 __imul__ (self, that)
 
 __repr__ (self)
 

Static Public Attributes

 bisect = bisect_right
 

Protected Member Functions

 _expand (self, pos)
 
 _delete (self, pos, idx)
 
 _loc (self, pos, idx)
 
 _pos (self, idx)
 
 _build_index (self)
 
 _check_order (self, idx, val)
 
 _islice (self, min_pos, min_idx, max_pos, max_idx, reverse)
 
 _make_cmp (seq_op, doc)
 
 _check (self)
 

Protected Attributes

 _len
 
 _maxes
 
 _lists
 
 _index
 
 _load
 
 _twice
 
 _half
 
 _offset
 

Static Protected Attributes

 _clear = clear
 
 _update = update
 
 _delitem = __delitem__
 
 _getitem = __getitem__
 
 _bisect_right = bisect_right
 

Detailed Description

SortedList provides most of the same methods as a list but keeps the items
in sorted order.

Constructor & Destructor Documentation

◆ __init__()

UM.SortedList.SortedList.__init__ (   self,
  iterable = None,
  load = 1000 
)
SortedList provides most of the same methods as a list but keeps the
items in sorted order.

An optional *iterable* provides an initial series of items to populate
the SortedList.

An optional *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 elements.  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.

Reimplemented in UM.SortedList.SortedListWithKey.

Member Function Documentation

◆ __add__()

UM.SortedList.SortedList.__add__ (   self,
  that 
)
Return a new sorted list containing all the elements in *self* and
*that*. Elements in *that* do not need to be properly ordered with
respect to *self*.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ __contains__()

UM.SortedList.SortedList.__contains__ (   self,
  val 
)
Return True if and only if *val* is an element in the list.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ __delitem__()

UM.SortedList.SortedList.__delitem__ (   self,
  idx 
)
Remove the element at *idx*. Supports slicing.

◆ __getitem__()

UM.SortedList.SortedList.__getitem__ (   self,
  idx 
)
Return the element at *idx*. Supports slicing.

◆ __iadd__()

UM.SortedList.SortedList.__iadd__ (   self,
  that 
)
Update *self* to include all values in *that*. Elements in *that* do not
need to be properly ordered with respect to *self*.

◆ __imul__()

UM.SortedList.SortedList.__imul__ (   self,
  that 
)
Increase the length of the list by appending *that* shallow copies of
each item.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ __iter__()

UM.SortedList.SortedList.__iter__ (   self)
Return an iterator over the Sequence.

Iterating the Sequence while adding or deleting values may raise a
`RuntimeError` or fail to iterate over all entries.

◆ __len__()

UM.SortedList.SortedList.__len__ (   self)
Return the number of elements in the list.

◆ __mul__()

UM.SortedList.SortedList.__mul__ (   self,
  that 
)
Return a new sorted list containing *that* shallow copies of each item
in SortedList.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ __new__()

UM.SortedList.SortedList.__new__ (   cls,
  iterable = None,
  key = None,
  load = 1000 
)
SortedList provides most of the same methods as a list but keeps the
items in sorted order.

An optional *iterable* provides an initial series of items to populate
the SortedList.

An optional *key* argument will return an instance of subtype
SortedListWithKey.

An optional *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 elements.  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.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ __repr__()

UM.SortedList.SortedList.__repr__ (   self)
Return string representation of sequence.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ __reversed__()

UM.SortedList.SortedList.__reversed__ (   self)
Return an iterator to traverse the Sequence in reverse.

Iterating the Sequence while adding or deleting values may raise a
`RuntimeError` or fail to iterate over all entries.

◆ __setitem__()

UM.SortedList.SortedList.__setitem__ (   self,
  index,
  value 
)
Replace the item at position *index* with *value*.

Supports slice notation. Raises a :exc:`ValueError` if the sort order
would be violated. When used with a slice and iterable, the
:exc:`ValueError` is raised before the list is mutated if the sort order
would be violated by the operation.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ _build_index()

UM.SortedList.SortedList._build_index (   self)
protected
Build an 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 self._pos for details.

◆ _delete()

UM.SortedList.SortedList._delete (   self,
  pos,
  idx 
)
protected
Delete the item 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 self._loc.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ _expand()

UM.SortedList.SortedList._expand (   self,
  pos 
)
protected
Splits sublists that are more than double the load level.

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 self._loc.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ _islice()

UM.SortedList.SortedList._islice (   self,
  min_pos,
  min_idx,
  max_pos,
  max_idx,
  reverse 
)
protected
Returns an iterator that slices `self` using two index pairs,
`(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 (alpha, beta) into a single index that corresponds to
the position of the value in the sorted list.

Most queries require the index be built. Details of the index are
described in self._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 self._build_index:

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

Tree:

         14
      5      9
    3   2  4   5

Converting 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.

Computing the index is the sum of the total and beta: 5 + 3 = 8.

◆ _pos()

UM.SortedList.SortedList._pos (   self,
  idx 
)
protected
Convert an index into a pair (alpha, beta) that can be used to access
the corresponding _lists[alpha][beta] position.

Most queries require the index be built. Details of the index are
described in self._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 self._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.

◆ add()

UM.SortedList.SortedList.add (   self,
  val 
)
Add the element *val* to the list.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ append()

UM.SortedList.SortedList.append (   self,
  val 
)
Append the element *val* to the list. Raises a ValueError if the *val*
would violate the sort order.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ bisect_left()

UM.SortedList.SortedList.bisect_left (   self,
  val 
)
Similar to the *bisect* module in the standard library, this returns an
appropriate index to insert *val*. If *val* is already present, the
insertion point will be before (to the left of) any existing entries.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ bisect_right()

UM.SortedList.SortedList.bisect_right (   self,
  val 
)
Same as *bisect_left*, but if *val* is already present, the insertion
point will be after (to the right of) any existing entries.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ clear()

UM.SortedList.SortedList.clear (   self)
Remove all the elements from the list.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ copy()

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

Reimplemented in UM.SortedList.SortedListWithKey.

◆ count()

UM.SortedList.SortedList.count (   self,
  val 
)
Return the number of occurrences of *val* in the list.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ discard()

UM.SortedList.SortedList.discard (   self,
  val 
)
Remove the first occurrence of *val*.

If *val* is not a member, does nothing.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ extend()

UM.SortedList.SortedList.extend (   self,
  values 
)
Extend the list by appending all elements from the *values*. Raises a
ValueError if the sort order would be violated.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ index()

UM.SortedList.SortedList.index (   self,
  val,
  start = None,
  stop = None 
)
Return the smallest *k* such that L[k] == val and i <= k < j`.  Raises
ValueError if *val* is not present.  *stop* defaults to the end of the
list. *start* defaults to the beginning. Negative indices are supported,
as for slice indices.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ insert()

UM.SortedList.SortedList.insert (   self,
  idx,
  val 
)
Insert the element *val* into the list at *idx*. Raises a ValueError if
the *val* at *idx* would violate the sort order.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ irange()

UM.SortedList.SortedList.irange (   self,
  minimum = None,
  maximum = None,
  inclusive = (True, True),
  reverse = False 
)
Create an iterator of values between `minimum` and `maximum`.

`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.

Both `minimum` and `maximum` default to `None` which is automatically
inclusive of the start and end of the list, respectively.

When `reverse` is `True` the values are yielded from the iterator in
reverse order; `reverse` defaults to `False`.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ islice()

UM.SortedList.SortedList.islice (   self,
  start = None,
  stop = None,
  reverse = False 
)
Returns an iterator that slices `self` from `start` to `stop` index,
inclusive and exclusive respectively.

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

Both `start` and `stop` default to `None` which is automatically
inclusive of the beginning and end.

◆ pop()

UM.SortedList.SortedList.pop (   self,
  idx = -1 
)
Remove and return item at *idx* (default last).  Raises IndexError if
list is empty or index is out of range.  Negative indices are supported,
as for slice indices.

◆ remove()

UM.SortedList.SortedList.remove (   self,
  val 
)
Remove first occurrence of *val*.

Raises ValueError if *val* is not present.

Reimplemented in UM.SortedList.SortedListWithKey.

◆ update()

UM.SortedList.SortedList.update (   self,
  iterable 
)
Update the list by adding all elements from *iterable*.

Reimplemented in UM.SortedList.SortedListWithKey.


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