Crate interval_tree 

Interval tree for overlap queries on half-open [lo, hi) intervals.

An Interval<T> is a tagged pair (lo, hi) with an associated payload. This crate builds the simple static interval tree described by the CLRS-style construction:

• median-split on mid = (lo + hi) / 2
• store intervals whose midpoint lies on the left of mid in left
• store intervals whose midpoint lies on the right of mid in right
• store intervals that contain mid in middle (their lo <= mid <= hi)

IntervalTree::query returns every interval whose [lo, hi) overlaps a query interval [qlo, qhi).

The implementation is the canonical O(n log n) build / O(k log n) query variant; it is built once on construction and immutable thereafter.

Structs

Interval

A half-open interval [lo, hi) carrying a payload.

IntervalTree

Static interval tree.