IntervalTree class

A non-overlapping collection of intervals organized into a tree.

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

final IntervalTree tree = IntervalTree.from([[1, 3], [5, 8], [10, 15]]);
print(tree); // IntervalTree([1, 3], [5, 8], [10, 15])

tree.add([2, 6]);
print(tree); // IntervalTree([1, 8], [10, 15])

tree.remove([12, 16]);
print(tree); // IntervalTree([1, 8], [10, 12])

As illustrated by the above example, IntervalTree automatically joins and splits appropriate intervals at insertions and removals, respectively, whilst maintaining a collection of non-overlapping intervals.

IntervalTree can also calculate unions, intersections, and differences between collections of intervals:

final IntervalTree tree = IntervalTree.from([[1, 8], [10, 12]]);
final IntervalTree other = IntervalTree.from([[0, 2], [5, 7]]);

print(tree.union(other)); // IntervalTree([0, 8], [10, 12])
print(tree.intersection(other)); // IntervalTree([1, 2], [5, 7])
print(tree.difference(other)); // IntervalTree([2, 5], [7, 8], [10, 12])

IntervalTree is an Iterable collection offering all standard iterable operations, such as easily iterating the entire tree, or accessing the first and last intervals.

for (final interval in tree) {
  print(interval); // [1, 8] \n [10, 12]
}

print(tree.first); // [1, 8]
print(tree.last); // [10, 12]

Notice that all methods that take interval arguments accept either Interval objects or literal lists with two items. The latter is a natural syntax for specifying intervals:

tree.add([0, 5]); // vs. tree.add(Interval(0, 5));

Notice that the Interval class name unfortunately clashes with the Interval class from the Flutter animation library. However, there are two ways around this problem. Either use the syntax with list literals, or import either library with a name prefix, for example:

import 'package:interval_tree/interval_tree.dart' as ivt;

final interval = ivt.Interval(1, 2);
Mixed in types
Available Extensions

Constructors

IntervalTree([dynamic interval])
Creates a tree, optionally with an interval.
IntervalTree.from(Iterable intervals)
Creates a tree from given iterable of intervals.
factory
IntervalTree.of(Iterable<Interval?> intervals)
Creates a tree from intervals.
factory

Properties

first → Interval
Returns the first interval in tree, otherwise throw StateError.
no setteroverride
hashCode → int
The hash code for this object.
no setterinherited
isEmpty → bool
Returns true if there are no intervals in this tree.
no setteroverride
isNotEmpty → bool
Returns true if there is at least one interval in this tree.
no setteroverride
iterator → TreeIterator<Interval>
Returns a bidirectional iterator that allows iterating the intervals.
no setteroverride
last → Interval
Returns the first interval in tree, otherwise throw StateError.
no setteroverride
length → int
Returns the number of intervals in this tree.
no setteroverride
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited
single → Interval
Checks that this tree has only one interval, and returns that interval.
no setteroverride

Methods

add(dynamic interval) → void
Adds an interval into this tree.
addAll(Iterable intervals) → void
Adds all intervals into this tree.
any(bool test(Interval element)) → bool
Checks whether any element of this iterable satisfies test.
inherited
cast<R>() → Iterable<R>
A view of this iterable as an iterable of R instances.
inherited
clear() → void
Clears this tree.
contains(Object? element) → bool
Whether the collection contains an element equal to element.
override
difference(IntervalTree other) → IntervalTree
elementAt(int index) → Interval
Returns the indexth element.
inherited
every(bool test(Interval element)) → bool
Checks whether every element of this iterable satisfies test.
inherited
expand<T>(Iterable<T> toElements(Interval element)) → Iterable<T>
Expands each element of this Iterable into zero or more elements.
inherited
firstWhere(bool test(Interval element), {Interval orElse()?}) → Interval
The first element that satisfies the given predicate test.
inherited
fold<T>(T initialValue, T combine(T previousValue, Interval element)) → T
Reduces a collection to a single value by iteratively combining each element of the collection with an existing value
inherited
followedBy(Iterable<Interval> other) → Iterable<Interval>
Creates the lazy concatenation of this iterable and other.
inherited
forEach(void action(Interval element)) → void
Invokes action on each element of this iterable in iteration order.
inherited
intersection(IntervalTree other) → IntervalTree
join([String separator = ""]) → String
Converts each element to a String and concatenates the strings.
inherited
lastWhere(bool test(Interval element), {Interval orElse()?}) → Interval
The last element that satisfies the given predicate test.
inherited
map<T>(T toElement(Interval e)) → Iterable<T>
The current elements of this iterable modified by toElement.
inherited
noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
reduce(Interval combine(Interval value, Interval element)) → Interval
Reduces a collection to a single value by iteratively combining elements of the collection using the provided function.
inherited
remove(dynamic interval) → void
Removes an interval from this tree.
removeAll(Iterable intervals) → void
Removes all intervals from this tree.
singleWhere(bool test(Interval element), {Interval orElse()?}) → Interval
The single element that satisfies test.
inherited
skip(int count) → Iterable<Interval>
Creates an Iterable that provides all but the first count elements.
inherited
skipWhile(bool test(Interval value)) → Iterable<Interval>
Creates an Iterable that skips leading elements while test is satisfied.
inherited
take(int count) → Iterable<Interval>
Creates a lazy iterable of the count first elements of this iterable.
inherited
takeWhile(bool test(Interval value)) → Iterable<Interval>
Creates a lazy iterable of the leading elements satisfying test.
inherited
toList({bool growable = true}) → List<Interval>
Creates a List containing the elements of this Iterable.
inherited
toSet() → Set<Interval>
Creates a Set containing the same elements as this iterable.
inherited
toString() → String
Returns a string representation of the tree.
override
union(IntervalTree other) → IntervalTree
where(bool test(Interval element)) → Iterable<Interval>
Creates a new lazy Iterable with all elements that satisfy the predicate test.
inherited
whereType<T>() → Iterable<T>
Creates a new lazy Iterable with all elements that have type T.
inherited

Operators

operator ==(Object other) → bool
The equality operator.
inherited