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

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

__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

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

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

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

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

__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

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

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

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