segmentlist

class igwn_segments.segmentlist(iterable=(), /)

Bases: list

The segmentlist class defines a list of segments, and is an extension of the built-in list class. This class provides addtional methods that assist in the manipulation of lists of segments. In particular, arithmetic operations such as union and intersection are provided. Unlike the segment class, the segmentlist class is closed under all supported arithmetic operations.

All standard Python sequence-like operations are supported, like slicing, iteration and so on, including arithmetic operations. However, the arithmetic and other methods for this class generally require the segmentlist to be in what is refered to as a “coalesced” state — consisting solely of disjoint segments listed in ascending order. Using the standard Python sequence-like operations, a segmentlist can be easily constructed that is not in this state, for example by simply appending a segment to the end of the list that overlaps some other segment already in the list. The use of methods that require coalesced lists with lists that are not coalesced has undefined results. For performance reasons, safety checks for coalescedness are not included in any moethods, however the class provides the .coalesce() method that transforms a segmentlist into the coalesced state in-place and can be used to sanitize segmentlist objects whose state is not known. All arithmetic methods return coalesced results, so typically the .coalesce() method will be executed once after importing a segmentlist from an untrusted source, then there is never a need to call the .coalesce() method again as long as the segmentlists are manipulated exclusively via the arithmetic operators.

Example:

>>> x = segmentlist([segment(-10, 10)])
>>> x |= segmentlist([segment(20, 30)])
>>> x -= segmentlist([segment(-5, 5)])
>>> print(x)
[segment(-10, -5), segment(5, 10), segment(20, 30)]
>>> print(~x)
[segment(-infinity, -10), segment(-5, 5), segment(10, 20), segment(30, infinity)]

Methods Summary

coalesce()	Sort the elements of the list into ascending order, and merge continuous segments into single segments.
contract(object, /)	Execute the .contract() method on each segment in the list and coalesce the result.
extent()	Return the segment whose end-points denote the maximum and minimum extent of the segmentlist.
find(object, /)	Return the smallest i such that i is the index of an element that wholly contains item.
intersects(object, /)	Returns True if the intersection of self and the segmentlist other is not the null set, otherwise returns False.
intersects_segment(object, /)	Returns True if the intersection of self and the segment other is not the null set, otherwise returns False.
protract(object, /)	Execute the .protract() method on each segment in the list and coalesce the result.
shift(object, /)	Execute the .shift() method on each segment in the list.
value_slice_to_index(object, /)	Convert the slice s from a slice of values to a slice of indexes.

Methods Documentation

coalesce()

Sort the elements of the list into ascending order, and merge continuous segments into single segments. Segmentlist is modified in place. This operation is O(n log n).

contract(object, /)

Execute the .contract() method on each segment in the list and coalesce the result. Segmentlist is modified in place.

extent()

Return the segment whose end-points denote the maximum and minimum extent of the segmentlist. Does not require the segmentlist to be coalesced.

find(object, /)

Return the smallest i such that i is the index of an element that wholly contains item. Raises ValueError if no such element exists. Does not require the segmentlist to be coalesced.

intersects(object, /)

Returns True if the intersection of self and the segmentlist other is not the null set, otherwise returns False. The algorithm is O(n), but faster than explicit calculation of the intersection, i.e. by testing bool(self & other). Requires both lists to be coalesced.

intersects_segment(object, /)

Returns True if the intersection of self and the segment other is not the null set, otherwise returns False. The algorithm is O(log n). Requires the list to be coalesced.

protract(object, /)

Execute the .protract() method on each segment in the list and coalesce the result. Segmentlist is modified in place.

shift(object, /)

Execute the .shift() method on each segment in the list. The algorithm is O(n) and does not require the list to be coalesced nor does it coalesce the list. Segmentlist is modified in place.

value_slice_to_index(object, /)

Convert the slice s from a slice of values to a slice of indexes. self must be coalesced, the operation is O(log n). This is used to extract from a segmentlist the segments that span a given range of values, and is useful in reducing operation counts when many repeated operations are required within a limited range of values.

NOTE: the definition of the transformation is important, and some care might be needed to use this tool properly. The start and stop values of the slice are transformed independently. The start value is mapped to the index of the first segment whose upper bound is greater than start, meaning the first segment spanning values greater than or equal to the value of start. The stop value is mapped to 1 + the index of the last segment whose lower bound is less than stop, meaning the last segment spanning values less than the value of stop. This can lead to unexpected behaviour if value slices whose upper and lower bounds are identical are transformed to index slices. For example:

>>> x = segmentlist([segment(-10, -5), segment(5, 10), segment(20, 30)])
>>> x.value_slice_to_index(slice(5, 5))
slice(1, 1, None)
>>> x.value_slice_to_index(slice(6, 6))
slice(1, 2, None)

Both value slices are zero-length, but one has yielded a zero-length (null) index slice, while the other has not. The two value slices start at 5 and 6 respectively. Both starting values lie within segment 1, and in both cases the start value has been mapped to index 1, as expected. The first slice ends at 5, meaning it expresses the idea of a range of values upto but not including 5, which corresponds to segments upto but not including index 1, and so that stop value has been mapped to an index slice upper bound of 1. The second slice ends at 6, and the range of values upto but not including 6 corresponds to segment indexes upto but not including 2, which is what we see that bound has been mapped to.

Examples:

>>> x = segmentlist([segment(-10, -5), segment(5, 10), segment(20, 30)])
>>> x
[segment(-10, -5), segment(5, 10), segment(20, 30)]
>>> x[x.value_slice_to_index(slice(7, 8))]
[segment(5, 10)]
>>> x[x.value_slice_to_index(slice(7, 18))]
[segment(5, 10)]
>>> x[x.value_slice_to_index(slice(7, 20))]
[segment(5, 10)]
>>> x[x.value_slice_to_index(slice(7, 25))]
[segment(5, 10), segment(20, 30)]
>>> x[x.value_slice_to_index(slice(10, 10))]
[]
>>> x[x.value_slice_to_index(slice(10, 18))]
[]
>>> x[x.value_slice_to_index(slice(10, 20))]
[]
>>> x[x.value_slice_to_index(slice(10, 25))]
[segment(20, 30)]
>>> x[x.value_slice_to_index(slice(20, 20))]
[]
>>> x[x.value_slice_to_index(slice(21, 21))]
[segment(20, 30)]
>>> x[x.value_slice_to_index(slice(-20, 8))]
[segment(-10, -5), segment(5, 10)]
>>> x[x.value_slice_to_index(slice(-20, -15))]
[]
>>> x[x.value_slice_to_index(slice(11, 18))]
[]
>>> x[x.value_slice_to_index(slice(40, 50))]
[]
>>> x[x.value_slice_to_index(slice(None, 0))]
[segment(-10, -5)]
>>> x[x.value_slice_to_index(slice(0, None))]
[segment(5, 10), segment(20, 30)]