Summary
A sorted list with efficient query performance and memory usage. |
|
A sorted set with efficient query performance and memory usage. |
SortedList
-
class
pygm.
SortedList
(arg=None, typecode=None, epsilon=64) A sorted list with efficient query performance and memory usage.
The list is initialised with the content of the provided iterable
arg
.The
typecode
argument is a single character that restricts the type of the stored elements. Type codes are defined in the array module of the standard library. If no type code is specified, the type is inferred from the contents ofarg
.The
epsilon
argument allows to trade off memory usage with query performance. The default value is adequate in most cases.Methods for adding and removing elements:
Methods for accessing and querying elements:
Methods for iterating elements:
Methods for lexicographical comparisons:
Other methods:
- Parameters
arg (iterable, optional) – initial elements. Defaults to None.
typecode (char, optional) – type of the stored elements. Defaults to None.
epsilon (int, optional) – space-time trade-off parameter. Defaults to 64.
Example
>>> from pygm import SortedList >>> sl = SortedList([0, 1, 34, 144, 1, 55, 233, 2, 3, 21, 89, 5, 8, 13]) >>> sl SortedList([0, 1, 1, ..., 144, 233]) >>> sl.find_gt(9) # smallest element > 9 13 >>> sl.count(1) # number of elements == 1 2 >>> 42 in sl # membership test False >>> list(sl.range(0, 21, inclusive=(False, True))) # elements 0 < x <= 21 [1, 1, 2, 3, 5, 8, 13, 21] >>> sl[2:10:3] # slicing syntax support SortedList([1, 5, 21]) >>> (sl + [-3, -2, -1]).rank(0) # number of elements <= 0 4
-
__add__
(other) Return a new
SortedList
by merging the elements ofself
withother
.self.__add__(other)
<==>self + other
Values in
other
do not need to be in sorted order.- Parameters
other (iterable) – a sequence of values
- Returns
new list with the merged elements
- Return type
-
__contains__
(x) Check whether
self
contains the given valuex
or not.self.__repr__(x)
<==>x in self
- Parameters
x – value to search
- Returns
True
if an element equal tox
is found,False
otherwise
- Return type
bool
-
__copy__
() Return a copy of
self
.- Returns
new list with the same elements of
self
- Return type
-
__eq__
(other) Return
True
if and only ifself
is equal toother
.self.__eq__(other)
<==>self == other
Comparisons use the lexicographical order.
- Parameters
other (iterable) – a sequence of values
- Returns
True
if sorted list is equal to other- Return type
bool
-
__ge__
(other) Return
True
if and only ifself
is greater than or equal toother
.self.__ge__(other)
<==>self >= other
Comparisons use the lexicographical order.
- Parameters
other (iterable) – a sequence of values
- Returns
True
if sorted list is greater than or equal to other- Return type
bool
-
__getitem__
(i) Return the element at position
i
.self.__getitem__(i)
<==>self[i]
- Parameters
i (int or slice) – index of the element
- Returns
element at position
i
-
__gt__
(other) Return
True
if and only ifself
is greater thanother
.self.__gt__(other)
<==>self > other
Comparisons use the lexicographical order.
- Parameters
other (iterable) – a sequence of values
- Returns
True
if sorted list is greater than other- Return type
bool
-
__init__
(arg=None, typecode=None, epsilon=64) Initialize self. See help(type(self)) for accurate signature.
-
__iter__
() Return an iterator over the elements of
self
.self.__iter__()
<==>iter(self)
- Returns
iterator over the elements
- Return type
iterator
-
__le__
(other) Return
True
if and only ifself
is less than or equal toother
.self.__le__(other)
<==>self <= other
Comparisons use the lexicographical order.
- Parameters
other (iterable) – a sequence of values
- Returns
True
if sorted list is less than or equal to other- Return type
bool
-
__len__
() Return the number of elements in
self
.self.__len__()
<==>len(self)
- Returns
number of elements
- Return type
int
-
__lt__
(other) Return
True
if and only ifself
is less thanother
.self.__lt__(other)
<==>self < other
Comparisons use the lexicographical order.
- Parameters
other (iterable) – a sequence of values
- Returns
True
if sorted list is less than other- Return type
bool
-
__ne__
(other) Return
True
if and only ifself
is not equal toother
.self.__ne__(other)
<==>self != other
Comparisons use the lexicographical order.
- Parameters
other (iterable) – a sequence of values
- Returns
True
if sorted list is not equal to other- Return type
bool
-
__repr__
() Return a string representation of self.
self.__repr__()
<==>repr(self)
- Returns
repr(self)
- Return type
str
-
__reversed__
() Return a reverse iterator over the elements of
self
.self.__iter__()
<==>iter(self)
- Returns
reverse iterator over the elements
- Return type
iterator
-
__sub__
(other) Return a new
SortedList
by removing fromself
the elements found inother
.Equivalent elements are treated individually, that is, if some element is found m times in
self
and n times inother
, it will appear max(m-n, 0) times in the result.self.__sub__(other)
<==>self - other
Values in
other
do not need to be in sorted order.- Parameters
other (iterable) – a sequence of values
- Returns
new list with the elements in the difference
- Return type
-
bisect_left
(x) Locate the insertion point for
x
to maintain sorted order.If
x
is already present, the insertion point will be before (to the left of) any existing entries.Similar to the bisect module in the standard library.
- Parameters
x – value to compare the elements to
- Returns
insertion index in sorted list
- Return type
int
-
bisect_right
(x) Locate the insertion point for
x
to maintain sorted order.If
x
is already present, the insertion point will be after (to the right of) any existing entries.Similar to the bisect module in the standard library.
- Parameters
x – value to compare the elements to
- Returns
insertion index in sorted list
- Return type
int
-
copy
() Return a copy of
self
.- Returns
new list with the same elements of
self
- Return type
-
count
(x) Return the number of elements equal to
x
.- Parameters
x – value to count
- Returns
number of elements
== x
- Return type
int
-
drop_duplicates
() Return
self
with duplicate elements removed.- Returns
new list without duplicates
- Return type
-
find_ge
(x) Find the leftmost element greater than or equal to
x
.- Parameters
x – value to compare the elements to
- Returns
value of the leftmost element
>= x
, orNone
if no such element is found
-
find_gt
(x) Find the leftmost element greater than
x
.- Parameters
x – value to compare the elements to
- Returns
value of the leftmost element
> x
, orNone
if no such element is found
-
find_le
(x) Find the rightmost element less than or equal to
x
- Parameters
x – value to compare the elements to
- Returns
value of the rightmost element
<= x
, orNone
if no such element is found
-
find_lt
(x) Find the rightmost element less than
x
.- Parameters
x – value to compare the elements to
- Returns
value of the rightmost element
< x
, orNone
if no such element is found
-
index
(x, start=None, stop=None) Return the first index of
x
.- Parameters
x – element in the sorted list
start (int, optional) – restrict the search to the elements from this position onwards. Defaults to
None
.stop (int, optional) – restrict the search to the elements before this position. Defaults to
None
.
- Returns
first index of
x
- Return type
int
- Raises
ValueError – if
x
is not present
-
range
(a, b, inclusive=True, True, reverse=False) Return an iterator over elements between
a
andb
.- Parameters
a – lower bound value
b – upper bound value
inclusive (tuple[bool, bool], optional) – a pair of boolean indicating whether the bounds are inclusive (
True
) or exclusive (False
). Defaults to(True, True)
.reverse (bool, optional) – if
True
return an reverse iterator. Defaults toFalse
.
- Returns
iterator over the elements between the given bounds
-
rank
(x) Return the number of elements less than or equal to
x
- Parameters
x – value to compare the elements to
- Returns
number of elements
<= x
- Return type
int
-
stats
() Return a dict containing statistics about
self
.The keys are:
'data size'
size of the elements in bytes'index size'
size of the index in bytes'leaf segments'
number of segments in the last level of the index'height'
number of levels of the index'epsilon'
value of the trade-off parameter of the index'typecode'
type of the elements
- Returns
a dictionary with stats about
self
- Return type
dict[str, object]
SortedSet
-
class
pygm.
SortedSet
(arg=None, typecode=None, epsilon=64) A sorted set with efficient query performance and memory usage.
The set is initialised with the content of the provided iterable
arg
.The
typecode
argument is a single character that restricts the type of the stored elements. Type codes are defined in the array module of the standard library. If no type code is specified, the type is inferred from the contents ofarg
.The
epsilon
argument allows to trade off memory usage with query performance. The default value is adequate in most cases.Methods for set operations:
SortedSet.difference()
(alias forset - other
)SortedSet.intersection()
(alias forset & other
)SortedSet.union()
(alias forset | other
)SortedSet.symmetric_difference()
(alias forset ^ other
)
Methods for accessing and querying elements:
Methods for set comparisons:
SortedSet.__eq__()
(set equality)SortedSet.__ne__()
(set inequality)SortedSet.__ge__()
(superset)SortedSet.__gt__()
(proper superset)SortedSet.__le__()
(subset)SortedSet.__lt__()
(proper subset)
Methods for iterating elements:
Other methods:
- Parameters
arg (iterable, optional) – initial elements. Defaults to None.
typecode (char, optional) – type of the stored elements. Defaults to None.
epsilon (int, optional) – space-time trade-off parameter. Defaults to 64.
-
__contains__
(x) Check whether
self
contains the given valuex
or not.self.__repr__(x)
<==>x in self
- Parameters
x – value to search
- Returns
True
if an element equal tox
is found,False
otherwise
- Return type
bool
-
__copy__
() Return a copy of
self
.- Returns
new set with the same elements of
self
- Return type
-
__eq__
(other) Return
True
if and only ifself
is equal toother
.self.__eq__(other)
<==>self == other
Comparisons use set semantics.
- Parameters
other (SortedSet or set) – a sequence of values
- Returns
True
if sorted set is equal toother
- Return type
bool
-
__ge__
(other) Return
True
if and only ifself
is a superset ofother
.self.__ge__(other)
<==>self >= other
<==>self.issuperset(other)
Comparisons use set semantics.
- Parameters
other (SortedSet or set) – a sequence of values
- Returns
True
if sorted set is a superset ofother
- Return type
bool
-
__getitem__
(i) Return the element at position
i
.self.__getitem__(i)
<==>self[i]
- Parameters
i (int or slice) – index of the element
- Returns
element at position
i
-
__gt__
(other) Return
True
if and only ifself
is a proper superset ofother
.self.__gt__(other)
<==>self > other
Comparisons use set semantics.
- Parameters
other (SortedSet or set) – a sequence of values
- Returns
True
if sorted set is a proper superset ofother
- Return type
bool
-
__init__
(arg=None, typecode=None, epsilon=64) Initialize self. See help(type(self)) for accurate signature.
-
__iter__
() Return an iterator over the elements of
self
.self.__iter__()
<==>iter(self)
- Returns
iterator over the elements
- Return type
iterator
-
__le__
(other) Return
True
if and only ifself
is a subset ofother
.self.__le__(other)
<==>self <= other
<==>self.issubset(other)
Comparisons use set semantics.
- Parameters
other (SortedSet or set) – a sequence of values
- Returns
True
if sorted set is a subset ofother
- Return type
bool
-
__len__
() Return the number of elements in
self
.self.__len__()
<==>len(self)
- Returns
number of elements
- Return type
int
-
__lt__
(other) Return
True
if and only ifself
is a proper subset ofother
.self.__lt__(other)
<==>self < other
Comparisons use set semantics.
- Parameters
other (SortedSet or set) – a sequence of values
- Returns
True
if sorted set is a proper subset ofother
- Return type
bool
-
__ne__
(other) Return
True
if and only ifself
is not equal toother
.self.__eq__(other)
<==>self != other
Comparisons use set semantics.
- Parameters
other (SortedSet or set) – a sequence of values
- Returns
True
if sorted set is not equal toother
- Return type
bool
-
__repr__
() Return a string representation of self.
self.__repr__()
<==>repr(self)
- Returns
repr(self)
- Return type
str
-
__reversed__
() Return a reverse iterator over the elements of
self
.self.__iter__()
<==>iter(self)
- Returns
reverse iterator over the elements
- Return type
iterator
-
bisect_left
(x) Locate the insertion point for
x
to maintain sorted order.If
x
is already present, the insertion point will be before (to the left of) any existing entries.Similar to the bisect module in the standard library.
- Parameters
x – value to compare the elements to
- Returns
insertion index in sorted list
- Return type
int
-
bisect_right
(x) Locate the insertion point for
x
to maintain sorted order.If
x
is already present, the insertion point will be after (to the right of) any existing entries.Similar to the bisect module in the standard library.
- Parameters
x – value to compare the elements to
- Returns
insertion index in sorted list
- Return type
int
-
copy
() Return a copy of
self
.- Returns
new set with the same elements of
self
- Return type
-
count
(x) Return the number of elements equal to
x
.- Parameters
x – value to count
- Returns
number of elements
== x
- Return type
int
-
difference
(other) Return a
SortedSet
with the elements ofself
not found inother
.Values in
other
do not need to be in sorted order.self.difference(other)
<==>self.__sub__(other)
<==>self - other
- Parameters
other (iterable) – a sequence of values
- Returns
new set with the elements in the difference
- Return type
-
find_ge
(x) Find the leftmost element greater than or equal to
x
.- Parameters
x – value to compare the elements to
- Returns
value of the leftmost element
>= x
, orNone
if no such element is found
-
find_gt
(x) Find the leftmost element greater than
x
.- Parameters
x – value to compare the elements to
- Returns
value of the leftmost element
> x
, orNone
if no such element is found
-
find_le
(x) Find the rightmost element less than or equal to
x
- Parameters
x – value to compare the elements to
- Returns
value of the rightmost element
<= x
, orNone
if no such element is found
-
find_lt
(x) Find the rightmost element less than
x
.- Parameters
x – value to compare the elements to
- Returns
value of the rightmost element
< x
, orNone
if no such element is found
-
index
(x, start=None, stop=None) Return the first index of
x
.- Parameters
x – element in the sorted list
start (int, optional) – restrict the search to the elements from this position onwards. Defaults to
None
.stop (int, optional) – restrict the search to the elements before this position. Defaults to
None
.
- Returns
first index of
x
- Return type
int
- Raises
ValueError – if
x
is not present
-
intersection
(other) Return a
SortedSet
with the elements found in bothself
andother
.Values in
other
do not need to be in sorted order.self.intersection(other)
<==>self.__and__(other)
<==>self & other
- Parameters
other (iterable) – a sequence of values
- Returns
new set with the elements in the intersection
- Return type
-
isdisjoint
(other) Return
True
if and only if the set has no elements in common withother
.Sets are disjoint if and only if their intersection is the empty set.
- Parameters
other (iterable) – a sequence of values
- Returns
True
ifself
is disjoint fromother
- Return type
bool
-
issubset
(other) Return
True
if and only ifself
is a subset ofother
.self.__le__(other)
<==>self <= other
<==>self.issubset(other)
Comparisons use set semantics.
- Parameters
other (SortedSet or set) – a sequence of values
- Returns
True
if sorted set is a subset ofother
- Return type
bool
-
issuperset
(other) Return
True
if and only ifself
is a superset ofother
.self.__ge__(other)
<==>self >= other
<==>self.issuperset(other)
Comparisons use set semantics.
- Parameters
other (SortedSet or set) – a sequence of values
- Returns
True
if sorted set is a superset ofother
- Return type
bool
-
range
(a, b, inclusive=True, True, reverse=False) Return an iterator over elements between
a
andb
.- Parameters
a – lower bound value
b – upper bound value
inclusive (tuple[bool, bool], optional) – a pair of boolean indicating whether the bounds are inclusive (
True
) or exclusive (False
). Defaults to(True, True)
.reverse (bool, optional) – if
True
return an reverse iterator. Defaults toFalse
.
- Returns
iterator over the elements between the given bounds
-
rank
(x) Return the number of elements less than or equal to
x
- Parameters
x – value to compare the elements to
- Returns
number of elements
<= x
- Return type
int
-
stats
() Return a dict containing statistics about
self
.The keys are:
'data size'
size of the elements in bytes'index size'
size of the index in bytes'leaf segments'
number of segments in the last level of the index'height'
number of levels of the index'epsilon'
value of the trade-off parameter of the index'typecode'
type of the elements
- Returns
a dictionary with stats about
self
- Return type
dict[str, object]
-
symmetric_difference
(other) Return a
SortedSet
with the elements found in eitherself
orother
but not in both of them.Values in
other
do not need to be in sorted order.self.symmetric_difference(other)
<==>self.__xor__(other)
<==>self ^ other
- Parameters
other (iterable) – a sequence of values
- Returns
new set with the elements in the symmetric difference
- Return type
-
union
(other) Return a new
SortedSet
with the elements in one or bothself
andother
.Values in
other
do not need to be in sorted order.self.union(other)
<==>self | other
- Parameters
other (iterable) – a sequence of values
- Returns
new set with the elements in the union
- Return type