RangeTrees.jl

This Julia package defines the RangeNode type to represent an augmented interval tree created from a Vector{UnitRange{T}} where {T<:Integer}. (The tree is represented by its root node.)

A fast intersect method for a target range and a RangeNode can be used to evaluate coverage by the ranges in the tree routed at the node, as in the coverage program from bedtools.

Tree traversal, printing, etc. use the AbstractTrees.jl framework.

The facilities of this package are a subset of those offered by IntervalTrees.jl but tuned to the particular task of intersecting a UnitRange target with the intervals (also represented as UnitRange) in the tree.

The example in the figure on the Wikipedia page can be reproduced as

julia> using RangeTrees

julia> rr = RangeNode([0:0, 3:40, 10:14, 20:35, 29:98]);

julia> print_tree(rn)
(10:14, 98)
├─ (3:40, 40)
│  └─ (0:0, 0)
└─ (29:98, 98)
   └─ (20:35, 35)

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

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

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

Each node in the print_tree output is shown as the range at that node and the maximum value of last(range) in the subtree rooted at that node. This is the augmentation in the tree that allows for fast intersection of the nodes in the tree with a target tree.

The tree rt is not the same as the one shown in the figure because a RangeNode is constructed to be balanced and the one in the figure is not balanced. Note that in the figure the intervals exclude the right hand endpoint whereas Julia's UnitRange{<:Integer} is inclusive of both end points. Thus [20, 36) in the figure corresponds to the range 20:35.

The intersect! method allows for passing the vector that will be the result, reducing the memory allocations. Note that the first argument to intersect! should be wrapped in empty! because intersect! is recursive and push!s each intersection onto the end of result.