Optimize the implementation of LINQ partitioning APIs

[Dixin]

My PR #48559 "Add LINQ APIs for Index and Range" was just merged, and this is a following up. @eiriktsarpalis @stephentoub

Background:

• LINQ internally use IPartition<T> to optimize the implementation of partitioning operators, like Take, Skip, ElementAt
• Later, more partitioning operators are added for LINQ, like TakeLast, SkipLast, Take(System.Range), ElementAt(System.Index). These new APIs are implemented by yield return.

Proposal

It is best to have an unified implementation of all the partitioning and element operators based on IPartition<T>.

Internal API changes

Current IPartition<T>:

interface IPartition<TSource>
{
 TSource? TryGetElementAt(int index, out bool found);
 IPartition<TSource> Take(int count);
 IPartition<TSource> Skip(int count);
 // Other members ...
}

1. Update IPartition<T> to support indexes from start or end:

interface IPartition<TSource>
{
 // New members.
 bool TryGetElementAt(int index, bool isIndexFromEnd, [MaybeNullWhen(false)] out TSource element);
 IPartition<TSource> Take(int startIndexInclusive, int endIndexExclusive, bool isStartIndexFromEnd, bool isEndIndexFromEnd);
 // Original members.
 TSource? TryGetElementAt(int index, out bool found)
 {
 found = TryGetElementAt(index, false, out TSource? element);
 return element;
 }
 IPartition<TSource> Take(int count) => Take(0, count, false, false);;
 IPartition<TSource> Skip(int count) => Take(count, 0, false, true);
 // Other members ...
}

2. Update all types that implement IPartition<T>. All optimization code should be in these types, not in the LINQ operators.
   • EmptyPartition<TElement>
   • ListPartition<TSource>
   • EnumerablePartition<TSource>
   • RangeIterator
   • RepeatIterator<TResult>
   • SelectArrayIterator<TSource, TResult>
   • SelectRangeIterator<TResult>
   • SelectListIterator<TSource, TResult>
   • SelectIListIterator<TSource, TResult>
   • SelectIPartitionIterator<TSource, TResult>
   • SelectListPartitionIterator<TSource, TResult>
   • OrderedPartition<TElement>
   • OrderedEnumerable<TElement, TKey>
3. Implement Enumerable.TakeIterator based on IPartition<T>, then use Enumerable.TakeIterator to implement Take, Skip, TakeLast, SkipLast, Take(System.Range).
4. Update ElementAt(System.Index) to utilize IPartition<T>TryGetElementAt

Then all partition and element APIs should be consolidated, optimized, consistent.

Tagging subscribers to this area: @eiriktsarpalis
See info in area-owners.md if you want to be subscribed.

Issue Details

---

My PR #48559 "Add LINQ APIs for Index and Range" was just merged, and this is a following up. @eiriktsarpalis @stephentoub

Background:

• LINQ internally use IPartition<T> to optimize the implementation of partitioning operators, like Take, Skip, ElementAt
• Later, more partitioning operators are added for LINQ, like TakeLast, SkipLast, Take(System.Range), ElementAt(System.Index). These new APIs are implemented by yield return.

Proposal

It is best to have an unified implementation of all the partitioning and element operators based on IPartition<T>.

Internal API changes

Current IPartition<T>:

interface IPartition<TSource>
{
 TSource? TryGetElementAt(int index, out bool found);
 IPartition<TSource> Take(int count);
 IPartition<TSource> Skip(int count);
 // Other members ...
}

1. Update IPartition<T> to support indexes from start or end:

interface IPartition<TSource>
{
 // New members.
 bool TryGetElementAt(int index, bool isIndexFromEnd, [MaybeNullWhen(false)] out TSource element);
 IPartition<TSource> Take(int startIndexInclusive, int endIndexExclusive, bool isStartIndexFromEnd, bool isEndIndexFromEnd);
 // Original members.
 TSource? TryGetElementAt(int index, out bool found)
 {
 found = TryGetElementAt(index, false, out TSource? element);
 return element;
 }
 IPartition<TSource> Take(int count) => Take(0, count, false, false);;
 IPartition<TSource> Skip(int count) => Take(count, 0, false, true);
 // Other members ...
}

2. Update all types that implement IPartition<T>. All optimization code should be in these types, not in the LINQ operators.
   • EmptyPartition<TElement>
   • ListPartition<TSource>
   • EnumerablePartition<TSource>
   • RangeIterator
   • RepeatIterator<TResult>
   • SelectArrayIterator<TSource, TResult>
   • SelectRangeIterator<TResult>
   • SelectListIterator<TSource, TResult>
   • SelectIListIterator<TSource, TResult>
   • SelectIPartitionIterator<TSource, TResult>
   • SelectListPartitionIterator<TSource, TResult>
   • OrderedPartition<TElement>
   • OrderedEnumerable<TElement, TKey>
3. Implement Enumerable.TakeIterator based on IPartition<T>, then use Enumerable.TakeIterator to implement Take, Skip, TakeLast, SkipLast, Take(System.Range).
4. Update ElementAt(System.Index) to utilize IPartition<T>TryGetElementAt

Then all partition and element APIs should be consolidated, optimized, consistent.

Author:	Dixin
Assignees:	-
Labels:	area-System.Linq, untriaged
Milestone:	-

[eiriktsarpalis]

This is related to #48634. Note that I did not add a Range method to IPartition<T> but combined the existing Take and Skip methods. Since most IPartition<T> implementations are slicing constructs, this might result in one intermediate allocation but should not have impact on enumeration performance.