stef-gms / interval_tree

A non-overlapping interval tree for Dart

Interval Tree for Dart

A Dart implementation of an interval tree, with support for calculating unions, intersections, and differences between individual intervals, or entire iterable collections of intervals, such as other interval trees.

Mutable

IntervalTree has support for adding and removing intervals, or entire iterable collections of intervals, such as other interval trees.

Non-overlapping

IntervalTree automatically joins and splits appropriate intervals at insertions and removals, respectively, whilst maintaining a collection of non-overlapping intervals.

Iterable

IntervalTree is an iterable collection offering all standard iterable operations, such as easily accessing the first and last interval.

History

IntervalTree started off as a quick and dirty Dart port of Erik Garrison's simple C++ interval tree implementation, but was soon re-written and based on quiver.collection's AVL implementation of a self-balancing binary tree AvlTreeSet.