Table of Contents

RangeSet<T> Class

Definition

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

Represents a sorted set of non-overlapping half-open ranges.

public sealed class RangeSet<T> : IReadOnlyCollection<Range<T>>, IEnumerable<Range<T>>, IEnumerable where T : IComparable<T>

Type Parameters

T

The comparable endpoint type.

Inheritance
RangeSet<T>
Implements
Inherited Members
Extension Methods

Examples

// Track disjoint blocks of allocated row IDs. Adjacent and overlapping inserts merge automatically.
var allocated = new RangeSet<int>();
allocated.Add(  0,  10);   // [0, 10)
allocated.Add( 20,  30);   // [20, 30)
allocated.Add(  5,  25);   // merges all three into the single range [0, 30)

Console.WriteLine(allocated.Count);          // 1
Console.WriteLine(allocated.Contains(15));   // true
allocated.Remove(10, 20);                    // splits into [0, 10) and [20, 30)

Remarks

Ranges are stored in two compact parallel arrays - one for the inclusive start of each range and one for the exclusive end. The arrays are kept sorted by start endpoint, and adjacent or overlapping ranges are merged on insertion.

Ranges use half-open semantics: [startInclusive, endExclusive).

This type is not thread-safe.

Constructors

RangeSet()

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

public RangeSet()

RangeSet(IComparer<T>?)

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

public RangeSet(IComparer<T>? comparer)

Parameters

comparer IComparer<T>

The endpoint comparer, or null to use Default.

RangeSet(IEnumerable<Range<T>>, IComparer<T>?)

Initializes a new instance of the RangeSet<T> class containing the specified ranges.

public RangeSet(IEnumerable<Range<T>> ranges, IComparer<T>? comparer = null)

Parameters

ranges IEnumerable<Range<T>>

The ranges to add. Must not be null.

comparer IComparer<T>

The endpoint comparer, or null to use Default.

Exceptions

ArgumentNullException

ranges is null.

Properties

Capacity

Gets the allocated range capacity.

public int Capacity { get; }

Property Value

int

The current allocated capacity of the underlying storage.

Comparer

Gets the comparer used to order range endpoints.

public IComparer<T> Comparer { get; }

Property Value

IComparer<T>

The active endpoint comparer.

Count

Gets the number of stored ranges.

public int Count { get; }

Property Value

int

The number of ranges currently stored in the set.

this[int]

Gets the range at the specified sorted index.

public Range<T> this[int index] { get; }

Parameters

index int

The zero-based range index.

Property Value

Range<T>

The range at index.

Exceptions

ArgumentOutOfRangeException

index is negative or greater than or equal to Count.

Methods

Add(Range<T>)

Adds the specified range to the set, merging any overlapping or adjacent ranges.

public bool Add(Range<T> range)

Parameters

range Range<T>

The range to add.

Returns

bool

true if the set was changed; false if the range was already fully covered and the set was left unchanged.

Add(T, T)

Adds a half-open range to the set, merging any overlapping or adjacent ranges.

public bool Add(T startInclusive, T endExclusive)

Parameters

startInclusive T

The inclusive start.

endExclusive T

The exclusive end.

Returns

bool

true if the set was changed; false if the range was already fully covered and the set was left unchanged.

Exceptions

ArgumentNullException

startInclusive or endExclusive is null.

ArgumentException

startInclusive is greater than or equal to endExclusive.

Clear()

Removes all ranges from the set.

public void Clear()

Contains(T)

Determines whether the specified value falls inside any stored range.

public bool Contains(T value)

Parameters

value T

The value to test. Must not be null.

Returns

bool

true if the value is contained; otherwise, false.

Exceptions

ArgumentNullException

value is null.

Contains(T, T)

Determines whether the specified range is fully contained in this set.

public bool Contains(T startInclusive, T endExclusive)

Parameters

startInclusive T

The inclusive start.

endExclusive T

The exclusive end.

Returns

bool

true if the range is fully contained; otherwise, false.

Exceptions

ArgumentNullException

startInclusive or endExclusive is null.

ArgumentException

startInclusive is greater than or equal to endExclusive.

EnsureCapacity(int)

Ensures that the set can hold at least the specified number of ranges without reallocating.

public int EnsureCapacity(int capacity)

Parameters

capacity int

The desired capacity.

Returns

int

The current capacity.

Exceptions

ArgumentOutOfRangeException

capacity is negative.

Except(RangeSet<T>)

Returns a new set containing the ranges in this set except those covered by another set.

public RangeSet<T> Except(RangeSet<T> other)

Parameters

other RangeSet<T>

The other set. Must not be null.

Returns

RangeSet<T>

A new RangeSet<T> containing the difference.

Exceptions

ArgumentNullException

other is null.

GetEnumerator()

Returns an enumerator that iterates through the stored ranges in ascending order.

public RangeSet<T>.Enumerator GetEnumerator()

Returns

RangeSet<T>.Enumerator

An RangeSet<T>.Enumerator over the stored ranges.

Intersect(RangeSet<T>)

Returns a new set containing the intersection of this set and another set.

public RangeSet<T> Intersect(RangeSet<T> other)

Parameters

other RangeSet<T>

The other set. Must not be null.

Returns

RangeSet<T>

A new RangeSet<T> containing the intersection.

Exceptions

ArgumentNullException

other is null.

Overlaps(T, T)

Determines whether the specified range overlaps any stored range.

public bool Overlaps(T startInclusive, T endExclusive)

Parameters

startInclusive T

The inclusive start.

endExclusive T

The exclusive end.

Returns

bool

true if the range overlaps a stored range; otherwise, false.

Exceptions

ArgumentNullException

startInclusive or endExclusive is null.

ArgumentException

startInclusive is greater than or equal to endExclusive.

Remove(Range<T>)

Removes the specified range from the set.

public bool Remove(Range<T> range)

Parameters

range Range<T>

The range to remove.

Returns

bool

true if the set was changed; otherwise, false.

Remove(T, T)

Removes the specified half-open range from the set, trimming or splitting overlapping ranges as needed.

public bool Remove(T startInclusive, T endExclusive)

Parameters

startInclusive T

The inclusive start.

endExclusive T

The exclusive end.

Returns

bool

true if the set was changed; otherwise, false.

Exceptions

ArgumentNullException

startInclusive or endExclusive is null.

ArgumentException

startInclusive is greater than or equal to endExclusive.

ToArray()

Copies the stored ranges to a new array in ascending sorted order.

public Range<T>[] ToArray()

Returns

Range<T>[]

A new array containing the stored ranges.

Union(RangeSet<T>)

Returns a new set containing the union of this set and another set.

public RangeSet<T> Union(RangeSet<T> other)

Parameters

other RangeSet<T>

The other set. Must not be null.

Returns

RangeSet<T>

A new RangeSet<T> containing the union.

Exceptions

ArgumentNullException

other is null.

Explicit Interface Implementations

IEnumerable<Range<T>>.GetEnumerator()

Returns an enumerator that iterates through the collection.

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

Returns

IEnumerator<Range<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