<s> from __future__ import absolute_import , print_function , division <EOL> from operator import itemgetter , attrgetter <EOL> from petl . compat import text_type <EOL> from petl . util . base import asindices , records , Table , values , rowgroupby <EOL> from petl . errors import DuplicateKeyError <EOL> from petl . transform . basics import addfield <EOL> from petl . transform . sorts import sort <EOL> def tupletree ( table , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , value = None ) : <EOL> """<STR_LIT>""" <EOL> import intervaltree <EOL> tree = intervaltree . IntervalTree ( ) <EOL> it = iter ( table ) <EOL> hdr = next ( it ) <EOL> flds = list ( map ( text_type , hdr ) ) <EOL> assert start in flds , '<STR_LIT>' <EOL> assert stop in flds , '<STR_LIT>' <EOL> getstart = itemgetter ( flds . index ( start ) ) <EOL> getstop = itemgetter ( flds . index ( stop ) ) <EOL> if value is None : <EOL> getvalue = tuple <EOL> else : <EOL> valueindices = asindices ( hdr , value ) <EOL> assert len ( valueindices ) > <NUM_LIT:0> , '<STR_LIT>' <EOL> getvalue = itemgetter ( * valueindices ) <EOL> for row in it : <EOL> tree . addi ( getstart ( row ) , getstop ( row ) , getvalue ( row ) ) <EOL> return tree <EOL> def facettupletrees ( table , key , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , value = None ) : <EOL> """<STR_LIT>""" <EOL> import intervaltree <EOL> it = iter ( table ) <EOL> hdr = next ( it ) <EOL> flds = list ( map ( text_type , hdr ) ) <EOL> assert start in flds , '<STR_LIT>' <EOL> assert stop in flds , '<STR_LIT>' <EOL> getstart = itemgetter ( flds . index ( start ) ) <EOL> getstop = itemgetter ( flds . index ( stop ) ) <EOL> if value is None : <EOL> getvalue = tuple <EOL> else : <EOL> valueindices = asindices ( hdr , value ) <EOL> assert len ( valueindices ) > <NUM_LIT:0> , '<STR_LIT>' <EOL> getvalue = itemgetter ( * valueindices ) <EOL> keyindices = asindices ( hdr , key ) <EOL> assert len ( keyindices ) > <NUM_LIT:0> , '<STR_LIT>' <EOL> getkey = itemgetter ( * keyindices ) <EOL> trees = dict ( ) <EOL> for row in it : <EOL> k = getkey ( row ) <EOL> if k not in trees : <EOL> trees [ k ] = intervaltree . IntervalTree ( ) <EOL> trees [ k ] . addi ( getstart ( row ) , getstop ( row ) , getvalue ( row ) ) <EOL> return trees <EOL> def recordtree ( table , start = '<STR_LIT:start>' , stop = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> import intervaltree <EOL> getstart = attrgetter ( start ) <EOL> getstop = attrgetter ( stop ) <EOL> tree = intervaltree . IntervalTree ( ) <EOL> for rec in records ( table ) : <EOL> tree . addi ( getstart ( rec ) , getstop ( rec ) , rec ) <EOL> return tree <EOL> def facetrecordtrees ( table , key , start = '<STR_LIT:start>' , stop = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> import intervaltree <EOL> getstart = attrgetter ( start ) <EOL> getstop = attrgetter ( stop ) <EOL> getkey = attrgetter ( key ) <EOL> trees = dict ( ) <EOL> for rec in records ( table ) : <EOL> k = getkey ( rec ) <EOL> if k not in trees : <EOL> trees [ k ] = intervaltree . IntervalTree ( ) <EOL> trees [ k ] . addi ( getstart ( rec ) , getstop ( rec ) , rec ) <EOL> return trees <EOL> def intervallookup ( table , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , value = None , <EOL> include_stop = False ) : <EOL> """<STR_LIT>""" <EOL> tree = tupletree ( table , start = start , stop = stop , value = value ) <EOL> return IntervalTreeLookup ( tree , include_stop = include_stop ) <EOL> Table . intervallookup = intervallookup <EOL> def _search_tree ( tree , start , stop , include_stop ) : <EOL> if stop is None : <EOL> if include_stop : <EOL> stop = start + <NUM_LIT:1> <EOL> start -= <NUM_LIT:1> <EOL> args = ( start , stop ) <EOL> else : <EOL> args = ( start , ) <EOL> else : <EOL> if include_stop : <EOL> stop += <NUM_LIT:1> <EOL> start -= <NUM_LIT:1> <EOL> args = ( start , stop ) <EOL> results = sorted ( tree . search ( * args ) ) <EOL> return results <EOL> class IntervalTreeLookup ( object ) : <EOL> def __init__ ( self , tree , include_stop = False ) : <EOL> self . tree = tree <EOL> self . include_stop = include_stop <EOL> def search ( self , start , stop = None ) : <EOL> results = _search_tree ( self . tree , start , stop , self . include_stop ) <EOL> return [ r . data for r in results ] <EOL> find = search <EOL> def intervallookupone ( table , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , value = None , <EOL> include_stop = False , strict = True ) : <EOL> """<STR_LIT>""" <EOL> tree = tupletree ( table , start = start , stop = stop , value = value ) <EOL> return IntervalTreeLookupOne ( tree , strict = strict , include_stop = include_stop ) <EOL> Table . intervallookupone = intervallookupone <EOL> class IntervalTreeLookupOne ( object ) : <EOL> def __init__ ( self , tree , strict = True , include_stop = False ) : <EOL> self . tree = tree <EOL> self . strict = strict <EOL> self . include_stop = include_stop <EOL> def search ( self , start , stop = None ) : <EOL> results = _search_tree ( self . tree , start , stop , self . include_stop ) <EOL> if len ( results ) == <NUM_LIT:0> : <EOL> return None <EOL> elif len ( results ) > <NUM_LIT:1> and self . strict : <EOL> raise DuplicateKeyError ( ( start , stop ) ) <EOL> else : <EOL> return results [ <NUM_LIT:0> ] . data <EOL> find = search <EOL> def intervalrecordlookup ( table , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , include_stop = False ) : <EOL> """<STR_LIT>""" <EOL> tree = recordtree ( table , start = start , stop = stop ) <EOL> return IntervalTreeLookup ( tree , include_stop = include_stop ) <EOL> Table . intervalrecordlookup = intervalrecordlookup <EOL> def intervalrecordlookupone ( table , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , <EOL> include_stop = False , strict = True ) : <EOL> """<STR_LIT>""" <EOL> tree = recordtree ( table , start = start , stop = stop ) <EOL> return IntervalTreeLookupOne ( tree , include_stop = include_stop , strict = strict ) <EOL> Table . intervalrecordlookupone = intervalrecordlookupone <EOL> def facetintervallookup ( table , key , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , <EOL> value = None , include_stop = False ) : <EOL> """<STR_LIT>""" <EOL> trees = facettupletrees ( table , key , start = start , stop = stop , value = value ) <EOL> out = dict ( ) <EOL> for k in trees : <EOL> out [ k ] = IntervalTreeLookup ( trees [ k ] , include_stop = include_stop ) <EOL> return out <EOL> Table . facetintervallookup = facetintervallookup <EOL> def facetintervallookupone ( table , key , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , <EOL> value = None , include_stop = False , strict = True ) : <EOL> """<STR_LIT>""" <EOL> trees = facettupletrees ( table , key , start = start , stop = stop , value = value ) <EOL> out = dict ( ) <EOL> for k in trees : <EOL> out [ k ] = IntervalTreeLookupOne ( trees [ k ] , include_stop = include_stop , <EOL> strict = strict ) <EOL> return out <EOL> Table . facetintervallookupone = facetintervallookupone <EOL> def facetintervalrecordlookup ( table , key , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , <EOL> include_stop = False ) : <EOL> """<STR_LIT>""" <EOL> trees = facetrecordtrees ( table , key , start = start , stop = stop ) <EOL> out = dict ( ) <EOL> for k in trees : <EOL> out [ k ] = IntervalTreeLookup ( trees [ k ] , include_stop = include_stop ) <EOL> return out <EOL> Table . facetintervalrecordlookup = facetintervalrecordlookup <EOL> def facetintervalrecordlookupone ( table , key , start , stop , include_stop = False , <EOL> strict = True ) : <EOL> """<STR_LIT>""" <EOL> trees = facetrecordtrees ( table , key , start = start , stop = stop ) <EOL> out = dict ( ) <EOL> for k in trees : <EOL> out [ k ] = IntervalTreeLookupOne ( trees [ k ] , include_stop = include_stop , <EOL> strict = strict ) <EOL> return out <EOL> Table . facetintervalrecordlookupone = facetintervalrecordlookupone <EOL> def intervaljoin ( left , right , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , rstart = '<STR_LIT:start>' , <EOL> rstop = '<STR_LIT>' , lkey = None , rkey = None , include_stop = False , <EOL> lprefix = None , rprefix = None ) : <EOL> """<STR_LIT>""" <EOL> assert ( lkey is None ) == ( rkey is None ) , '<STR_LIT>' <EOL> return IntervalJoinView ( left , right , lstart = lstart , lstop = lstop , <EOL> rstart = rstart , rstop = rstop , lkey = lkey , <EOL> rkey = rkey , include_stop = include_stop , <EOL> lprefix = lprefix , rprefix = rprefix ) <EOL> Table . intervaljoin = intervaljoin <EOL> class IntervalJoinView ( Table ) : <EOL> def __init__ ( self , left , right , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , <EOL> rstart = '<STR_LIT:start>' , rstop = '<STR_LIT>' , lkey = None , rkey = None , <EOL> include_stop = False , lprefix = None , rprefix = None ) : <EOL> self . left = left <EOL> self . lstart = lstart <EOL> self . lstop = lstop <EOL> self . lkey = lkey <EOL> self . right = right <EOL> self . rstart = rstart <EOL> self . rstop = rstop <EOL> self . rkey = rkey <EOL> self . include_stop = include_stop <EOL> self . lprefix = lprefix <EOL> self . rprefix = rprefix <EOL> def __iter__ ( self ) : <EOL> return iterintervaljoin ( <EOL> left = self . left , <EOL> right = self . right , <EOL> lstart = self . lstart , <EOL> lstop = self . lstop , <EOL> rstart = self . rstart , <EOL> rstop = self . rstop , <EOL> lkey = self . lkey , <EOL> rkey = self . rkey , <EOL> include_stop = self . include_stop , <EOL> missing = None , <EOL> lprefix = self . lprefix , <EOL> rprefix = self . rprefix , <EOL> leftouter = False <EOL> ) <EOL> def intervalleftjoin ( left , right , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , rstart = '<STR_LIT:start>' , <EOL> rstop = '<STR_LIT>' , lkey = None , rkey = None , include_stop = False , <EOL> missing = None , lprefix = None , rprefix = None ) : <EOL> """<STR_LIT>""" <EOL> assert ( lkey is None ) == ( rkey is None ) , '<STR_LIT>' <EOL> return IntervalLeftJoinView ( left , right , lstart = lstart , lstop = lstop , <EOL> rstart = rstart , rstop = rstop , lkey = lkey , <EOL> rkey = rkey , include_stop = include_stop , <EOL> missing = missing , lprefix = lprefix , <EOL> rprefix = rprefix ) <EOL> Table . intervalleftjoin = intervalleftjoin <EOL> class IntervalLeftJoinView ( Table ) : <EOL> def __init__ ( self , left , right , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , <EOL> rstart = '<STR_LIT:start>' , rstop = '<STR_LIT>' , lkey = None , rkey = None , <EOL> missing = None , include_stop = False , lprefix = None , rprefix = None ) : <EOL> self . left = left <EOL> self . lstart = lstart <EOL> self . lstop = lstop <EOL> self . lkey = lkey <EOL> self . right = right <EOL> self . rstart = rstart <EOL> self . rstop = rstop <EOL> self . rkey = rkey <EOL> self . missing = missing <EOL> self . include_stop = include_stop <EOL> self . lprefix = lprefix <EOL> self . rprefix = rprefix <EOL> def __iter__ ( self ) : <EOL> return iterintervaljoin ( <EOL> left = self . left , <EOL> right = self . right , <EOL> lstart = self . lstart , <EOL> lstop = self . lstop , <EOL> rstart = self . rstart , <EOL> rstop = self . rstop , <EOL> lkey = self . lkey , <EOL> rkey = self . rkey , <EOL> include_stop = self . include_stop , <EOL> missing = self . missing , <EOL> lprefix = self . lprefix , <EOL> rprefix = self . rprefix , <EOL> leftouter = True <EOL> ) <EOL> def intervalantijoin ( left , right , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , rstart = '<STR_LIT:start>' , <EOL> rstop = '<STR_LIT>' , lkey = None , rkey = None , include_stop = False , <EOL> missing = None ) : <EOL> """<STR_LIT>""" <EOL> assert ( lkey is None ) == ( rkey is None ) , '<STR_LIT>' <EOL> return IntervalAntiJoinView ( left , right , lstart = lstart , lstop = lstop , <EOL> rstart = rstart , rstop = rstop , lkey = lkey , <EOL> rkey = rkey , include_stop = include_stop , <EOL> missing = missing ) <EOL> Table . intervalantijoin = intervalantijoin <EOL> class IntervalAntiJoinView ( Table ) : <EOL> def __init__ ( self , left , right , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , <EOL> rstart = '<STR_LIT:start>' , rstop = '<STR_LIT>' , lkey = None , rkey = None , <EOL> missing = None , include_stop = False ) : <EOL> self . left = left <EOL> self . lstart = lstart <EOL> self . lstop = lstop <EOL> self . lkey = lkey <EOL> self . right = right <EOL> self . rstart = rstart <EOL> self . rstop = rstop <EOL> self . rkey = rkey <EOL> self . missing = missing <EOL> self . include_stop = include_stop <EOL> def __iter__ ( self ) : <EOL> return iterintervaljoin ( <EOL> left = self . left , <EOL> right = self . right , <EOL> lstart = self . lstart , <EOL> lstop = self . lstop , <EOL> rstart = self . rstart , <EOL> rstop = self . rstop , <EOL> lkey = self . lkey , <EOL> rkey = self . rkey , <EOL> include_stop = self . include_stop , <EOL> missing = self . missing , <EOL> lprefix = None , <EOL> rprefix = None , <EOL> leftouter = True , <EOL> anti = True <EOL> ) <EOL> def iterintervaljoin ( left , right , lstart , lstop , rstart , rstop , lkey , <EOL> rkey , include_stop , missing , lprefix , rprefix , leftouter , <EOL> anti = False ) : <EOL> lit = iter ( left ) <EOL> lhdr = next ( lit ) <EOL> lflds = list ( map ( text_type , lhdr ) ) <EOL> rit = iter ( right ) <EOL> rhdr = next ( rit ) <EOL> rflds = list ( map ( text_type , rhdr ) ) <EOL> asindices ( lhdr , lstart ) <EOL> asindices ( lhdr , lstop ) <EOL> if lkey is not None : <EOL> asindices ( lhdr , lkey ) <EOL> asindices ( rhdr , rstart ) <EOL> asindices ( rhdr , rstop ) <EOL> if rkey is not None : <EOL> asindices ( rhdr , rkey ) <EOL> if lprefix is None : <EOL> outhdr = list ( lflds ) <EOL> if not anti : <EOL> outhdr . extend ( rflds ) <EOL> else : <EOL> outhdr = list ( lprefix + f for f in lflds ) <EOL> if not anti : <EOL> outhdr . extend ( rprefix + f for f in rflds ) <EOL> yield tuple ( outhdr ) <EOL> getlstart = itemgetter ( lflds . index ( lstart ) ) <EOL> getlstop = itemgetter ( lflds . index ( lstop ) ) <EOL> if rkey is None : <EOL> lookup = intervallookup ( right , rstart , rstop , include_stop = include_stop ) <EOL> search = lookup . search <EOL> for lrow in lit : <EOL> start = getlstart ( lrow ) <EOL> stop = getlstop ( lrow ) <EOL> rrows = search ( start , stop ) <EOL> if rrows : <EOL> if not anti : <EOL> for rrow in rrows : <EOL> outrow = list ( lrow ) <EOL> outrow . extend ( rrow ) <EOL> yield tuple ( outrow ) <EOL> elif leftouter : <EOL> outrow = list ( lrow ) <EOL> if not anti : <EOL> outrow . extend ( [ missing ] * len ( rflds ) ) <EOL> yield tuple ( outrow ) <EOL> else : <EOL> lookup = facetintervallookup ( right , key = rkey , start = rstart , <EOL> stop = rstop , include_stop = include_stop ) <EOL> search = dict ( ) <EOL> for f in lookup : <EOL> search [ f ] = lookup [ f ] . search <EOL> getlkey = itemgetter ( * asindices ( lflds , lkey ) ) <EOL> for lrow in lit : <EOL> lkey = getlkey ( lrow ) <EOL> start = getlstart ( lrow ) <EOL> stop = getlstop ( lrow ) <EOL> try : <EOL> rrows = search [ lkey ] ( start , stop ) <EOL> except KeyError : <EOL> rrows = None <EOL> except AttributeError : <EOL> rrows = None <EOL> if rrows : <EOL> if not anti : <EOL> for rrow in rrows : <EOL> outrow = list ( lrow ) <EOL> outrow . extend ( rrow ) <EOL> yield tuple ( outrow ) <EOL> elif leftouter : <EOL> outrow = list ( lrow ) <EOL> if not anti : <EOL> outrow . extend ( [ missing ] * len ( rflds ) ) <EOL> yield tuple ( outrow ) <EOL> def intervaljoinvalues ( left , right , value , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , <EOL> rstart = '<STR_LIT:start>' , rstop = '<STR_LIT>' , lkey = None , rkey = None , <EOL> include_stop = False ) : <EOL> """<STR_LIT>""" <EOL> assert ( lkey is None ) == ( rkey is None ) , '<STR_LIT>' <EOL> if lkey is None : <EOL> lkp = intervallookup ( right , start = rstart , stop = rstop , value = value , <EOL> include_stop = include_stop ) <EOL> f = lambda row : lkp . search ( row [ lstart ] , row [ lstop ] ) <EOL> else : <EOL> lkp = facetintervallookup ( right , rkey , start = rstart , stop = rstop , <EOL> value = value , include_stop = include_stop ) <EOL> f = lambda row : lkp [ row [ lkey ] ] . search ( row [ lstart ] , row [ lstop ] ) <EOL> return addfield ( left , value , f ) <EOL> Table . intervaljoinvalues = intervaljoinvalues <EOL> def intervalsubtract ( left , right , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , rstart = '<STR_LIT:start>' , <EOL> rstop = '<STR_LIT>' , lkey = None , rkey = None , include_stop = False ) : <EOL> """<STR_LIT>""" <EOL> assert ( lkey is None ) == ( rkey is None ) , '<STR_LIT>' <EOL> return IntervalSubtractView ( left , right , lstart = lstart , lstop = lstop , <EOL> rstart = rstart , rstop = rstop , lkey = lkey , <EOL> rkey = rkey , include_stop = include_stop ) <EOL> Table . intervalsubtract = intervalsubtract <EOL> class IntervalSubtractView ( Table ) : <EOL> def __init__ ( self , left , right , lstart = '<STR_LIT:start>' , lstop = '<STR_LIT>' , <EOL> rstart = '<STR_LIT:start>' , rstop = '<STR_LIT>' , lkey = None , rkey = None , <EOL> include_stop = False ) : <EOL> self . left = left <EOL> self . lstart = lstart <EOL> self . lstop = lstop <EOL> self . lkey = lkey <EOL> self . right = right <EOL> self . rstart = rstart <EOL> self . rstop = rstop <EOL> self . rkey = rkey <EOL> self . include_stop = include_stop <EOL> def __iter__ ( self ) : <EOL> return iterintervalsubtract ( self . left , self . right , self . lstart , <EOL> self . lstop , self . rstart , self . rstop , <EOL> self . lkey , self . rkey , self . include_stop ) <EOL> def iterintervalsubtract ( left , right , lstart , lstop , rstart , rstop , lkey , rkey , <EOL> include_stop ) : <EOL> lit = iter ( left ) <EOL> lhdr = next ( lit ) <EOL> lflds = list ( map ( text_type , lhdr ) ) <EOL> rit = iter ( right ) <EOL> rhdr = next ( rit ) <EOL> asindices ( lhdr , lstart ) <EOL> asindices ( lhdr , lstop ) <EOL> if lkey is not None : <EOL> asindices ( lhdr , lkey ) <EOL> asindices ( rhdr , rstart ) <EOL> asindices ( rhdr , rstop ) <EOL> if rkey is not None : <EOL> asindices ( rhdr , rkey ) <EOL> outhdr = list ( lflds ) <EOL> yield tuple ( outhdr ) <EOL> lstartidx , lstopidx = asindices ( lhdr , ( lstart , lstop ) ) <EOL> getlcoords = itemgetter ( lstartidx , lstopidx ) <EOL> getrcoords = itemgetter ( * asindices ( rhdr , ( rstart , rstop ) ) ) <EOL> if rkey is None : <EOL> lookup = intervallookup ( right , rstart , rstop , include_stop = include_stop ) <EOL> search = lookup . search <EOL> for lrow in lit : <EOL> start , stop = getlcoords ( lrow ) <EOL> rrows = search ( start , stop ) <EOL> if not rrows : <EOL> yield tuple ( lrow ) <EOL> else : <EOL> rivs = sorted ( [ getrcoords ( rrow ) for rrow in rrows ] , <EOL> key = itemgetter ( <NUM_LIT:0> ) ) <EOL> for x , y in _subtract ( start , stop , rivs ) : <EOL> out = list ( lrow ) <EOL> out [ lstartidx ] = x <EOL> out [ lstopidx ] = y <EOL> yield tuple ( out ) <EOL> else : <EOL> lookup = facetintervallookup ( right , key = rkey , start = rstart , stop = rstop , <EOL> include_stop = include_stop ) <EOL> getlkey = itemgetter ( * asindices ( lhdr , lkey ) ) <EOL> for lrow in lit : <EOL> lkey = getlkey ( lrow ) <EOL> start , stop = getlcoords ( lrow ) <EOL> try : <EOL> rrows = lookup [ lkey ] . search ( start , stop ) <EOL> except KeyError : <EOL> rrows = None <EOL> except AttributeError : <EOL> rrows = None <EOL> if not rrows : <EOL> yield tuple ( lrow ) <EOL> else : <EOL> rivs = sorted ( [ getrcoords ( rrow ) for rrow in rrows ] , <EOL> key = itemgetter ( <NUM_LIT:0> ) ) <EOL> for x , y in _subtract ( start , stop , rivs ) : <EOL> out = list ( lrow ) <EOL> out [ lstartidx ] = x <EOL> out [ lstopidx ] = y <EOL> yield tuple ( out ) <EOL> from collections import namedtuple <EOL> _Interval = namedtuple ( '<STR_LIT>' , '<STR_LIT>' ) <EOL> def collapsedintervals ( table , start = '<STR_LIT:start>' , stop = '<STR_LIT>' , key = None ) : <EOL> """<STR_LIT>""" <EOL> if key is None : <EOL> table = sort ( table , key = start ) <EOL> for iv in _collapse ( values ( table , ( start , stop ) ) ) : <EOL> yield iv <EOL> else : <EOL> table = sort ( table , key = ( key , start ) ) <EOL> for k , g in rowgroupby ( table , key = key , value = ( start , stop ) ) : <EOL> for iv in _collapse ( g ) : <EOL> yield ( k , ) + iv <EOL> Table . collapsedintervals = collapsedintervals <EOL> def _collapse ( intervals ) : <EOL> """<STR_LIT>""" <EOL> span = None <EOL> for start , stop in intervals : <EOL> if span is None : <EOL> span = _Interval ( start , stop ) <EOL> elif start <= span . stop < stop : <EOL> span = _Interval ( span . start , stop ) <EOL> elif start > span . stop : <EOL> yield span <EOL> span = _Interval ( start , stop ) <EOL> if span is not None : <EOL> yield span <EOL> def _subtract ( start , stop , intervals ) : <EOL> """<STR_LIT>""" <EOL> remainder_start = start <EOL> sub_stop = None <EOL> for sub_start , sub_stop in _collapse ( intervals ) : <EOL> if remainder_start < sub_start : <EOL> yield _Interval ( remainder_start , sub_start ) <EOL> remainder_start = sub_stop <EOL> if sub_stop is not None and sub_stop < stop : <EOL> yield _Interval ( sub_stop , stop ) </s>
