|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
namespace System.Linq
{
public static partial class Enumerable
{
private abstract partial class OrderedIterator<TElement> : Iterator<TElement>, IOrderedEnumerable<TElement>
{
internal readonly IEnumerable<TElement> _source;
protected OrderedIterator(IEnumerable<TElement> source) => _source = source;
private protected int[] SortedMap(TElement[] buffer) => GetEnumerableSorter().Sort(buffer, buffer.Length);
internal int[] SortedMap(TElement[] buffer, int minIdx, int maxIdx) =>
GetEnumerableSorter().Sort(buffer, buffer.Length, minIdx, maxIdx);
internal abstract EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement>? next = null);
internal abstract CachingComparer<TElement> GetComparer(CachingComparer<TElement>? childComparer = null);
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
IOrderedEnumerable<TElement> IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, IComparer<TKey>? comparer, bool descending) =>
new OrderedIterator<TElement, TKey>(_source, keySelector, comparer, @descending, this);
public TElement? TryGetLast(Func<TElement, bool> predicate, out bool found)
{
CachingComparer<TElement> comparer = GetComparer();
using (IEnumerator<TElement> e = _source.GetEnumerator())
{
TElement value;
do
{
if (!e.MoveNext())
{
found = false;
return default;
}
value = e.Current;
}
while (!predicate(value));
comparer.SetElement(value);
while (e.MoveNext())
{
TElement x = e.Current;
if (predicate(x) && comparer.Compare(x, false) >= 0)
{
value = x;
}
}
found = true;
return value;
}
}
}
private sealed partial class OrderedIterator<TElement, TKey> : OrderedIterator<TElement>
{
private readonly OrderedIterator<TElement>? _parent;
private readonly Func<TElement, TKey> _keySelector;
private readonly IComparer<TKey> _comparer;
private readonly bool _descending;
private TElement[]? _buffer;
private int[]? _map;
internal OrderedIterator(IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey>? comparer, bool descending, OrderedIterator<TElement>? parent) :
base(source)
{
if (source is null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
}
if (keySelector is null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keySelector);
}
_parent = parent;
_keySelector = keySelector;
_comparer = comparer ?? Comparer<TKey>.Default;
_descending = descending;
}
private protected override Iterator<TElement> Clone() => new OrderedIterator<TElement, TKey>(_source, _keySelector, _comparer, _descending, _parent);
internal override EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement>? next)
{
// Special case the common use of string with default comparer. Comparer<string>.Default checks the
// thread's Culture on each call which is an overhead which is not required, because we are about to
// do a sort which remains on the current thread (and EnumerableSorter is not used afterwards).
IComparer<TKey> comparer = _comparer;
if (typeof(TKey) == typeof(string) && comparer == Comparer<string>.Default)
{
comparer = (IComparer<TKey>)StringComparer.CurrentCulture;
}
EnumerableSorter<TElement> sorter = new EnumerableSorter<TElement, TKey>(_keySelector, comparer, _descending, next);
if (_parent is not null)
{
sorter = _parent.GetEnumerableSorter(sorter);
}
return sorter;
}
internal override CachingComparer<TElement> GetComparer(CachingComparer<TElement>? childComparer)
{
CachingComparer<TElement> cmp = childComparer is null
? new CachingComparer<TElement, TKey>(_keySelector, _comparer, _descending)
: new CachingComparerWithChild<TElement, TKey>(_keySelector, _comparer, _descending, childComparer);
return _parent is not null ? _parent.GetComparer(cmp) : cmp;
}
public override bool MoveNext()
{
int state = _state;
Initialized:
if (state > 1)
{
Debug.Assert(_buffer is not null);
Debug.Assert(_map is not null);
Debug.Assert(_map.Length == _buffer.Length);
int[] map = _map;
int i = state - 2;
if ((uint)i < (uint)map.Length)
{
_current = _buffer[map[i]];
_state++;
return true;
}
}
else if (state == 1)
{
TElement[] buffer = _source.ToArray();
if (buffer.Length != 0)
{
_map = SortedMap(buffer);
_buffer = buffer;
_state = state = 2;
goto Initialized;
}
}
Dispose();
return false;
}
public override void Dispose()
{
_buffer = null;
_map = null;
base.Dispose();
}
}
/// <summary>An ordered enumerable used by Order/OrderDescending for Ts that are bitwise indistinguishable for any considered equal.</summary>
private sealed partial class ImplicitlyStableOrderedIterator<TElement> : OrderedIterator<TElement>
{
private readonly bool _descending;
private TElement[]? _buffer;
public ImplicitlyStableOrderedIterator(IEnumerable<TElement> source, bool descending) : base(source)
{
Debug.Assert(TypeIsImplicitlyStable<TElement>());
if (source is null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
}
_descending = descending;
}
private protected override Iterator<TElement> Clone() => new ImplicitlyStableOrderedIterator<TElement>(_source, _descending);
internal override CachingComparer<TElement> GetComparer(CachingComparer<TElement>? childComparer) =>
childComparer is null ?
new CachingComparer<TElement, TElement>(EnumerableSorter<TElement>.IdentityFunc, Comparer<TElement>.Default, _descending) :
new CachingComparerWithChild<TElement, TElement>(EnumerableSorter<TElement>.IdentityFunc, Comparer<TElement>.Default, _descending, childComparer);
internal override EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement>? next) =>
new EnumerableSorter<TElement, TElement>(EnumerableSorter<TElement>.IdentityFunc, Comparer<TElement>.Default, _descending, next);
public override bool MoveNext()
{
int state = _state;
TElement[]? buffer;
Initialized:
if (state > 1)
{
buffer = _buffer;
Debug.Assert(buffer is not null);
int i = state - 2;
if ((uint)i < (uint)buffer.Length)
{
_current = buffer[i];
_state++;
return true;
}
}
else if (state == 1)
{
buffer = _source.ToArray();
if (buffer.Length != 0)
{
Sort(buffer, _descending);
_buffer = buffer;
_state = state = 2;
goto Initialized;
}
}
Dispose();
return false;
}
public override void Dispose()
{
_buffer = null;
base.Dispose();
}
private static void Sort(Span<TElement> span, bool descending)
{
if (descending)
{
span.Sort(static (a, b) => Comparer<TElement>.Default.Compare(b, a));
}
else
{
span.Sort();
}
}
}
// A comparer that chains comparisons, and pushes through the last element found to be
// lower or higher (depending on use), so as to represent the sort of comparisons
// done by OrderBy().ThenBy() combinations.
private abstract class CachingComparer<TElement>
{
internal abstract int Compare(TElement element, bool cacheLower);
internal abstract void SetElement(TElement element);
}
private class CachingComparer<TElement, TKey> : CachingComparer<TElement>
{
protected readonly Func<TElement, TKey> _keySelector;
protected readonly IComparer<TKey> _comparer;
protected readonly bool _descending;
protected TKey? _lastKey;
public CachingComparer(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending)
{
_keySelector = keySelector;
_comparer = comparer;
_descending = descending;
}
internal override int Compare(TElement element, bool cacheLower)
{
TKey newKey = _keySelector(element);
int cmp = _descending ? _comparer.Compare(_lastKey, newKey) : _comparer.Compare(newKey, _lastKey);
if (cacheLower == cmp < 0)
{
_lastKey = newKey;
}
return cmp;
}
internal override void SetElement(TElement element)
{
_lastKey = _keySelector(element);
}
}
private sealed class CachingComparerWithChild<TElement, TKey> : CachingComparer<TElement, TKey>
{
private readonly CachingComparer<TElement> _child;
public CachingComparerWithChild(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending, CachingComparer<TElement> child)
: base(keySelector, comparer, descending)
{
_child = child;
}
internal override int Compare(TElement element, bool cacheLower)
{
TKey newKey = _keySelector(element);
int cmp = _descending ? _comparer.Compare(_lastKey, newKey) : _comparer.Compare(newKey, _lastKey);
if (cmp == 0)
{
return _child.Compare(element, cacheLower);
}
if (cacheLower == cmp < 0)
{
_lastKey = newKey;
_child.SetElement(element);
}
return cmp;
}
internal override void SetElement(TElement element)
{
base.SetElement(element);
_child.SetElement(element);
}
}
private abstract class EnumerableSorter<TElement>
{
/// <summary>Function that returns its input unmodified.</summary>
/// <remarks>
/// Used for reference equality in order to avoid unnecessary computation when a caller
/// can benefit from knowing that the produced value is identical to the input.
/// </remarks>
internal static readonly Func<TElement, TElement> IdentityFunc = e => e;
internal abstract void ComputeKeys(TElement[] elements, int count);
internal abstract int CompareAnyKeys(int index1, int index2);
private int[] ComputeMap(TElement[] elements, int count)
{
ComputeKeys(elements, count);
int[] map = new int[count];
FillIncrementing(map, 0);
return map;
}
internal int[] Sort(TElement[] elements, int count)
{
int[] map = ComputeMap(elements, count);
QuickSort(map, 0, count - 1);
return map;
}
internal int[] Sort(TElement[] elements, int count, int minIdx, int maxIdx)
{
int[] map = ComputeMap(elements, count);
PartialQuickSort(map, 0, count - 1, minIdx, maxIdx);
return map;
}
internal TElement ElementAt(TElement[] elements, int count, int idx)
{
int[] map = ComputeMap(elements, count);
return idx == 0 ?
elements[Min(map, count)] :
elements[QuickSelect(map, count - 1, idx)];
}
protected abstract void QuickSort(int[] map, int left, int right);
// Sorts the k elements between minIdx and maxIdx without sorting all elements
// Time complexity: O(n + k log k) best and average case. O(n^2) worse case.
protected abstract void PartialQuickSort(int[] map, int left, int right, int minIdx, int maxIdx);
// Finds the element that would be at idx if the collection was sorted.
// Time complexity: O(n) best and average case. O(n^2) worse case.
protected abstract int QuickSelect(int[] map, int right, int idx);
protected abstract int Min(int[] map, int count);
}
private sealed class EnumerableSorter<TElement, TKey> : EnumerableSorter<TElement>
{
private readonly Func<TElement, TKey> _keySelector;
private readonly IComparer<TKey> _comparer;
private readonly bool _descending;
private readonly EnumerableSorter<TElement>? _next;
private TKey[]? _keys;
internal EnumerableSorter(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TElement>? next)
{
_keySelector = keySelector;
_comparer = comparer;
_descending = descending;
_next = next;
}
internal override void ComputeKeys(TElement[] elements, int count)
{
Func<TElement, TKey> keySelector = _keySelector;
if (!ReferenceEquals(keySelector, IdentityFunc))
{
var keys = new TKey[count];
for (int i = 0; i < keys.Length; i++)
{
keys[i] = keySelector(elements[i]);
}
_keys = keys;
}
else
{
// The key selector is our known identity function, which means we don't
// need to invoke the key selector for every element. Further, we can just
// use the original array as the keys (even if count is smaller, as the additional
// values will just be ignored).
Debug.Assert(typeof(TKey) == typeof(TElement));
_keys = (TKey[])(object)elements;
}
_next?.ComputeKeys(elements, count);
}
internal override int CompareAnyKeys(int index1, int index2)
{
TKey[]? keys = _keys;
Debug.Assert(keys is not null);
int c = _comparer.Compare(keys[index1], keys[index2]);
if (c == 0)
{
if (_next is null)
{
return index1 - index2; // ensure stability of sort
}
return _next.CompareAnyKeys(index1, index2);
}
// -c will result in a negative value for int.MinValue (-int.MinValue == int.MinValue).
// Flipping keys earlier is more likely to trigger something strange in a comparer,
// particularly as it comes to the sort being stable.
return (_descending != (c > 0)) ? 1 : -1;
}
private int CompareAnyKeys_DefaultComparer_NoNext_Ascending(int index1, int index2)
{
Debug.Assert(typeof(TKey).IsValueType);
Debug.Assert(_comparer == Comparer<TKey>.Default);
Debug.Assert(_next is null);
Debug.Assert(!_descending);
TKey[]? keys = _keys;
Debug.Assert(keys is not null);
int c = Comparer<TKey>.Default.Compare(keys[index1], keys[index2]);
return
c == 0 ? index1 - index2 : // ensure stability of sort
c;
}
private int CompareAnyKeys_DefaultComparer_NoNext_Descending(int index1, int index2)
{
Debug.Assert(typeof(TKey).IsValueType);
Debug.Assert(_comparer == Comparer<TKey>.Default);
Debug.Assert(_next is null);
Debug.Assert(_descending);
TKey[]? keys = _keys;
Debug.Assert(keys is not null);
int c = Comparer<TKey>.Default.Compare(keys[index2], keys[index1]);
return
c == 0 ? index1 - index2 : // ensure stability of sort
c;
}
private int CompareKeys(int index1, int index2) => index1 == index2 ? 0 : CompareAnyKeys(index1, index2);
protected override void QuickSort(int[] keys, int lo, int hi)
{
Comparison<int> comparison;
if (typeof(TKey).IsValueType && _next is null && _comparer == Comparer<TKey>.Default)
{
// We can use Comparer<TKey>.Default.Compare and benefit from devirtualization and inlining.
// We can also avoid extra steps to check whether we need to deal with a subsequent tie breaker (_next).
if (!_descending)
{
comparison = CompareAnyKeys_DefaultComparer_NoNext_Ascending;
}
else
{
comparison = CompareAnyKeys_DefaultComparer_NoNext_Descending;
}
}
else
{
comparison = CompareAnyKeys;
}
new Span<int>(keys, lo, hi - lo + 1).Sort(comparison);
}
// Sorts the k elements between minIdx and maxIdx without sorting all elements
// Time complexity: O(n + k log k) best and average case. O(n^2) worse case.
protected override void PartialQuickSort(int[] map, int left, int right, int minIdx, int maxIdx)
{
do
{
int i = left;
int j = right;
int x = map[i + ((j - i) >> 1)];
do
{
while (i < map.Length && CompareKeys(x, map[i]) > 0)
{
i++;
}
while (j >= 0 && CompareKeys(x, map[j]) < 0)
{
j--;
}
if (i > j)
{
break;
}
if (i < j)
{
int temp = map[i];
map[i] = map[j];
map[j] = temp;
}
i++;
j--;
}
while (i <= j);
if (minIdx >= i)
{
left = i + 1;
}
else if (maxIdx <= j)
{
right = j - 1;
}
if (j - left <= right - i)
{
if (left < j)
{
PartialQuickSort(map, left, j, minIdx, maxIdx);
}
left = i;
}
else
{
if (i < right)
{
PartialQuickSort(map, i, right, minIdx, maxIdx);
}
right = j;
}
}
while (left < right);
}
// Finds the element that would be at idx if the collection was sorted.
// Time complexity: O(n) best and average case. O(n^2) worse case.
protected override int QuickSelect(int[] map, int right, int idx)
{
int left = 0;
do
{
int i = left;
int j = right;
int x = map[i + ((j - i) >> 1)];
do
{
while (i < map.Length && CompareKeys(x, map[i]) > 0)
{
i++;
}
while (j >= 0 && CompareKeys(x, map[j]) < 0)
{
j--;
}
if (i > j)
{
break;
}
if (i < j)
{
int temp = map[i];
map[i] = map[j];
map[j] = temp;
}
i++;
j--;
}
while (i <= j);
if (i <= idx)
{
left = i + 1;
}
else
{
right = j - 1;
}
if (j - left <= right - i)
{
if (left < j)
{
right = j;
}
left = i;
}
else
{
if (i < right)
{
left = i;
}
right = j;
}
}
while (left < right);
return map[idx];
}
protected override int Min(int[] map, int count)
{
int index = 0;
for (int i = 1; i < count; i++)
{
if (CompareKeys(map[i], map[index]) < 0)
{
index = i;
}
}
return map[index];
}
}
}
}
|