h&EC       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcd>Closed intervals of totally ordered types, e.g. time intervals(c) Lackmann PhymetricGPL-3olaf.klinke@phymetric.de experimental Safe-Inferred 89::;eclosed-intervalsThe result of 6, either the empty sequence, a singleton or two subsequences of roughly the same sizeclosed-intervalsSearch tree of intervals.closed-intervals/class of Intervals whose bounds can be adjustedclosed-intervals!Time types supporting differencesclosed-intervalsfuences support   efficiently only in the case when the sequence has the property that for any split  xs = ys <> zs< into non-empty parts the convex hull of each part is the  and  of the leftmost and rightmost element, respectively. This property is guaranteed by ( but does not hold in the case where the sequence contains nested intervals:propSplit (\xs -> hullSeqNonNested xs == hullSeq xs) . splitSeq . sortByRight $ Seq.fromList ([(1,3),(2,4),(4,5),(3,6)] :: [(Int,Int)])FalseThus, when querying against a set of intervals with nesting, you must use an  instead. Observe that non-nestedness is a quite strong property. The logical negation of the sentence 8there exist intervals i, j such that i is contained in j is for all i, j either  lb i < lb j or  ub i > ub j . But if  lb i < lb j then also  ub i < ub j- because otherwise i contains j. Likewise,  ub i > ub j implies  lb i > lb j otherwise i contains j. Hence a non-nested sequence of intervals can be sorted by either left of right end-point resulting in the same order. forevery genNonNestedIntervalSeq $ \xs -> propSplit (\subseq -> hullSeqNonNested subseq == hullSeq subseq) (splitSeq xs) closed-intervalsclass of search structures for interval intersection queries, returning a g 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 contentsclosed-intervals*dump the entire search structure's contentclosed-intervals overlapTime i i == intervalDuration iforeveryPair genInterval $ \i j -> not (i `properlyIntersects` j) ==> overlapTime i j == 0foreveryPair genInterval $ \i j -> overlapTime i j == (sum $ fmap intervalDuration $ maybeIntersection i j)closed-intervals0Prevailing annotation in the first time intervalforevery genInterval $ \i c -> prevailing i (Seq.singleton (c,i)) == Just (c::Char)foreveryPairOf genInterval genLabeledSeq $ \i js -> isJust (prevailing i js) == any (intersects i . snd) jsforevery genInterval $ \i -> foreveryPair 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` jforeveryPair genInterval $ \i j -> i `intersects` j ==> (maybeUnion i j >>= maybeIntersection i) == Just iclosed-intervalsthe intersection of two intervals is either empty or an interval.foreveryPair genInterval $ \i j -> i `intersects` j ==> i `contains` fromJust (maybeIntersection i j)closed-intervalsO(n) 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)]>foreveryPair genInterval $ \i j -> length (i `without` j) <= 24forevery genInterval $ \i -> i `without` i == []foreveryPair genInterval $ \i j -> all (contains i) (i `without` j)foreveryPair 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.forevery genSortedIntervals $ all (\xs -> and $ List.zipWith intersects xs (tail xs)) . contiguousforevery genSortedIntervals $ all ((1==).length.components) . contiguousclosed-intervals)Connected components of a list sorted by ) , akin to groupBy $#. The precondition is not checked.forevery genSortedIntervals $ \xs -> all (\i -> any (flip contains i) (components xs)) xsforevery genSortedIntervals $ \xs -> let cs = components xs in all (\(i,j) -> i == j || not (i `intersects` j)) [(c1,c2) | c1 <- cs, c2 <- cs]closed-intervalssame as . Is there a way to unify both?forevery genSortedIntervals $ \xs -> componentsSeq (Seq.fromList xs) == Seq.fromList (components xs)forevery genSortedIntervalSeq $ \xs -> let cs = componentsSeq xs in all (\(i,j) -> i == j || not (i `intersects` j)) $ do {c1 <- cs; c2 <- cs; return (c1,c2)}closed-intervals&compute the components of the part of i covered by the intervals.foreveryPairOf genInterval genIntervalSeq $ \i js -> all (contains i) (covered i js)foreveryPairOf genInterval genIntervalSeq $ \i js -> covered i (covered i js) == covered i js closed-intervalsh if the first interval is completely covered by the given intervalsforeveryPair genInterval $ \i j -> j `contains` i == i `coveredBy` [j]foreveryPairOf genInterval genSortedIntervals $ \i js -> i `coveredBy` js ==> any (flip contains i) (components js)!closed-intervalspercentage of coverage of the first interval by the second sequence of intervalsforeveryPairOf genNonEmptyInterval genIntervalSeq $ \i js -> i `coveredBy` js == (fractionCovered i js >= (1::Rational))foreveryPairOf genNonEmptyInterval genNonEmptyIntervalSeq $ \i js -> any (properlyIntersects i) js == (fractionCovered i js > (0::Rational))"closed-intervalsOverlap ordering. Returns i or j! if the intervals are disjoint, k if the intervals overlap. Note that this violates the following property: " x y == k && " y z == k => " x z == k i.e., " is not transitive.foreveryPair genInterval $ \i j -> i `intersects` j == (overlap i j == EQ)#closed-intervalsOverlap ordering. Returns i or j if the intervals are disjoint or touch in end point(s) only, k if the intervals properly overlap. Note that this violates the following property: # x y == k && # y z == k => # x z == k i.e., # is not transitive.foreveryPair genInterval $ \i j -> i `properlyIntersects` j == (properOverlap i j == EQ)$closed-intervalsintersection query.2((1,2)::(Int,Int)) `intersects` ((2,3)::(Int,Int))TrueforeveryPair genInterval $ \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.foreveryPair genInterval $ \i j -> ((i `intersects` j) && not (i `properlyIntersects` j)) == (ub i == lb j || ub j == lb i)&closed-intervalssubset containment/forevery genInterval $ \i -> i `contains` iforeveryPair genInterval $ \i j -> (i `contains` j && j `contains` i) == (i==j)foreveryPair 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.forevery genSortedList $ \xs -> (components $ toList $ fromEndPoints xs) == if length xs < 2 then [] else [(head xs, last xs)]forevery genSortedList $ \xs -> hullSeqNonNested (fromEndPoints xs) == if length xs < 2 then Nothing else Just (head xs,last xs))closed-intervalslexicographical sort by , then inverse . If the sequence of intervals is non-nested, then in the resulting list the intervals intersecting a given interval form a contiguous sublist.foreveryPairOf genInterval genNonNestedIntervalSeq $ \i js -> toList (getIntersects i (FromSortedSeq js)) `isSubsequenceOf` toList jsforevery genSortedIntervalSeq $ \xs -> propSplit (\subseq -> subseq == sortByRight subseq) (splitSeq xs)*closed-intervalsO(n)0 Extract all intervals intersecting a given one.+closed-intervalsO(n)9 Extract all intervals properly intersecting a given one.,closed-intervalsO(n) convex hull of a sorted ()) sequence of intervals. the upper bound is guaranteed to be in the rightmost interval, but we have no guarantee of the lower bound.forevery genSortedIntervalSeq $ \xs -> hullSeq xs == if Seq.null xs then Nothing else Just (minimum (fmap lb xs),maximum (fmap ub xs))forevery 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) 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,2),(2,3),(3,6),(6,7)] :: [(Int,Int)])#([(2,2),(2,3),(3,6)],[(3,6),(6,7)])foreveryPairOf genInterval genNonNestedIntervalSeq $ \i js' -> let js = toList js' in fst (splitIntersecting i js) == filter (intersects i) jsforeveryPairOf genInterval genNonNestedIntervalSeq $ \i js' -> let js = toList js' in 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)])foreveryPairOf genInterval genNonNestedIntervalSeq $ \i js' -> let js = toList js' in fst (splitProperlyIntersecting i js) == filter (properlyIntersects i) jsforeveryPairOf genInterval genNonNestedIntervalSeq $ \i js' -> let js = toList js' in all (not.properlyContains i) (snd (splitProperlyIntersecting i js))/closed-intervals the empty 0closed-intervals,smallest interval covering the entire tree. l if the tree is empty.forevery genSortedIntervalSeq $ \xs -> hullSeq xs == hullOfTree (itree 4 xs)1closed-intervals:invariant to be maintained for proper intersection queries9forevery genIntervalSeq $ \xs -> invariant . itree 4 $ xsmclosed-intervals.Intersection query. O(binsize+log(n/binsize)).foreveryPairOf genInterval genIntervalSeq $ \i t -> on (==) sortByRight (getIntersects i $ itree 2 t) (i `intersecting` t)nclosed-intervals.Intersection query. O(binsize+log(n/binsize)).foreveryPairOf genInterval genIntervalSeq $ \i t -> on (==) sortByRight (getProperIntersects i $ itree 2 t) (i `intersectingProperly` t)oclosed-intervalsWhen the actual result of m9 is not important, only whether there are intersections.pclosed-intervalsWhen the actual result of m9 is not important, only whether there are intersections.2closed-intervals2transform the interval tree into the tree of hulls3closed-intervals!generalises Control.Monad.filterM4closed-intervals#re-assemble a split into a sequence5closed-intervalstest if a sequence property holds for each sequence in the split.6closed-intervals)Split a Sequence in half, needed for the   instance. prop> forevery 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(1)9 bounds of an ordered, non-nested sequence of intervals. l , if empty.forevery genNonNestedIntervalSeq $ \xs -> hullSeqNonNested xs == hullSeq xsqclosed-intervalsQuery an ordered f/uence of non-nested intervals for a predicate p that has the property j & k && p i k ==> p i j 1and return all elements satisfying the predicate.foreveryPairOf genInterval genNonNestedIntervalSeq $ \i js -> getIntersects i (FromSortedSeq js) == intersecting i jsrclosed-intervalsQuery an ordered f/uence of non-nested intervals for a predicate p that has the property j & k && p i k ==> p i j =closed-intervalsBeware that using >>= may destroy non-nestedness.>closed-intervalsBeware that using  * may destroy non-nestedness.Cclosed-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:  $%&' "#!,9)(-.8/7012*+3456%Closed intervals on the UTC time axis(c) Lackmann PhymetricGPL-3olaf.klinke@phymetric.de experimental Safe-Inferred )*1B Yclosed-intervals.Time intervals comprising quarter of an hour. Zclosed-intervalsTime intervals of length 10 minutes. In logging applications, aggregate values (e.g. averages, sums, ...) are often taken over a period of 10 minutes and associated with the time when the aggregation was computed. To create your custom aggregate data type, pair this time interval with the aggregate value, like follows. data SumOver10Minutes s = Aggregate { aggregateValue :: s, aggregatedOver :: Min10 } instance Interval UTCTime (SumOver10Minutes s) where lb = lb.aggregatedOver ub = ub.aggregatedOver compositeAggregate :: (Interval UTCTime i, Monoid s, Foldable f, IntersectionQuery f UTCTime t) => i -> t (SumOver10Minutes s) -> s compositeAggregate i = foldMap aggregateValue . getProperIntersects i [closed-intervalsClosed time intervals of statically known length in minutes. Although such intervals are completely determined by the end time of type s/ that was used for construction, we cache  and  als lazy fields of type t to speed up  queries. \closed-intervals?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrpqspqtpqumvwxyz{|}~~~/closed-intervals-0.2.1.0-Ex32lVqviHOJ0OTGNsnvUQ Data.IntervalData.Interval.TimePaths_closed_intervalsITreeAdjust adjustBoundsshiftTimeDifferencediffTimeaddTime NonNestedSeq FromSortedSeqgetSeqIntersectionQuery getIntersectsgetProperIntersectssomeIntersectssomeProperlyIntersects maybeBoundsstoredIntervalsIntervallbub endPointsintervalDuration overlapTime prevailing maybeUnionmaybeIntersectionhullwithout contiguous components componentsSeqcovered coveredByfractionCoveredoverlap properOverlap intersectsproperlyIntersectscontainsproperlyContains fromEndPoints sortByRight intersectingintersectingProperlyhullSeqsplitIntersectingsplitProperlyIntersecting emptyITree hullOfTree invarianttoTreefilterMjoinSeq propSplitsplitSeqinsertitreehullSeqNonNested$fIntervaleIdentity$fIntervale(,)$fFiltrableNonNestedSeq$fMonadNonNestedSeq$fAlternativeNonNestedSeq$fApplicativeNonNestedSeq$fMonoidNonNestedSeq$fSemigroupNonNestedSeq#$fIntersectionQueryNonNestedSeqeSeq$fTimeDifferenceZonedTime$fTimeDifferenceLocalTime$fTimeDifferenceUTCTime $fAdjuste(,)$fFoldableITree$fFunctorITree$fIntersectionQueryITreeeSeq $fShowBlock$fIntervaleBlock $fMonoidBlock$fSemigroupBlock$fFoldableBlock$fFunctorBlock $fOrdBlock $fEqBlock$fShowSplitSeq$fEqNonNestedSeq$fOrdNonNestedSeq$fShowNonNestedSeq$fFunctorNonNestedSeq$fFoldableNonNestedSeq$fTraversableNonNestedSeqMin15Min10MinuteIntervalubZoned fromEndTimeuntil10until15$fShowMinuteInterval$fShowMinuteInterval0$fIntervalUTCTimeMinuteInterval$fOrdMinuteInterval$fEqMinuteIntervalSplitSeqcontainers-0.6.5.1Data.Sequence.InternalSeqbase Data.FoldableFoldableghc-prim GHC.TypesTrueLTGTEQ GHC.MaybeNothinggetIntersectsITgetProperIntersectsITsomeIntersectsITsomeProperlyIntersectsITfindSeq existsSeq time-1.11.1.1&Data.Time.LocalTime.Internal.ZonedTime ZonedTime Data.Time.Clock.Internal.UTCTimeUTCTimezonedTimeToUTCversiongetDataFileName getBinDir getLibDir getDynLibDir getDataDir getLibexecDir getSysconfDir