IntervalSet¶

class part.IntervalSet(iterable=None)¶

Interval Set class.

The IntervalSet abstract class is designed to hold disjoint sorted intervals. It implements the AbstractSet protocol. It is implemented in two concrete classes:

Note

Les \(n\) (or \(n_0\)) the number of intervals of the self variable and \(m\) the number of intervals in the other variable. Let \(n_1, ... n_k\) the number of intervals for methods with multiple arguments.

The complexity in time of methods is estimated at (it has to be proven, see https://github.com/chdemko/py-part/issues/3):

Methods	Average case
`__len__()`	\(O(1)\)
`__contains__()`	\(O(\log(n))\)
`__getitem__()`	\(O(1)\) \(O(n)\)
`__iter__()`	\(O(1)\)
`__invert__()`	\(O(n)\)
`__reversed__()`	\(O(n)\)
`__eq__()`	\(O(n)\)
`__ne__()`	\(O(n)\)
`__le__()`	\(O(n\log(m))\)
`__lt__()`	\(O(n\log(m))\)
`__ge__()`	\(O(m\log(n))\)
`__gt__()`	\(O(m\log(n))\)
`__and__()`	\(O(\log^2(n)+\log^2(m)))\)
`__or__()`	\(O(\log^2(n)+\log^2(m)))\)
`__sub__()`	\(O(\log^2(n)+\log^2(m)))\)
`__xor__()`	\(O(\log^2(n)+\log^2(m)))\)
`copy()`	\(O(n)\)
`select()`	\(O(\log(n))\)
`issuperset()`	\(O(m\log(n))\)
`issubset()`	\(O(n\log(m))\)
`union()`	\(O(\sum_{i=0}^k\log^2(n_i))\)
`intersection()`	\(O(\sum_{i=0}^k\log^2(n_i))\)
`difference()`	\(O(\sum_{i=0}^k\log^2(n_i))\)
`symmetric_difference()`	\(O(\sum_{i=0}^k\log^2(n_i))\)

The iteration using __iter__() or select() is in \(O(n)\).

Methods	Worst Case (when different of average case)
`__and__()`	\(O(m\log(m)+n\log(n))\)
`__or__()`	\(O(m\log(m)+n\log(n))\)
`__sub__()`	\(O(m\log(m)+n\log(n))\)
`__xor__()`	\(O(m\log(m)+n\log(n))\)
`intersection()`	\(O(\sum_{i=0}^k n_i\log(n_i))\)
`union()`	\(O(\sum_{i=0}^k n_i\log(n_i))\)
`difference()`	\(O(\sum_{i=0}^k n_i\log(n_i))\)
`symmetric_difference()`	\(O(\sum_{i=0}^k n_i\log(n_i))\)

__init__(iterable=None)¶

Initialize an IntervalSet instance.

Parameters: iterable (Iterable) – An iterable of Atomic or valid tuple.

__str__()¶: Return str(self).

__eq__(other)¶: Return self==other.

__le__(other)¶

Test whether every element in the set is in other.

Parameters: other (Iterable) – An iterable of Atomic or valid tuple.
Returns: If the set is subset of the other.
Return type: True

See also

issubset: subset test.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int](
...     [2, (6, 7), (8, 9, None), (10, 11, True, True)]
... )
>>> b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
>>> print(a)
[2;2] | [6;7) | (8;9) | [10;11]
>>> print(b)
[0;7) | [8;13)
>>> a <= b
True

__lt__(other)¶

Return self<other.

Test whether the set is a proper subset of other, that is, self <= other and self != other.

Parameters: other (Iterable) – An iterable of Atomic or valid tuple.
Returns: If the set is a proper subset of the other.
Return type: True

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int](
...     [2, (6, 7), (8, 9, None), (10, 11, True, True)]
... )
>>> b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
>>> print(a)
[2;2] | [6;7) | (8;9) | [10;11]
>>> print(b)
[0;7) | [8;13)
>>> a < b
True

__ge__(other)¶

Test whether every element in other is in the set.

Parameters: other (Iterable) – An iterable of Atomic or valid tuple.
Returns: If the set is superset of the other.
Return type: True

See also

issuperset: superset test.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int](
...     [2, (6, 7), (8, 9, None), (10, 11, True, True)]
... )
>>> b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
>>> print(a)
[2;2] | [6;7) | (8;9) | [10;11]
>>> print(b)
[0;7) | [8;13)
>>> a >= b
False

__gt__(other)¶

Return self>other.

Test whether the set is a proper superset of other, that is, self >= other and self != other.

Parameters: other (Iterable) – An iterable of Atomic or valid tuple.
Returns: If the set is a proper superset of the other.
Return type: True

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int](
...     [2, (6, 7), (8, 9, None), (10, 11, True, True)]
... )
>>> b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
>>> print(a)
[2;2] | [6;7) | (8;9) | [10;11]
>>> print(b)
[0;7) | [8;13)
>>> a > b
False

__len__()¶

Return the number of inner intervals.

Returns: The number of inner intervals.
Return type: int

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int](
...     [2, (6, 7), (8, 9, None), (10, 11, True, True)]
... )
>>> len(a)
4

__contains__(value)¶

Test the membership.

Parameters

value (object) – The value to search.

Returns

True – if the value is contained in self.
False – otherwise.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet([(2, 8), (10, 11, True, True)])
>>> print(a)
[2;8) | [10;11]
>>> (10,13) in a
False
>>> (3,4) in a
True

__getitem__(item)¶

Return the nth interval. The array access operator supports slicing.

Parameters: item (int) – The interval requested.
Returns
Return type: The nth interval
Raises: IndexError – If the item is out of range.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int](
...     [2, (6, 7), (8, 9, None), (10, 11, True, True)]
... )
>>> print(a[0])
[2;2]
>>> print(a[2])
(8;9)
>>> print(a[2])
(8;9)
>>> print(a[1:3])
[6;7) | (8;9)

__iter__()¶

Return an iterator over the intervals.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int](
...     [2, (6, 7), (8, 9, None), (10, 11, True, True)]
... )
>>> print(list(str(interval) for interval in a))
['[2;2]', '[6;7)', '(8;9)', '[10;11]']

__and__(other)¶

Return the intersection of self with other.

Parameters: other (IntervalSet) – Another interval set.
Returns: The intersection of self with other.
Return type: IntervalSet

See also

intersection: Intersection with several interval sets.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int]([(2, 8), (10, 11, True, True)])
>>> b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
>>> print(a)
[2;8) | [10;11]
>>> print(b)
[0;7) | [8;13)
>>> print(a & b)
[2;7) | [10;11]

__or__(other)¶

Return the union of self with other.

Parameters: other (IntervalSet) – Another interval set.
Returns: The union of self with other.
Return type: IntervalSet

See also

union: Union with several interval sets.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int]([(2, 8), (10, 11, True, True)])
>>> b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
>>> print(a)
[2;8) | [10;11]
>>> print(b)
[0;7) | [8;13)
>>> print(a | b)
[0;13)

__sub__(other)¶

Return the difference of self with other.

Parameters: other (IntervalSet) – Another interval set.
Returns: The difference of self with other.
Return type: IntervalSet

See also

difference: Difference with several interval sets.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int]([(2, 8), (10, 11, True, True)])
>>> b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
>>> print(a)
[2;8) | [10;11]
>>> print(b)
[0;7) | [8;13)
>>> print(a - b)
[7;8)

__xor__(other)¶

Return the symmetric difference of self with other.

Parameters: other (IntervalSet) – Another interval set.
Returns: The symmetric difference of self with other.
Return type: IntervalSet

See also

symmetric_difference: Symmetric difference with several interval sets.

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int]([(2, 8), (10, 11, True, True)])
>>> b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
>>> print(a)
[2;8) | [10;11]
>>> print(b)
[0;7) | [8;13)
>>> print(a ^ b)
[0;2) | [7;10) | (11;13)

__invert__()¶

Return the complement of self.

Returns: The complement of self.
Return type: IntervalSet

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int]([(2, 8), (10, 11, True, True)])
>>> print(a)
[2;8) | [10;11]
>>> print(~a)
(-inf;2) | [8;10) | (11;+inf)

__reversed__()¶

Implement the reversed iterator.

Returns: An iterator over the reversed interval collection
Return type: Iterator[Interval]

isdisjoint(other)¶

Return the disjointness between self and other.

Return True 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 (IntervalSet) – An iterable of Atomic or valid tuple for an interval creation.

Returns

True – if the sets are disjoint,
False – otherwise.

issubset(other)¶

Return True if the set is a subset of the other.

Parameters

other (IntervalSet) – An iterable of Atomic or valid tuple for an interval creation.

Returns

True – if the set is a subset of the other,
False – otherwise.

See also

__le__: subset test.

issuperset(other)¶

Return True if the set is a superset of the other.

Parameters

other (IntervalSet) – An iterable of Atomic or valid tuple for an interval creation.

Returns

True – if the set is a superset of the other,
False – otherwise.

See also

__ge__: superset test.

union(*args)¶

Return the union of a list of sorted interval sets.

Parameters: *args (Iterable[IntervalValue]) – An iterable of Atomic or valid tuple for an interval creation.
Returns: a sorted interval set
Return type: IntervalSet
Raises: TypeError – if an argument is not iterable.

See also

__or__: An union is equivalent to several __or__().

Examples

>>> from part import FrozenIntervalSet
>>> print(
...     FrozenIntervalSet[int]([(1, 3), (4, 10)]).union(
...         FrozenIntervalSet[int]([(2, 5), (6, 8)]),
...         FrozenIntervalSet[int]([(2, 3), (4, 11)])
...     )
... )
[1;11)
>>> print(FrozenIntervalSet[int]().union())

>>> print(FrozenIntervalSet[int]([(1, 3), (4, 10)]).union())
[1;3) | [4;10)
>>> print(FrozenIntervalSet[int]([(1, 3)]).union(
...     FrozenIntervalSet[int]([(4, 10)]))
... )
[1;3) | [4;10)
>>> print(FrozenIntervalSet[int]([(1, 3, True, True)]).union(
...     FrozenIntervalSet[int]([(3, 10)]))
... )
[1;10)
>>> print(FrozenIntervalSet[int]([(1, 3)]).union(
...     FrozenIntervalSet[int]([(1, 3)]))
... )
[1;3)
>>> print(
...     FrozenIntervalSet[int]([(0, 2), (5, 10), (13, 23), (24, 25)]).union(
...         FrozenIntervalSet[int](
...             [
...                 (1, 5, True, True),
...                 (8, 12),
...                 (15, 18),
...                 (20, 24, True, True)
...             ]
...         ),
...         FrozenIntervalSet[int](
...             [(1, 9), (16, 30)]
...         )
...     )
... )
[0;12) | [13;30)

intersection(*args)¶

Return the intersection of a list of sorted interval sets.

Parameters: *args (Iterable[IntervalValue]) – An iterable of Atomic or valid tuple for an interval creation.
Returns: a sorted interval set
Return type: IntervalSet
Raises: TypeError – if an argument is not iterable.

See also

__and__: An intersection is equivalent to several __and__().

Examples

>>> from part import FrozenIntervalSet
>>> print(
...     FrozenIntervalSet[int]([(1, 3), (4, 10)]).intersection(
...         FrozenIntervalSet[int]([(2, 5), (6, 8)]),
...         FrozenIntervalSet[int]([(2, 3), (4, 11)])
...     )
... )
[2;3) | [4;5) | [6;8)
>>> print(FrozenIntervalSet[int]().intersection())

>>> print(FrozenIntervalSet[int]([(1, 3), (4, 10)]).intersection())
[1;3) | [4;10)
>>> print(FrozenIntervalSet[int]([(1, 3)]).intersection(
...     FrozenIntervalSet[int]([(4, 10)]))
... )

>>> print(FrozenIntervalSet[int]([(1, 3, True, True)]).intersection(
...     FrozenIntervalSet[int]([(3, 10)]))
... )
[3;3]
>>> print(FrozenIntervalSet[int]([(1, 3)]).intersection(
...     FrozenIntervalSet[int]([(1, 3)]))
... )
[1;3)
>>> print(
...     FrozenIntervalSet[int](
...         [(0, 2), (5, 10), (13, 23), (24, 25)]
...     ).intersection(
...         FrozenIntervalSet[int](
...             [
...                 (1, 5, True, True),
...                 (8, 12),
...                 (15, 18),
...                 (20, 24, True, True)
...             ]
...         ),
...         FrozenIntervalSet[int](
...             [(1, 9), (16, 30)]
...         )
...     )
... )
[1;2) | [5;5] | [8;9) | [16;18) | [20;23) | [24;24]

difference(*args)¶

Return the difference with of a list of sorted interval sets.

Parameters: *args (Iterable[IntervalValue]) – An iterable of Atomic or valid tuple for an interval creation.
Returns: a sorted interval set
Return type: IntervalSet
Raises: TypeError – if an argument is not iterable.

See also

__sub__: A difference is equivalent to several __sub__().

symmetric_difference(other)¶

Return the symmetric difference with of another sorted interval set.

Parameters: other (Iterable[IntervalValue]) – An iterable of Atomic or valid tuple for an interval creation.
Returns: a sorted interval set.
Return type: IntervalSet
Raises: TypeError – if other is not iterable.

See also

__xor__: A symmetric difference is equivalent to several __xor__().

copy()¶

Create a shallow copy of self.

Returns: A shallow copy of self.
Return type: IntervalSet

select(value, strict=True)¶

Select all intervals that have a non-empty intersection with value.

Parameters

value (Atomic, TO Tuple[TO, TO], Tuple[TO, TO, Optional[bool]], Tuple[TO, TO, Optional[bool], Optional[bool]]) – The value to search
strict (bool) – Is the comparison strict?

Returns

An iterator over the selected intervals.

Return type

Iterator[Interval]

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet[int](
...     [2, (6, 7), (8, 10, None), (11, 13, True, True)]
... )
>>> print(list(str(interval) for interval in a.select((5, 9))))
['[6;7)']
>>> print(list(str(interval) for interval in a.select((2, 9))))
['[2;2]', '[6;7)']
>>> print(
...     list(str(interval) for interval in a.select((2, 9), strict=False))
... )
['[2;2]', '[6;7)', '(8;10)']