Skip to content
FutureBlitz

    Install

    Import std.collections.interval_tree

    std.collections.interval_tree

    A tree of values over intervals, which finds those that overlap an interval or hold a key.

    IntervalTree<K, V>: values, each over an interval of keys from a low to a high, both in it, which finds the intervals that overlap another, or hold a key, without going over the others. It's a balanced tree of the intervals, by low and then by high, each node with the values over its interval and the highest high under it, so a search skips what ends early.

    std/collections/interval_tree.fb

    Types

    IntervalTree class 

    @DebugElements Public Class IntervalTree<K: Comparable, V> Implements Iterable<(K, K, V)>, Cloneable, Defaultable

    Values over ranges of keys, found by the ranges that hold a key or overlap another range.

    Examples

    Local meetings = IntervalTree<Int, String>()
meetings.Add(9, 11, "standup")
meetings.Add(10, 12, "review")
meetings.Add(14, 15, "lunch")
Expect(meetings.Containing(10).Count == 2)
Expect(meetings.Overlapping(12, 13) == [(10, 12, "review")])

    std/collections/interval_tree.fb, line 42

    • Public Property Count: Int property #

      How many values it has, over all its intervals.

    • @PanicsAtCaller Public Method Add(low: K, high: K, value: V) method #

      Adds a value over the interval from low to high, after any others over it. A high below low panics, and so does an end that isn't equal to itself, like NaN.

    • Public Method Remove(low: K, high: K, value: V): Bool method #

      Removes the first value over the interval from low to high that's equal to value, and tells whether there was one. An end that isn't equal to itself has none.

    • Public Method Contains(low: K, high: K, value: V): Bool method #

      Whether a value equal to value is over the interval from low to high, which an end that isn't equal to itself never has.

    • Public Method Clear() method #

      Takes every interval out.

    • Public Method Overlapping(low: K, high: K): (K, K, V)[] method #

      The intervals that overlap the one from low to high, with their values, by low and then by high, in a new array. A high below low overlaps nothing, and so does an end that isn't equal to itself.

    • Public Method Containing(key: K): (K, K, V)[] method #

      The intervals that hold key, with their values, by low and then by high, in a new array.

    • Public Method ToArray(): (K, K, V)[] method #

      Each interval's low and high with each of its values, by low and then by high, in a new array.

    • Public Static Method DefaultValue(): IntervalTree<K, V> static method #

      A new, empty IntervalTree.

    • Public Method Clone(): IntervalTree<K, V> method #

      A new IntervalTree with the same intervals and values.

    • Public Method Iterate(): IntervalTreeIterator<K, V> method #

      Each interval's low and high with each of its values, as a tuple, by low and then by high. Adding or removing a value while going over them panics.

    IntervalTreeIterator struct 

    Public Struct IntervalTreeIterator<K: Comparable, V> Implements Iterator<(K, K, V)>

    The intervals of an IntervalTree and their values, by low and then by high, which a For loop goes over.

    std/collections/interval_tree.fb, line 305

    • @PanicsAtCaller Public ByRef Method Next(): (K, K, V)? method #

      The next interval's low and high, with one of its values, by low and then by high, or Null after the last. Panics when the IntervalTree changed since the loop began.

    Extends

    IntervalTree extend 

    Extend IntervalTree<K, V> Implements Equatable

    Compares IntervalTrees with == and !=, where their values can be compared.

    std/collections/interval_tree.fb, line 349

    • Operator ==(a: IntervalTree<K, V>, b: IntervalTree<K, V>): Bool operator #

      Whether the two have the same intervals, with equal values in the same order.

    IntervalTree extend 

    Extend IntervalTree<K, V> Implements Printable

    Shows an IntervalTree in a string, as its ToString writes it.

    std/collections/interval_tree.fb, line 361

    • Public Method ToString(): String method #

      Its intervals and their values, in order, as an array of tuples: "[(1, 3, a), (2, 5, b)]".

    Report an issue with this page or with FutureBlitz on GitHub.