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]

Return str(self).

__repr__()[source]

Return repr(self).

__hash__()[source]

Return hash(self).

__lt__(other)[source]

Return self<value.

__eq__(other)[source]

Return self==value.

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]

Return self+value.

__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 builtins.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>)[source]

Bases: sortedcontainers.sortedlist.SortedKeyList

a list of intervals kept in ascending order

Initialize sorted-key list instance.

Optional iterable argument provides an initial iterable of values to initialize the sorted-key list.

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

Runtime complexity: O(n*log(n))

>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl
SortedKeyList([], key=<built-in function neg>)
>>> skl = SortedKeyList([3, 1, 2], key=neg)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
Parameters:
  • iterable – initial values (optional)
  • key – function used to extract comparison key (optional)
update(iterable)[source]

Update the list by adding all elements from iterable.

add(item)[source]

Add value to sorted-key list.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl.add(3)
>>> skl.add(1)
>>> skl.add(2)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
Parameters:value – value to add to sorted-key list
insert(item)[source]

Raise not-implemented error.

Raises:NotImplementedError – use sl.add(value) instead
__iadd__(item)[source]

Update sorted list with values from other.

sl.__iadd__(other) <==> sl += other

Values in other do not need to be in sorted order.

Runtime complexity: O(k*log(n)) – approximate.

>>> sl = SortedList('bat')
>>> sl += 'cat'
>>> sl
SortedList(['a', 'a', 'b', 'c', 't', 't'])
Parameters:other – other iterable
Returns:existing sorted list
__add__(item)[source]

Return new sorted-key list containing all values in both sequences.

skl.__add__(other) <==> skl + other

Values in other do not need to be in sorted-key order.

Runtime complexity: O(n*log(n))

>>> from operator import neg
>>> skl1 = SortedKeyList([5, 4, 3], key=neg)
>>> skl2 = SortedKeyList([2, 1, 0], key=neg)
>>> skl1 + skl2
SortedKeyList([5, 4, 3, 2, 1, 0], key=<built-in function neg>)
Parameters:other – other iterable
Returns:new sorted-key list
__call__(x)[source]

returns intervals containing x

__str__()[source]

string representation : like a list of Intervals

DEFAULT_LOAD_FACTOR = 1000
__abstractmethods__ = frozenset()
__class__

alias of abc.ABCMeta

__contains__(value)

Return true if value is an element of the sorted-key list.

skl.__contains__(value) <==> value in skl

Runtime complexity: O(log(n))

>>> from operator import neg
>>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
>>> 3 in skl
True
Parameters:value – search for value in sorted-key list
Returns:true if value in sorted-key list
__copy__()

Return a shallow copy of the sorted-key list.

Runtime complexity: O(n)

Returns:new sorted-key list
__delattr__

Implement delattr(self, name).

__delitem__(index)

Remove value at index from sorted list.

sl.__delitem__(index) <==> del sl[index]

Supports slicing.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList('abcde')
>>> del sl[2]
>>> sl
SortedList(['a', 'b', 'd', 'e'])
>>> del sl[:2]
>>> sl
SortedList(['d', 'e'])
Parameters:index – integer or slice for indexing
Raises:IndexError – if index out of range
__dir__() → list

default dir() implementation

__eq__(other)

Return true if and only if sorted list is equal to other.

sl.__eq__(other) <==> sl == other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:otherother sequence
Returns:true if sorted list is equal to other
__format__()

default object formatter

__ge__(other)

Return true if and only if sorted list is greater than or equal to other.

sl.__ge__(other) <==> sl >= other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:otherother sequence
Returns:true if sorted list is greater than or equal to other
__getattribute__

Return getattr(self, name).

__getitem__(index)

Lookup value at index in sorted list.

sl.__getitem__(index) <==> sl[index]

Supports slicing.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList('abcde')
>>> sl[1]
'b'
>>> sl[-1]
'e'
>>> sl[2:5]
['c', 'd', 'e']
Parameters:index – integer or slice for indexing
Returns:value or list of values
Raises:IndexError – if index out of range
__gt__(other)

Return true if and only if sorted list is greater than other.

sl.__gt__(other) <==> sl > other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:otherother sequence
Returns:true if sorted list is greater than other
__hash__ = None
__imul__(num)

Update the sorted list with num shallow copies of values.

sl.__imul__(num) <==> sl *= num

Runtime complexity: O(n*log(n))

>>> sl = SortedList('abc')
>>> sl *= 3
>>> sl
SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
Parameters:num (int) – count of shallow copies
Returns:existing sorted list
__init__(iterable=None, key=<function identity>)

Initialize sorted-key list instance.

Optional iterable argument provides an initial iterable of values to initialize the sorted-key list.

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

Runtime complexity: O(n*log(n))

>>> from operator import neg
>>> skl = SortedKeyList(key=neg)
>>> skl
SortedKeyList([], key=<built-in function neg>)
>>> skl = SortedKeyList([3, 1, 2], key=neg)
>>> skl
SortedKeyList([3, 2, 1], key=<built-in function neg>)
Parameters:
  • iterable – initial values (optional)
  • key – function used to extract comparison key (optional)
__iter__()

Return an iterator over the sorted list.

sl.__iter__() <==> iter(sl)

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

__le__(other)

Return true if and only if sorted list is less than or equal to other.

sl.__le__(other) <==> sl <= other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:otherother sequence
Returns:true if sorted list is less than or equal to other
__len__()

Return the size of the sorted list.

sl.__len__() <==> len(sl)

Returns:size of sorted list
__lt__(other)

Return true if and only if sorted list is less than other.

sl.__lt__(other) <==> sl < other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:otherother sequence
Returns:true if sorted list is less than other
__mul__(num)

Return new sorted-key list with num shallow copies of values.

skl.__mul__(num) <==> skl * num

Runtime complexity: O(n*log(n))

>>> from operator import neg
>>> skl = SortedKeyList([3, 2, 1], key=neg)
>>> skl * 2
SortedKeyList([3, 3, 2, 2, 1, 1], key=<built-in function neg>)
Parameters:num (int) – count of shallow copies
Returns:new sorted-key list
__ne__(other)

Return true if and only if sorted list is not equal to other.

sl.__ne__(other) <==> sl != other

Comparisons use lexicographical order as with sequences.

Runtime complexity: O(n)

Parameters:otherother sequence
Returns:true if sorted list is not equal to other
static __new__(cls, iterable=None, key=<function identity>)

Create new sorted list or sorted-key list instance.

Optional key-function argument will return an instance of subtype SortedKeyList.

>>> sl = SortedList()
>>> isinstance(sl, SortedList)
True
>>> sl = SortedList(key=lambda x: -x)
>>> isinstance(sl, SortedList)
True
>>> isinstance(sl, SortedKeyList)
True
Parameters:
  • iterable – initial values (optional)
  • key – function used to extract comparison key (optional)
Returns:

sorted list or sorted-key list instance

__radd__(other)

Return new sorted-key list containing all values in both sequences.

skl.__add__(other) <==> skl + other

Values in other do not need to be in sorted-key order.

Runtime complexity: O(n*log(n))

>>> from operator import neg
>>> skl1 = SortedKeyList([5, 4, 3], key=neg)
>>> skl2 = SortedKeyList([2, 1, 0], key=neg)
>>> skl1 + skl2
SortedKeyList([5, 4, 3, 2, 1, 0], key=<built-in function neg>)
Parameters:other – other iterable
Returns:new sorted-key list
__reduce__()

helper for pickle

__reduce_ex__()

helper for pickle

__repr__()

Return string representation of sorted-key list.

skl.__repr__() <==> repr(skl)

Returns:string representation
__reversed__()

Return a reverse iterator over the sorted list.

sl.__reversed__() <==> reversed(sl)

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

__rmul__(num)

Return new sorted list with num shallow copies of values.

sl.__mul__(num) <==> sl * num

Runtime complexity: O(n*log(n))

>>> sl = SortedList('abc')
>>> sl * 3
SortedList(['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'])
Parameters:num (int) – count of shallow copies
Returns:new sorted list
__setattr__

Implement setattr(self, name, value).

__setitem__(index, value)

Raise not-implemented error.

sl.__setitem__(index, value) <==> sl[index] = value

Raises:NotImplementedError – use del sl[index] and sl.add(value) instead
__sizeof__() → int

size of object in memory, in bytes

__slots__ = ()
append(value)

Raise not-implemented error.

Implemented to override MutableSequence.append which provides an erroneous default implementation.

Raises:NotImplementedError – use sl.add(value) instead
bisect(value)

Return an index to insert value in the sorted-key list.

Similar to bisect_left, but if value is already present, the insertion point with be after (to the right of) any existing values.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_right(1)
5
Parameters:value – insertion index of value in sorted-key list
Returns:index
bisect_key(key)

Return an index to insert key in the sorted-key list.

Similar to bisect_key_left, but if key is already present, the insertion point with be after (to the right of) any existing keys.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_right(-1)
5
Parameters:key – insertion index of key in sorted-key list
Returns:index
bisect_key_left(key)

Return an index to insert key in the sorted-key list.

If the key is already present, the insertion point will be before (to the left of) any existing keys.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_left(-1)
4
Parameters:key – insertion index of key in sorted-key list
Returns:index
bisect_key_right(key)

Return an index to insert key in the sorted-key list.

Similar to bisect_key_left, but if key is already present, the insertion point with be after (to the right of) any existing keys.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_key_right(-1)
5
Parameters:key – insertion index of key in sorted-key list
Returns:index
bisect_left(value)

Return an index to insert value in the sorted-key list.

If the value is already present, the insertion point will be before (to the left of) any existing values.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_left(1)
4
Parameters:value – insertion index of value in sorted-key list
Returns:index
bisect_right(value)

Return an index to insert value in the sorted-key list.

Similar to bisect_left, but if value is already present, the insertion point with be after (to the right of) any existing values.

Similar to the bisect module in the standard library.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedList([5, 4, 3, 2, 1], key=neg)
>>> skl.bisect_right(1)
5
Parameters:value – insertion index of value in sorted-key list
Returns:index
clear()

Remove all values from sorted-key list.

Runtime complexity: O(n)

copy()

Return a shallow copy of the sorted-key list.

Runtime complexity: O(n)

Returns:new sorted-key list
count(value)

Return number of occurrences of value in the sorted-key list.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedKeyList([4, 4, 4, 4, 3, 3, 3, 2, 2, 1], key=neg)
>>> skl.count(2)
2
Parameters:value – value to count in sorted-key list
Returns:count
discard(value)

Remove value from sorted-key list if it is a member.

If value is not a member, do nothing.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.discard(1)
>>> skl.discard(0)
>>> skl == [5, 4, 3, 2]
True
Parameters:valuevalue to discard from sorted-key list
extend(values)

Raise not-implemented error.

Implemented to override MutableSequence.extend which provides an erroneous default implementation.

Raises:NotImplementedError – use sl.update(values) instead
index(value, start=None, stop=None)

Return first index of value in sorted-key list.

Raise ValueError if value is not present.

Index must be between start and stop for the value to be considered present. The default value, None, for start and stop indicate the beginning and end of the sorted-key list.

Negative indices are supported.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedKeyList([5, 4, 3, 2, 1], key=neg)
>>> skl.index(2)
3
>>> skl.index(0)
Traceback (most recent call last):
  ...
ValueError: 0 is not in list
Parameters:
  • value – value in sorted-key list
  • start (int) – start index (default None, start of sorted-key list)
  • stop (int) – stop index (default None, end of sorted-key list)
Returns:

index of value

Raises:

ValueError – if value is not present

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

Create an iterator of values between minimum and maximum.

Both minimum and maximum default to None which is automatically inclusive of the beginning and end of the sorted-key list.

The argument 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.

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

>>> from operator import neg
>>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
>>> it = skl.irange(14.5, 11.5)
>>> list(it)
[14, 13, 12]
Parameters:
  • minimum – minimum value to start iterating
  • maximum – maximum value to stop iterating
  • inclusive – pair of booleans
  • reverse (bool) – yield values in reverse order
Returns:

iterator

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

Create an iterator of values between min_key and max_key.

Both min_key and max_key default to None which is automatically inclusive of the beginning and end of the sorted-key list.

The argument 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.

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

>>> from operator import neg
>>> skl = SortedKeyList([11, 12, 13, 14, 15], key=neg)
>>> it = skl.irange_key(-14, -12)
>>> list(it)
[14, 13, 12]
Parameters:
  • min_key – minimum key to start iterating
  • max_key – maximum key to stop iterating
  • inclusive – pair of booleans
  • reverse (bool) – yield values in reverse order
Returns:

iterator

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

Return an iterator that slices sorted list from start to stop.

The start and stop index are treated inclusive and exclusive, respectively.

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

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

>>> sl = SortedList('abcdefghij')
>>> it = sl.islice(2, 6)
>>> list(it)
['c', 'd', 'e', 'f']
Parameters:
  • start (int) – start index (inclusive)
  • stop (int) – stop index (exclusive)
  • reverse (bool) – yield values in reverse order
Returns:

iterator

key

Function used to extract comparison key from values.

pop(index=-1)

Remove and return value at index in sorted list.

Raise IndexError if the sorted list is empty or index is out of range.

Negative indices are supported.

Runtime complexity: O(log(n)) – approximate.

>>> sl = SortedList('abcde')
>>> sl.pop()
'e'
>>> sl.pop(2)
'c'
>>> sl
SortedList(['a', 'b', 'd'])
Parameters:index (int) – index of value (default -1)
Returns:value
Raises:IndexError – if index is out of range
remove(value)

Remove value from sorted-key list; value must be a member.

If value is not a member, raise ValueError.

Runtime complexity: O(log(n)) – approximate.

>>> from operator import neg
>>> skl = SortedKeyList([1, 2, 3, 4, 5], key=neg)
>>> skl.remove(5)
>>> skl == [4, 3, 2, 1]
True
>>> skl.remove(0)
Traceback (most recent call last):
  ...
ValueError: 0 not in list
Parameters:valuevalue to remove from sorted-key list
Raises:ValueError – if value is not in sorted-key list
reverse()

Raise not-implemented error.

Sorted list maintains values in ascending sort order. Values may not be reversed in-place.

Use reversed(sl) for an iterator over values in descending sort order.

Implemented to override MutableSequence.reverse which provides an erroneous default implementation.

Raises:NotImplementedError – use reversed(sl) instead
class Goulib.interval.Box(*args)[source]

Bases: list

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

__init__(*args)[source]

Initialize self. See help(type(self)) for accurate signature.

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
min
max
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 builtins.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

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*