Runtime: Consider creating an IndexSet Type

Created on 10 Sep 2019  路  14Comments  路  Source: dotnet/runtime

Now that C# 8 has Ranges, perhaps it is time to consider adding an "IndexSet" type. An IndexSet is a sorted collection of unique, unsigned, non-contiguous integers, generally represented as Ranges. For ex: The following IndexSet contains 260 integers in 3 Ranges.
IndexSet anIndexSet = { [0..100], [150..300], [1000..1010] }

This is potentially useful in a number of applications. For ex: Http response codes in the 2xx range are usually a success of some kind. A call such as HttpResponseSuccessIndexSet.Contains(210) is trivial to do with an IndexSet. An IndexSet can also be used to store indices into other data structures. Other examples would be to return a set of Ranges from a 1D/2D matrix, return a set of rows from a table, Ranges of enum values etc.

Rationale
Compared to storing entire sets of integers in a dictionary, an IndexSet:
1. Uses less memory
2. Can efficiently answer questions about intersections and membership
3. Can efficiently return an index that is greater/equal/lesser than a specified index
4. Always has the same ordering(sorted) => supports iteration over the indices potentially applying delegates

Note: An IndexSet is NOT efficient when storing arbitrary integers because each index will be stored as a Range
Note: An IndexSet also stores only 1 instance of an index

An API Sketch
```C#
public class ReadOnlyIndexSet : IEnumerable
{
public ReadOnlyIndexSet(Range range) { }

    public ReadOnlyIndexSet(ReadOnlyIndexSet indexSet) { }

    /// <summary>
    /// Returns the number of integers in the current ReadOnlyIndexSet
    /// </summary>
    public int Count() => throw new NotImplementedException();

    /// <summary>
    /// Returns the number of integers in the given range
    /// </summary>
    /// <param name="range"></param>
    /// <returns></returns>
    public int Count(Range range) => throw new NotImplementedException();

    public Range this[int index]
    {
        get;
    }

    public bool Contains(int value);

    /// <summary>
    /// Returns true if this ReadOnlyIndexSet contains all the integers in other
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public bool Contains(ReadOnlyIndexSet other) => throw new NotImplementedException();

    public bool Contains(Range other) => throw new NotImplementedException();

    /// <summary>
    /// Returns true if this ReadOnlyIndexSet intersects any of the integers in other
    /// </summary>
    /// <param name="other"></param>
    /// <returns></returns>
    public bool Intersects(ReadOnlyIndexSet other) => throw new NotImplementedException();

    public bool Intersects(Range other) => throw new NotImplementedException();

    public int Start { get; }
    public int End { get; }

    public int IndexLessThanOrEqualTo(int value);
    public int IndexGreaterThanOrEqualTo(int value);
    public int IndexLessThan(int value);
    public int IndexGreaterThan(int value);

 }

public class IndexSet : ReadOnlyIndexSet
{
    public IndexSet(Range range) : base(range) { }

    public void Add(int index);

    public void Add(ReadOnlyIndexSet indexSet);

    public void Add(Range range);

    public void Remove(int index);

    public void Remove(ReadOnlyIndexSet indexSet);

    public void Remove(Range range);

    public void RemoveAll();
}

Example:

```C# <code>
 List<string> cities = new List<string>() { "New York", "Vancouver", "Seattle", "Frankfurt", "Paris", "Chicago", "Vienna" };

            IndexSet americanCities = new IndexSet(new Range(0, 2));
            americanCities.Add(5);

            // Queries
            americanCities.Contains(1..2); // Will return true
            americanCities.Contains(2..5); // Will return false
            americanCities.Intersects(2..5); // Will return true
            americanCities.IndexGreaterThan(2); // Will return 5

I've tried to keep the number of APIs minimal. For ex: APIs around enumeration of the underlying indices can be added, but I figured they are easy enough to achieve with the currently proposed APIs.

Tagging @safern since he owns Systems.Collections.Specialized and this feels like a good fit. Looking forward to hearing the community's thoughts around this.

Discussion

  1. What's the advantage of an IndexSet over SortedSet?
    Memory essentially. As the number of indexes(stored as Ranges) increases, an IndexSet uses lesser memory compared to a SortedSet. An IndexSet is more specialized than a SortedSet/HashSet/Set of Range because any modifications work on the underlying ranges. Hopefully, the following examples make it clear:
    IndexSet myIndexSet = new IndexSet() { [1..4], [6..8] }; myIndexSet.Add(5); // myIndexSet will now hold {[1..8]} myIndexSet.Add([5..9]); // myIndexSet will hold {[1..9]}
    If I instead used a Set, for the same ops, depending on the Set comparator, I might end up with:
    Set<Range> myset = new Set<Range>() { [1..4], [6..8] }; myset.Add(5); // myset will now hold {[1..4], [5], [6..8]} myset.Add([5..9]); //myset will hold {[1..4], [5], [5..9], [6..8]}?
    Removing an index from an IndexSet makes the difference more apparent:
    IndexSet myIndexSet = new IndexSet() { [1..4], [6..8] }; myIndexSet.Remove(2); // myIndexSet will now hold {[1], [3..4], [6..8]}
    With a Set, to remove from the middle of a Range, I'd have to first remove the range containing 2 i.e. [1..4] from the set, split it into [1] and [3..4], and then re-add them to the Set.
api-suggestion area-System.Collections
Source
picture pgovind
😕1

Most helpful comment

What's the advantage of an IndexSet over SortedSet?

I added a discussion section to adddress the question.

I see. So this is basically just a range which can support holes?

picture FiniteReality on 13 Sep 2019
👍2

All 14 comments

What's the advantage of an IndexSet over SortedSet<Range>? The only thing I see being a possible advantage would be to use a bitmap to implement it, but those have lots of downsides which need fairly specific use-cases to make useful. (e.g. universe size, memory usage, and when they're sparse)

FiniteReality picture FiniteReality on 12 Sep 2019

What's the advantage of an IndexSet over SortedSet?

I added a discussion section to adddress the question.

pgovind picture pgovind on 13 Sep 2019

cc @ahsonkhan and @bartonjs for their take.

danmosemsft picture danmosemsft on 13 Sep 2019

What's the advantage of an IndexSet over SortedSet?

I added a discussion section to adddress the question.

I see. So this is basically just a range which can support holes?

FiniteReality picture FiniteReality on 13 Sep 2019
👍2

I see. So this is basically just a range which can support holes?

Yup

pgovind picture pgovind on 24 Sep 2019

Where do you see this type being used?

If it's just a mathy data structure it probably doesn't meet the general applicability for being part of the core framework; but instead seems like it'd be more useful in a standalone offering.

bartonjs picture bartonjs on 24 Sep 2019

What's the exact bar to meet to be a part of the core framework? For ex: If I was, say, designing a UI combo-box, and wanted to return the items that were selected, I could return it as an IndexSet. It would save some bytes when consecutive indices are selected. Would something like that meet the bar?
Also, we're already using it in our Regex code. ParseRegexNode uses a SingleRange internally, and we've defined functions to collapse multiple SingleRanges essentially resulting in an IndexSet.

pgovind picture pgovind on 4 Nov 2019
👍1

I implemented one of these with a SIMD b+tree like ~15 years ago 馃槉. It seems niche, lets get some good examples up for this.

scalablecory picture scalablecory on 14 Nov 2019

IndexSet should have UnionWith etc.

scalablecory picture scalablecory on 14 Nov 2019

Just adding a note that https://github.com/dotnet/corefx/issues/26528 is very similar to this proposal. dotnet/runtime#934 is an extension method only for Span, whereas an IndexSet makes sense across all collections that can be indexed. An IndexSet is more general than the SpanSplitEnumerator that dotnet/runtime#934 asks for in that sense. However, I do recognize that SpanSplitEnumerator makes sense for when non-allocation is important at the expense of losing the ability to mutate the underlying Ranges.

pgovind picture pgovind on 18 Nov 2019

cc @GrabYourPitchforks

pgovind picture pgovind on 18 Nov 2019

Coincidentally, I actually have a use case for this myself now; I have a commands library which breaks arguments into individual tokens (hello world is translated into hello and world for example) - a type like this would be an excellent way to avoid allocations until absolutely necessary by just passing through the raw input string and a list of indices, as well as making argument parsing easier. (Such as combining arguments, manual parsing, etc.)

FiniteReality picture FiniteReality on 6 Dec 2019
👍1 
public ReadOnlyIndexSet(Range range) { }
public bool Contains(int value);

What would new ReadOnlyIndexSet(5..^5).Contains(10) return?

KalleOlaviNiemitalo picture KalleOlaviNiemitalo on 21 Jul 2020

I think @KalleOlaviNiemitalo's comment demonstrates why we wouldn't want to use Range in this type. This seems very similar to https://github.com/dotnet/runtime/issues/417, which considered Range.Contains(Index) and was ultimately rejected due to its ambiguity.

If you instead used a custom data structure such as the following, it would eliminate this problem. (Both _start_ and _end_ would need to be inclusive, otherwise you can't represent int.MinValue or int.MaxValue.)

public struct IndexSetEntry
{
    public int StartInclusive { get; set; }
    public int EndInclusive { get; set; }
}

Assuming the ambiguity is addressed, do you think this could be used outside the Regex class? Since that class is perf-sensitive I'm curious as to whether they'd stick with their list-based implementation even if we had a friendlier API.

GrabYourPitchforks picture GrabYourPitchforks on 23 Jul 2020
Was this page helpful?
0 / 5 - 0 ratings

Related issues

GitAntoinee picture GitAntoinee  路  3Comments
noahfalk picture noahfalk  路  3Comments
v0l picture v0l  路  3Comments
omajid picture omajid  路  3Comments
jzabroski picture jzabroski  路  3Comments