abstand
A simple, correct, efficient interval tree implementation.
Motivation
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.
Usage
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 |
Notes
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.
Releases & Development Snapshots
Releases
You can subscribe to the atom feed to be notified of project releases.
The most recently released version of the package is 1.1.0.
1.1.0 Release (2024-06-02Z)
- Add findExact() for trees that care about interval identity.
The compiled artifacts for the release (and all previous releases) are available on Maven Central.
Maven Modules
<dependency> <group>com.io7m.abstand</group> <artifactId>com.io7m.abstand.core</artifactId> <version>1.1.0</version> </dependency><dependency> <group>com.io7m.abstand</group> <artifactId>com.io7m.abstand.generation</artifactId> <version>1.1.0</version> </dependency><dependency> <group>com.io7m.abstand</group> <artifactId>com.io7m.abstand.tests</artifactId> <version>1.1.0</version> </dependency>
Previous Releases
The changelogs for the most recent previous releases are as follows:
1.0.0 Release (2024-06-01Z)
- Initial public release.
Development Snapshots
At the time of writing, the current unstable development version of the package is 1.1.1-SNAPSHOT.
Development snapshots may be available in the Central Portal Snapshots repository. Snapshots are published to this repository every time the project is built by the project's continuous integration system, but snapshots do expire after around ninety days and so may or may not be available depending on when a build of the package was last triggered.
Manual
This project does not have any user manuals or other documentation beyond what might be present on the page above.
Sources
This project uses Git to manage source code.
Repository: https://www.github.com/io7m-com/abstand
$ git clone --recursive https://www.github.com/io7m-com/abstand
Issues
This project uses GitHub Issues to track issues.
License
Copyright © 2024 Mark Raynsford <code@io7m.com> https://www.io7m.com Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies. THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.