Usage Guide

Intervals in SortedIntervals are plain (start, stop) tuples. Most functions that operate on collections of intervals assume the collection is sorted by start time. Functions that require non-overlapping input will validate this and throw an error if violated.

Overlap Detection

Test whether intervals overlap, or find overlapping pairs within a collection.

check_overlap tests whether two intervals share any points (closed-interval semantics, so touching endpoints count as overlapping):

check_overlap((1, 5), (3, 8))   # true
check_overlap((1, 5), (5, 8))   # true  (touching)
check_overlap((1, 5), (6, 8))   # false

It also works on a vector, checking all pairs:

check_overlap([(1, 3), (2, 5), (7, 9)])  # true — (1,3) and (2,5) overlap

is_subinterval tests containment:

is_subinterval((2, 4), (1, 5))  # true — (2,4) is inside (1,5)
is_subinterval((2, 6), (1, 5))  # false

find_overlaps returns, for each interval, the indices of all other intervals it overlaps with. Assumes sorted input so it can stop early:

find_overlaps([(1, 5), (3, 7), (10, 12)])
# [[2], [1], []] — interval 1 overlaps interval 2 and vice versa

find_all_overlapping takes two sorted, non-overlapping interval lists and returns a BitVector marking which intervals in the first list overlap with any interval in the second:

find_all_overlapping([(1, 3), (5, 7), (10, 12)], [(2, 6)])
# BitVector([1, 1, 0])

Intersections

Compute the overlapping region between intervals.

interval_intersect returns the intersection of two intervals, or nothing if they don't overlap:

interval_intersect((1, 5), (3, 8))  # (3, 5)
interval_intersect((1, 2), (3, 4))  # nothing

interval_intersect_measure returns just the length of the overlap:

interval_intersect_measure((0, 10), (5, 15))  # 5
interval_intersect_measure((1, 2), (3, 4))    # 0

interval_intersections computes all pairwise intersections between two sorted, non-overlapping lists:

interval_intersections([(1, 5), (7, 10)], [(3, 8)])
# [(3, 5), (7, 8)]

interval_intersections_overlapping does the same but allows the input lists to contain overlapping intervals (they must still be sorted by start time). Overlapping results are merged:

interval_intersections_overlapping([(1, 5), (3, 7)], [(2, 10)])
# [(2, 7)]

Set Operations

intervals_diff computes the set difference — the portions of the first list not covered by the second:

intervals_diff([(1, 10)], [(3, 5), (7, 8)])
# [(1, 3), (5, 7), (8, 10)]

interval_complements finds the gaps between intervals within a bounding range. An optional contraction parameter shrinks each gap boundary inward:

interval_complements(0, 10, [(2, 4), (6, 8)])
# [(0, 2), (4, 6), (8, 10)]

interval_complements(0.0, 10.0, [(4.0, 6.0)], 1.0)
# [(1.0, 3.0), (7.0, 9.0)]

overlap_interval_union returns the bounding interval that covers both inputs:

overlap_interval_union((1, 5), (3, 8))  # (1, 8)

Merging and Expansion

join_intervals merges successive intervals when the gap between them is at most min_gap:

join_intervals([(1, 3), (4, 6), (10, 12)], 1)
# [(1, 6), (10, 12)]

join_intervals! does the same in-place, resizing the input vector.

expand_intervals widens each interval by expand / 2 on each side, then merges any resulting overlaps:

expand_intervals([(2, 4), (8, 10)], 2)
# [(1, 5), (7, 11)]

expand_intervals! does the same in-place.

throttle converts a sorted vector of points into intervals by grouping consecutive points that are within min_gap of each other:

throttle([1, 2, 3, 10, 11, 20], 2)
# [(1, 3), (10, 11), (20, 20)]

Validation

intervals_are_ordered checks that intervals are well-formed (start <= stop), sorted by start time, and non-overlapping:

intervals_are_ordered([(1, 3), (4, 6)])  # true
intervals_are_ordered([(1, 5), (3, 7)])  # false — overlapping
intervals_are_ordered([(5, 1)])          # false — malformed

intervals_are_partially_ordered is the same but allows overlaps:

intervals_are_partially_ordered([(1, 5), (3, 7)])  # true

Both accept an accessor function for working with non-tuple collections:

intervals_are_ordered(x -> x.time, my_data)

Utilities

measure and midpoint compute basic interval properties:

measure((3, 7))   # 4
midpoint((2, 6))  # 4.0
measure(nothing)  # 0 — useful after interval_intersect

clip_int clamps an interval to lie within bounds (each endpoint clamped independently):

clip_int((1, 10), (3, 8))  # (3, 8)

clip_interval_duration clips an interval to bounds while attempting to preserve its duration by shifting:

clip_interval_duration(8, 12, 0, 10)  # (6, 10) — shifted left to fit
clip_interval_duration(-2, 5, 0, 10)  # (0, 7)  — shifted right to fit

interval_indices finds the index range in a sorted vector that falls within an interval, using binary search:

interval_indices([10, 20, 30, 40, 50], 15, 35)  # (2, 3)

mask_events returns a view of a sorted vector containing only elements within a range:

mask_events([1, 3, 5, 7, 9], 2, 6)  # [3, 5]

maximum_interval_overlap finds which interval in a collection has the greatest overlap with a target:

maximum_interval_overlap([(1, 5), (4, 10), (12, 15)], (3, 8))
# (2, 4) — index 2, overlap of 4

measure_to_bounds converts (start, duration) to (start, stop):

measure_to_bounds(5, 3)  # (5, 8)

reduce_extrema and extrema_red compute bounding ranges:

reduce_extrema((1, 5), (3, 8))              # (1, 8)
extrema_red([(1, 5), (3, 8), (6, 7)])       # (1, 8)

parse_ranges_str parses human-readable range strings:

parse_ranges_str("1-3, 7, 10-12")  # [1, 2, 3, 7, 10, 11, 12]

clipsize! resizes a vector and releases excess memory capacity:

v = Vector{Int}(undef, 100)
clipsize!(v, 3)  # now length 3 with no excess allocation