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

Public Member Functions

 __init__ (self, iterable=None, key=identity, load=1000)
 
 __new__ (cls, iterable=None, key=identity, load=1000)
 
 clear (self)
 
 add (self, val)
 
 update (self, iterable)
 
 __contains__ (self, val)
 
 discard (self, val)
 
 remove (self, val)
 
 __setitem__ (self, index, 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, val)
 
 bisect_right (self, val)
 
 bisect_key_left (self, key)
 
 bisect_key_right (self, key)
 
 count (self, val)
 
 copy (self)
 
 append (self, val)
 
 extend (self, values)
 
 insert (self, idx, val)
 
 index (self, val, start=None, stop=None)
 
 __add__ (self, that)
 
 __mul__ (self, that)
 
 __imul__ (self, that)
 
 __repr__ (self)
 
- Public Member Functions inherited from UM.SortedList.SortedList
 __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
 
 bisect_key = bisect_key_right
 
- Static Public Attributes inherited from UM.SortedList.SortedList
 bisect = bisect_right
 

Protected Member Functions

 _expand (self, pos)
 
 _delete (self, pos, idx)
 
 _check_order (self, idx, key, val)
 
 _check (self)
 
- Protected Member Functions inherited from UM.SortedList.SortedList
 _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
 
 _keys
 
 _index
 
 _key
 
 _load
 
 _twice
 
 _half
 
 _offset
 
- Protected Attributes inherited from UM.SortedList.SortedList
 _len
 
 _maxes
 
 _lists
 
 _index
 
 _load
 
 _twice
 
 _half
 
 _offset
 

Static Protected Attributes

 _clear = clear
 
 _update = update
 
 _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
 
 _delitem = __delitem__
 
 _getitem = __getitem__
 
 _bisect_right = bisect_right
 

Detailed Description

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

Constructor & Destructor Documentation

◆ __init__()

UM.SortedList.SortedListWithKey.__init__ (   self,
  iterable = None,
  key = identity,
  load = 1000 
)
SortedListWithKey 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 SortedListWithKey.

An optional *key* argument defines a callable that, like the `key`
argument to Python's `sorted` function, extracts a comparison key from
each element. The default is the identity function.

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

Member Function Documentation

◆ __add__()

UM.SortedList.SortedListWithKey.__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 from UM.SortedList.SortedList.

◆ __contains__()

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

Reimplemented from UM.SortedList.SortedList.

◆ __imul__()

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

Reimplemented from UM.SortedList.SortedList.

◆ __mul__()

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

Reimplemented from UM.SortedList.SortedList.

◆ __new__()

UM.SortedList.SortedListWithKey.__new__ (   cls,
  iterable = None,
  key = identity,
  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 from UM.SortedList.SortedList.

◆ __repr__()

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

Reimplemented from UM.SortedList.SortedList.

◆ __setitem__()

UM.SortedList.SortedListWithKey.__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 from UM.SortedList.SortedList.

◆ _check()

UM.SortedList.SortedListWithKey._check (   self)
protected

Reimplemented from UM.SortedList.SortedList.

◆ _check_order()

UM.SortedList.SortedListWithKey._check_order (   self,
  idx,
  key,
  val 
)
protected

Reimplemented from UM.SortedList.SortedList.

◆ _delete()

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

◆ _expand()

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

◆ add()

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

Reimplemented from UM.SortedList.SortedList.

◆ append()

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

Reimplemented from UM.SortedList.SortedList.

◆ bisect_key_left()

UM.SortedList.SortedListWithKey.bisect_key_left (   self,
  key 
)
Similar to the *bisect* module in the standard library, this returns an
appropriate index to insert a value with a given *key*. If values with
*key* are already present, the insertion point will be before (to the
left of) any existing entries.

◆ bisect_key_right()

UM.SortedList.SortedListWithKey.bisect_key_right (   self,
  key 
)
Same as *bisect_key_left*, but if *key* is already present, the insertion
point will be after (to the right of) any existing entries.

◆ bisect_left()

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

◆ bisect_right()

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

◆ clear()

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

Reimplemented from UM.SortedList.SortedList.

◆ copy()

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

Reimplemented from UM.SortedList.SortedList.

◆ count()

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

Reimplemented from UM.SortedList.SortedList.

◆ discard()

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

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

Reimplemented from UM.SortedList.SortedList.

◆ extend()

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

Reimplemented from UM.SortedList.SortedList.

◆ index()

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

◆ insert()

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

◆ irange()

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

◆ irange_key()

UM.SortedList.SortedListWithKey.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`.

`inclusive` is a pair of booleans that indicates whether the min_key
and max_key ought to be included in the range, respectively. The
default is (True, True) such that the range is inclusive of both
`min_key` and `max_key`.

Both `min_key` and `max_key` 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`.

◆ remove()

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

Raises ValueError if *val* is not present.

Reimplemented from UM.SortedList.SortedList.

◆ update()

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

Reimplemented from UM.SortedList.SortedList.


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