Skip to content


Repository files navigation


Maven Central Maven Central (snapshot) Codecov Java Version


JVM Platform Status
OpenJDK (Temurin) Current Linux Build (OpenJDK (Temurin) Current, Linux)
OpenJDK (Temurin) LTS Linux Build (OpenJDK (Temurin) LTS, Linux)
OpenJDK (Temurin) Current Windows Build (OpenJDK (Temurin) Current, Windows)
OpenJDK (Temurin) LTS Windows Build (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.