Summary¶

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 of arg.

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:

• SortedList.__add__()

• SortedList.__sub__()

• SortedList.drop_duplicates()

Methods for accessing and querying elements:

• SortedList.__getitem__()

• SortedList.__contains__()

• SortedList.bisect_left()

• SortedList.bisect_right()

• SortedList.count()

• SortedList.find_ge()

• SortedList.find_gt()

• SortedList.find_le()

• SortedList.find_lt()

• SortedList.index()

• SortedList.rank()

• SortedList.approximate_rank()

Methods for iterating elements:

• SortedList.range()

• SortedList.__iter__()

• SortedList.__reversed__()

Methods for lexicographical comparisons:

• SortedList.__eq__()

• SortedList.__ne__()

• SortedList.__ge__()

• SortedList.__gt__()

• SortedList.__le__()

• SortedList.__lt__()

Other methods:

• SortedList.copy()

• SortedList.stats()

• SortedList.segment()

• SortedList.__repr__()

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 of self with other.

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:

SortedList

classmethod __class_getitem__()¶

Represent a PEP 585 generic type

E.g. for t = list[int], t.__origin__ is list and t.__args__ is (int,).

__contains__(x)¶

Check whether self contains the given value x or not.

self.__repr__(x) <==> x in self

Parameters:

x – value to search

Returns:

True if an element equal to x is found, False

otherwise

Return type:

bool

__copy__()¶

Return a copy of self.

Returns:

new list with the same elements of self

Return type:

SortedList

__eq__(other)¶

Return True if and only if self is equal to other.

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 if self is greater than or equal to other.

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 if self is greater than other.

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

__hash__ = None¶

__init__(arg=None, typecode=None, epsilon=64)¶

__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 if self is less than or equal to other.

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 if self is less than other.

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 if self is not equal to other.

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 from self the elements found in other.

Equivalent elements are treated individually, that is, if some element is found m times in self and n times in other, 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:

SortedList

approximate_rank(x)¶

Return an approximate rank and the range where x can be found.

Parameters:

x – value to compare the elements to

Returns:

the approximate rank, the lower bound

(inclusive) and the upper bound (exclusive) of the range where x can be found

Return type:

tuple[int, int, int]

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:

SortedList

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:

SortedList

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, or None 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, or None 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, or None 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, or None 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 and b.

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 to False

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

segment(level_num: int, segment_num: int)¶

Return a segment from the index data structure.

The segment is represented as a dict with keys:

• 'key' the key of the segment

• 'slope' the slope of the segment

• 'intercept' the intercept of the segment

Parameters:

• level_num (int) – the level number of the segment

• segment_num (int) – the segment number within the level

Returns:

the segment data

Return type:

dict[str, object]

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

• 'segment size' size of a segment in bytes

• 'leaf segments' number of segments in the last level of the index

• 'segments counts' number of segments in each level of the index

• 'height' number of levels of the index

• 'epsilon' error bound for the last level of the index

• 'epsilon recursive' error bound for the upper levels 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 of arg.

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 for set - other)

• SortedSet.intersection() (alias for set & other)

• SortedSet.union() (alias for set | other)

• SortedSet.symmetric_difference() (alias for set ^ other)

Methods for accessing and querying elements:

• SortedSet.__getitem__()

• SortedSet.__contains__()

• SortedSet.bisect_left()

• SortedSet.bisect_right()

• SortedSet.count()

• SortedSet.find_ge()

• SortedSet.find_gt()

• SortedSet.find_le()

• SortedSet.find_lt()

• SortedSet.index()

• SortedSet.rank()

• SortedSet.approximate_rank()

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:

• SortedSet.range()

• SortedSet.__iter__()

• SortedSet.__reversed__()

Other methods:

• SortedSet.copy()

• SortedSet.stats()

• SortedSet.segment()

• SortedSet.__repr__()

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.

classmethod __class_getitem__()¶

Represent a PEP 585 generic type

E.g. for t = list[int], t.__origin__ is list and t.__args__ is (int,).

__contains__(x)¶

Check whether self contains the given value x or not.

self.__repr__(x) <==> x in self

Parameters:

x – value to search

Returns:

True if an element equal to x is found, False

otherwise

Return type:

bool

__copy__()¶

Return a copy of self.

Returns:

new set with the same elements of self

Return type:

SortedSet

__eq__(other)¶

Return True if and only if self is equal to other.

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 to other

Return type:

bool

__ge__(other)¶

Return True if and only if self is a superset of other.

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 of 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 if self is a proper superset of other.

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 of other

Return type:

bool

__hash__ = None¶

__init__(arg=None, typecode=None, epsilon=64)¶

__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 if self is a subset of other.

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 of 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 if self is a proper subset of other.

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 of other

Return type:

bool

__ne__(other)¶

Return True if and only if self is not equal to other.

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

approximate_rank(x)¶

Return an approximate rank and the range where x can be found.

Parameters:

x – value to compare the elements to

Returns:

the approximate rank, the lower bound

(inclusive) and the upper bound (exclusive) of the range where x can be found

Return type:

tuple[int, int, int]

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:

SortedSet

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 of self not found in other.

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:

SortedSet

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, or None 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, or None 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, or None 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, or None 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 both self and other.

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:

SortedSet

isdisjoint(other)¶

Return True if and only if the set has no elements in common with other.

Sets are disjoint if and only if their intersection is the empty set.

Parameters:

other (iterable) – a sequence of values

Returns:

True if self is disjoint from other

Return type:

bool

issubset(other)¶

Return True if and only if self is a subset of other.

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 of other

Return type:

bool

issuperset(other)¶

Return True if and only if self is a superset of other.

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 of other

Return type:

bool

range(a, b, inclusive=(True, True), reverse=False)¶

Return an iterator over elements between a and b.

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 to False

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

segment(level_num: int, segment_num: int)¶

Return a segment from the index data structure.

The segment is represented as a dict with keys:

• 'key' the key of the segment

• 'slope' the slope of the segment

• 'intercept' the intercept of the segment

Parameters:

• level_num (int) – the level number of the segment

• segment_num (int) – the segment number within the level

Returns:

the segment data

Return type:

dict[str, object]

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

• 'segment size' size of a segment in bytes

• 'leaf segments' number of segments in the last level of the index

• 'segments counts' number of segments in each level of the index

• 'height' number of levels of the index

• 'epsilon' error bound for the last level of the index

• 'epsilon recursive' error bound for the upper levels 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 either self or other 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:

SortedSet

union(other)¶

Return a new SortedSet with the elements in one or both self and other.

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:

SortedSet