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

value (IntervalValue) –
The value to search:
strict (bool) – Is the comparison strict?

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}