ligo.segments

This module defines the segment and segmentlist objects, as well as the infinity object used to define semi-infinite and infinite segments.

See also:

glue.segmentsUtils

class ligo.segments.infinity

Bases: object

The infinity object possess the algebraic properties necessary for use as a bound on semi-infinite and infinite segments.

This class uses comparison-by-identity rather than comparison-by-value. What this means, is there are only ever two instances of this class, representing positive and negative infinity respectively. All other “instances” of this class are infact simply references to one of these two, and comparisons are done by checking which one you’ve got. This improves speed and reduces memory use, and is similar in implementation to Python’s boolean True and False objects.

The normal way to obtain references to positive or negative infinity is to do infinity() or -infinity() respectively. It is also possible to select the sign by passing a single numeric argument to the constructor. The sign of the argument causes a reference to either positive or negative infinity to be returned, respectively. For example infinity(-1) is equivalent to -infinity(). However, this feature is a little slower and not recommended for normal use; it is provided only to simplify the pickling and unpickling of instances of the class.

Example:

>>> x = infinity()
>>> x > 0
True
>>> x + 10 == x
True
>>> segment(-10, 10) - segment(-x, 0)
segment(0, 10)
>>> import math
>>> math.isinf(x)
True

class ligo.segments.segment

Bases: tuple

The segment class defines objects that represent a range of values. A segment has a start and an end, and is taken to represent the range of values in the semi-open interval [start, end). Some limited arithmetic operations are possible with segments, but because the set of (single) segments is not closed under the sensible definitions of the standard arithmetic operations, the behaviour of the arithmetic operators on segments may not be as you would expect. For general arithmetic on segments, use segmentlist objects. The methods for this class exist mostly for purpose of simplifying the implementation of the segmentlist class.

The segment class is a subclass of the tuple built-in class provided by Python. This means segments are immutable — you cannot modify a segment object after creating it, to change the boundaries of a segment you must create a new segment object with the desired boundaries. Like tuples, segments can be used as dictionary keys, and like tuples the comparison used to find a segment in the dictionary is done by value not by ID. And, like tuples, a segment can be created from any sequence-like object by passing it to the constructor (the sequence must have exactly two elements in it).

Example:

>>> segment(0, 10) & segment(5, 15)
segment(5, 10)
>>> segment(0, 10) | segment(5, 15)
segment(0, 15)
>>> segment(0, 10) - segment(5, 15)
segment(0, 5)
>>> segment(0, 10) < segment(5, 15)
True
>>> segment(1, 2) in segment(0, 10)
True
>>> segment(1, 11) in segment(0, 10)
False
>>> segment(0, 1)
segment(0, 1)
>>> segment(1, 0)
segment(0, 1)
>>> bool(segment(0, 1))
True
>>> bool(segment(0, 0))
False
>>> segment("AAA Towing", "York University") & segment("Pool", "Zoo")
segment('Pool', 'York University')
>>> x = [0, 1]  # a list
>>> segment(x)
segment(0, 1)
>>> y = segment(0, 1)
>>> y == x
True
>>> y is x
False
>>> x in y
True
>>> z = {x: ["/path/to/file1", "/path/to/file2"]}
>>> y in z
True
>>> z[y]
['/path/to/file1', '/path/to/file2']

connects(other)

Returns True if ths segment and other touch but do not overlap

contract(x)

Return a new segment whose bounds are given by adding x to the segment’s lower bound and subtracting x from the segment’s upper bound.

count()

Return number of occurrences of value.

disjoint(other)

Returns >0 if self covers an interval above other’s interval, <0 if self covers an interval below other’s, or 0 if the two intervals are not disjoint (intersect or touch). A return value of 0 indicates the two segments would coalesce.

index()

Return first index of value.

Raises ValueError if the value is not present.

intersects(other)

Return True if the intersection of self and other is not a null segment.

protract(x)

Return a new segment whose bounds are given by subtracting x from the segment’s lower bound and adding x to the segment’s upper bound.

shift(x)

Return a new segment whose bounds are given by adding x to the segment’s upper and lower bounds.

class ligo.segments.segmentlist

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. The class provides the .coalesce() method that can be called to put a segmentlist in the coalesced state. 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)]

append()

Append object to the end of the list.

clear()

Remove all items from list.

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

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

copy()

Return a shallow copy of the list.

count()

Return number of occurrences of value.

extend()

Extend list by appending elements from the iterable.

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

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.

index()

Return first index of value.

Raises ValueError if the value is not present.

insert()

Insert object before index.

intersects(other)

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

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.

pop()

Remove and return item at index (default last).

Raises IndexError if list is empty or index is out of range.

protract(x)

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

remove()

Remove first occurrence of value.

Raises ValueError if the value is not present.

reverse()

Reverse IN PLACE.

shift(x)

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.

sort()

Stable sort IN PLACE.

class ligo.segments.segmentlistdict(*args)

Bases: dict

A dictionary associating a unique label and numeric offset with each of a set of segmentlist objects.

This class implements a standard mapping interface, with additional features added to assist with the manipulation of a collection of segmentlist objects. In particular, methods for taking unions and intersections of the lists in the dictionary are available, as well as the ability to record and apply numeric offsets to the boundaries of the segments in each list.

The numeric offsets are stored in the “offsets” attribute, which itself is a dictionary, associating a number with each key in the main dictionary. Assigning to one of the entries of the offsets attribute has the effect of shifting the corresponding segmentlist from its original position (not its current position) by the given amount.

Example:

>>> x = segmentlistdict()
>>> x["H1"] = segmentlist([segment(0, 10)])
>>> print(x)
{'H1': [segment(0, 10)]}
>>> x.offsets["H1"] = 6
>>> print(x)
{'H1': [segment(6.0, 16.0)]}
>>> x.offsets.clear()
>>> print(x)
{'H1': [segment(0.0, 10.0)]}
>>> x["H2"] = segmentlist([segment(5, 15)])
>>> x.intersection(["H1", "H2"])
[segment(5, 10.0)]
>>> x.offsets["H1"] = 6
>>> x.intersection(["H1", "H2"])
[segment(6.0, 15)]
>>> c = x.extract_common(["H1", "H2"])
>>> c.offsets.clear()
>>> assert c == {'H2': [segment(6.0, 15)], 'H1': [segment(0.0, 9.0)]}

all_intersects(other)

Returns True if each segmentlist in self intersects the corresponding segmentlist in other; returns False if this is not the case or if self is empty.

See also:

.intersects, .intersects_all(), .all_intersects_all()

all_intersects_all(other)

Returns True if self and other have the same keys, and each segmentlist intersects the corresponding segmentlist in the other; returns False if this is not the case or if either dictionary is empty.

See also:

.intersects(), .all_intersects(), .intersects_all()

clear() → None. Remove all items from D.

coalesce()

Run .coalesce() on all segmentlists.

contract(x)

Run .contract(x) on all segmentlists.

copy(keys=None)

Return a copy of the segmentlistdict object. The return value is a new object with a new offsets attribute, with references to the original keys, and shallow copies of the segment lists. Modifications made to the offset dictionary or segmentlists in the object returned by this method will not affect the original, but without using much memory until such modifications are made. If the optional keys argument is not None, then should be an iterable of keys and only those segmentlists will be copied (KeyError is raised if any of those keys are not in the segmentlistdict).

More details. There are two “built-in” ways to create a copy of a segmentlist object. The first is to initialize a new object from an existing one with

>>> old = segmentlistdict()
>>> new = segmentlistdict(old)

This creates a copy of the dictionary, but not of its contents. That is, this creates new with references to the segmentlists in old, therefore changes to the segmentlists in either new or old are reflected in both. The second method is

>>> new = old.copy()

This creates a copy of the dictionary and of the segmentlists, but with references to the segment objects in the original segmentlists. Since segments are immutable, this effectively creates a completely independent working copy but without the memory cost of a full duplication of the data.

extend(other)

Appends the segmentlists from other to the corresponding segmentlists in self, adding new segmentslists to self as needed.

extent()

Return a dictionary of the results of running .extent() on each of the segmentlists.

extent_all()

Return the result of running .extent() on the union of all lists in the dictionary.

extract_common(keys)

Return a new segmentlistdict containing only those segmentlists associated with the keys in keys, with each set to their mutual intersection. The offsets are preserved.

find(item)

Return a dictionary of the results of running .find() on each of the segmentlists.

Example:

>>> x = segmentlistdict()
>>> x["H1"] = segmentlist([segment(0, 10)])
>>> x["H2"] = segmentlist([segment(5, 15)])
>>> assert x.find(7) == {'H2': 0, 'H1': 0}

NOTE: all segmentlists must contain the item or KeyError is raised.

fromkeys()

Create a new dictionary with keys from iterable and values set to value.

get()

Return the value for key if key is in the dictionary, else default.

intersection(keys)

Return the intersection of the segmentlists associated with the keys in keys.

intersects(other)

Returns True if there exists a segmentlist in self that intersects the corresponding segmentlist in other; returns False otherwise.

See also:

.intersects_all(), .all_intersects(), .all_intersects_all()

intersects_all(other)

Returns True if each segmentlist in other intersects the corresponding segmentlist in self; returns False if this is not the case, or if other is empty.

See also:

.intersects(), .all_intersects(), .all_intersects_all()

intersects_segment(seg)

Returns True if any segmentlist in self intersects the segment, otherwise returns False.

is_coincident(other, keys=None)

Return True if any segment in any list in self intersects any segment in any list in other. If the optional keys argument is not None, then it should be an iterable of keys and only segment lists for those keys will be considered in the test (instead of raising KeyError, keys not present in both segment list dictionaries will be ignored). If keys is None (the default) then all segment lists are considered.

This method is equivalent to the intersects() method, but without requiring the keys of the intersecting segment lists to match.

items() → a set-like object providing a view on D's items

keys() → a set-like object providing a view on D's keys

keys_at(x)

Return a list of the keys for the segment lists that contain x.

Example:

>>> x = segmentlistdict()
>>> x["H1"] = segmentlist([segment(0, 10)])
>>> x["H2"] = segmentlist([segment(5, 15)])
>>> x.keys_at(12)
['H2']

map(func)

Return a dictionary of the results of func applied to each of the segmentlist objects in self.

Example:

>>> x = segmentlistdict()
>>> x["H1"] = segmentlist([segment(0, 10)])
>>> x["H2"] = segmentlist([segment(5, 15)])
>>> assert x.map(lambda l: 12 in l) == {'H2': True, 'H1': False}

pop(k[, d]) → v, remove specified key and return the corresponding value.

If key is not found, d is returned if given, otherwise KeyError is raised

popitem() → (k, v), remove and return some (key, value) pair as a

2-tuple; but raise KeyError if D is empty.

protract(x)

Run .protract(x) on all segmentlists.

setdefault()

Insert key with a value of default if key is not in the dictionary.

Return the value for key if key is in the dictionary, else default.

union(keys)

Return the union of the segmentlists associated with the keys in keys.

update([E, ]**F) → None. Update D from dict/iterable E and F.

If E is present and has a .keys() method, then does: for k in E: D[k] = E[k] If E is present and lacks a .keys() method, then does: for k, v in E: D[k] = v In either case, this is followed by: for k in F: D[k] = F[k]

values() → an object providing a view on D's values