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.
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.
-
start
¶ The interval’s start
-
end
¶ The interval’s end
-
size
¶
-
center
¶
-
__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)
-
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
-
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: other – other 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: other – other 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: other – other 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: other – other 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: other – other 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: other – other 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]
andsl.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: value – value 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: 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: 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: value – value 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
-
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
¶
-
__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
-
__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*¶
-