| JVM | Platform | Status |
|---|---|---|
| OpenJDK (Temurin) Current | Linux |  |
| OpenJDK (Temurin) LTS | Linux |  |
| OpenJDK (Temurin) Current | Windows |  |
| OpenJDK (Temurin) LTS | Windows |  |
A simple, correct, efficient interval tree implementation.
At the time of writing, no interval tree implementations exist for Java that have all of the following properties:
- Simple, readable, and well-commented.
- Not part of an existing massive, poor-quality library such as Guava.
- Heavily tested with an exhaustive test suite.
- Liberally licensed.
- Published to Maven Central.
- JPMS-ready.
- OSGi-ready.
The abstand package provides a generic interval tree implementation based
on an AVL tree that aims to meet
all of the above requirements.
Implementations of the IntervalTreeType are implementations of Set that
also allow for overlapping queries:
var t = IntervalTree.<Long>create();
t.add(IntervalL.of(20, 30));
t.add(IntervalL.of(25, 30));
var o = t.overlapping(IntervalL.of(26, 28));
// o == [[20, 30], [25, 30]];
Interval trees contain values of type IntervalType<S> for some scalar
type S. The following implementations are provided:
| Type | Description |
|---|---|
IntervalD |
Intervals with double-typed values |
IntervalB |
Intervals with BigInteger-typed values |
IntervalL |
Intervals with long-typed values |
IntervalI |
Intervals with int-typed values |
Credit is given to someone named "John Hargrove" who published what appears to be the only comprehensible explanation of AVL tree rotations online. All other texts appear to contain subtle mistakes, or miss the exact conditions required for each rotation type to be applicable.
He originally published a document online, but I've included a copy in the references subdirectory as I do not trust random files published in the home directories of computer science students on university servers to stay accessible.