IntervalTree<T> Class

Definition

Namespace

Bodu.Collections.Generic

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

IntervalTree{T}.Enumerator.cs

Represents a collection of closed intervals [low, high] that may freely overlap, answering stabbing queries (QueryPoint(T) - all intervals containing a point) and overlap-window queries (QueryOverlaps(T, T) - all intervals intersecting a window) in O(log n + k).

public sealed class IntervalTree<T> : IReadOnlyCollection<(T Low, T High)>, IEnumerable<(T Low, T High)>, IEnumerable where T : notnull

Type Parameters

T

The type of the interval endpoints. Endpoints must not be null.

Inheritance

object

IntervalTree<T>

Implements

IReadOnlyCollection<(T Low, T High)>

IEnumerable<(T Low, T High)>

IEnumerable

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Examples

var bookings = new IntervalTree<int>();
bookings.Add(9, 11);    // 09:00-11:00
bookings.Add(10, 12);   // 10:00-12:00 - overlaps are stored, not merged
bookings.Add(14, 15);

foreach ((int low, int high) in bookings.QueryPoint(10))
    Console.WriteLine($"[{low}, {high}]");            // [9, 11] then [10, 12]

bool clash = bookings.Intersects(11, 13);             // true - [10, 12] reaches into the window

Remarks

IntervalTree<T> is backed by a max-endpoint augmented red-black tree ordered by the (low, high) lexicographic pair: every node carries the greatest high endpoint in its subtree, maintained through all rotations, so queries prune whole subtrees that cannot reach the probe. See Bodu.Collections/docs/interval-tree-design.md for the design decision record.

This type is the only member of the Bodu range family that stores overlapping intervals. RangeSet<T> and RangeDictionary<TKey, TValue> are sorted non-overlapping maps that merge or reject overlapping inserts, and Bodu.Numerics' IntervalSet<T> normalizes its contents to disjoint ranges - reach for this type when the overlaps themselves are the data.

Intervals are closed on both ends: [low, high] contains every point x with low <= x <= high under the active comparer, and low equal to high is a valid degenerate interval. Duplicate intervals are permitted - each Add(T, T) of an existing (low, high) pair increments a per-node multiplicity, and Remove(T, T) removes one occurrence at a time. Count and enumeration include duplicates.

This type is not thread-safe.

Constructors

IntervalTree()

Initializes a new instance of the IntervalTree<T> class using the default comparer.

public IntervalTree()

IntervalTree(IComparer<T>?)

Initializes a new instance of the IntervalTree<T> class using the specified comparer.

public IntervalTree(IComparer<T>? comparer)

Parameters

comparer IComparer<T>

The endpoint ordering comparer, or null to use the default comparer.

Properties

Comparer

Gets the comparer that defines the endpoint ordering.

public IComparer<T> Comparer { get; }

Property Value

IComparer<T>

The active endpoint comparer.

Count

Gets the total number of stored intervals, duplicates included.

public int Count { get; }

Property Value

int

The number of intervals currently stored in the tree.

Methods

Add(T, T)

Adds the closed interval [low, high] to the tree.

public void Add(T low, T high)

Parameters

low T

The inclusive lower endpoint. Must not be null.

high T

The inclusive upper endpoint. Must not be null.

Remarks

Overlapping intervals are always accepted, and adding an interval equal to one already stored records a duplicate occurrence rather than being rejected - the per-node multiplicity is incremented and Count grows by one.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

Clear()

Removes all intervals from the tree.

public void Clear()

Contains(T, T)

Determines whether the tree stores the exact interval [low, high].

public bool Contains(T low, T high)

Parameters

low T

The inclusive lower endpoint. Must not be null.

high T

The inclusive upper endpoint. Must not be null.

Returns

bool

true if at least one occurrence of the exact interval is stored; otherwise, false.

Remarks

This is an exact-match test on the (low, high) pair. Use Intersects(T, T) or IntersectsPoint(T) to ask whether any stored interval merely overlaps a window or point.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

GetEnumerator()

Returns an enumerator that iterates through the stored intervals in ascending (low, high) order, repeating duplicate intervals once per occurrence.

public IntervalTree<T>.Enumerator GetEnumerator()

Returns

IntervalTree<T>.Enumerator

An IntervalTree<T>.Enumerator over the stored intervals.

Intersects(T, T)

Determines whether any stored interval intersects the closed window [low, high], without enumerating the matches.

public bool Intersects(T low, T high)

Parameters

low T

The inclusive lower edge of the window. Must not be null.

high T

The inclusive upper edge of the window. Must not be null.

Returns

bool

true if at least one stored interval overlaps the window; otherwise, false.

Remarks

This is the early-exit form of QueryOverlaps(T, T) - a single O(log n) descent regardless of how many intervals match.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

IntersectsPoint(T)

Determines whether any stored interval contains point, without enumerating the matches.

public bool IntersectsPoint(T point)

Parameters

point T

The point to test. Must not be null.

Returns

bool

true if at least one stored interval contains the point; otherwise, false.

Remarks

This is the early-exit form of QueryPoint(T) - a single O(log n) descent regardless of how many intervals match.

Exceptions

ArgumentNullException

point is null.

QueryOverlaps(T, T)

Returns all stored intervals intersecting the closed window [low, high], in ascending (low, high) order.

public IEnumerable<(T Low, T High)> QueryOverlaps(T low, T high)

Parameters

low T

The inclusive lower edge of the window. Must not be null.

high T

The inclusive upper edge of the window. Must not be null.

Returns

IEnumerable<(T Low, T High)>

A lazily evaluated sequence of the intervals overlapping the window.

Remarks

An interval matches when it shares at least one point with the window - touching at a single common endpoint counts, because both the stored intervals and the window are closed. Duplicate intervals are repeated once per stored occurrence. Iterating costs O(log n + k) for k reported intervals in the common case.

The sequence is live: each fresh iteration re-resolves against the tree's current state. Within a single iteration it is fail-fast - any structural mutation causes the next advance to throw InvalidOperationException.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

QueryPoint(T)

Returns all stored intervals containing point (the stabbing query), in ascending (low, high) order.

public IEnumerable<(T Low, T High)> QueryPoint(T point)

Parameters

point T

The point to stab. Must not be null.

Returns

IEnumerable<(T Low, T High)>

A lazily evaluated sequence of the intervals whose closed range contains the point.

Remarks

Both endpoints are inclusive: an interval [low, high] matches when low <= point <= high under the active comparer. Duplicate intervals are repeated once per stored occurrence. Iterating costs O(log n + k) for k reported intervals in the common case.

The sequence is live: each fresh iteration re-resolves against the tree's current state. Within a single iteration it is fail-fast - any structural mutation causes the next advance to throw InvalidOperationException.

Exceptions

ArgumentNullException

point is null.

Remove(T, T)

Removes one occurrence of the exact interval [low, high] from the tree.

public bool Remove(T low, T high)

Parameters

low T

The inclusive lower endpoint. Must not be null.

high T

The inclusive upper endpoint. Must not be null.

Returns

bool

true if an occurrence was removed; otherwise, false when the exact interval is not stored.

Remarks

Only an exact (low, high) match is removed - intervals that merely overlap the arguments are untouched. When the interval is stored more than once, one occurrence is removed per call; the node itself is deleted only when its multiplicity reaches zero.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

Explicit Interface Implementations

IEnumerable<(T, T)>.GetEnumerator()

Returns an enumerator that iterates through the collection.

IEnumerator<(T Low, T High)> IEnumerable<(T, T)>.GetEnumerator()

Returns

IEnumerator<(T Low, T High)>

An enumerator that can be used to iterate through the collection.

IEnumerable.GetEnumerator()

Returns an enumerator that iterates through a collection.

IEnumerator IEnumerable.GetEnumerator()

Returns

IEnumerator

An IEnumerator object that can be used to iterate through the collection.

Applies to

Product	Versions
.NET	8, 10