h$0.      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLM>Closed intervals of totally ordered types, e.g. time intervals(c) Lackmann PhymetricGPL-3olaf.klinke@phymetric.de experimental Safe-Inferred>?.25closed-intervalsSearch tree of intervals.closed-intervals/class of Intervals whose bounds can be adjustedclosed-intervals!Time types supporting differencesclosed-intervalsclass of search structures for interval intersection queries, returning a N of intervals.closed-intervals%all intervalls touching the first one closed-intervals1all intervals properly intersecting the first one closed-intervals&does any interval touch the first one? closed-intervals3does any interval properly intersect the first one? closed-intervalsthe convex hull of the contents closed-intervals overlapTime i i == intervalDuration igenInterval /\* \i j -> not (i `properlyIntersects` j) ==> overlapTime i j == 0genInterval /\* \i j -> overlapTime i j == (sum $ fmap intervalDuration $ maybeIntersection i j)closed-intervals0Prevailing annotation in the first time intervalgenInterval /\ \i c -> prevailing i (Seq.singleton (c,i)) == Just (c::Char)genInterval /\ \i -> genLabeledSeq /\ \js -> isJust (prevailing i js) == any (intersects i . snd) jsgenInterval /\ \i -> genLabeledSeq /\* \js ks -> all (flip elem $ catMaybes [prevailing i js, prevailing i ks]) $ prevailing i (js<>ks)closed-intervals isJust (maybeUnion i j) ==> fromJust (maybeUnion i j) `contains` i && fromJust (maybeUnion i j) `contains` jgenInterval /\* \i j -> i `intersects` j ==> (maybeUnion i j >>= maybeIntersection i) == Just iclosed-intervalsthe intersection of two intervals is either empty or an interval.genInterval /\* \i j -> i `intersects` j ==> i `contains` fromJust (maybeIntersection i j)closed-intervals convex hull\xs -> isJust (hull xs) ==> all (\x -> fromJust (hull xs) `contains` x) (xs :: [(Int,Int)])closed-intervalsSet difference. The resulting list has zero, one or two elements.without' (1,5) (4,5)[(1,4)]without' (1,5) (2,3) [(1,2),(3,5)]without' (1,5) (1,5)[]without' (1,5) (0,1)[(1,5)]3genInterval /\* \i j -> length (i `without` j) <= 2(genInterval /\ \i -> i `without` i == []8genInterval /\* \i j -> all (contains i) (i `without` j)genInterval /\* \i j -> not $ any (properlyIntersects j) (i `without` j)closed-intervals  is not an equivalence relation, because it is not transitive. Hence groupBy   does not do what one might expect. This function does the expected and groups overlapping intervals into contiguous blocks.genSortedIntervals /\ all (\xs -> and $ List.zipWith intersects xs (tail xs)) . contiguousclosed-intervals)Connected components of a list sorted by % , akin to groupBy  #. The precondition is not checked.genSortedIntervals /\ \xs -> all (\i -> any (flip contains i) (components xs)) xsclosed-intervalssame as . Is there a way to unify both?genSortedIntervals /\ \xs -> componentsSeq (Seq.fromList xs) == Seq.fromList (components xs)closed-intervals&compute the components of the part of i covered by the intervals.genInterval /\ \i -> genIntervalSeq /\ \js -> all (contains i) (covered i js)genInterval /\ \i -> genIntervalSeq /\ \js -> covered i (covered i js) == covered i jsclosed-intervalsO if the first interval is completely covered by the given intervals;genInterval /\* \i j -> j `contains` i == i `coveredBy` [j]genInterval /\ \i -> genSortedIntervals /\ \js -> i `coveredBy` js ==> any (flip contains i) (components js)closed-intervalspercentage of coverage of the first interval by the second sequence of intervalsgenNonEmptyInterval /\ \i -> genIntervalSeq /\ \js -> i `coveredBy` js == (fractionCovered i js >= (1::Rational))genNonEmptyInterval /\ \i -> genNonEmptyIntervalSeq /\ \js -> any (properlyIntersects i) js == (fractionCovered i js > (0::Rational))closed-intervalsOverlap ordering. Returns P or Q! if the intervals are disjoint, R if the intervals overlap. Note that this violates the following property:  x y == R &&  y z == R =>  x z == R i.e.,  is not transitive.genInterval /\* \i j -> i `intersects` j == (overlap i j == EQ)closed-intervalsOverlap ordering. Returns P or Q if the intervals are disjoint or touch in end point(s) only, R if the intervals properly overlap. Note that this violates the following property:  x y == R &&  y z == R =>  x z == R i.e.,  is not transitive.genInterval /\* \i j -> i `properlyIntersects` j == (properOverlap i j == EQ) closed-intervalsintersection query.2((1,2)::(Int,Int)) `intersects` ((2,3)::(Int,Int))TruegenInterval /\* \i j -> (lb i <= ub i && lb j <= ub j && i `intersects` j) == (max (lb i) (lb j) <= min (ub i) (ub j))!closed-intervalsproper intersection.genInterval /\* \i j -> ((i `intersects` j) && not (i `properlyIntersects` j)) == (ub i == lb j || ub j == lb i)"closed-intervalssubset containment#genInterval /\ \i -> i `contains` igenInterval /\* \i j -> (i `contains` j && j `contains` i) == (i==j)genInterval /\* \i j -> i `contains` j == (maybeUnion i j == Just i)#closed-intervalsproper subset containment$closed-intervalsconstruct a sorted sequence of intervals from a sorted sequence of bounds. Fails if the input sequence is not sorted.genSortedList /\ \xs -> (components $ toList $ fromEndPoints xs) == if length xs < 2 then [] else [(head xs, last xs)]%closed-intervalslexicographical sort by , then inverse . In the resulting list, the intervals intersecting a given interval form a contiguous sublist.genInterval /\ \i -> genSortedIntervalSeq /\ \js -> toList (getIntersects i js) `List.isSubsequenceOf` toList js&closed-intervals/extract all intervals intersecting a given one.'closed-intervals8extract all intervals properly intersecting a given one.(closed-intervalsconvex hull of a sorted sequence of intervals. the lower bound is guaranteed to be in the leftmost interval, but we have no guarantee of the upper bound.=genSortedIntervalSeq /\ \xs -> hullSeq xs == hull (toList xs))closed-intervalsWhen you face the problem of matching two series of intervals against each other, a streaming approach might be more efficient than transforming one of the streams into a search structure. This function drops intervals from the list until the (contiguous, see %) block of intersecting intervals is found. This block (except intervals containing the  of the query) is removed from the stream. When used as a state transformer on a stream [i] of non-properly overlapping intervals, then one obtains the stream of blocks intersecting the stream of queries. splitIntersecting ((2,5) :: (Int,Int)) ([(0,1),(2,3),(2,2),(3,6),(6,7)] :: [(Int,Int)])#([(2,3),(2,2),(3,6)],[(3,6),(6,7)])genInterval /\ \i -> genSortedIntervals /\ \js -> fst (splitIntersecting i js) == filter (intersects i) jsgenInterval /\ \i -> genSortedIntervals /\ \js -> all (\j -> not (ub j < ub i)) (snd (splitIntersecting i js))*closed-intervalsLike ) but disregards those intervals that merely touch the query. Retains overlapping intervals properly containing the  of the query. When used as a state transformer on an ascending stream [i] of non-properly overlapping intervals, then one obtains the stream of blocks properly intersecting the stream of queries.splitProperlyIntersecting ((2,5) :: (Int,Int)) ([(0,1),(2,3),(2,2),(3,5),(5,6),(6,7)] :: [(Int,Int)])([(2,3),(3,5)],[(5,6),(6,7)])genInterval /\ \i -> genSortedIntervals /\ \js -> fst (splitProperlyIntersecting i js) == filter (properlyIntersects i) jsgenInterval /\ \i -> genSortedIntervals /\ \js -> all (not.contains i) (snd (splitProperlyIntersecting i js))+closed-intervals the empty ,closed-intervals,smallest interval covering the entire tree. S if the tree is empty.-closed-intervals:invariant to be maintained for proper intersection queriesinvariant . itree 4 . fmap (\(x,y) -> (x, x + QC.getNonNegative y :: Integer)).closed-intervals.Intersection query. O(binsize+log(n/binsize)).genInterval /\ \i -> genIntervalSeq /\ \t -> on (==) sortByLeft (getIntersectsIT i $ itree 2 t) (i `intersecting` t)/closed-intervals.Intersection query. O(binsize+log(n/binsize)).genInterval /\ \i -> genIntervalSeq /\ \t -> on (==) sortByLeft (getProperIntersectsIT i $ itree 2 t) (i `intersectingProperly` t)0closed-intervalsWhen the actual result of .9 is not important, only whether there are intersections.1closed-intervalsWhen the actual result of .9 is not important, only whether there are intersections.2closed-intervals2retrieve the left-most interval from the tree, or S if it is empty.3closed-intervals2transform the interval tree into the tree of hulls4closed-intervals!generalises Control.Monad.filterM6closed-intervalsSplit a Sequence in half, needed for the IntersectionQuery instances. prop> genIntervalSeq / is -> joinSeq (splitSeq is) == is7closed-intervalsinsert the interval at the deepest possible location into the tree. Does not change the overall structure, in particular no re-balancing is performed.8closed-intervalsConstruct an interval tree with bins of maximal given size. The function first sorts the intervals, then splits into chunks of given size. The leftmost endpoints of the chunks define boundary points. Next, all intervals properly overlapping a boundary are removed from the chunks and kept separately. The chunks are arranged as the leaves of a binary search tree. Then the intervals overlapping boundaries are placed at internal nodes of the tree. Hence if all intervals are mutually non-overlapping properly, the resulting tree is a pure binary search tree with bins of given size as leaves.9closed-intervalsO(log n)- bounds of an ordered sequence of intervals. S , if empty.genDisjointIntervalSeq /\ \xs -> hullSeqNonOverlap xs == hullSeq xs:closed-intervalsQuery an ordered T4uence of non-overlapping intervals for a predicate p that has the property j " k && p i k ==> p i j 1and return all elements satisfying the predicate.genInterval /\ \i -> genDisjointIntervalSeq /\ \js -> findSeq intersects i js == intersecting i js;closed-intervalsQuery an ordered T4uence of non-overlapping intervals for a predicate p that has the property j " k && p i k ==> p i j ?closed-intervals preserves the TimeZoneclosed-intervalsadjust lower and upper boundclosed-intervals*change both bounds using the same functionclosed-intervals lower boundclosed-intervals upper boundclosed-intervalsend points (inclusive)<  !"#$%&'()*+,-./0123456789:;<   !"#(%$)*8+7,&./012:;9-3'456 Safe-Inferred.UVWXYZ[\      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVTUWTUXTUYQZ[\]^_`abcdef/closed-intervals-0.1.1.0-Ey3clpgYCjh2Pjz0xGBuxW Data.IntervalPaths_closed_intervalsITreeAdjust adjustBoundsshiftTimeDifferencediffTimeaddTimeIntersectionQuery getIntersectsgetProperIntersectssomeIntersectssomeProperlyIntersects maybeBoundsIntervallbub endPointsintervalDuration overlapTime prevailing maybeUnionmaybeIntersectionhullwithout contiguous components componentsSeqcovered coveredByfractionCoveredoverlap properOverlap intersectsproperlyIntersectscontainsproperlyContains fromEndPoints sortByLeft intersectingintersectingProperlyhullSeqsplitIntersectingsplitProperlyIntersecting emptyITree hullOfTree invariantgetIntersectsITgetProperIntersectsITsomeIntersectsITsomeProperlyIntersectsITleftmostIntervaltoTreefilterMjoinSeqsplitSeqinsertitreehullSeqNonOverlapfindSeq existsSeq$fIntervaleIdentity$fIntervale(,)$fIntersectionQuerySeqeSeq$fTimeDifferenceZonedTime$fTimeDifferenceLocalTime$fTimeDifferenceUTCTime $fAdjuste(,)$fFoldableITree$fFunctorITree$fIntersectionQueryITreeeSeq $fShowBlock $fMonoidBlock$fSemigroupBlock$fFoldableBlock$fFunctorBlock $fOrdBlock $fEqBlock$fShowSplitSeqbase Data.FoldableFoldableghc-prim GHC.TypesTrueLTGTEQ GHC.MaybeNothingcontainers-0.6.2.1Data.Sequence.InternalSeqversion getBinDir getLibDir getDynLibDir getDataDir getLibexecDir getSysconfDirgetDataFileName