overlapping_ranges.py

def _overlapping_ranges_iter(iter1, iter2, *, include_empty=False, range_getter=None):
    """Iterates over two iterables of ranges and returns a iterator over all 
    ranges with their common values.
    
    Input: two sorted iterators that have a sortable start end
    Output: iterator of tuples of the form (start, end, val1|None, val2|None)
    
    By default, range_getter gets its start from val[0] and end from val[1], but
    may be replaced with any method that takes a value and returns a 2-tuple of 
    start, end.
    
    Example: in1: (1, 2)
                  (2, 4)   
             in2: (0, 5)
             out: (0, 1, None,   (0, 5))
                  (1, 2, (1, 2), (0, 5)),
                  (2, 4, (2, 4), (0, 5)),
                  (4, 5, None,   (0, 5))
                  
    If include_empty is True, this will also include s, e, None, None values
    between the different ranges.
    """
    
    if range_getter is None:
        range_getter = lambda v: (v[0], v[1])
    
    iter1 = iter(iter1)
    iter2 = iter(iter2)
    
    def _next(i):  # formats the next of the iterable properly
        v = next(i, None)
        if v is None:
            return v
        start, end = range_getter(v)
        return start, end, v
    def _yield_empty(prev_end, *next_starts):  # yields empty row if necessary
        try:
            next_start = min((x[0] for x in next_starts if x is not None))
        except ValueError:  # no valid iterables
            return
        else:
            if include_empty and next_start > prev_end:
                yield prev_end, next_start, None, None
                
    v1 = _next(iter1)
    v2 = _next(iter2)
    
    while True:
        if v1 is None and v2 is None:  # both iterators are exhausted
            break
            
        elif v1 is None:  # iter1 is exhausted
            yield v2[0], v2[1], None, v2[2]
            old_end, v2 = v2[1], _next(iter2)
            yield from _yield_empty(old_end, v2)
            
        elif v2 is None:  # iter2 is exhausted
            yield v1[0], v1[1], v1[2], None
            old_end, v1 = v1[1], _next(iter1)
            yield from _yield_empty(old_end, v1)
            
        elif v1[0:2] == v2[0:2]:  # v1 and v2 are the same
            yield v1[0], v1[1], v1[2], v2[2]
            old_end, v1, v2 = v1[1], _next(iter1), _next(iter2)
            yield from _yield_empty(old_end, v1, v2)
            
        elif v1[1] <= v2[0]:  # v1 is entirely before v2
            yield v1[0], v1[1], v1[2], None
            old_end, v1 = v1[1], _next(iter1)
            yield from _yield_empty(old_end, v1, v2)
            
        elif v2[1] <= v1[0]:  # v2 is entirely before v1
            yield v2[0], v2[1], None, v2[2]
            old_end, v2 = v2[1], _next(iter2)
            yield from _yield_empty(old_end, v2, v1)
            
        elif v1[0] < v2[0]:  # v1 starts before v2
            yield v1[0], v2[0], v1[2], None
            v1 = v2[0], v1[1], v1[2]
            
        elif v2[0] < v1[0]:  # v2 starts before v1
            yield v2[0], v1[0], None, v2[2]
            v2 = v1[0], v2[1], v2[2]
            
        elif v1[0] == v2[0] and v1[1] < v2[1]:  # v1 is v2 start, but v1 ends first
            yield v1[0], v1[1], v1[2], v2[2]
            v2 = v1[1], v2[1], v2[2]
            v1 = _next(iter1)
            
        elif v1[0] == v2[0] and v2[1] < v1[1]:  # v1 is v2 start, but v2 ends first
            yield v1[0], v2[1], v1[2], v2[2]
            v1 = v2[1], v1[1], v1[2]
            v2 = _next(iter2)
        
        else:
            raise RuntimeError("Unknown state", v1, v2)
            
def overlapping_ranges_iter(*iters, **kwargs):
    """Makes _ranges_iter suitable for any number of iterators.
    Note: for two iterators, this is the same als _ranges_iter
    """
    if not iters:
        return
    elif len(iters) == 1:
        yield from (x[:3] for x in _overlapping_ranges_iter(iters[0], [], **kwargs))
    else:
        result = _overlapping_ranges_iter(*iters[:2], **kwargs)
        for i in iters[2:]:
            result = ((s, e) + v1[2:] + (v2, ) for s, e, v1, v2 in _overlapping_ranges_iter(result, i, **kwargs))
        yield from result