IntervalTree<TKey, TValue> Class

Definition

Namespace

Bodu.Collections.Generic

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

IntervalTree{T,T}.Enumerator.cs

Represents a collection of closed intervals [low, high] that may freely overlap, each carrying an associated value, answering stabbing queries (QueryPoint(TKey)) and overlap-window queries (QueryOverlaps(TKey, TKey)) in O(log n + k).

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

Type Parameters

TKey

The type of the interval endpoints.

TValue

The type of the value carried by each stored interval.

Inheritance

object

IntervalTree<TKey, TValue>

Implements

IReadOnlyCollection<(TKey Low, TKey High, TValue Value)>

IEnumerable<(TKey Low, TKey High, TValue Value)>

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 meetings = new IntervalTree<int, string>();
meetings.Add(9, 11, "stand-up");
meetings.Add(10, 12, "design review");   // overlaps are stored, not merged
meetings.Add(10, 12, "1:1");             // same slot, different value - also stored

foreach ((int low, int high, string name) in meetings.QueryPoint(10))
    Console.WriteLine($"[{low}, {high}] {name}");

meetings.Remove(10, 12, "1:1");          // removes exactly that entry

Remarks

IntervalTree<TKey, TValue> is the value-carrying counterpart of IntervalTree<T>, backed by the same max-endpoint augmented red-black tree ordered by the (low, high) lexicographic pair. See Bodu.Collections/docs/interval-tree-design.md for the design decision record and the boundary against the non-overlapping RangeSet<T> / RangeDictionary<TKey, TValue> range maps.

Intervals are closed on both ends and duplicates of the same (low, high) pair are permitted - including with equal values. Where the unkeyed tree keeps a per-node multiplicity count, this type keeps a per-node value list in insertion order: Add(TKey, TKey, TValue) appends, Remove(TKey, TKey) removes the first stored entry, and Remove(TKey, TKey, TValue) removes the first entry whose value matches under Default. Count and enumeration include every stored entry.

This type is not thread-safe.

Endpoints must not be null.

Constructors

IntervalTree()

Initializes a new instance of the IntervalTree<TKey, TValue> class using the default comparer.

public IntervalTree()

IntervalTree(IComparer<TKey>?)

Initializes a new instance of the IntervalTree<TKey, TValue> class using the specified comparer.

public IntervalTree(IComparer<TKey>? comparer)

Parameters

comparer IComparer<TKey>

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

Properties

Comparer

Gets the comparer that defines the endpoint ordering.

public IComparer<TKey> Comparer { get; }

Property Value

IComparer<TKey>

The active endpoint comparer.

Count

Gets the total number of stored entries, duplicates included.

public int Count { get; }

Property Value

int

The number of interval/value entries currently stored in the tree.

Methods

Add(TKey, TKey, TValue)

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

public void Add(TKey low, TKey high, TValue value)

Parameters

low TKey

The inclusive lower endpoint. Must not be null.

high TKey

The inclusive upper endpoint. Must not be null.

value TValue

The value to associate with the interval.

Remarks

Overlapping intervals are always accepted, and adding to an interval already stored appends the value to that node's entry list - the same (low, high) pair may carry many values, including comparer-equal duplicates. Values are retained in insertion order per interval.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

Clear()

Removes all entries from the tree.

public void Clear()

Contains(TKey, TKey)

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

public bool Contains(TKey low, TKey high)

Parameters

low TKey

The inclusive lower endpoint. Must not be null.

high TKey

The inclusive upper endpoint. Must not be null.

Returns

bool

true if at least one entry with the exact interval is stored; otherwise, false.

Remarks

This is an exact-match test on the (low, high) pair, regardless of the values carried. Use Intersects(TKey, TKey) or IntersectsPoint(TKey) 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 entries in ascending (low, high) order, yielding an interval's values in insertion order.

public IntervalTree<TKey, TValue>.Enumerator GetEnumerator()

Returns

IntervalTree<TKey, TValue>.Enumerator

An IntervalTree<TKey, TValue>.Enumerator over the stored entries.

Intersects(TKey, TKey)

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

public bool Intersects(TKey low, TKey high)

Parameters

low TKey

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

high TKey

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(TKey, TKey) - a single O(log n) descent regardless of how many entries match.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

IntersectsPoint(TKey)

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

public bool IntersectsPoint(TKey point)

Parameters

point TKey

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(TKey) - a single O(log n) descent regardless of how many entries match.

Exceptions

ArgumentNullException

point is null.

QueryOverlaps(TKey, TKey)

Returns all stored entries whose interval intersects the closed window [low, high], in ascending (low, high) order with each interval's values in insertion order.

public IEnumerable<(TKey Low, TKey High, TValue Value)> QueryOverlaps(TKey low, TKey high)

Parameters

low TKey

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

high TKey

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

Returns

IEnumerable<(TKey Low, TKey High, TValue Value)>

A lazily evaluated sequence of the entries 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. Iterating costs O(log n + k) for k reported entries 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(TKey)

Returns all stored entries whose interval contains point (the stabbing query), in ascending (low, high) order with each interval's values in insertion order.

public IEnumerable<(TKey Low, TKey High, TValue Value)> QueryPoint(TKey point)

Parameters

point TKey

The point to stab. Must not be null.

Returns

IEnumerable<(TKey Low, TKey High, TValue Value)>

A lazily evaluated sequence of the entries whose closed interval contains the point.

Remarks

Both endpoints are inclusive: an interval [low, high] matches when low <= point <= high under the active comparer. Iterating costs O(log n + k) for k reported entries 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(TKey, TKey)

Removes the first stored entry of the exact interval [low, high] from the tree.

public bool Remove(TKey low, TKey high)

Parameters

low TKey

The inclusive lower endpoint. Must not be null.

high TKey

The inclusive upper endpoint. Must not be null.

Returns

bool

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

Remarks

Only an exact (low, high) match is affected. When the interval carries multiple values, the earliest inserted entry is removed; use Remove(TKey, TKey, TValue) to remove a specific value. The node is deleted only when its entry list empties.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

Remove(TKey, TKey, TValue)

Removes the first stored entry of the exact interval [low, high] whose value equals value under Default.

public bool Remove(TKey low, TKey high, TValue value)

Parameters

low TKey

The inclusive lower endpoint. Must not be null.

high TKey

The inclusive upper endpoint. Must not be null.

value TValue

The value identifying the entry to remove.

Returns

bool

true if a matching entry was removed; otherwise, false when the exact interval is not stored or carries no matching value.

Remarks

When the interval carries several equal values, one entry is removed per call. The node is deleted only when its entry list empties.

Exceptions

ArgumentNullException

low or high is null.

ArgumentException

low orders after high under the active comparer.

Explicit Interface Implementations

IEnumerable<(TKey, TKey, TValue)>.GetEnumerator()

Returns an enumerator that iterates through the collection.

IEnumerator<(TKey Low, TKey High, TValue Value)> IEnumerable<(TKey, TKey, TValue)>.GetEnumerator()

Returns

IEnumerator<(TKey Low, TKey High, TValue Value)>

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