RangeTrees

RangeNode

An augmented, balanced, binary interval tree of intervals of integers represented as a UnitRange.

```jldoctest julia> rn = RangeNode([0:0, 3:40, 10:14, 20:35, 29:98]); # example from Wikipedia page

julia> intersect(40:59, rn) 2-element Vector{UnitRange{Int64}}: 40:40 40:59 ````

intersect!(result::Vector{UnitRange{T}}, target::AbstractUnitRange, rn::RangeNode{T}) where {T}

Recursively intersect target with the intervals in the tree rooted at rn.

Non-empty intersections are pushed onto result in the same order as the intersecting nodes appear in the tree. Storing maxlast allows for the pre-order depth-first search to be truncated when a node's maxlast is less than first(target). Because the nodes are in non-decreasing order of first(intvl) the right subtree can be skipped when last(target) < first(intvl).

midrange(rng::AbstractUnitRange{T}) where {T<:Integer}

Return the median of rng, rounding up when length(rng) is even.

splitrange(rng)

Split rng into mid, the value of midrange, the UnitRange to the left of mid and the UnitRange to the right.