Goulib.interval module

operations on [a..b[ intervals

Goulib.interval.in_interval(interval, x, closed=True)[source]
Returns:bool True if x is in interval [a,b] or [b,a] (tuple)
Goulib.interval.intersect(t1, t2)[source]
Returns:bool True if intervals [t1[ [t2[ intersect
Goulib.interval.intersection(t1, t2)[source]
Returns:tuple intersection between 2 intervals (tuples),

or None if intervals don’t intersect

Goulib.interval.intersectlen(t1, t2, none=0)[source]
Parameters:
  • t1 – interval 1 (tuple)
  • t2 – interval 2 (tuple)
  • none – value to return when t1 does not intersect t2
Returns:

len of intersection between 2 intervals (tuples),

or none if intervals don’t intersect

class Goulib.interval.Interval(start, end)[source]

Bases: list

Represents an interval. Defined as half-open interval [start,end), which includes the start position but not the end. Start and end do not have to be numeric types. They might especially be time, date or timedate as used in datetime2

inspired from http://code.activestate.com/recipes/576816-interval/ alternatives could be https://pypi.python.org/pypi/interval/

(outdated, no more doc) or https://pypi.python.org/pypi/pyinterval/

Construct, start must be <= end.

__init__(start, end)[source]

Construct, start must be <= end.

start

The interval’s start

end

The interval’s end

__str__()[source]
__repr__()[source]
__hash__()[source]
__lt__(other)[source]
__eq__(other)[source]
size
center
separation(other)[source]
Returns:distance between self and other, negative if overlap
overlap(other, allow_contiguous=False)[source]
Returns:True iff self intersects other.
intersection(other)[source]
Returns:Intersection with other, or None if no intersection.
__iadd__(other)[source]

expands self to contain other.

hull(other)[source]
Returns:new Interval containing both self and other.
__add__(other)[source]
__contains__(x)[source]
Returns:True if x in self.
subset(other)[source]
Returns:True iff self is subset of other.
proper_subset(other)[source]
Returns:True iff self is proper subset of other.
empty()[source]
Returns:True iff self is empty.
__nonzero__()[source]
singleton()[source]
Returns:True iff self.end - self.start == 1.
__class__

alias of type

__delattr__

Implement delattr(self, name).

__delitem__

Delete self[key].

__dir__() → list

default dir() implementation

__format__()

default object formatter

__ge__

Return self>=value.

__getattribute__

Return getattr(self, name).

__getitem__()

x.__getitem__(y) <==> x[y]

__gt__

Return self>value.

__imul__

Implement self*=value.

__iter__

Implement iter(self).

__le__

Return self<=value.

__len__

Return len(self).

__mul__

Return self*value.n

__ne__

Return self!=value.

__new__()

Create and return a new object. See help(type) for accurate signature.

__reduce__()

helper for pickle

__reduce_ex__()

helper for pickle

__reversed__()

L.__reversed__() – return a reverse iterator over the list

__rmul__

Return self*value.

__setattr__

Implement setattr(self, name, value).

__setitem__

Set self[key] to value.

__sizeof__()

L.__sizeof__() – size of L in memory, in bytes

append(object) → None -- append object to end
clear() → None -- remove all items from L
copy() → list -- a shallow copy of L
count(value) → integer -- return number of occurrences of value
extend(iterable) → None -- extend list by appending elements from the iterable
index(value[, start[, stop]]) → integer -- return first index of value.

Raises ValueError if the value is not present.

insert()

L.insert(index, object) – insert object before index

pop([index]) → item -- remove and return item at index (default last).

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

remove(value) → None -- remove first occurrence of value.

Raises ValueError if the value is not present.

reverse()

L.reverse() – reverse IN PLACE

sort(key=None, reverse=False) → None -- stable sort *IN PLACE*
class Goulib.interval.Intervals(iterable=None, key=<function identity>, load=1000)[source]

Bases: sortedcontainers.sortedlist.SortedListWithKey

a list of intervals kept in ascending order

SortedListWithKey provides most of the same methods as list but keeps the items in sorted order.

An optional iterable provides an initial series of items to populate the SortedListWithKey.

An optional key argument defines a callable that, like the key argument to Python’s sorted function, extracts a comparison key from each element. The default is the identity function.

An optional load specifies the load-factor of the list. The default load factor of ‘1000’ works well for lists from tens to tens of millions of elements. Good practice is to use a value that is the cube root of the list size. With billions of elements, the best load factor depends on your usage. It’s best to leave the load factor at the default until you start benchmarking.

update(iterable)[source]

Update the list by adding all elements from iterable.

add(item)[source]
insert(item)[source]
__iadd__(item)[source]
__add__(item)[source]
__call__(x)[source]

returns intervals containing x

__str__()[source]

string representation : like a list of Intervals

__abstractmethods__ = frozenset()
__class__

alias of ABCMeta

__contains__(val)

Return True if and only if val is an element in the list.

__copy__()

Return a shallow copy of the sorted list.

__delattr__

Implement delattr(self, name).

__delitem__(idx)

Remove the element at idx. Supports slicing.

__dir__() → list

default dir() implementation

__eq__(that)

Return True if and only if Sequence is equal to that.

__format__()

default object formatter

__ge__(that)

Return True if and only if Sequence is greater than or equal to that.

__getattribute__

Return getattr(self, name).

__getitem__(idx)

Return the element at idx. Supports slicing.

__gt__(that)

Return True if and only if Sequence is greater than that.

__hash__ = None
__imul__(that)

Increase the length of the list by appending that shallow copies of each item.

__init__(iterable=None, key=<function identity>, load=1000)

SortedListWithKey provides most of the same methods as list but keeps the items in sorted order.

An optional iterable provides an initial series of items to populate the SortedListWithKey.

An optional key argument defines a callable that, like the key argument to Python’s sorted function, extracts a comparison key from each element. The default is the identity function.

An optional load specifies the load-factor of the list. The default load factor of ‘1000’ works well for lists from tens to tens of millions of elements. Good practice is to use a value that is the cube root of the list size. With billions of elements, the best load factor depends on your usage. It’s best to leave the load factor at the default until you start benchmarking.

__iter__()

Return an iterator over the Sequence.

Iterating the Sequence while adding or deleting values may raise a RuntimeError or fail to iterate over all entries.

__le__(that)

Return True if and only if Sequence is less than or equal to that.

__len__()

Return the number of elements in the list.

__lt__(that)

Return True if and only if Sequence is less than that.

__mul__(that)

Return a new sorted list containing that shallow copies of each item in SortedListWithKey.

__ne__(that)

Return True if and only if Sequence is not equal to that.

__new__(iterable=None, key=<function identity>, load=1000)
__reduce__()

helper for pickle

__reduce_ex__()

helper for pickle

__repr__()

Return string representation of sequence.

__reversed__()

Return an iterator to traverse the Sequence in reverse.

Iterating the Sequence while adding or deleting values may raise a RuntimeError or fail to iterate over all entries.

__setattr__

Implement setattr(self, name, value).

__setitem__(index, value)

Replace the item at position index with value.

Supports slice notation. Raises a ValueError if the sort order would be violated. When used with a slice and iterable, the ValueError is raised before the list is mutated if the sort order would be violated by the operation.

__sizeof__() → int

size of object in memory, in bytes

__slots__ = ()
append(val)

Append the element val to the list. Raises a ValueError if the val would violate the sort order.

bisect(val)

Same as bisect_left, but if val is already present, the insertion point will be after (to the right of) any existing entries.

bisect_key(key)

Same as bisect_key_left, but if key is already present, the insertion point will be after (to the right of) any existing entries.

bisect_key_left(key)

Similar to the bisect module in the standard library, this returns an appropriate index to insert a value with a given key. If values with key are already present, the insertion point will be before (to the left of) any existing entries.

bisect_key_right(key)

Same as bisect_key_left, but if key is already present, the insertion point will be after (to the right of) any existing entries.

bisect_left(val)

Similar to the bisect module in the standard library, this returns an appropriate index to insert val. If val is already present, the insertion point will be before (to the left of) any existing entries.

bisect_right(val)

Same as bisect_left, but if val is already present, the insertion point will be after (to the right of) any existing entries.

clear()

Remove all the elements from the list.

copy()

Return a shallow copy of the sorted list.

count(val)

Return the number of occurrences of val in the list.

discard(val)

Remove the first occurrence of val.

If val is not a member, does nothing.

extend(values)

Extend the list by appending all elements from the values. Raises a ValueError if the sort order would be violated.

index(val, start=None, stop=None)

Return the smallest k such that L[k] == val and i <= k < j`. Raises ValueError if val is not present. stop defaults to the end of the list. start defaults to the beginning. Negative indices are supported, as for slice indices.

irange(minimum=None, maximum=None, inclusive=(True, True), reverse=False)

Create an iterator of values between minimum and maximum.

inclusive is a pair of booleans that indicates whether the minimum and maximum ought to be included in the range, respectively. The default is (True, True) such that the range is inclusive of both minimum and maximum.

Both minimum and maximum default to None which is automatically inclusive of the start and end of the list, respectively.

When reverse is True the values are yielded from the iterator in reverse order; reverse defaults to False.

irange_key(min_key=None, max_key=None, inclusive=(True, True), reverse=False)

Create an iterator of values between min_key and max_key.

inclusive is a pair of booleans that indicates whether the min_key and max_key ought to be included in the range, respectively. The default is (True, True) such that the range is inclusive of both min_key and max_key.

Both min_key and max_key default to None which is automatically inclusive of the start and end of the list, respectively.

When reverse is True the values are yielded from the iterator in reverse order; reverse defaults to False.

islice(start=None, stop=None, reverse=False)

Returns an iterator that slices self from start to stop index, inclusive and exclusive respectively.

When reverse is True, values are yielded from the iterator in reverse order.

Both start and stop default to None which is automatically inclusive of the beginning and end.

pop(idx=-1)

Remove and return item at idx (default last). Raises IndexError if list is empty or index is out of range. Negative indices are supported, as for slice indices.

remove(val)

Remove first occurrence of val.

Raises ValueError if val is not present.

reverse()

S.reverse() – reverse IN PLACE

class Goulib.interval.Box(*args)[source]

Bases: list

a N dimensional rectangular box defined by a list of N Intervals

__init__(*args)[source]
corner(n)[source]

return n-th corner of box 0-th corner is “start” made of all minimal values of intervals -1.th corner is “end”, made of all maximal values of intervals

start
end
size
center
__call__()[source]
Returns:tuple of all intervals as tuples
__iadd__(other)[source]

enlarge box if required to contain specified point :param other: Box or (list of) N-tuple point(s)

__add__(other)[source]

enlarge box if required to contain specified point :param other: Box or (list of) N-tuple point(s) :return: new Box containing both

__contains__(other)[source]
Returns:True if x in self.
__nonzero__()[source]
empty()[source]
Returns:True iff Box is empty.
__class__

alias of type

__delattr__

Implement delattr(self, name).

__delitem__

Delete self[key].

__dir__() → list

default dir() implementation

__eq__

Return self==value.

__format__()

default object formatter

__ge__

Return self>=value.

__getattribute__

Return getattr(self, name).

__getitem__()

x.__getitem__(y) <==> x[y]

__gt__

Return self>value.

__hash__ = None
__imul__

Implement self*=value.

__iter__

Implement iter(self).

__le__

Return self<=value.

__len__

Return len(self).

__lt__

Return self<value.

__mul__

Return self*value.n

__ne__

Return self!=value.

__new__()

Create and return a new object. See help(type) for accurate signature.

__reduce__()

helper for pickle

__reduce_ex__()

helper for pickle

__repr__

Return repr(self).

__reversed__()

L.__reversed__() – return a reverse iterator over the list

__rmul__

Return self*value.

__setattr__

Implement setattr(self, name, value).

__setitem__

Set self[key] to value.

__sizeof__()

L.__sizeof__() – size of L in memory, in bytes

__str__

Return str(self).

append(object) → None -- append object to end
clear() → None -- remove all items from L
copy() → list -- a shallow copy of L
count(value) → integer -- return number of occurrences of value
extend(iterable) → None -- extend list by appending elements from the iterable
index(value[, start[, stop]]) → integer -- return first index of value.

Raises ValueError if the value is not present.

insert()

L.insert(index, object) – insert object before index

max
min
pop([index]) → item -- remove and return item at index (default last).

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

remove(value) → None -- remove first occurrence of value.

Raises ValueError if the value is not present.

reverse()

L.reverse() – reverse IN PLACE

sort(key=None, reverse=False) → None -- stable sort *IN PLACE*