C# 8.0 in-depth: Understanding index and range, and working with LINQ and IEnumerable<T>

C# 8.0 introduces index and range for array. This part discussed the index and range types, syntax, compilation, and how to apply them with LINQ for any type that implements IEnumerable<T>.

Index and Range types and C# syntax

The System.Index and System.Range structures are introduced to the new .NET Standard. Index is a wrapper of int index value (non-negative int means index from start, negative int means index from the end), and Range is a tuple of start Index and end Index:

public readonly struct Index : IEquatable<Index>
{
    private readonly int _value;

    public Index(int value, bool fromEnd)
    {
        if (value < 0)
        {
            ThrowHelper.ThrowValueArgumentOutOfRange_NeedNonNegNumException();
        }
        this._value = fromEnd ? ~value : value;
    }

    public int Value => this._value >= 0 ? this._value : ~this._value;

    public bool FromEnd => _value < 0;

    public static implicit operator Index(int value) => new Index(value, false);

    // Other members.
}

public readonly struct Range : IEquatable<Range>
{
    private Range(Index start, Index end)
    {
        this.Start = start; this.End = end;
    }

    public Index Start { get; }

    public Index End { get; }

    public static Range Create(Index start, Index end) => 
        new Range(start, end);
    
    public static Range All() => 
        new Range(new Index(0, false), new Index(0, true));

    // Other members.
}

C# 8.0 introduces the index and range syntax:

Index index1 = 1; // Index 1 from start.
Index index2 = ^2; // Index 2 from end.
Range range1 = 1..10; // Start index is 1 from start, end index is 10 from start.
Range range2 = 10..^5; // Start index is 1 from start, end index is 5 from end.
Range range3 = ^10..; // Start index is 10 from end, end index is 0 from end.
Range range4 = ..; // Start index is 0 from start, end index is 0 from end.

These are syntactic sugars, which are compiled to:

Index index3 = 1;
Index index2 = new Index(2, true);
Range range5 = Range.Create(1, 10);
Range range4 = Range.Create(10, new Index(5, true));
Range range3 = Range.FromStart(new Index(10, true));
Range range2 = Range.All();

Index and Range for array

C# introduces syntactic sugars to enable Index with array:

int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int value = array[^1];

It is compiled to normal int indexer access:

int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Index index = new Index(1, true);
int value = index.FromEnd ? array[array.Length - index.Value] : array[index.Value];

And this is the range syntactic sugar for array slice:

int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] slice = array[^9..7];

It is compiled to array copy:

int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Range range = Range.Create(new Index(9, true), 7);
int startIndex = range.Start.FromEnd ? array.Length - range.Start.Value : range.Start.Value;
int rangeLength = (range.End.FromEnd ? array.Length - range.End.Value : range.End.Value) - startIndex;
int[] slice = new int[rangeLength];
Array.Copy(sourceArray: array, sourceIndex: startIndex, destinationArray: slice, destinationIndex: 0, length: rangeLength);

LINQ queries - Index and Range for IEnumerable<T>

Currently (v3.0.0-preview2/SDK 3.0.100-preview-010184), the index and range work with array, and do not work with other types, like List<T>. It is natural and convenient to support index and range in LINQ, so they can work with any type that implements IEnumerable<T>. The goals of these LINQ APIs are:

  • Use index to locate an element in sequence, use range to slice sequence. The usage is the same as index/range for array, but with deferred execution for slice with range.
  • Use range to start fluent LINQ query.

This enables the index and range to work with any type that implements IEnumerable<T>.

LINQ already has ElementAt(int index) and ElementOrDefault(int index) query operator. It would be natural to have a overload for System.Index: ElementAt(Index index) and ElementOrDefault(Index index), and a new method ElementsIn(Range range), so that LINQ can seamlessly work with C# 8.0:

Index index = ...;
var element1 = source1.ElementAt(index);
var element2 = source2.ElementAtOrDefault(^ 5);
Range range = ...;
var slice1 = source3.ElementsIn(range);
var slice2 = source4.ElementsIn(2..^ 2)
var slice2 = source5.ElementsIn(^ 10..);

The following Range overload and AsEnumerable overload for System.Range convert it to a sequence, so that LINQ query can be started fluently from c# range:

Index index = ...;
var element1 = source1.ElementAt(index);
var element2 = source2.ElementAtOrDefault(^ 5);
Range range = ...;
var slice1 = source3.ElementsIn(range);
var slice2 = source4.ElementsIn(2..^ 2)
var slice2 = source5.ElementsIn(^ 10..);

APIs

For LINQ to Objects, ideally:

namespace System.Linq
{
    public static partial class Queryable
    {
        public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, Index index) { throw null; }

        public static TSource ElementAtOrDefault<TSource>(this IEnumerable<TSource> source, Index index) { throw null; }

        public static IEnumerable<TSource> ElementsIn<TSource>(this IEnumerable<TSource> source, Range range) { throw null; }

        public static IEnumerable<TSource> Range<TSource>(Range range) { throw null; }

        public static IEnumerable<TSource> AsEnumerable<TSource>(this Range source) { throw null; }
    }
}

For remote LINQ, ideally:

namespace System.Linq
{
    public static partial class Queryable
    {
        public static TSource ElementAt<TSource>(this IQueryable<TSource> source, Index index) { throw null; }

        public static TSource ElementAtOrDefault<TSource>(this IQueryable<TSource> source, Index index) { throw null; }

        public static IQueryable<TSource> ElementsIn<TSource>(this IQueryable<TSource> source, Range range) { throw null; }
    }
}

Implementation details

These APIs' implementation is self-contained so that the code can be just copied to use.

The implementation of ElementAt(Index), ElementOrDefault(Index) and ElementsIn(Range) for IQueryable<T> is straightforward. They just create an expression tree.

internal static class QueryableExtensions
{
    public static TSource ElementAt<TSource>(this IQueryable<TSource> source, Index index)
    {
        if (source == null)
            // throw Error.ArgumentNull(nameof(source));
            throw new ArgumentNullException(nameof(source));
        return source.Provider.Execute<TSource>(
            Expression.Call(
                null,
                CachedReflectionInfo.ElementAt_TSource_2(typeof(TSource)),
                source.Expression, Expression.Constant(index)
                ));
    }

    public static TSource ElementAtOrDefault<TSource>(this IQueryable<TSource> source, Index index)
    {
        if (source == null)
            // throw Error.ArgumentNull(nameof(source));
            throw new ArgumentNullException(nameof(source));
        return source.Provider.Execute<TSource>(
            Expression.Call(
                null,
                CachedReflectionInfo.ElementAtOrDefault_TSource_2(typeof(TSource)),
                source.Expression, Expression.Constant(index)
                ));
    }

    public static IQueryable<TSource> ElementsIn<TSource>(this IQueryable<TSource> source, Range range)
    {
        if (source == null)
            // throw Error.ArgumentNull(nameof(source));
            throw new ArgumentNullException(nameof(source));

        return source.Provider.CreateQuery<TSource>(
            Expression.Call(
                null,
                CachedReflectionInfo.ElementsIn_TSource_2(typeof(TSource)),
                source.Expression, Expression.Constant(range)));
    }
}

internal static class CachedReflectionInfo
{
    private static MethodInfo s_ElementAt_TSource_2;

    public static MethodInfo ElementAt_TSource_2(Type TSource) =>
         (s_ElementAt_TSource_2 ??
         (s_ElementAt_TSource_2 = new Func<IQueryable<object>, Index, object>(QueryableExtensions.ElementAt).GetMethodInfo().GetGenericMethodDefinition()))
          .MakeGenericMethod(TSource);

    private static MethodInfo s_ElementAtOrDefault_TSource_2;

    public static MethodInfo ElementAtOrDefault_TSource_2(Type TSource) =>
         (s_ElementAtOrDefault_TSource_2 ??
         (s_ElementAtOrDefault_TSource_2 = new Func<IQueryable<object>, Index, object>(QueryableExtensions.ElementAtOrDefault).GetMethodInfo().GetGenericMethodDefinition()))
          .MakeGenericMethod(TSource);

    private static MethodInfo s_ElementsIn_TSource_2;

    public static MethodInfo ElementsIn_TSource_2(Type TSource) =>
         (s_ElementsIn_TSource_2 ??
         (s_ElementsIn_TSource_2 = new Func<IQueryable<object>, Range, IQueryable<object>>(QueryableExtensions.ElementsIn).GetMethodInfo().GetGenericMethodDefinition()))
          .MakeGenericMethod(TSource);
}

These methods for IEnumerable<T> are straightforward as well, I just followed the behavior and exceptions of array with range. See unit tests https://github.com/Dixin/CodeSnippets/blob/master/Linq.Range/Linq.Range.Tests/ElementsInTests.cs.

ElementAt(Index) and ElementAtOrDefault(Index):

public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, Index index)
{
    if (source == null)
    {
        // ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
        throw new ArgumentNullException(nameof(source));
    }

    if (!index.FromEnd)
    {
        return source.ElementAt(index.Value);
    }

    int indexFromEnd = index.Value;
    if (indexFromEnd > 0)
    {
        if (source is IList<TSource> list)
        {
            return list[list.Count - indexFromEnd];
        }

        using (IEnumerator<TSource> e = source.GetEnumerator())
        {
            if (e.MoveNext())
            {
                Queue<TSource> queue = new Queue<TSource>();
                queue.Enqueue(e.Current);
                while (e.MoveNext())
                {
                    if (queue.Count == indexFromEnd)
                    {
                        queue.Dequeue();
                    }

                    queue.Enqueue(e.Current);
                }

                if (queue.Count == indexFromEnd)
                {
                    return queue.Dequeue();
                }
            }
        }
    }

    // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index);
    throw new ArgumentOutOfRangeException(nameof(index));
    return default!;
}

public static TSource ElementAtOrDefault<TSource>(this IEnumerable<TSource> source, Index index)
{
    if (source == null)
    {
        // ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
        throw new ArgumentNullException(nameof(source));

    }

    if (!index.FromEnd)
    {
        return source.ElementAtOrDefault(index.Value);
    }

    int indexFromEnd = index.Value;
    if (indexFromEnd > 0)
    {
        if (source is IList<TSource> list)
        {
            int count = list.Count;
            if (count >= indexFromEnd)
            {
                return list[count - indexFromEnd];
            }
        }

        using (IEnumerator<TSource> e = source.GetEnumerator())
        {
            if (e.MoveNext())
            {
                Queue<TSource> queue = new Queue<TSource>();
                queue.Enqueue(e.Current);
                while (e.MoveNext())
                {
                    if (queue.Count == indexFromEnd)
                    {
                        queue.Dequeue();
                    }

                    queue.Enqueue(e.Current);
                }

                if (queue.Count == indexFromEnd)
                {
                    return queue.Dequeue();
                }
            }
        }
    }

    return default!;
}

ElementsIn(Range):

public static IEnumerable<TSource> ElementsIn<TSource>(this IEnumerable<TSource> source, Range range)
{
    if (source == null)
    {
        // ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
        throw new ArgumentNullException(nameof(source));
    }

    return ElementsInIterator(source, range);
}

private static IEnumerable<TSource> ElementsInIterator<TSource>(IEnumerable<TSource> source, Range range)
{
    Index start = range.Start;
    Index end = range.End;

    if (source is IList<TSource> list)
    {
        int count = list.Count;
        if (count == 0 && range.Equals(System.Range.All()))
        {
            yield break;
        }

        int firstIndex = start.FromEnd ? count - start.Value : start.Value;
        int lastIndex = (end.FromEnd ? count - end.Value : end.Value) - 1;
        if (lastIndex < firstIndex - 1)
        {
            // ThrowHelper.ThrowOverflowException();
            throw new OverflowException(); // Following the behavior of array with range.
        }

        if (firstIndex < 0 || lastIndex < 0)
        {
            // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
            throw new ArgumentOutOfRangeException(nameof(range)); // Following the behavior of array with range.
        }

        if (firstIndex >= count || lastIndex >= count)
        {
            // ThrowHelper.ThrowArgumentException(ExceptionArgument.range);
            throw new ArgumentException(nameof(range)); // Following the behavior of array with range.
        }

        for (int currentIndex = firstIndex; currentIndex <= lastIndex; currentIndex++)
        {
            yield return list[currentIndex];
        }
        yield break;
    }

    using (IEnumerator<TSource> e = source.GetEnumerator())
    {
        int currentIndex = -1;
        if (start.FromEnd)
        {
            if (!e.MoveNext())
            {
                const int count = 0;
                int firstIndex = count - start.Value;
                int lastIndex = (end.FromEnd ? count - end.Value : end.Value) - 1;
                if (lastIndex < firstIndex - 1)
                {
                    // ThrowHelper.ThrowOverflowException();
                    throw new OverflowException(); // Following the behavior of array with range.
                }

                // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
                throw new ArgumentOutOfRangeException(nameof(range));
            }
            else
            {
                Queue<TSource> queue = new Queue<TSource>();
                queue.Enqueue(e.Current);
                currentIndex++;

                int takeLastCount = start.Value;
                while (e.MoveNext())
                {
                    if (queue.Count == takeLastCount)
                    {
                        queue.Dequeue();
                    }

                    queue.Enqueue(e.Current);
                    currentIndex++;
                }

                if (queue.Count < takeLastCount)
                {
                    // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
                    throw new ArgumentOutOfRangeException(nameof(range));
                }

                int firstIndex = currentIndex + 1 - takeLastCount;
                int lastIndex = end.FromEnd ? currentIndex - end.Value : end.Value - 1;
                if (lastIndex < firstIndex - 1)
                {
                    // ThrowHelper.ThrowOverflowException();
                    throw new OverflowException(); // Following the behavior of array with range.
                }

                for (int index = firstIndex; index <= lastIndex; index++)
                {
                    yield return queue.Dequeue();
                }
            }
        }
        else
        {
            int firstIndex = start.Value;
            if (!e.MoveNext())
            {
                if (range.Equals(System.Range.All()))
                {
                    yield break;
                }

                const int count = 0;
                int lastIndex = (end.FromEnd ? count - end.Value : end.Value) - 1;
                if (lastIndex < firstIndex - 1)
                {
                    // ThrowHelper.ThrowOverflowException();
                    throw new OverflowException(); // Following the behavior of array with range.
                }
                // ThrowHelper.ThrowArgumentException(ExceptionArgument.range);
                throw new ArgumentException(nameof(range)); // Following the behavior of array with range.
            }

            currentIndex++;
            while (currentIndex < firstIndex && e.MoveNext())
            {
                currentIndex++;
            }

            if (currentIndex != firstIndex)
            {
                // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
                throw new ArgumentOutOfRangeException(nameof(range));
            }

            if (end.FromEnd)
            {
                int skipLastCount = end.Value;
                if (skipLastCount > 0)
                {
                    Queue<TSource> queue = new Queue<TSource>();
                    do
                    {
                        if (queue.Count == skipLastCount)
                        {
                            yield return queue.Dequeue();
                        }

                        queue.Enqueue(e.Current);
                        currentIndex++;
                    }
                    while (e.MoveNext());
                }
                else
                {
                    do
                    {
                        yield return e.Current;
                        currentIndex++;
                    }
                    while (e.MoveNext());
                }

                if (firstIndex + skipLastCount > currentIndex)
                {
                    // ThrowHelper.ThrowOverflowException();
                    throw new OverflowException(); // Following the behavior of array with range.
                }
            }
            else
            {
                int lastIndex = end.Value - 1;
                if (lastIndex < firstIndex - 1)
                {
                    // ThrowHelper.ThrowOverflowException();
                    throw new OverflowException(); // Following the behavior of array with range.
                }

                if (lastIndex == firstIndex - 1)
                {
                    yield break;
                }

                yield return e.Current;
                while (currentIndex < lastIndex && e.MoveNext())
                {
                    currentIndex++;
                    yield return e.Current;
                }

                if (currentIndex != lastIndex)
                {
                    // ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.range);
                    throw new ArgumentOutOfRangeException(nameof(range));
                }
            }
        }
    }
}

For Range(Range) and AsEnumerable(Range), the question is: what does Range's start Index and end Index mean when the index is from the end? For example, 10..20 can be easily converted to a sequence of 10, 11,12, ... 19, but how about ^20...^10? In my current implementation, regarding Index's value can be from 0 to int.MaxValue, I assume a virtual "full range" 0..2147483648, and any Range instance is a slice of that "full range". So:

  • Ranges .. and 0.. and ..^0 and 0..^0 are converted to "full sequence" 0, 1, .. 2147483647
  • Range 100..^47 is converted to sequence 100, 101, .. 2147483600
  • Range ^48..^40 is converted to sequence 2147483600, 2147483601 .. 2147483607
  • Range 10..10 is converted to empty sequence

etc.

public static IEnumerable<int> Range(Range range)
{
    Index startIndex = range.Start;
    Index endIndex = range.End;
    int firstValue = startIndex.FromEnd ? int.MaxValue - startIndex.Value + 1 : startIndex.Value;
    int lastValue = endIndex.FromEnd ? int.MaxValue - endIndex.Value : endIndex.Value - 1;
    if (lastValue < firstValue - 1)
    {
        // ThrowHelper.ThrowOverflowException();
        throw new OverflowException(); // Following the behavior of array with range.
    }

    if (lastValue == firstValue - 1)
    {
        return Enumerable.Empty<int>();
    }

    return RangeIterator(firstValue, lastValue);
}

private static IEnumerable<int> RangeIterator(int firstValue, int lastValue)
{
    for (int value = firstValue; value <= lastValue; value = checked(value + 1))
    {
        yield return value;
        if (value == int.MaxValue)
        {
            yield break;
        }
    }
}

public static IEnumerable<int> AsEnumerable(this Range range)
{
    int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int[] slice = array[^ 9..7];
    return Range(range);
}

See unit tests of AsEnumerable(Range) https://github.com/Dixin/CodeSnippets/blob/master/Linq.Range/Linq.Range.Tests/AsEnumerableTests.cs.

4 Comments

  • I have the following code:

    var accidents = text.Skip(NumberOfAccidentsLine + 1).Take(numberOfAccidentsInFile).ToArray();
    where accidents is an array of strings.

    I want to make a Linq transformation from the string array to an array of Accident objects as follows:

    return accidents.Select(t => new Accident() {Id = i, Name = t.Replace("\"", string.Empty)}).ToArray();
    How do I retrieve the index i from the accidents array using Linq or do I have to go old school?

    #c# #linq #ienumerable

  • This is a great article on understanding the new features of C# 8 and LINQ. I also found a great article on <a href="https://systemoutofmemory.com/blogs/the-programmer-blog/c-sharp-iterate-dictionary">C# iterate dictionary which explains how to iterate dictionaries using LINQ. Let me know what you think.

    Vihaan


  • You're so awesome! I do not believe I've read through anything like that before. So nice to find somebody with unique thoughts on this subject matter. Seriously.. thank you for starting this up. This web site is something that is needed on the internet, someone with a little originality!

  • I like reading through a post that can make people think. Also, thank you for allowing for me to comment!

Add a Comment

As it will appear on the website

Not displayed

Your website