Table of Contents

NavigableSet<T> Class

Definition

Namespace
Bodu.Collections.Generic
Assembly
Bodu.Collections.dll
Package
Bodu.Collections 1.0.0
Source
NavigableSet{T}.Enumerator.cs

Represents a sorted set augmented with order statistics - an ISet<T> that keeps its elements in comparer order and answers nearest-neighbour (TryGetFloor(T, out T) / TryGetCeiling(T, out T) / TryGetHigher(T, out T) / TryGetLower(T, out T)), rank/select (IndexOf(T) / GetAt(int)), and range-counting queries in O(log n).

public sealed class NavigableSet<T> : ISet<T>, ICollection<T>, IReadOnlyCollection<T>, IEnumerable<T>, IEnumerable where T : notnull

Type Parameters

T

The type of elements in the set. Elements must not be null.

Inheritance
NavigableSet<T>
Implements
ISet<T>
Inherited Members
Extension Methods

Examples

var prices = new NavigableSet<decimal>();
prices.Add(10.00m);
prices.Add(10.25m);
prices.Add(10.50m);

prices.TryGetFloor(10.30m, out decimal floor);    // 10.25 - greatest element <= 10.30
prices.TryGetCeiling(10.30m, out decimal ceiling);// 10.50 - least element >= 10.30

int rank = prices.IndexOf(10.25m);                // 1 - zero-based rank in sorted order
decimal median = prices.GetAt(prices.Count / 2);  // 10.25 - k-th smallest
int inBand = prices.CountInRange(10.00m, 10.30m); // 2 - O(log n), no iteration

Remarks

NavigableSet<T> is backed by an order-statistic red-black tree: every node carries the size of its subtree, maintained through all rotations, so positional queries read only size fields on a root-to-node path. See Bodu.Collections/docs/navigable-collections-design.md for the backing-structure decision record.

Compared with SortedSet<T>, this type adds rank/select (IndexOf(T) is the zero-based rank of an element; GetAt(int) is the k-th smallest element), O(log n) CountInRange(T, T), the four nearest-neighbour queries, and cheap Ascending() / Descending() / Range(T, T) views. Unlike SortedSet<T>, null elements are rejected, consistent with the rest of the Bodu collection family.

Elements that the comparer orders equal are treated as duplicates: Add(T) returns false and preserves the stored element.

This type is not thread-safe.

Constructors

NavigableSet()

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

public NavigableSet()

NavigableSet(IComparer<T>?)

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

public NavigableSet(IComparer<T>? comparer)

Parameters

comparer IComparer<T>

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

NavigableSet(IEnumerable<T>, IComparer<T>?)

Initializes a new instance of the NavigableSet<T> class containing the distinct elements from source, bulk-loaded into a balanced tree.

public NavigableSet(IEnumerable<T> source, IComparer<T>? comparer = null)

Parameters

source IEnumerable<T>

The source collection. Must not be null.

comparer IComparer<T>

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

Remarks

The source is sorted and deduplicated (comparer-equal duplicates keep the first occurrence), then built directly into a balanced tree - O(n log n) overall, O(n) after the sort.

Exceptions

ArgumentNullException

source is null.

ArgumentException

source contains a null element.

Properties

Comparer

Gets the comparer that defines the element ordering.

public IComparer<T> Comparer { get; }

Property Value

IComparer<T>

The active ordering comparer.

Count

Gets the number of elements in the set.

public int Count { get; }

Property Value

int

The number of elements currently stored in the set.

IsReadOnly

Gets a value indicating whether the set is read-only.

public bool IsReadOnly { get; }

Property Value

bool

Always false.

Max

Gets the largest element in the set.

public T Max { get; }

Property Value

T

The maximum element under the active comparer.

Exceptions

InvalidOperationException

The set is empty.

Min

Gets the smallest element in the set.

public T Min { get; }

Property Value

T

The minimum element under the active comparer.

Exceptions

InvalidOperationException

The set is empty.

Methods

Add(T)

Adds the specified item to the set.

public bool Add(T item)

Parameters

item T

The item to add. Must not be null.

Returns

bool

true if the item was added; otherwise, false when the set already contains a comparer-equal element.

Exceptions

ArgumentNullException

item is null.

Ascending()

Returns a live view of the set in ascending comparer order.

public IEnumerable<T> Ascending()

Returns

IEnumerable<T>

A lazily evaluated sequence over the current elements, smallest first.

Remarks

The view is live: each fresh iteration re-resolves against the set's current state, so mutations made after the view was obtained are reflected the next time it is iterated. Within a single iteration the view is fail-fast - any structural mutation causes the next advance to throw InvalidOperationException.

Clear()

Removes all elements from the set.

public void Clear()

Contains(T)

Determines whether the set contains the specified item.

public bool Contains(T item)

Parameters

item T

The item to locate. Must not be null.

Returns

bool

true if a comparer-equal element exists; otherwise, false.

Exceptions

ArgumentNullException

item is null.

CopyTo(T[], int)

Copies the elements to the specified array in ascending order, starting at arrayIndex.

public void CopyTo(T[] array, int arrayIndex)

Parameters

array T[]

The destination array. Must not be null.

arrayIndex int

The destination start index.

Exceptions

ArgumentNullException

array is null.

ArgumentOutOfRangeException

arrayIndex is negative.

ArgumentException

array does not have enough space starting at arrayIndex.

CountInRange(T, T)

Returns the number of elements within the inclusive range [lowInclusive, highInclusive].

public int CountInRange(T lowInclusive, T highInclusive)

Parameters

lowInclusive T

The inclusive lower bound. Must not be null.

highInclusive T

The inclusive upper bound. Must not be null.

Returns

int

The count of stored elements no smaller than the lower bound and no larger than the upper bound.

Remarks

Runs in O(log n) as a subtraction of two rank walks; neither bound needs to be present in the set.

Exceptions

ArgumentNullException

lowInclusive or highInclusive is null.

ArgumentException

lowInclusive orders after highInclusive under the active comparer.

Descending()

Returns a live view of the set in descending comparer order.

public IEnumerable<T> Descending()

Returns

IEnumerable<T>

A lazily evaluated sequence over the current elements, largest first.

Remarks

The view is live: each fresh iteration re-resolves against the set's current state, so mutations made after the view was obtained are reflected the next time it is iterated. Within a single iteration the view is fail-fast - any structural mutation causes the next advance to throw InvalidOperationException.

ExceptWith(IEnumerable<T>)

Modifies the current set so that it contains only elements that are not present in other.

public void ExceptWith(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to subtract. Must not be null.

Remarks

Removes element-at-a-time - O(m log n) for m elements in other.

Exceptions

ArgumentNullException

other is null.

GetAt(int)

Returns the element at the specified zero-based rank - the k-th smallest element.

public T GetAt(int rank)

Parameters

rank int

The zero-based rank of the element to select.

Returns

T

The element whose rank is rank.

Remarks

Runs in O(log n) by descending on subtree sizes.

Exceptions

ArgumentOutOfRangeException

rank is negative or greater than or equal to Count.

GetEnumerator()

Returns an enumerator that iterates through the set in ascending comparer order.

public NavigableSet<T>.Enumerator GetEnumerator()

Returns

NavigableSet<T>.Enumerator

An NavigableSet<T>.Enumerator over the set elements.

IndexOf(T)

Returns the zero-based rank of value in ascending comparer order.

public int IndexOf(T value)

Parameters

value T

The element to locate. Must not be null.

Returns

int

The number of elements smaller than value, or -1 if it is not present.

Remarks

Runs in O(log n) by accumulating subtree sizes along the search path.

Exceptions

ArgumentNullException

value is null.

IntersectWith(IEnumerable<T>)

Modifies the current set so that it contains only elements that are also present in other.

public void IntersectWith(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to intersect with. Must not be null.

Remarks

Sorts other into a scratch array under this set's comparer and merge-walks it against the in-order enumeration to find the non-members - O(n + m log m) overall, with no tree nodes allocated for other.

Exceptions

ArgumentNullException

other is null.

IsProperSubsetOf(IEnumerable<T>)

Determines whether the current set is a proper (strict) subset of other.

public bool IsProperSubsetOf(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to test against. Must not be null.

Returns

bool

true if the current set is a subset of other and the two are not equal; otherwise, false.

Exceptions

ArgumentNullException

other is null.

IsProperSupersetOf(IEnumerable<T>)

Determines whether the current set is a proper (strict) superset of other.

public bool IsProperSupersetOf(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to test against. Must not be null.

Returns

bool

true if the current set is a superset of other and the two are not equal; otherwise, false.

Exceptions

ArgumentNullException

other is null.

IsSubsetOf(IEnumerable<T>)

Determines whether the current set is a subset of other.

public bool IsSubsetOf(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to test against. Must not be null.

Returns

bool

true if every element of the current set is also in other; otherwise, false.

Exceptions

ArgumentNullException

other is null.

IsSupersetOf(IEnumerable<T>)

Determines whether the current set is a superset of other.

public bool IsSupersetOf(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to test against. Must not be null.

Returns

bool

true if every element of other is also in the current set; otherwise, false.

Exceptions

ArgumentNullException

other is null.

Overlaps(IEnumerable<T>)

Determines whether the current set and other share any elements.

public bool Overlaps(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to test against. Must not be null.

Returns

bool

true if the two collections share at least one element; otherwise, false.

Exceptions

ArgumentNullException

other is null.

Range(T, T)

Returns a live view of the elements within the inclusive range [lowInclusive, highInclusive] in ascending comparer order.

public IEnumerable<T> Range(T lowInclusive, T highInclusive)

Parameters

lowInclusive T

The inclusive lower bound. Must not be null.

highInclusive T

The inclusive upper bound. Must not be null.

Returns

IEnumerable<T>

A lazily evaluated sequence over the in-range elements, smallest first.

Remarks

The bounds need not be present in the set. The walk descends directly to the first in-range element and stops past the last, so iterating costs O(log n + k) for k yielded elements.

The view is live over the bound pair: each fresh iteration re-resolves against the set's current state. Within a single iteration the view is fail-fast - any structural mutation causes the next advance to throw InvalidOperationException.

Exceptions

ArgumentNullException

lowInclusive or highInclusive is null.

ArgumentException

lowInclusive orders after highInclusive under the active comparer.

Remove(T)

Removes the specified item from the set.

public bool Remove(T item)

Parameters

item T

The item to remove. Must not be null.

Returns

bool

true if the item was removed; otherwise, false.

Exceptions

ArgumentNullException

item is null.

SetEquals(IEnumerable<T>)

Determines whether the current set contains exactly the same elements as other.

public bool SetEquals(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to compare against. Must not be null.

Returns

bool

true if the two collections contain the same elements (ignoring duplicates and order); otherwise, false.

Exceptions

ArgumentNullException

other is null.

SymmetricExceptWith(IEnumerable<T>)

Modifies the current set so that it contains only elements that are present either in the current set or in other, but not in both.

public void SymmetricExceptWith(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to apply symmetric difference with. Must not be null.

Remarks

Sorts and deduplicates other into a scratch array and toggles membership per distinct element - O(m log m + m log n) overall, with no tree nodes allocated for other.

Exceptions

ArgumentNullException

other is null.

TryGetCeiling(T, out T)

Attempts to get the least element greater than or equal to value.

public bool TryGetCeiling(T value, out T ceiling)

Parameters

value T

The reference value. Must not be null.

ceiling T

When this method returns true, the ceiling element.

Returns

bool

true if a ceiling exists; otherwise, false.

Exceptions

ArgumentNullException

value is null.

TryGetFloor(T, out T)

Attempts to get the greatest element less than or equal to value.

public bool TryGetFloor(T value, out T floor)

Parameters

value T

The reference value. Must not be null.

floor T

When this method returns true, the floor element.

Returns

bool

true if a floor exists; otherwise, false.

Exceptions

ArgumentNullException

value is null.

TryGetHigher(T, out T)

Attempts to get the least element strictly greater than value.

public bool TryGetHigher(T value, out T higher)

Parameters

value T

The reference value. Must not be null.

higher T

When this method returns true, the next-higher element.

Returns

bool

true if a higher element exists; otherwise, false.

Exceptions

ArgumentNullException

value is null.

TryGetLower(T, out T)

Attempts to get the greatest element strictly less than value.

public bool TryGetLower(T value, out T lower)

Parameters

value T

The reference value. Must not be null.

lower T

When this method returns true, the next-lower element.

Returns

bool

true if a lower element exists; otherwise, false.

Exceptions

ArgumentNullException

value is null.

TryGetMax(out T)

Attempts to get the largest element in the set.

public bool TryGetMax(out T max)

Parameters

max T

When this method returns true, the maximum element.

Returns

bool

true if the set is non-empty; otherwise, false.

TryGetMin(out T)

Attempts to get the smallest element in the set.

public bool TryGetMin(out T min)

Parameters

min T

When this method returns true, the minimum element.

Returns

bool

true if the set is non-empty; otherwise, false.

UnionWith(IEnumerable<T>)

Modifies the current set so that it contains every element that is present in either this set or other.

public void UnionWith(IEnumerable<T> other)

Parameters

other IEnumerable<T>

The collection to union with. Must not be null.

Remarks

Adds element-at-a-time - O(m log(n + m)) for m elements in other.

Exceptions

ArgumentNullException

other is null.

Explicit Interface Implementations

ICollection<T>.Add(T)

Adds item via the Add(T) contract.

void ICollection<T>.Add(T item)

Parameters

item T

The item to add.

Remarks

Discards the boolean result of Add(T); callers that need to detect a duplicate-add should invoke the typed Add(T) overload directly.

IEnumerable<T>.GetEnumerator()

Returns an enumerator that iterates through the collection.

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

Returns

IEnumerator<T>

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

ProductVersions
.NET8, 10