Part library

py-part 1 is a library for managing intervals, interval sets and interval dictionaries.

Installation

Install py-part using the command

$ pip install py-part

To upgrade to the most recent release, use

$ pip install --upgrade py-part

To upgrade to the current develop branch, use

$ pip install --pre --upgrade --force --no-cache \
>     git+https://github.com/chdemko/py-part

pip is a script that downloads and installs modules from the Python Package Index, PyPI. It should come installed with your python distribution. If you are running linux, pip may be bundled separately. On a Debian-based system (including Ubuntu), you can install it using

# apt-get update
# apt-get install python3-pip

Building wheels and docs and running the tests

First clone the repository

$ git clone git@github.com:chdemko/py-part.git
$ cd py-part

Building the docs

$ pip install .[docs]
$ python setup.py build_sphinx

Building the wheel with cython

$ pip install .[build]
$ python setup.py bdist --cythonize

Building the wheel

$ pip install .
$ python setup.py bdist

Running the tests

$ pip install tox
$ tox -e py

Tutorial

Intervals

[1]:

from part import Interval, Atomic

Construction

An interval can be created using:

  • the constructor

  • static methods

[2]:

print(Interval[int](lower_value=10, upper_value=20))

[10;20)

[3]:

print(Interval[str](lower_value="abc", upper_value="def", upper_closed=True))

['abc';'def']

[4]:

print(Interval[int](lower_closed=None, lower_value=10, upper_value=20))

(10;20)

[5]:

print(Interval[int]())

(-inf;+inf)

[6]:

print(Atomic[int].from_tuple((10, 20)))

[10;20)

[7]:

print(Atomic[int].from_tuple((10, 20, None)))

(10;20)

[8]:

print(Atomic[int].from_tuple((10, 20, None, True)))

(10;20]

[9]:

print(Atomic[int].from_value(10))

[10;10]

[10]:

print(Interval[int].lower_limit(value=10))

[10;+inf)

[11]:

print(Interval[int].lower_limit(value=10, closed=None))

(10;+inf)

[12]:

print(Interval[int].upper_limit(value=10))

(-inf;10)

[13]:

print(Interval[int].upper_limit(value=10, closed=True))

(-inf;10]

Properties

Properties can be easily accessed.

[14]:

a = Atomic[int].from_tuple((10, 20, None))
print(a.lower)
print(a.lower_value)
print(a.lower_closed)
print(a.upper)
print(a.upper_value)
print(a.upper_closed)

10+
10
None
20-
20
None

Comparison

Intervals can be compared using Allen’s algebra:

[15]:

a = Atomic[int].from_tuple((10, 20, None))

[16]:

a.meets(Atomic[int].from_tuple((20, 30)))

[16]:

False

[17]:

a.meets(Atomic[int].from_tuple((20, 30)), strict=False)

[17]:

True

[18]:

a.overlaps(Atomic[int].from_tuple((15, 30)))

[18]:

True

[19]:

a.starts(Atomic[int].from_tuple((20, 40, None)))

[19]:

False

[20]:

a.starts(Atomic[int].from_tuple((10, 40, None)), strict=False)

[20]:

True

[21]:

a.during(Atomic[int].from_tuple((0, 30)))

[21]:

True

[22]:

a.finishes(Atomic[int].from_tuple((0, 20)))

[22]:

True

Operations

Intervals support set operation: union, intersection and complement. These operations produce instance of FrozenSetInterval.

[23]:

a = Atomic[int].from_tuple((10, 20, None))
b = Atomic[int].from_tuple((15, 30))
c = Atomic[int].from_tuple((30, 40))

[24]:

print(a | b)
print(a | c)
print(a & b)
print(a & c)
print(a - b)
print(a ^ b)
print(~a)

(10;30)
(10;20) | [30;40)
[15;20)

(10;15)
(10;15) | [20;30)
(-inf;10] | [20;+inf)

Interval sets

There exists two versions of interval sets:

  • FrozenIntervalSet

  • MutableIntervalSet

FrozenIntervalSet is slightly more efficient than MutableIntervalSet.

Frozen Interval Set

[25]:

from part import FrozenIntervalSet
Construction

A frozen interval set can be constructed using an iterable of interval-like values.

[26]:

a = FrozenIntervalSet[int]([2, (6, 7), (8, 9, None), (10, 11, True, True)])

[27]:

print(a)

[2;2] | [6;7) | (8;9) | [10;11]
Properties

  • the number of intervals can be known using the standard function len;

  • iteration over a set of intervals is obtained by using the standard function iter;

  • the intervals are accessible using their indices.

[28]:

print(len(a))
print([str(interval) for interval in a])
print(a[0])
print(a[2])
print(a[1:3])

4
['[2;2]', '[6;7)', '(8;9)', '[10;11]']
[2;2]
(8;9)
[6;7) | (8;9)
Comparison

Interval set can be compared using the set comparison operators.

[29]:

a = FrozenIntervalSet[int]([2, (6, 7), (8, 9, None), (10, 11, True, True)])
b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
print(a)
print(b)

[2;2] | [6;7) | (8;9) | [10;11]
[0;7) | [8;13)

[30]:

a <= b

[30]:

True

[31]:

a < b

[31]:

True

[32]:

a == b

[32]:

False

[33]:

a >= b

[33]:

False

[34]:

a > b

[34]:

False
Operations

Classical set operations are defined.

[35]:

a = FrozenIntervalSet[int]([(2, 8), (10, 11, True, True)])
b = FrozenIntervalSet[int]([(0, 7), (8, 13)])
print(a)
print(b)

[2;8) | [10;11]
[0;7) | [8;13)

[36]:

print((10,13) in a)
print((10,13) in b)
print(a | b)
print(a.union(b))
print(a & b)
print(a.intersection(b))

False
True
[0;13)
[0;13)
[2;7) | [10;11]
[2;7) | [10;11]

[37]:

print(~a)

(-inf;2) | [8;10) | (11;+inf)

[38]:

print(a - b)
print(a.difference(b))
print(a ^ b)
print(a.symmetric_difference(b))

[7;8)
[7;8)
[0;2) | [7;10) | (11;13)
[0;2) | [7;10) | (11;13)
Selection
[39]:

a = FrozenIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])

[40]:

print([str(interval) for interval in a.select((5, 9))])

['[6;7)']

[41]:

print([str(interval) for interval in a.select((2, 9))])

['[2;2]', '[6;7)']

[42]:

print([str(interval) for interval in a.select((2, 9), strict=False)])

['[2;2]', '[6;7)', '(8;10)']

Mutable Interval Set

In addition to frozen interval set operations, the mutable interval set implements method that can modify the set.

[43]:

from part import MutableIntervalSet
Element operations
[44]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
print(a)
a.add((2, 6))
print(a)

[2;2] | [6;7) | (8;10) | [11;13]
[2;7) | (8;10) | [11;13]

[45]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
print(a)
a.discard((2, 8))
print(a)

[2;2] | [6;7) | (8;10) | [11;13]
(8;10) | [11;13]

[46]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
print(a)
try:
    a.remove((2, 8))
except KeyError as e:
    print(e)

[2;2] | [6;7) | (8;10) | [11;13]
'(2, 8)'

[47]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
print(a)
print(a.pop())
print(a)

[2;2] | [6;7) | (8;10) | [11;13]
[2;2]
[6;7) | (8;10) | [11;13]

[48]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
print(a)
a.clear()
print(a)

[2;2] | [6;7) | (8;10) | [11;13]
Set operations
[49]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
b = MutableIntervalSet[int]([(0, 7), (8, 12)])
print(a)
print(b)
a.update(b)
print(a)
a |= MutableIntervalSet[int]([(7, 8)])
print(a)

[2;2] | [6;7) | (8;10) | [11;13]
[0;7) | [8;12)
[0;7) | [8;13]
[0;13]

[50]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
b = MutableIntervalSet[int]([(0, 7), (8, 12)])
print(a)
print(b)
a.intersection_update(b)
print(a)
a &= MutableIntervalSet[int]([(6, 11)])
print(a)

[2;2] | [6;7) | (8;10) | [11;13]
[0;7) | [8;12)
[2;2] | [6;7) | (8;10) | [11;12)
[6;7) | (8;10)

[51]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
b = MutableIntervalSet[int]([(0, 7), (8, 12)])
print(a)
print(b)
a.difference_update(b)
print(a)
a -= MutableIntervalSet[int]([12])
print(a)

[2;2] | [6;7) | (8;10) | [11;13]
[0;7) | [8;12)
[12;13]
(12;13]

[52]:

a = MutableIntervalSet[int]([2, (6, 7), (8, 10, None), (11, 13, True, True)])
b = MutableIntervalSet[int]([(0, 7), (8, 12)])
print(a)
print(b)
a.symmetric_difference_update(b)
print(a)
a ^= MutableIntervalSet[int]([(8,12)])
print(a)

[2;2] | [6;7) | (8;10) | [11;13]
[0;7) | [8;12)
[0;2) | (2;6) | [8;8] | [10;11) | [12;13]
[0;2) | (2;6) | (8;10) | [11;13]

Interval dicts

There exists two versions of interval dicts:

  • FrozenIntervalDict

  • MutableIntervalDict

FrozenIntervalDict is slightly more efficient than MutableIntervalDict.

Frozen Interval Dict

[53]:

from part import FrozenIntervalDict
Construction

A frozen interval dict can be constructed using an iterable.

[54]:

print(FrozenIntervalDict[int, int]({(10, 15): 1, (20, 25): 2, (30, 35): 3}))

{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}

[55]:

print(FrozenIntervalDict[int, int]([((10, 15), 1), ((20, 25), 2), ((30, 35), 3)]))

{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
Properties

  • the number of intervals can be known using the standard function len;

  • iteration over a dict of intervals is obtained by using the standard function iter;

  • the values are accessible using their intervals;

  • new dict can be created using the slice notation.

[56]:

a = FrozenIntervalDict[int, int]({(10, 15): 1, (20, 25): 2, (30, 35): 3})
print(len(a))
print([str(interval) for interval in a])
print(a[(10, 15)])
print(a[(11, 12)])
print((11, 12) in a)
print((12, 17) in a)
try:
    print(a[(12, 17)])
except KeyError as e:
    print(e)
print(a[12:32])

3
['[10;15)', '[20;25)', '[30;35)']
1
1
True
False
'(12, 17)'
{'[12;15)': 1, '[20;25)': 2, '[30;32)': 3}
Iteration

As for classical python dictionaries, methods keys, values and items are available.

[57]:

a = FrozenIntervalDict[int, int]({(10, 15): 1, (20, 25): 2, (30, 35): 3})
print([str(interval) for interval in a.keys()])
print([str(value) for value in a.values()])
print([f"{interval}:{value}" for interval, value in a.items()])

['[10;15)', '[20;25)', '[30;35)']
['1', '2', '3']
['[10;15):1', '[20;25):2', '[30;35):3']
Selection
[58]:

a = FrozenIntervalDict[int, int]({(10, 15): 1, (20, 25): 2, (30, 35): 3})
print([str(interval) for interval in a.select((12, 26))])
print([str(interval) for interval in a.select((12, 22), strict=False)])

['[20;25)']
['[10;15)', '[20;25)']
Compression
[59]:

a = FrozenIntervalDict[int, int]({(10, 15): 1, (14, 25): 1, (30, 35): 2, (33, 45): 2})
print(a)
print(a.compress())

{'[10;14)': 1, '[14;25)': 1, '[30;33)': 2, '[33;45)': 2}
{'[10;25)': 1, '[30;45)': 2}

Mutable Interval Dict

[60]:

from part import MutableIntervalDict
Modify items
[61]:

a = MutableIntervalDict[int, int]({(10, 15): 1, (20, 25): 2, (30, 35): 3})
print(a)
a[12] = 4
print(a)
a[14:22] = 5
print(a)
del a[12:22]
print(a)

{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
{'[10;12)': 1, '[12;12]': 4, '(12;15)': 1, '[20;25)': 2, '[30;35)': 3}
{'[10;12)': 1, '[12;12]': 4, '(12;14)': 1, '[14;22)': 5, '[22;25)': 2, '[30;35)': 3}
{'[10;12)': 1, '[22;25)': 2, '[30;35)': 3}
Update
[62]:

a = MutableIntervalDict[int, int](
    {(10, 15): 1, (20, 25): 2, (30, 35): 3},
    operator=lambda x, y: x + y
)
a |= MutableIntervalDict[int, int]({(14, 21): 2})
print(a)

{'[10;14)': 1, '[14;15)': 3, '[15;20)': 2, '[20;21)': 4, '[21;25)': 2, '[30;35)': 3}

[63]:

a = MutableIntervalDict[float, set](
    operator=lambda x, y: x | y,
    strict=False,
)
print(a)
a |= MutableIntervalDict[float, set]({(1.2, 3.6): {1}, (3.8, 4.5) : {2}})
print(a)
a |= MutableIntervalDict[float, set]({(2, 4): {3}})
print(a)

{}
{'[1.2;3.6)': {1}, '[3.8;4.5)': {2}}
{'[1.2;2)': {1}, '[2;3.6)': {1, 3}, '[3.6;3.8)': {3}, '[3.8;4)': {2, 3}, '[4;4.5)': {2}}
Clear
[64]:

a = MutableIntervalDict[int, int]({(10, 15): 1, (20, 25): 2, (30, 35): 3})
print(a)
a.clear()
print(a)

{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
{}

Application Programming Interface

Atomic classes

TotallyOrdered

class part.TotallyOrdered

TotallyOrdered class.

Sub-class of this abstract class must implement a total order on a type.

abstract __lt__(other)

Return self<other.

abstract __gt__(other)

Return self>other.

abstract __le__(other)

Return self<=other.

abstract __ge__(other)

Return self>=other.

abstract __ne__(other)

Return self!=other.

abstract __eq__(other)

Return self==other.

__weakref__

list of weak references to the object (if defined)

Atomic

class part.Atomic(*args, **kwds)

Atomic class.

The Atomic class represents an abstract version of two concrete classes:

abstract __str__()

Return str(self).

__eq__(other)

Return self==other.

__lt__(other)

Return self<other.

__gt__(other)

Return self>other.

abstract __hash__()

Return hash(self).

abstract __bool__()

Return bool(self).

Returns

  • True – If the subset is non empty.

  • False – Otherwise.

abstract __or__(other)

Return the union of self with other.

Parameters

other (Atomic, tuple) – Another atomic subset.

Returns

The union of self and other.

Return type

FrozenIntervalSet

abstract __and__(other)

Return the intersection of self with other.

Parameters

other (Atomic, tuple) – Another atomic subset.

Returns

The intersection of self and other.

Return type

FrozenIntervalSet

abstract __sub__(other)

Return the difference of self with other.

Parameters

other (Atomic, tuple) – Another atomic subset.

Returns

The difference of self and other.

Return type

FrozenIntervalSet

abstract __xor__(other)

Return the symmetric difference of self with other.

Parameters

other (Atomic, tuple) – Another atomic subset.

Returns

The symmetric difference of self and other.

Return type

FrozenIntervalSet

abstract __invert__()

Return the complement of self.

Returns

The complement of self.

Return type

FrozenIntervalSet

static from_tuple(item)

Create an interval from a tuple.

Parameters

item (IntervalTuple) –

The tuple to transform:

  • a pair <a,b> designates an interval closed on the left and open on the right;

  • a triple <a,b,bool> designates an interval open/closed on the left and open on the right;

  • a quadruplet <a,b,bool,bool> designates an interval open/closed on the left and open/closed on the right.

Returns

  • Interval – The tuple transformed into an interval.

  • Empty – If the interval is empty

Examples

>>> from part import Atomic
>>> print(Atomic[int].from_tuple((10, 20)))
[10;20)
>>> print(Atomic[int].from_tuple((10, 20, True, None)))
[10;20)
>>> print(Atomic[int].from_tuple((10, 20, None, None)))
(10;20)
>>> print(Atomic[int].from_tuple((10, 20, None, True)))
(10;20]
static from_value(value)

Create an interval from any value.

Parameters

value (object) – The value to transform.

Returns

The value transformed into an interval containing one value.

Return type

Interval

Examples

>>> from part import Atomic
>>> print(Atomic[int].from_value(10))
[10;10]
abstract before(other, strict=True, reverse=False)

Return True if the subset is the before the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the before strict?

  • reverse (bool) – is the before reversed?

Raises
abstract meets(other, strict=True, reverse=False)

Return True if the subset meets the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the meets strict?

  • reverse (bool) – is the meets reversed?

Raises
abstract overlaps(other, strict=True, reverse=False)

Return True if the subset overlaps the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the overlap strict?

  • reverse (bool) – is the overlaps reversed?

Raises
abstract starts(other, strict=True, reverse=False)

Return True if the subset starts the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the starts strict?

  • reverse (bool) – is the starts reversed?

Raises
abstract during(other, strict=True, reverse=False)

Return True if the subset is during the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the during strict?

  • reverse (bool) – is the during reversed?

Raises
abstract finishes(other, strict=True, reverse=False)

Return True if the subset finishes the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the finishes strict?

  • reverse (bool) – is the finishes reversed?

Raises

Empty

class part.Empty(*args)

Bases: Generic[part.atomic.TO], part.utils.Singleton, part.atomic.Atomic[part.atomic.TO]

Empty set class.

The Empty class (which inherits from the Atomic class) represent the empty set. There is only one instance of this class.

__str__()

Return str(self).

__hash__()

Return hash(self).

__bool__()

Return bool(self).

Returns

An empty set is always False.

Return type

False

__or__(other)

Return self|other.

__and__(other)

Return self^other.

__sub__(other)

Return self-other.

__xor__(other)

Return self^other.

__invert__()

Return ~self.

before(other, strict=True, reverse=False)

See Atomic.before().

meets(other, strict=True, reverse=False)

See Atomic.meets().

overlaps(other, strict=True, reverse=False)

See Atomic.overlaps().

starts(other, strict=True, reverse=False)

See Atomic.starts().

during(other, strict=True, reverse=False)

See Atomic.during().

finishes(other, strict=True, reverse=False)

See Atomic.finishes().

Interval

class part.Interval(lower_value=None, upper_value=None, lower_closed=True, upper_closed=None)

Interval class.

The Interval class (which inherits from the Atomic class) is designed to hold range values. Allen’s interval algebra has been implemented.

An interval can hold any type of value that implements a total order.

Each bound of the interval can be open or closed.

static __new__(cls, lower_value=None, upper_value=None, lower_closed=True, upper_closed=None)

Create an Atomic instance.

Keyword Arguments

  • lower_value (TO, optional) – Any python comparable object.

  • upper_value (TO, optional) – Any python comparable object.

  • lower_closed (bool, optional) – A boolean value.

  • upper_closed (bool, optional) – A boolean value.

Returns

  • Interval – if the arguments define a non-empty interval.

  • Empty – otherwise.

Raises

ValueError – If lower_value is not comparable with upper_value.

See also

__init__

For interval initialization.

Examples

>>> from part import Interval
>>> a = Interval[int](lower_value=10, upper_value=0)
>>> bool(a)
False
__init__(lower_value=None, upper_value=None, lower_closed=True, upper_closed=None)

Initialize an Interval instance.

By default, an interval is closed to the left and open to the right.

Keyword Arguments

  • lower_value (TO, optional) – Any python object.

  • upper_value (TO, optional) – Any python object.

  • lower_closed (bool, optional) – A boolean value.

  • upper_closed (bool, optional) – A boolean value.

See also

__new__

For detection of empty interval creation.

Examples

>>> from part import Interval
>>> print(Interval[int](lower_value=10, upper_value=20))
[10;20)
>>> print(Interval[str](lower_value="abc", upper_value="def",
... upper_closed=True))
['abc';'def']
>>> print(Interval[int](lower_closed=None, lower_value=10, upper_value=20))
(10;20)
>>> print(Interval[int]())
(-inf;+inf)
__str__()

Return str(self).

__eq__(other)

Return self==other.

__lt__(other)

Comparison using Allen’s algebra.

Parameters

other (Atomic) – Another atomic value.

Returns

  • True – if the interval is lesser than the other.

  • False – otherwise.

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> a < Atomic[int].from_tuple((25, 30))
True
__gt__(other)

Comparison using Allen’s algebra.

Parameters

other (Atomic) – Another atomic value.

Returns

  • True – if the interval is greater than the other.

  • False – otherwise.

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> a > Atomic[int].from_tuple((25, 30))
False
__hash__()

Return hash(self).

__bool__()

Return bool(self).

Returns

An interval is always True.

Return type

True

__or__(other)

Compute the union of two intervals.

Parameters

other (Atomic) – Another atomic value.

Returns

The union of the interval and the other.

Return type

FrozenIntervalSet

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> b = Atomic[int].from_tuple((15, 30))
>>> c = Atomic[int].from_tuple((30, 40))
>>> print(a | b)
(10;30)
>>> print(a | c)
(10;20) | [30;40)
__and__(other)

Compute the intersection of two intervals.

Parameters

other (Atomic) – Another atomic value.

Returns

The intersection of the interval and the other.

Return type

FrozenIntervalSet

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> b = Atomic[int].from_tuple((15, 30))
>>> c = Atomic[int].from_tuple((30, 40))
>>> print(a & b)
[15;20)
>>> print(a & c)
__sub__(other)

Compute the difference of two intervals.

Parameters

other (Atomic) – Another atomic value.

Returns

The difference between the interval and the other.

Return type

FrozenIntervalSet

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> b = Atomic[int].from_tuple((15, 30))
>>> c = Atomic[int].from_tuple((30, 40))
>>> print(a - b)
(10;15)
>>> print(a - c)
(10;20)
__xor__(other)

Compute the symmetric difference of two intervals.

Parameters

other (Atomic) – Another atomic value.

Returns

The symmetric difference between the interval and the other.

Return type

FrozenIntervalSet

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> b = Atomic[int].from_tuple((15, 30))
>>> c = Atomic[int].from_tuple((30, 40))
>>> print(a ^ b)
(10;15) | [20;30)
>>> print(a ^ c)
(10;20) | [30;40)
__invert__()

Compute the complement of the interval.

Returns

The complement of the interval.

Return type

FrozenIntervalSet

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> print(~a)
(-inf;10] | [20;+inf)
static upper_limit(value=None, closed=None)

Create an interval from an upper limit.

Parameters

  • value (TO) – The upper limit.

  • closed (bool) – Is the interval closed?

Returns

An interval with an upper limit.

Return type

Interval

Examples

>>> from part import Interval
>>> print(Interval[int].upper_limit(value=10))
(-inf;10)
>>> print(Interval[int].upper_limit(value=10, closed=True))
(-inf;10]
static lower_limit(value=None, closed=True)

Create an interval from a lower limit.

Parameters

  • value (TO) – The lower limit.

  • closed (bool) – Is the interval closed?

Returns

An interval with a lower limit.

Return type

Interval

Examples

>>> from part import Interval
>>> print(Interval[int].lower_limit(value=10))
[10;+inf)
>>> print(Interval[int].lower_limit(value=10, closed=None))
(10;+inf)
before(other, strict=True, reverse=False)

Return True if the subset is the before the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the before strict?

  • reverse (bool) – is the before reversed?

Raises

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> a.before(Atomic[int].from_tuple((25, 30)))
True
meets(other, strict=True, reverse=False)

Return True if the subset meets the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the meets strict?

  • reverse (bool) – is the meets reversed?

Raises

Examples

>>> from part import Atomic
>>> a = Atomic.from_tuple((10, 20, None))
>>> a.meets(Atomic[int].from_tuple((20, 30)))
False
>>> a.meets(Atomic[int].from_tuple((20, 30)), strict=False)
True
overlaps(other, strict=True, reverse=False)

Return True if the subset overlaps the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the overlaps strict?

  • reverse (bool) – is the overlaps reversed?

Raises

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> a.overlaps(Atomic[int].from_tuple((15, 30)))
True
starts(other, strict=True, reverse=False)

Return True if the subset starts the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the starts strict?

  • reverse (bool) – is the starts reversed?

Raises

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> a.starts(Atomic[int].from_tuple((20, 40, None)))
False
>>> a.starts(Atomic[int].from_tuple((10, 40, None)), strict=False)
True
during(other, strict=True, reverse=False)

Return True if the subset is during the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the during strict?

  • reverse (bool) – is the during reversed?

Raises

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> a.during(Atomic[int].from_tuple((0, 30)))
True
finishes(other, strict=True, reverse=False)

Return True if the subset finishes the other.

Parameters

  • other (Atomic) – Another atomic object.

  • strict (bool) – is the finishes strict?

  • reverse (bool) – is the finishes reversed?

Raises

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> a.finishes(Atomic[int].from_tuple((0, 20)))
True
property lower

Get the lower property.

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> print(a.lower)
10+
property lower_value

Get the lower_value property.

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> print(a.lower_value)
10
property lower_closed

Get the lower_closed property.

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> print(a.lower_closed)
None
property upper

Get the upper property.

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> print(a.upper)
20-
property upper_value

Get the lower_value property.

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> print(a.upper_value)
20
property upper_closed

Get the upper_closed property.

Examples

>>> from part import Atomic
>>> a = Atomic[int].from_tuple((10, 20, None))
>>> print(a.upper_closed)
None

Set classes

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
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)']

FrozenIntervalSet

class part.FrozenIntervalSet(iterable=None)

Frozen Interval Set class.

The FrozenIntervalSet class (which inherits from the IntervalSet class) is designed to hold frozen disjoint intervals.

__init__(iterable=None)

Initialize a FrozenIntervalSet instance.

Parameters

iterable (Iterable) –

An optional iterable of:

Examples

>>> from part import FrozenIntervalSet
>>> a = FrozenIntervalSet([2, (6, 7), (8, 9, None), (10, 11, True, True)])
>>> print(a)
[2;2] | [6;7) | (8;9) | [10;11]
__hash__()

A FrozenIntervalSet instance is hashable.

It can be used as key in dictionaries.

__getitem__(item)

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

Parameters

item (Union[int, slice]) – 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([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)

MutableIntervalSet

class part.MutableIntervalSet(iterable=None)

Mutable Interval Set class.

The MutableIntervalSet class (which inherits from the IntervalSet class) is designed to hold mutable disjoint sorted intervals.

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:

Methods

Average case

__getitem__()

\(O(\log(n))\) \(O(n)\)

__iand__()

\(O(\log^2(n)+\log^2(m)))\)

__ior__()

\(O(\log^2(n)+\log^2(m)))\)

__isub__()

\(O(\log^2(n)+\log^2(m)))\)

__ixor__()

\(O(\log^2(n)+\log^2(m)))\)

update()

\(O(\sum_{i=0}^k\log^2(n_i))\)

intersection_update()

\(O(\sum_{i=0}^k\log^2(n_i))\)

difference_update()

\(O(\sum_{i=0}^k\log^2(n_i))\)

symmetric_difference_update()

\(O(\sum_{i=0}^k\log^2(n_i))\)

add()

\(O(\log(n))\)

remove()

\(O(\log(n))\)

discard()

\(O(\log(n))\)

pop()

\(O(\log(n))\)

clear()

\(O(1)\)

Methods

Worst Case (when different of average case)

__iand__()

\(O(m\log(m)+n\log(n))\)

__ior__()

\(O(m\log(m)+n\log(n))\)

__isub__()

\(O(m\log(m)+n\log(n))\)

__ixor__()

\(O(m\log(m)+n\log(n))\)

update()

\(O(\sum_{i=0}^k n_i\log(n_i))\)

intersection_update()

\(O(\sum_{i=0}^k n_i\log(n_i))\)

difference_update()

\(O(\sum_{i=0}^k n_i\log(n_i))\)

symmetric_difference_update()

\(O(\sum_{i=0}^k n_i\log(n_i))\)
__init__(iterable=None)

Initialize a MutableIntervalSet instance.

Parameters

iterable (Iterable) –

An optional iterable of either

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
__ior__(other)

Update self with the union other.

Parameters

other (IntervalSet) – Another interval set.

Returns

The updated MutableIntervalSet.

Return type

MutableIntervalSet

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> b = MutableIntervalSet([(0, 7), (8, 12)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> print(b)
[0;7) | [8;12)
>>> a |= b
>>> print(a)
[0;7) | [8;13]
__iand__(other)

Update self with the intersection with other.

Parameters

other (IntervalSet) – Another interval set.

Returns

The updated MutableIntervalSet.

Return type

MutableIntervalSet

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> b = MutableIntervalSet([(0, 7), (8, 12)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> print(b)
[0;7) | [8;12)
>>> a &= b
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;12)
__isub__(other)

Update self with the difference with other.

Parameters

other (IntervalSet) – Another interval set.

Returns

The updated MutableIntervalSet.

Return type

MutableIntervalSet

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> b = MutableIntervalSet([(0, 7), (8, 12)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> print(b)
[0;7) | [8;12)
>>> a -= b
>>> print(a)
[12;13]
__ixor__(other)

Update self with the symmetric difference with other.

Parameters

other (IntervalSet) – Another interval set.

Returns

The updated MutableIntervalSet.

Return type

MutableIntervalSet

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> b = MutableIntervalSet([(0, 7), (8, 12)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> print(b)
[0;7) | [8;12)
>>> a ^= b
>>> print(a)
[0;2) | (2;6) | [8;8] | [10;11) | [12;13]
update(*args)

Update the set, keeping only elements found in it and all others.

Parameters

*args (Iterable[IntervalValue]) – An iterable of Atomic or valid tuple for an interval creation.

Raises

TypeError – if an argument is not iterable.

intersection_update(*args)

Update the set, keeping only elements found in it and all others.

Parameters

*args (Iterable[IntervalValue]) – An iterable of Atomic or valid tuple for an interval creation.

Raises

TypeError – if an argument is not iterable.

difference_update(*args)

Update the set, removing elements found in others.

Parameters

*args (Iterable[IntervalValue]) – An iterable of Atomic or valid tuple for an interval creation.

Raises

TypeError – if an argument is not iterable.

symmetric_difference_update(other)

Update the set, keeping only elements found in either set, but not in both.

Parameters

other (Iterable[IntervalValue]) – An iterable of Atomic or valid tuple for an interval creation.

Raises

TypeError – if other is not iterable.

add(value)

Add element value to the set.

Parameters

value (IntervalValue) –

The value to add:

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> a.add((2, 6))
>>> print(a)
[2;7) | (8;10) | [11;13]
remove(value)

Remove element value from the set.

Parameters

value (IntervalValue) –

The value to remove:

Raises

KeyError – if value is not contained in the set.

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> try:
...     a.remove((2, 8))
... except KeyError as e:
...     print(e)
'(2, 8)'
discard(value)

Discard element value from the set.

Parameters

value (IntervalValue) –

The value to discard:

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> a.discard((2, 8))
>>> print(a)
(8;10) | [11;13]
pop()

Get the first interval.

Returns

The first interval.

Return type

part.Interval

Raises

KeyError – if the set is empty.

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> print(a.pop())
[2;2]
>>> print(a)
[6;7) | (8;10) | [11;13]
clear()

Remove all elements from the set.

Examples

>>> from part import MutableIntervalSet
>>> a = MutableIntervalSet([2, (6, 7), (8, 10, None), (11, 13, True, True)])
>>> print(a)
[2;2] | [6;7) | (8;10) | [11;13]
>>> a.clear()
>>> print(a)

Dictionary classes

IntervalDict

class part.IntervalDict

The IntervalDict abstract class can hold dict of disjoint sorted intervals.

It implements the Mapping 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)\)

__iter__()

\(O(1)\)

__contains__()

\(O(\log(n))\)

__getitem__()

\(O(\log(n))\) \(O(n)\)

__or__()

\(O(m\log(n+m))\)

copy()

\(O(n)\)

select()

\(O(\log(n))\)

compress()

\(O(n)\)

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

__init__()

Initialize IntervalDict instances.

__str__()

Return str(self).

Returns

The string representation of self.

Return type

str

Examples

>>> from part import FrozenIntervalDict
>>> a = FrozenIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> print(a)
{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
__len__()

Return the number of inner intervals.

Returns

The number of inner intervals.

Return type

int

Examples

>>> from part import FrozenIntervalDict
>>> a = FrozenIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> len(a)
3
__iter__()

Return an iterator over the intervals.

Examples

>>> from part import FrozenIntervalDict
>>> a = FrozenIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> print(list(str(interval) for interval in a))
['[10;15)', '[20;25)', '[30;35)']
__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 FrozenIntervalDict
>>> a = FrozenIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> print(a)
{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
>>> (10,13) in a
True
>>> (13,17) in a
False
__getitem__(key)

Return a value using either a slice or an interval value.

Parameters

key (Union[IntervalValue, slice]) – The interval requested.

Returns

Return type

The found value or a new IntervalDict if key is a slice.

Raises

KeyError – If the key is out of range.

Examples

>>> from part import FrozenIntervalDict
>>> a = FrozenIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> print(a)
{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
>>> print(a[12])
1
>>> print(a[(21, 24)])
2
>>> try:
...     print(a[(24, 26)])
... except KeyError as e:
...     print(e)
'(24, 26)'
>>> print(a[24:26])
{'[24;25)': 2}
__or__(other)

Construct a new dictionary using self and the other.

Parameters

other (IntervalDict) – Another interval dict.

Returns

The new IntervalDict.

Return type

IntervalDict

Examples

>>> from part import FrozenIntervalDict
>>> a = FrozenIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> print(a | FrozenIntervalDict[int, int]({(15, 22): 4}))
{'[10;15)': 1, '[15;22)': 4, '[22;25)': 2, '[30;35)': 3}
copy()

Return a shallow copy of the dictionary.

Returns

A shallow copy of the dictionary.

Return type

IntervalDict

Examples

>>> from part import FrozenIntervalDict
>>> a = FrozenIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> print(a)
{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
>>> b = a.copy()
>>> print(b)
{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
>>> a == b
True
>>> a is b
False
select(value, strict=True)

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

Parameters
Returns

An iterator over the selected items.

Return type

Iterator[Interval]]

Examples

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

Compress a dictionary.

Returns

A new dictionary where all useless intervals have been removed.

Return type

IntervalDict

Examples

>>> from part import FrozenIntervalDict
>>> a = FrozenIntervalDict[int, int](
...     {
...         (10, 15): 1,
...         (14, 25): 1,
...         (30, 35): 2,
...         (33, 45): 2
...     }
... )
>>> print(a)
{'[10;14)': 1, '[14;25)': 1, '[30;33)': 2, '[33;45)': 2}
>>> b = a.compress()
>>> print(b)
{'[10;25)': 1, '[30;45)': 2}

FrozenIntervalDict

class part.FrozenIntervalDict(iterable=None)

Frozen Interval Dictionary class.

The FrozenIntervalDict class (which inherits from the IntervalDict class) is designed to hold frozen dict of disjoint intervals.

__init__(iterable=None)

Initialize a FrozenIntervalDict instance.

Parameters

iterable (Iterable) – An optional iterable that can be converted to a dictionary of ( interval, value).

__hash__()

A FrozenIntervalDict instance is hashable.

It can be used as key in dictionaries.

MutableIntervalDict

class part.MutableIntervalDict(iterable=None, default=None, operator=None, strict=True)

Mutable Interval Dictionary class.

The MutableIntervalDict class (which inherits from the IntervalDict class) is designed to hold mutable dict of disjoint sorted intervals.

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:

Methods

Average case

__setitem__()

\(O(n)\)

__delitem__()

\(O(n)\)

__ior__()

\(O(m\log(n+m))\)

update()

\(O((\sum_{i=1}^kn_i)\log(\sum_{i=0}^kn_i))\)

clear()

\(O(1)\)
__init__(iterable=None, default=None, operator=None, strict=True)

Initialize a MutableIntervalDict instance.

Parameters

iterable (Iterable) – An optional iterable that can be converted to a dictionary of ( interval, value).

Keyword Arguments

  • default (Callable[[], V], optional) – The default factory.

  • operator (Callable[[V, V], V]) – The operator function.

  • strict (bool) – False if operator is a commutative and associative law on V.

Note

If operator is a commutative and associative law on V, the complexity in time is much faster if strict is set to False.

Examples

>>> from part import MutableIntervalDict
>>> a = MutableIntervalDict[int, set](
...     operator=lambda x, y: x | y,
...     strict=False
... )
>>> a.update({(1, 10): {1}})
>>> print(a)
{'[1;10)': {1}}
>>> a.update({(5, 20): {2}})
>>> print(a)
{'[1;5)': {1}, '[5;10)': {1, 2}, '[10;20)': {2}}
>>> a.update({(10, 30): {1}})
>>> print(a)
{'[1;5)': {1}, '[5;10)': {1, 2}, '[10;20)': {1, 2}, '[20;30)': {1}}
>>> print(a.compress())
{'[1;5)': {1}, '[5;20)': {1, 2}, '[20;30)': {1}}
__getitem__(key)

Return a value using either a slice or an interval value.

Parameters

key (Union[IntervalValue, slice]) – The interval requested.

Returns

Return type

The found value

Raises

KeyError – If the key is out of range.

__setitem__(key, value)

Set a value using either a slice or an interval value.

Parameters

key (Union[IntervalValue, slice]) – The interval requested.

Raises

KeyError – If the key is out of range.

Examples

>>> from part import MutableIntervalDict
>>> a = MutableIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> print(a)
{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
>>> a[12] = 4
>>> print(a)
{'[10;12)': 1, '[12;12]': 4, '(12;15)': 1, '[20;25)': 2, '[30;35)': 3}
>>> a[13:31] = 5
>>> print(a)
{'[10;12)': 1, '[12;12]': 4, '(12;13)': 1, '[13;31)': 5, '[31;35)': 3}
>>> a[:] = 0
>>> print(a)
{'(-inf;+inf)': 0}
__delitem__(key)

Delete a value using either a slice or an interval value.

Parameters

key (Union[IntervalValue, slice]) – The interval requested.

Raises

KeyError – If the key is out of range.

Examples

>>> from part import MutableIntervalDict
>>> a = MutableIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3}
... )
>>> print(a)
{'[10;15)': 1, '[20;25)': 2, '[30;35)': 3}
>>> del a[12]
>>> print(a)
{'[10;12)': 1, '(12;15)': 1, '[20;25)': 2, '[30;35)': 3}
>>> del a[13:31]
>>> print(a)
{'[10;12)': 1, '(12;13)': 1, '[31;35)': 3}
>>> del a[:]
>>> print(a)
{}
__or__(other)

Construct a new dictionary using self and the other.

Parameters

other (IntervalDict) – Another interval dict.

Returns

The new IntervalDict.

Return type

MutableIntervalDict

Examples

>>> from part import MutableIntervalDict
>>> a = MutableIntervalDict[int, int](
...     {(10, 15): 1, (20, 25): 2, (30, 35): 3},
...     operator=lambda x, y: x + y,
...     strict=False
... )
>>> print(a | FrozenIntervalDict[int, int]({(15, 22): 4}))
{'[10;15)': 1, '[15;20)': 4, '[20;22)': 6, '[22;25)': 2, '[30;35)': 3}
__ior__(other)

Update self with the other.

Parameters

other (IntervalDict) – Another interval dict.

Returns

The updated MutableIntervalDict.

Return type

MutableIntervalDict

Examples

>>> from part import MutableIntervalDict
>>> a = MutableIntervalDict[int, int](
...     operator=lambda x, y: x + y,
...     strict=False
... )
>>> a |= MutableIntervalDict[int, int]({(1, 10): 1})
>>> print(a)
{'[1;10)': 1}
>>> a |= MutableIntervalDict[int, int]({(5, 20): 2})
>>> print(a)
{'[1;5)': 1, '[5;10)': 3, '[10;20)': 2}
>>> a |= MutableIntervalDict[int, int]({(10, 30): 3})
>>> print(a)
{'[1;5)': 1, '[5;10)': 3, '[10;20)': 5, '[20;30)': 3}
update(*args)

Update the dict.

Parameters

*args (Iterable) – An iterable of IntervalDict or valid iterable for an interval dictionary creation.

Raises

TypeError – if an argument is not iterable.

Note

If the parameter strict used in the constructor is False, the complexity is in \(O(n\,log(n)\,k\,\lambda)\) where:

  • \(n\) is the length of *args;

  • \(k\) is the number of output intervals;

  • \(\lambda\) is the the cost of the operator parameter used in the constructor.

Examples

>>> from part import MutableIntervalDict
>>> from operator import add
>>> a = MutableIntervalDict[int, int](
...     operator=add,
...     default=lambda: 0,
... )
>>> a.update({(1, 10): 1})
>>> print(a)
{'[1;10)': 1}
>>> a.update(
...     FrozenIntervalDict[int, int]({(5, 20): 2}),
...     FrozenIntervalDict[int, int]({(10, 30): 3})
... )
>>> print(a)
{'[1;5)': 1, '[5;10)': 3, '[10;20)': 5, '[20;30)': 3}
>>> a = MutableIntervalDict[int, set](
...     operator=lambda x, y: x | y,
...     strict=False
... )
>>> a.update({(1, 10): {1}})
>>> print(a)
{'[1;10)': {1}}
>>> a.update(
...     FrozenIntervalDict[int, set]({(5, 20): {2}}),
...     FrozenIntervalDict[int, set]({(10, 30): {3}})
... )
>>> print(a)
{'[1;5)': {1}, '[5;10)': {1, 2}, '[10;20)': {2, 3}, '[20;30)': {3}}
clear()

Remove all items from self (same as del self[:]).

The part package is designed to maintain subsets of sorted spaces.

It defines several classes.

For atomic values:

  • TotallyOrdered which represents totally ordered type;

  • TO which represents a generic totally ordered type;

  • Atomic which represents any convex subset of a totally ordered space;

  • Empty which represents the empty subset. There is only one instance of this class;

  • Interval which represents a non-empty subset of a totally ordered space. There is a special instance representing the whole space;

For set classes:

For dictionary classes:

It also defines one constant:

  • INFINITY to hold the infinity value. (-INFINITY is also a valid expression);

Getting Help

Important

If you have any difficulties with py-part, please feel welcome to file an issue on github so that we can help.

Indices and tables

The py-part icon has been designed by Lorc and is distributed under the Creative Commons (Attribution 3.0 Unported) license.