Source code for stonesoup.types.interval

# -*- coding: utf-8 -*-
import copy
import operator
from itertools import combinations
from numbers import Real
from typing import Sequence, Union, MutableSequence, Tuple

from ..base import Property
from ..types import Type


[docs]class Interval(Type): """ Closed continuous interval class. Represents a continuous, closed interval of real numbers. Represented by a lower and upper bound. """ left: Union[int, float] = Property(doc="Lower bound of interval") right: Union[int, float] = Property(doc="Upper bound of interval") def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) if self.left >= self.right: raise ValueError('Must have left < right') def __hash__(self): return hash((self.left, self.right)) @property def length(self): return self.right - self.left def __contains__(self, item): if isinstance(item, Real): return self.left <= item <= self.right elif isinstance(item, Interval): return self & item == item else: return False def __str__(self): return '[{left}, {right}]'.format(left=self.left, right=self.right) def __repr__(self): return 'Interval{interval}'.format(interval=str(self)) def __eq__(self, other): return isinstance(other, Interval) and (self.left, self.right) == (other.left, other.right) def __and__(self, other): """Set-like intersection""" if not isinstance(other, Interval): raise ValueError("Can only intersect with Interval types") if not self.isdisjoint(other): new_interval = (max(self.left, other.left), min(self.right, other.right)) if new_interval[0] == new_interval[1]: return None else: return Interval(*new_interval) else: return None def __or__(self, other): """Set-like union""" if not isinstance(other, Interval): raise ValueError("Can only union with Interval types") if not self.isdisjoint(other): return [Interval(min(self.left, other.left), max(self.right, other.right))] else: return [copy.copy(self), copy.copy(other)] def __sub__(self, other): """Set-like difference""" if other is None: return [copy.copy(self)] elif not isinstance(other, Interval): raise ValueError("Can only subtract Interval types from Interval types") elif self.isdisjoint(other): return [copy.copy(self)] elif other.left <= self.left and self.right <= other.right: return [None] elif other.left <= self.left: return [Interval(other.right, self.right)] elif self.right <= other.right: return [Interval(self.left, other.left)] else: return [Interval(self.left, other.left), Interval(other.right, self.right)] def __xor__(self, other): """Set-like symmetric difference""" if not isinstance(other, Interval): raise ValueError("Can only subtract Interval types from Interval types") if self.isdisjoint(other): return [copy.copy(self), copy.copy(other)] # Union will return list with one interval return (self | other)[0] - (self & other) def __le__(self, other): """Subset check""" if not isinstance(other, Interval): raise ValueError("Can only compare Interval types to Interval types") return self in other def __lt__(self, other): """Proper subset check""" if not isinstance(other, Interval): raise ValueError("Can only compare Interval types to Interval types") return other.left < self.left and self.right < other.right def __ge__(self, other): """Superset check""" if not isinstance(other, Interval): raise ValueError("Can only compare Interval types to Interval types") return other <= self def __gt__(self, other): """Proper superset check""" if not isinstance(other, Interval): raise ValueError("Can only compare Interval types to Interval types") return other < self
[docs] def isdisjoint(self, other): """ Check whether two intervals are disjoint (do not overlap). Returns True if they are disjoint. Note: returns False if intervals endpoints 'meet'. For example [0, 1] meets [1, 2]. """ if not isinstance(other, Interval): raise ValueError("Interval types can only overlap with Interval types") lb = min(self.left, other.left) ub = max(self.right, other.right) return not ((ub - lb < self.length + other.length) or (self.right == other.left) or (other.right == self.left))
[docs]class Intervals(Type): """ Disjoint closed continuous intervals class. Represents a set of continuous, closed intervals of real numbers. Represented by a list of :class:`Interval` types. """ intervals: MutableSequence[Interval] = Property( default=None, doc="Container of :class:`Interval`") def __init__(self, *args, **kwargs): super().__init__(*args, **kwargs) if self.intervals is None: self.intervals = list() elif not isinstance(self.intervals, MutableSequence): if isinstance(self.intervals, (Interval, Tuple)): self.intervals = [self.intervals] else: raise ValueError("Must contain Interval types") elif len(self.intervals) == 2 and all(isinstance(elem, Real) for elem in self.intervals): self.intervals = [self.intervals] for i in range(len(self.intervals)): interval = self.intervals[i] if not isinstance(interval, Interval): if isinstance(interval, Sequence) and len(interval) == 2: self.intervals[i] = Interval(*interval) else: raise ValueError("Individual intervals must be an Interval or Sequence type") self.intervals = self.get_merged_intervals(self.intervals) def __hash__(self): return hash(tuple(self.intervals))
[docs] @staticmethod def overlap(intervals): """ Determine whether a pair of intervals in a list overlap (are not disjoint). Returns a pair of overlapping intervals if there are any, otherwise returns None. """ for int_1, int_2 in combinations(intervals, 2): if not int_1.isdisjoint(int_2): return int_1, int_2 return None
[docs] def isdisjoint(self, other): """ Determine whether all intervals in an :class:`Intervals` type are disjoint from all those in another. """ if not isinstance(other, Intervals): raise ValueError("Can only compare Intervals to Intervals") return all(interval.isdisjoint(other_int) for other_int in other for interval in self)
[docs] @staticmethod def get_merged_intervals(intervals): """Merge all intervals. Ie. combine any intervals that overlap, returning a new list of disjoint intervals.""" new_intervals = copy.copy(intervals) while True: # Continue while there are overlaps try: int_1, int_2 = Intervals.overlap(new_intervals) except TypeError: break else: # Remove overlapping intervals and add their union new_intervals.remove(int_1) new_intervals.remove(int_2) new_intervals.extend(int_1 | int_2) return sorted(new_intervals, key=operator.attrgetter('left'))
def __contains__(self, item): if not isinstance(item, (Real, Interval, Intervals)): return False if isinstance(item, Intervals): return all(any(other_int in interval for interval in self) for other_int in item) return any(item in interval for interval in self) def __str__(self): return str([[interval.left, interval.right] for interval in self]) def __repr__(self): return 'Intervals{intervals}'.format(intervals=str(self)) @property def length(self): return sum(interval.length for interval in self) def _iter(self, reverse): for interval in sorted(self.intervals, key=operator.attrgetter('left'), reverse=reverse): yield interval def __iter__(self): return self._iter(reverse=False) def __reversed__(self): return self._iter(reverse=True) def __eq__(self, other): if isinstance(other, Interval): other = Intervals(other) return isinstance(other, Intervals) and all( any(int1 == int2 for int2 in other) for int1 in self) def __and__(self, other): """Set-like intersection""" if not isinstance(other, (Interval, Intervals)): raise ValueError("Can only intersect with Intervals types") if isinstance(other, Interval): other = Intervals(other) new_intervals = list() for interval in self: for other_interval in other: new_interval = interval & other_interval if new_interval: new_intervals.append(new_interval) new_intervals = self.get_merged_intervals(new_intervals) new_intervals = Intervals(new_intervals) return new_intervals def __or__(self, other): """Set-like union""" if not isinstance(other, (Interval, Intervals)): raise ValueError('Can only union with Intervals types') if isinstance(other, Interval): other = Intervals(other) new_intervals = self.intervals + other.intervals new_intervals = self.get_merged_intervals(new_intervals) new_intervals = Intervals(new_intervals) return new_intervals def __sub__(self, other): """Set-like difference""" if other is None: return self.copy() elif not isinstance(other, (Interval, Intervals)): raise ValueError("Can only subtract Intervals from Intervals") if isinstance(other, Interval): other = Intervals(other) new_intervals = copy.copy(self.intervals) for other_interval in other: temp_intervals = list() for interval in new_intervals: diff = interval - other_interval if diff[0] is not None: temp_intervals.extend(diff) new_intervals = temp_intervals new_intervals = Intervals(new_intervals) return new_intervals def __xor__(self, other): """Set-like symmetric-difference""" if not isinstance(other, (Interval, Intervals)): raise ValueError("Can only compare Intervals from Intervals") if isinstance(other, Interval): other = Intervals(other) return (self | other) - (self & other) def __le__(self, other): """Subset check""" if not isinstance(other, (Interval, Intervals)): raise ValueError("Can only compare Intervals to Intervals") if isinstance(other, Interval): other = Intervals(other) return all(any(interval <= other_int for other_int in other) for interval in self) def __lt__(self, other): """"Proper subset check""" if not isinstance(other, (Interval, Intervals)): raise ValueError("Can only compare Intervals to Intervals") if isinstance(other, Interval): other = Intervals(other) return all(any(interval < other_int for other_int in other) for interval in self) def __ge__(self, other): """Superset check""" if not isinstance(other, (Interval, Intervals)): raise ValueError("Can only compare Intervals to Intervals") if isinstance(other, Interval): other = Intervals(other) return other <= self def __gt__(self, other): """Proper superset check""" if not isinstance(other, (Interval, Intervals)): raise ValueError("Can only compare Intervals to Intervals") if isinstance(other, Interval): other = Intervals(other) return other < self def copy(self): return Intervals(copy.copy(self.intervals)) def __len__(self): return len(self.intervals) def remove(self, elem): if not isinstance(elem, Interval): raise ValueError("Intervals only contain Interval types") try: self.intervals.remove(elem) except ValueError: raise ValueError("Interval not in list") def discard(self, elem): try: self.remove(elem) except ValueError: pass def pop(self): if len(self) == 0: raise KeyError("Contains no intervals") interval = next(iter(self)) self.intervals.remove(interval) return interval def clear(self): self.intervals = list()