namespace System
{
- [Serializable]
- [ComVisible (true)]
- // FIXME: We are doing way to many double/triple exception checks for the overloaded functions"
- public abstract class Array : ICloneable, ICollection, IList, IEnumerable
- , IStructuralComparable, IStructuralEquatable
+ public abstract partial class Array
{
// Constructor
private Array ()
return false;
}
+ int IList.IndexOf (object value)
+ {
+ if (this.Rank > 1)
+ throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
+
+ int length = this.Length;
+ for (int i = 0; i < length; i++) {
+ if (Object.Equals (this.GetValueImpl (i), value))
+ // array index may not be zero-based.
+ // use lower bound
+ return i + this.GetLowerBound (0);
+ }
+
+ unchecked {
+ // lower bound may be MinValue
+ return this.GetLowerBound (0) - 1;
+ }
+ }
+
internal void InternalArray__ICollection_CopyTo<T> (T[] array, int index)
{
if (array == null)
}
}
- [ComVisible (false)]
- public long LongLength {
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
- get { return Length; }
- }
-
public int Rank {
[ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
get {
}
}
- // IList interface
- object IList.this [int index] {
- get {
- if (unchecked ((uint) index) >= unchecked ((uint) Length))
- throw new IndexOutOfRangeException ("index");
- if (this.Rank > 1)
- throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported."));
- return GetValueImpl (index);
- }
- set {
- if (unchecked ((uint) index) >= unchecked ((uint) Length))
- throw new IndexOutOfRangeException ("index");
- if (this.Rank > 1)
- throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported."));
- SetValueImpl (value, index);
- }
- }
-
- int IList.Add (object value)
- {
- throw new NotSupportedException ();
- }
-
- void IList.Clear ()
- {
- Array.Clear (this, this.GetLowerBound (0), this.Length);
- }
-
- bool IList.Contains (object value)
- {
- if (this.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- int length = this.Length;
- for (int i = 0; i < length; i++) {
- if (Object.Equals (this.GetValueImpl (i), value))
- return true;
- }
- return false;
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- int IList.IndexOf (object value)
- {
- if (this.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- int length = this.Length;
- for (int i = 0; i < length; i++) {
- if (Object.Equals (this.GetValueImpl (i), value))
- // array index may not be zero-based.
- // use lower bound
- return i + this.GetLowerBound (0);
- }
-
- unchecked {
- // lower bound may be MinValue
- return this.GetLowerBound (0) - 1;
- }
- }
-
- void IList.Insert (int index, object value)
- {
- throw new NotSupportedException ();
- }
-
- void IList.Remove (object value)
- {
- throw new NotSupportedException ();
- }
-
- void IList.RemoveAt (int index)
- {
- throw new NotSupportedException ();
- }
-
// InternalCall Methods
[MethodImplAttribute (MethodImplOptions.InternalCall)]
extern int GetRank ();
[MethodImplAttribute (MethodImplOptions.InternalCall)]
public extern int GetLength (int dimension);
- [ComVisible (false)]
- public long GetLongLength (int dimension)
- {
- return GetLength (dimension);
- }
-
[ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
[MethodImplAttribute (MethodImplOptions.InternalCall)]
public extern int GetLowerBound (int dimension);
[MethodImplAttribute (MethodImplOptions.InternalCall)]
internal extern static Array CreateInstanceImpl (Type elementType, int[] lengths, int[] bounds);
- // Properties
- int ICollection.Count {
- get {
- return Length;
- }
- }
-
- public bool IsSynchronized {
- get {
- return false;
- }
- }
-
- public object SyncRoot {
- get {
- return this;
- }
- }
-
- public bool IsFixedSize {
- get {
- return true;
- }
- }
-
public bool IsReadOnly {
get {
return false;
}
}
- public IEnumerator GetEnumerator ()
- {
- return new SimpleEnumerator (this);
- }
-
- int IStructuralComparable.CompareTo (object other, IComparer comparer)
- {
- if (other == null)
- return 1;
-
- Array arr = other as Array;
- if (arr == null)
- throw new ArgumentException ("Not an array", "other");
-
- int len = GetLength (0);
- if (len != arr.GetLength (0))
- throw new ArgumentException ("Not of the same length", "other");
-
- if (Rank > 1)
- throw new ArgumentException ("Array must be single dimensional");
-
- if (arr.Rank > 1)
- throw new ArgumentException ("Array must be single dimensional", "other");
-
- for (int i = 0; i < len; ++i) {
- object a = GetValue (i);
- object b = arr.GetValue (i);
- int r = comparer.Compare (a, b);
- if (r != 0)
- return r;
- }
- return 0;
- }
-
- bool IStructuralEquatable.Equals (object other, IEqualityComparer comparer)
- {
- Array o = other as Array;
- if (o == null || o.Length != Length)
- return false;
-
- if (Object.ReferenceEquals (other, this))
- return true;
-
- for (int i = 0; i < Length; i++) {
- object this_item = this.GetValue (i);
- object other_item = o.GetValue (i);
- if (!comparer.Equals (this_item, other_item))
- return false;
- }
- return true;
- }
-
-
- int IStructuralEquatable.GetHashCode (IEqualityComparer comparer)
- {
- if (comparer == null)
- throw new ArgumentNullException ("comparer");
-
- int hash = 0;
- for (int i = 0; i < Length; i++)
- hash = ((hash << 7) + hash) ^ comparer.GetHashCode (GetValueImpl (i));
- return hash;
- }
-
[ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
public int GetUpperBound (int dimension)
{
return GetValue (ind);
}
- [ComVisible (false)]
- public object GetValue (long index)
- {
- if (index < 0 || index > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("index", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
-
- return GetValue ((int) index);
- }
-
- [ComVisible (false)]
- public object GetValue (long index1, long index2)
- {
- if (index1 < 0 || index1 > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
-
- if (index2 < 0 || index2 > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
-
- return GetValue ((int) index1, (int) index2);
- }
-
- [ComVisible (false)]
- public object GetValue (long index1, long index2, long index3)
- {
- if (index1 < 0 || index1 > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
-
- if (index2 < 0 || index2 > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
-
- if (index3 < 0 || index3 > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
-
- return GetValue ((int) index1, (int) index2, (int) index3);
- }
-
[ComVisible (false)]
public void SetValue (object value, long index)
{
SetValue (value, ind);
}
- internal static Array UnsafeCreateInstance (Type elementType, int length)
- {
- return CreateInstance (elementType, length);
- }
-
internal static Array UnsafeCreateInstance(Type elementType, int[] lengths, int[] lowerBounds)
{
return CreateInstance(elementType, lengths, lowerBounds);
return CreateInstance (elementType, GetIntArray (lengths));
}
- [ComVisible (false)]
- public object GetValue (params long [] indices)
- {
- if (indices == null)
- throw new ArgumentNullException ("indices");
- return GetValue (GetIntArray (indices));
- }
-
[ComVisible (false)]
public void SetValue (object value, params long [] indices)
{
SetValue (value, GetIntArray (indices));
}
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int BinarySearch (Array array, object value)
- {
- return BinarySearch (array, value, null);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int BinarySearch (Array array, object value, IComparer comparer)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- if (array.Length == 0)
- return -1;
-
- return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int BinarySearch (Array array, int index, int length, object value)
- {
- return BinarySearch (array, index, length, value, null);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- if (index < array.GetLowerBound (0))
- throw new ArgumentOutOfRangeException ("index", Locale.GetText (
- "index is less than the lower bound of array."));
- if (length < 0)
- throw new ArgumentOutOfRangeException ("length", Locale.GetText (
- "Value has to be >= 0."));
- // re-ordered to avoid possible integer overflow
- if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
- throw new ArgumentException (Locale.GetText (
- "index and length do not specify a valid range in array."));
-
- if (array.Length == 0)
- return -1;
-
- return DoBinarySearch (array, index, length, value, comparer);
- }
-
- static int DoBinarySearch (Array array, int index, int length, object value, IComparer comparer)
- {
- // cache this in case we need it
- if (comparer == null)
- comparer = Comparer.Default;
-
- int iMin = index;
- // Comment from Tum (tum@veridicus.com):
- // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
- int iMax = index + length - 1;
- int iCmp = 0;
- try {
- while (iMin <= iMax) {
- // Be careful with overflow
- // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
- int iMid = iMin + ((iMax - iMin) / 2);
- object elt = array.GetValueImpl (iMid);
-
- iCmp = comparer.Compare (elt, value);
-
- if (iCmp == 0)
- return iMid;
- else if (iCmp > 0)
- iMax = iMid - 1;
- else
- iMin = iMid + 1; // compensate for the rounding down
- }
- }
- catch (Exception e) {
- throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
- }
-
- return ~iMin;
- }
-
[ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
public static void Clear (Array array, int index, int length)
{
[MethodImplAttribute (MethodImplOptions.InternalCall)]
static extern void ClearInternal (Array a, int index, int count);
- [MethodImplAttribute (MethodImplOptions.InternalCall)]
- public extern object Clone ();
-
[ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
public static void Copy (Array sourceArray, Array destinationArray, int length)
{
throw new ArgumentOutOfRangeException ("length", Locale.GetText (
"Value has to be >= 0."));;
+ if (sourceArray.Rank != destinationArray.Rank)
+ throw new RankException(SR.Rank_MultiDimNotSupported);
+
if (sourceIndex < 0)
throw new ArgumentOutOfRangeException ("sourceIndex", Locale.GetText (
"Value has to be >= 0."));;
throw new ArgumentException (msg, string.Empty);
}
- if (sourceArray.Rank != destinationArray.Rank)
- throw new RankException (Locale.GetText ("Arrays must be of same size."));
-
Type src_type = sourceArray.GetType ().GetElementType ();
Type dst_type = destinationArray.GetType ().GetElementType ();
return source.IsAssignableFrom (target) || target.IsAssignableFrom (source);
}
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray,
- long destinationIndex, long length)
+ public static T [] FindAll<T> (T [] array, Predicate <T> match)
{
- if (sourceArray == null)
- throw new ArgumentNullException ("sourceArray");
-
- if (destinationArray == null)
- throw new ArgumentNullException ("destinationArray");
-
- if (sourceIndex < Int32.MinValue || sourceIndex > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("sourceIndex",
- Locale.GetText ("Must be in the Int32 range."));
-
- if (destinationIndex < Int32.MinValue || destinationIndex > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("destinationIndex",
- Locale.GetText ("Must be in the Int32 range."));
-
- if (length < 0 || length > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("length", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
-
- Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
- }
+ if (array == null)
+ throw new ArgumentNullException ("array");
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Copy (Array sourceArray, Array destinationArray, long length)
- {
- if (length < 0 || length > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("length", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
+ if (match == null)
+ throw new ArgumentNullException ("match");
- Copy (sourceArray, destinationArray, (int) length);
- }
+ int pos = 0;
+ T [] d = new T [array.Length];
+ foreach (T t in array)
+ if (match (t))
+ d [pos++] = t;
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int IndexOf (Array array, object value)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return IndexOf (array, value, 0, array.Length);
+ Resize <T> (ref d, pos);
+ return d;
}
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int IndexOf (Array array, object value, int startIndex)
+ [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
+ //
+ // The constrained copy should guarantee that if there is an exception thrown
+ // during the copy, the destination array remains unchanged.
+ // This is related to System.Runtime.Reliability.CER
+ public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
{
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return IndexOf (array, value, startIndex, array.Length - startIndex);
+ Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length);
}
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int IndexOf (Array array, object value, int startIndex, int count)
+ object GetValueWithFlattenedIndex_NoErrorCheck (int flattenedIndex)
{
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- // re-ordered to avoid possible integer overflow
- if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
- throw new ArgumentOutOfRangeException ();
-
- int max = startIndex + count;
- for (int i = startIndex; i < max; i++) {
- if (Object.Equals (array.GetValueImpl (i), value))
- return i;
- }
-
- return array.GetLowerBound (0) - 1;
- }
-
- public void Initialize()
- {
- //FIXME: We would like to find a compiler that uses
- // this method. It looks like this method do nothing
- // in C# so no exception is trown by the moment.
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int LastIndexOf (Array array, object value)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Length == 0)
- return array.GetLowerBound (0) - 1;
- return LastIndexOf (array, value, array.Length - 1);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int LastIndexOf (Array array, object value, int startIndex)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int LastIndexOf (Array array, object value, int startIndex, int count)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- int lb = array.GetLowerBound (0);
- // Empty arrays do not throw ArgumentOutOfRangeException
- if (array.Length == 0)
- return lb - 1;
-
- if (count < 0 || startIndex < lb ||
- startIndex > array.GetUpperBound (0) || startIndex - count + 1 < lb)
- throw new ArgumentOutOfRangeException ();
-
- for (int i = startIndex; i >= startIndex - count + 1; i--) {
- if (Object.Equals (array.GetValueImpl (i), value))
- return i;
- }
-
- return lb - 1;
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Reverse (Array array)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- Reverse (array, array.GetLowerBound (0), array.Length);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Reverse (Array array, int index, int length)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- if (index < array.GetLowerBound (0) || length < 0)
- throw new ArgumentOutOfRangeException ();
-
- // re-ordered to avoid possible integer overflow
- if (index > array.GetUpperBound (0) + 1 - length)
- throw new ArgumentException ();
-
- int end = index + length - 1;
- var et = array.GetType ().GetElementType ();
- switch (Type.GetTypeCode (et)) {
- case TypeCode.Boolean:
- while (index < end) {
- bool a, b;
-
- array.GetGenericValueImpl (index, out a);
- array.GetGenericValueImpl (end, out b);
- array.SetGenericValueImpl (index, ref b);
- array.SetGenericValueImpl (end, ref a);
- ++index;
- --end;
- }
- return;
-
- case TypeCode.Byte:
- case TypeCode.SByte:
- while (index < end) {
- byte a, b;
-
- array.GetGenericValueImpl (index, out a);
- array.GetGenericValueImpl (end, out b);
- array.SetGenericValueImpl (index, ref b);
- array.SetGenericValueImpl (end, ref a);
- ++index;
- --end;
- }
- return;
-
- case TypeCode.Int16:
- case TypeCode.UInt16:
- case TypeCode.Char:
- while (index < end) {
- short a, b;
-
- array.GetGenericValueImpl (index, out a);
- array.GetGenericValueImpl (end, out b);
- array.SetGenericValueImpl (index, ref b);
- array.SetGenericValueImpl (end, ref a);
- ++index;
- --end;
- }
- return;
-
- case TypeCode.Int32:
- case TypeCode.UInt32:
- case TypeCode.Single:
- while (index < end) {
- int a, b;
-
- array.GetGenericValueImpl (index, out a);
- array.GetGenericValueImpl (end, out b);
- array.SetGenericValueImpl (index, ref b);
- array.SetGenericValueImpl (end, ref a);
- ++index;
- --end;
- }
- return;
-
- case TypeCode.Int64:
- case TypeCode.UInt64:
- case TypeCode.Double:
- while (index < end) {
- long a, b;
-
- array.GetGenericValueImpl (index, out a);
- array.GetGenericValueImpl (end, out b);
- array.SetGenericValueImpl (index, ref b);
- array.SetGenericValueImpl (end, ref a);
- ++index;
- --end;
- }
- return;
-
- case TypeCode.Decimal:
- while (index < end) {
- decimal a, b;
-
- array.GetGenericValueImpl (index, out a);
- array.GetGenericValueImpl (end, out b);
- array.SetGenericValueImpl (index, ref b);
- array.SetGenericValueImpl (end, ref a);
- ++index;
- --end;
- }
- return;
-
- case TypeCode.String:
- while (index < end) {
- object a, b;
-
- array.GetGenericValueImpl (index, out a);
- array.GetGenericValueImpl (end, out b);
- array.SetGenericValueImpl (index, ref b);
- array.SetGenericValueImpl (end, ref a);
- ++index;
- --end;
- }
- return;
- default:
- if (array is object[])
- goto case TypeCode.String;
-
- // Very slow fallback
- while (index < end) {
- object val = array.GetValueImpl (index);
- array.SetValueImpl (array.GetValueImpl (end), index);
- array.SetValueImpl (val, end);
- ++index;
- --end;
- }
-
- return;
- }
- }
-
- public static void Reverse<T>(T[] array)
- {
- if (array == null)
- throw new ArgumentNullException (nameof (array));
-
- Reverse (array, 0, array.Length);
- }
-
- public static void Reverse<T>(T[] array, int index, int length)
- {
- if (array == null)
- throw new ArgumentNullException (nameof (array));
- if (index < 0 || length < 0)
- throw new ArgumentOutOfRangeException ((index < 0 ? nameof (index) : nameof (length)));
- if (array.Length - index < length)
- throw new ArgumentException ();
-
- int i = index;
- int j = index + length - 1;
- while (i < j) {
- T temp = array [i];
- array [i] = array [j];
- array [j] = temp;
- i++;
- j--;
- }
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort (Array array)
- {
- Sort (array, (IComparer)null);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort (Array keys, Array items)
- {
- Sort (keys, items, (IComparer)null);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort (Array array, IComparer comparer)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- SortImpl (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort (Array array, int index, int length)
- {
- Sort (array, index, length, (IComparer)null);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort (Array keys, Array items, IComparer comparer)
- {
- if (items == null) {
- Sort (keys, comparer);
- return;
- }
-
- if (keys == null)
- throw new ArgumentNullException ("keys");
-
- if (keys.Rank > 1 || items.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- SortImpl (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort (Array keys, Array items, int index, int length)
- {
- Sort (keys, items, index, length, (IComparer)null);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort (Array array, int index, int length, IComparer comparer)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
-
- if (index < array.GetLowerBound (0))
- throw new ArgumentOutOfRangeException ("index");
-
- if (length < 0)
- throw new ArgumentOutOfRangeException ("length", Locale.GetText (
- "Value has to be >= 0."));
-
- if (array.Length - (array.GetLowerBound (0) + index) < length)
- throw new ArgumentException ();
-
- SortImpl (array, null, index, length, comparer);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
- {
- if (items == null) {
- Sort (keys, index, length, comparer);
- return;
- }
-
- if (keys == null)
- throw new ArgumentNullException ("keys");
-
- if (keys.Rank > 1 || items.Rank > 1)
- throw new RankException ();
-
- if (keys.GetLowerBound (0) != items.GetLowerBound (0))
- throw new ArgumentException ();
-
- if (index < keys.GetLowerBound (0))
- throw new ArgumentOutOfRangeException ("index");
-
- if (length < 0)
- throw new ArgumentOutOfRangeException ("length", Locale.GetText (
- "Value has to be >= 0."));
-
- if (items.Length - (index + items.GetLowerBound (0)) < length || keys.Length - (index + keys.GetLowerBound (0)) < length)
- throw new ArgumentException ();
-
- SortImpl (keys, items, index, length, comparer);
- }
-
- private static void SortImpl (Array keys, Array items, int index, int length, IComparer comparer)
- {
- if (length <= 1)
- return;
-
- int low = index;
- int high = index + length - 1;
-
-#if !BOOTSTRAP_BASIC
- if (comparer == null && items is object[]) {
- /* Its better to compare typecodes as casts treat long/ulong/long based enums the same */
- switch (Type.GetTypeCode (keys.GetType ().GetElementType ())) {
- case TypeCode.Int32:
- qsort (keys as Int32[], items as object[], low, high);
- return;
- case TypeCode.Int64:
- qsort (keys as Int64[], items as object[], low, high);
- return;
- case TypeCode.Byte:
- qsort (keys as byte[], items as object[], low, high);
- return;
- case TypeCode.Char:
- qsort (keys as char[], items as object[], low, high);
- return;
- case TypeCode.DateTime:
- qsort (keys as DateTime[], items as object[], low, high);
- return;
- case TypeCode.Decimal:
- qsort (keys as decimal[], items as object[], low, high);
- return;
- case TypeCode.Double:
- qsort (keys as double[], items as object[], low, high);
- return;
- case TypeCode.Int16:
- qsort (keys as Int16[], items as object[], low, high);
- return;
- case TypeCode.SByte:
- qsort (keys as SByte[], items as object[], low, high);
- return;
- case TypeCode.Single:
- qsort (keys as Single[], items as object[], low, high);
- return;
- case TypeCode.UInt16:
- qsort (keys as UInt16[], items as object[], low, high);
- return;
- case TypeCode.UInt32:
- qsort (keys as UInt32[], items as object[], low, high);
- return;
- case TypeCode.UInt64:
- qsort (keys as UInt64[], items as object[], low, high);
- return;
- default:
- break;
- }
- }
-#endif
-
- if (comparer == null)
- CheckComparerAvailable (keys, low, high);
-
- try {
- qsort (keys, items, low, high, comparer);
- } catch (Exception e) {
- throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
- }
- }
-
- struct QSortStack {
- public int high;
- public int low;
- }
-
- static bool QSortArrange (Array keys, Array items, int lo, ref object v0, int hi, ref object v1, IComparer comparer)
- {
- IComparable cmp;
- object tmp;
-
- if (comparer != null) {
- if (comparer.Compare (v1, v0) < 0) {
- swap (keys, items, lo, hi);
- tmp = v0;
- v0 = v1;
- v1 = tmp;
-
- return true;
- }
- } else if (v0 != null) {
- cmp = v1 as IComparable;
-
- if (v1 == null || cmp.CompareTo (v0) < 0) {
- swap (keys, items, lo, hi);
- tmp = v0;
- v0 = v1;
- v1 = tmp;
-
- return true;
- }
- }
-
- return false;
- }
-
- unsafe static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
- {
- QSortStack* stack = stackalloc QSortStack [32];
- const int QSORT_THRESHOLD = 7;
- int high, low, mid, i, k;
- object key, hi, lo;
- IComparable cmp;
- int sp = 1;
-
- // initialize our stack
- stack[0].high = high0;
- stack[0].low = low0;
-
- do {
- // pop the stack
- sp--;
- high = stack[sp].high;
- low = stack[sp].low;
-
- if ((low + QSORT_THRESHOLD) > high) {
- // switch to insertion sort
- for (i = low + 1; i <= high; i++) {
- for (k = i; k > low; k--) {
- lo = keys.GetValueImpl (k - 1);
- hi = keys.GetValueImpl (k);
- if (comparer != null) {
- if (comparer.Compare (hi, lo) >= 0)
- break;
- } else {
- if (lo == null)
- break;
-
- if (hi != null) {
- cmp = hi as IComparable;
- if (cmp.CompareTo (lo) >= 0)
- break;
- }
- }
-
- swap (keys, items, k - 1, k);
- }
- }
-
- continue;
- }
-
- // calculate the middle element
- mid = low + ((high - low) / 2);
-
- // get the 3 keys
- key = keys.GetValueImpl (mid);
- hi = keys.GetValueImpl (high);
- lo = keys.GetValueImpl (low);
-
- // once we re-order the low, mid, and high elements to be in
- // ascending order, we'll use mid as our pivot.
- QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
- if (QSortArrange (keys, items, mid, ref key, high, ref hi, comparer))
- QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
-
- cmp = key as IComparable;
-
- // since we've already guaranteed that lo <= mid and mid <= hi,
- // we can skip comparing them again.
- k = high - 1;
- i = low + 1;
-
- do {
- // Move the walls in
- if (comparer != null) {
- // find the first element with a value >= pivot value
- while (i < k && comparer.Compare (key, keys.GetValueImpl (i)) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && comparer.Compare (key, keys.GetValueImpl (k)) < 0)
- k--;
- } else if (cmp != null) {
- // find the first element with a value >= pivot value
- while (i < k && cmp.CompareTo (keys.GetValueImpl (i)) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && cmp.CompareTo (keys.GetValueImpl (k)) < 0)
- k--;
- } else {
- // This has the effect of moving the null values to the front if comparer is null
- while (i < k && keys.GetValueImpl (i) == null)
- i++;
-
- while (k > i && keys.GetValueImpl (k) != null)
- k--;
- }
-
- if (k <= i)
- break;
-
- swap (keys, items, i, k);
-
- i++;
- k--;
- } while (true);
-
- // push our partitions onto the stack, largest first
- // (to make sure we don't run out of stack space)
- if ((high - k) >= (k - low)) {
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
-
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
- } else {
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
-
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
- }
- } while (sp > 0);
- }
-
- private static void CheckComparerAvailable (Array keys, int low, int high)
- {
- // move null keys to beginning of array,
- // ensure that non-null keys implement IComparable
- for (int i = 0; i < high; i++) {
- object obj = keys.GetValueImpl (i);
- if (obj == null)
- continue;
- if (!(obj is IComparable)) {
- string msg = Locale.GetText ("No IComparable interface found for type '{0}'.");
- throw new InvalidOperationException (String.Format (msg, obj.GetType ()));
- }
- }
- }
-
- private static void swap (Array keys, Array items, int i, int j)
- {
- object tmp = keys.GetValueImpl (i);
- keys.SetValueImpl (keys.GetValueImpl (j), i);
- keys.SetValueImpl (tmp, j);
-
- if (items != null) {
- tmp = items.GetValueImpl (i);
- items.SetValueImpl (items.GetValueImpl (j), i);
- items.SetValueImpl (tmp, j);
- }
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort<T> (T [] array)
- {
- Sort<T> (array, (IComparer<T>)null);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items)
- {
- Sort<TKey, TValue> (keys, items, (IComparer<TKey>)null);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort<T> (T [] array, IComparer<T> comparer)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- SortImpl<T> (array, 0, array.Length, comparer);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, IComparer<TKey> comparer)
- {
- if (items == null) {
- Sort<TKey> (keys, comparer);
- return;
- }
-
- if (keys == null)
- throw new ArgumentNullException ("keys");
-
- if (keys.Length > items.Length)
- throw new ArgumentException ("Length of keys is larger than length of items.");
-
- SortImpl<TKey, TValue> (keys, items, 0, keys.Length, comparer);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort<T> (T [] array, int index, int length)
- {
- Sort<T> (array, index, length, (IComparer<T>)null);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length)
- {
- Sort<TKey, TValue> (keys, items, index, length, (IComparer<TKey>)null);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort<T> (T [] array, int index, int length, IComparer<T> comparer)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (index < 0)
- throw new ArgumentOutOfRangeException ("index");
-
- if (length < 0)
- throw new ArgumentOutOfRangeException ("length", Locale.GetText (
- "Value has to be >= 0."));
-
- if (index + length > array.Length)
- throw new ArgumentException ();
-
- SortImpl<T> (array, index, length, comparer);
- }
-
- [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
- public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
- {
- if (items == null) {
- Sort<TKey> (keys, index, length, comparer);
- return;
- }
-
- if (keys == null)
- throw new ArgumentNullException ("keys");
-
- if (index < 0)
- throw new ArgumentOutOfRangeException ("index");
-
- if (length < 0)
- throw new ArgumentOutOfRangeException ("length");
-
- if (items.Length - index < length || keys.Length - index < length)
- throw new ArgumentException ();
-
- SortImpl<TKey, TValue> (keys, items, index, length, comparer);
- }
-
- private static void SortImpl<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
- {
- if (keys.Length <= 1)
- return;
-
- int low = index;
- int high = index + length - 1;
-
- //
- // Check for value types which can be sorted without Compare () method
- //
- if (comparer == null) {
- /* Avoid this when using full-aot to prevent the generation of many unused qsort<K,T> instantiations */
-#if !FULL_AOT_RUNTIME
-#if !BOOTSTRAP_BASIC
- switch (Type.GetTypeCode (typeof (TKey))) {
- case TypeCode.Int32:
- qsort (keys as Int32[], items, low, high);
- return;
- case TypeCode.Int64:
- qsort (keys as Int64[], items, low, high);
- return;
- case TypeCode.Byte:
- qsort (keys as byte[], items, low, high);
- return;
- case TypeCode.Char:
- qsort (keys as char[], items, low, high);
- return;
- case TypeCode.DateTime:
- qsort (keys as DateTime[], items, low, high);
- return;
- case TypeCode.Decimal:
- qsort (keys as decimal[], items, low, high);
- return;
- case TypeCode.Double:
- qsort (keys as double[], items, low, high);
- return;
- case TypeCode.Int16:
- qsort (keys as Int16[], items, low, high);
- return;
- case TypeCode.SByte:
- qsort (keys as SByte[], items, low, high);
- return;
- case TypeCode.Single:
- qsort (keys as Single[], items, low, high);
- return;
- case TypeCode.UInt16:
- qsort (keys as UInt16[], items, low, high);
- return;
- case TypeCode.UInt32:
- qsort (keys as UInt32[], items, low, high);
- return;
- case TypeCode.UInt64:
- qsort (keys as UInt64[], items, low, high);
- return;
- }
-#endif
-#endif
- // Using Comparer<TKey> adds a small overload, but with value types it
- // helps us to not box them.
- if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
- typeof (TKey).IsValueType)
- comparer = Comparer<TKey>.Default;
- }
-
- if (comparer == null)
- CheckComparerAvailable<TKey> (keys, low, high);
-
- //try {
- qsort (keys, items, low, high, comparer);
- //} catch (Exception e) {
- //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
- //}
- }
-
- // Specialized version for items==null
- private static void SortImpl<TKey> (TKey [] keys, int index, int length, IComparer<TKey> comparer)
- {
- if (keys.Length <= 1)
- return;
-
- int low = index;
- int high = index + length - 1;
-
- //
- // Check for value types which can be sorted without Compare () method
- //
- if (comparer == null) {
-#if !BOOTSTRAP_BASIC
- switch (Type.GetTypeCode (typeof (TKey))) {
- case TypeCode.Int32:
- qsort (keys as Int32[], low, high);
- return;
- case TypeCode.Int64:
- qsort (keys as Int64[], low, high);
- return;
- case TypeCode.Byte:
- qsort (keys as byte[], low, high);
- return;
- case TypeCode.Char:
- qsort (keys as char[], low, high);
- return;
- case TypeCode.DateTime:
- qsort (keys as DateTime[], low, high);
- return;
- case TypeCode.Decimal:
- qsort (keys as decimal[], low, high);
- return;
- case TypeCode.Double:
- qsort (keys as double[], low, high);
- return;
- case TypeCode.Int16:
- qsort (keys as Int16[], low, high);
- return;
- case TypeCode.SByte:
- qsort (keys as SByte[], low, high);
- return;
- case TypeCode.Single:
- qsort (keys as Single[], low, high);
- return;
- case TypeCode.UInt16:
- qsort (keys as UInt16[], low, high);
- return;
- case TypeCode.UInt32:
- qsort (keys as UInt32[], low, high);
- return;
- case TypeCode.UInt64:
- qsort (keys as UInt64[], low, high);
- return;
- }
-#endif
- // Using Comparer<TKey> adds a small overload, but with value types it
- // helps us to not box them.
- if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
- typeof (TKey).IsValueType)
- comparer = Comparer<TKey>.Default;
- }
-
- if (comparer == null)
- CheckComparerAvailable<TKey> (keys, low, high);
-
- //try {
- qsort<TKey> (keys, low, high, comparer);
- //} catch (Exception e) {
- //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
- //}
- }
-
- public static void Sort<T> (T [] array, Comparison<T> comparison)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (comparison == null)
- throw new ArgumentNullException ("comparison");
-
- SortImpl<T> (array, array.Length, comparison);
- }
-
- // used by List<T>.Sort (Comparison <T>)
- internal static void SortImpl<T> (T [] array, int length, Comparison<T> comparison)
- {
- if (length <= 1)
- return;
-
- try {
- int low0 = 0;
- int high0 = length - 1;
- qsort<T> (array, low0, high0, comparison);
- } catch (InvalidOperationException) {
- throw;
- } catch (Exception e) {
- throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e);
- }
- }
-
- static bool QSortArrange<T, U> (T [] keys, U [] items, int lo, int hi) where T : IComparable<T>
- {
- if (keys[lo] != null) {
- if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
- swap (keys, items, lo, hi);
- return true;
- }
- }
-
- return false;
- }
-
- // Specialized version for items==null
- static bool QSortArrange<T> (T [] keys, int lo, int hi) where T : IComparable<T>
- {
- if (keys[lo] != null) {
- if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
- swap (keys, lo, hi);
- return true;
- }
- }
-
- return false;
- }
-
- unsafe static void qsort<T, U> (T[] keys, U[] items, int low0, int high0) where T : IComparable<T>
- {
- QSortStack* stack = stackalloc QSortStack [32];
- const int QSORT_THRESHOLD = 7;
- int high, low, mid, i, k;
- int sp = 1;
- T key;
-
- // initialize our stack
- stack[0].high = high0;
- stack[0].low = low0;
-
- do {
- // pop the stack
- sp--;
- high = stack[sp].high;
- low = stack[sp].low;
-
- if ((low + QSORT_THRESHOLD) > high) {
- // switch to insertion sort
- for (i = low + 1; i <= high; i++) {
- for (k = i; k > low; k--) {
- // if keys[k] >= keys[k-1], break
- if (keys[k-1] == null)
- break;
-
- if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
- break;
-
- swap (keys, items, k - 1, k);
- }
- }
-
- continue;
- }
-
- // calculate the middle element
- mid = low + ((high - low) / 2);
-
- // once we re-order the lo, mid, and hi elements to be in
- // ascending order, we'll use mid as our pivot.
- QSortArrange<T, U> (keys, items, low, mid);
- if (QSortArrange<T, U> (keys, items, mid, high))
- QSortArrange<T, U> (keys, items, low, mid);
-
- key = keys[mid];
-
- // since we've already guaranteed that lo <= mid and mid <= hi,
- // we can skip comparing them again
- k = high - 1;
- i = low + 1;
-
- do {
- if (key != null) {
- // find the first element with a value >= pivot value
- while (i < k && key.CompareTo (keys[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && key.CompareTo (keys[k]) < 0)
- k--;
- } else {
- while (i < k && keys[i] == null)
- i++;
-
- while (k > i && keys[k] != null)
- k--;
- }
-
- if (k <= i)
- break;
-
- swap (keys, items, i, k);
-
- i++;
- k--;
- } while (true);
-
- // push our partitions onto the stack, largest first
- // (to make sure we don't run out of stack space)
- if ((high - k) >= (k - low)) {
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
-
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
- } else {
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
-
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
- }
- } while (sp > 0);
- }
-
- // Specialized version for items==null
- unsafe static void qsort<T> (T[] keys, int low0, int high0) where T : IComparable<T>
- {
- QSortStack* stack = stackalloc QSortStack [32];
- const int QSORT_THRESHOLD = 7;
- int high, low, mid, i, k;
- int sp = 1;
- T key;
-
- // initialize our stack
- stack[0].high = high0;
- stack[0].low = low0;
-
- do {
- // pop the stack
- sp--;
- high = stack[sp].high;
- low = stack[sp].low;
-
- if ((low + QSORT_THRESHOLD) > high) {
- // switch to insertion sort
- for (i = low + 1; i <= high; i++) {
- for (k = i; k > low; k--) {
- // if keys[k] >= keys[k-1], break
- if (keys[k-1] == null)
- break;
-
- if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
- break;
-
- swap (keys, k - 1, k);
- }
- }
-
- continue;
- }
-
- // calculate the middle element
- mid = low + ((high - low) / 2);
-
- // once we re-order the lo, mid, and hi elements to be in
- // ascending order, we'll use mid as our pivot.
- QSortArrange<T> (keys, low, mid);
- if (QSortArrange<T> (keys, mid, high))
- QSortArrange<T> (keys, low, mid);
-
- key = keys[mid];
-
- // since we've already guaranteed that lo <= mid and mid <= hi,
- // we can skip comparing them again
- k = high - 1;
- i = low + 1;
-
- do {
- if (key != null) {
- // find the first element with a value >= pivot value
- while (i < k && key.CompareTo (keys[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k >= i && key.CompareTo (keys[k]) < 0)
- k--;
- } else {
- while (i < k && keys[i] == null)
- i++;
-
- while (k >= i && keys[k] != null)
- k--;
- }
-
- if (k <= i)
- break;
-
- swap (keys, i, k);
-
- i++;
- k--;
- } while (true);
-
- // push our partitions onto the stack, largest first
- // (to make sure we don't run out of stack space)
- if ((high - k) >= (k - low)) {
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
-
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
- } else {
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
-
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
- }
- } while (sp > 0);
- }
-
- static bool QSortArrange<K, V> (K [] keys, V [] items, int lo, int hi, IComparer<K> comparer)
- {
- IComparable<K> gcmp;
- IComparable cmp;
-
- if (comparer != null) {
- if (comparer.Compare (keys[hi], keys[lo]) < 0) {
- swap<K, V> (keys, items, lo, hi);
- return true;
- }
- } else if (keys[lo] != null) {
- if (keys[hi] == null) {
- swap<K, V> (keys, items, lo, hi);
- return true;
- }
-
- gcmp = keys[hi] as IComparable<K>;
- if (gcmp != null) {
- if (gcmp.CompareTo (keys[lo]) < 0) {
- swap<K, V> (keys, items, lo, hi);
- return true;
- }
-
- return false;
- }
-
- cmp = keys[hi] as IComparable;
- if (cmp != null) {
- if (cmp.CompareTo (keys[lo]) < 0) {
- swap<K, V> (keys, items, lo, hi);
- return true;
- }
-
- return false;
- }
- }
-
- return false;
- }
-
- // Specialized version for items==null
- static bool QSortArrange<K> (K [] keys, int lo, int hi, IComparer<K> comparer)
- {
- IComparable<K> gcmp;
- IComparable cmp;
-
- if (comparer != null) {
- if (comparer.Compare (keys[hi], keys[lo]) < 0) {
- swap<K> (keys, lo, hi);
- return true;
- }
- } else if (keys[lo] != null) {
- if (keys[hi] == null) {
- swap<K> (keys, lo, hi);
- return true;
- }
-
- gcmp = keys[hi] as IComparable<K>;
- if (gcmp != null) {
- if (gcmp.CompareTo (keys[lo]) < 0) {
- swap<K> (keys, lo, hi);
- return true;
- }
-
- return false;
- }
-
- cmp = keys[hi] as IComparable;
- if (cmp != null) {
- if (cmp.CompareTo (keys[lo]) < 0) {
- swap<K> (keys, lo, hi);
- return true;
- }
-
- return false;
- }
- }
-
- return false;
- }
-
- unsafe static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
- {
- QSortStack* stack = stackalloc QSortStack [32];
- const int QSORT_THRESHOLD = 7;
- int high, low, mid, i, k;
- IComparable<K> gcmp;
- IComparable cmp;
- int sp = 1;
- K key;
-
- // initialize our stack
- stack[0].high = high0;
- stack[0].low = low0;
-
- do {
- // pop the stack
- sp--;
- high = stack[sp].high;
- low = stack[sp].low;
-
- if ((low + QSORT_THRESHOLD) > high) {
- // switch to insertion sort
- for (i = low + 1; i <= high; i++) {
- for (k = i; k > low; k--) {
- // if keys[k] >= keys[k-1], break
- if (comparer != null) {
- if (comparer.Compare (keys[k], keys[k-1]) >= 0)
- break;
- } else {
- if (keys[k-1] == null)
- break;
-
- if (keys[k] != null) {
- gcmp = keys[k] as IComparable<K>;
- cmp = keys[k] as IComparable;
- if (gcmp != null) {
- if (gcmp.CompareTo (keys[k-1]) >= 0)
- break;
- } else {
- if (cmp.CompareTo (keys[k-1]) >= 0)
- break;
- }
- }
- }
-
- swap<K, V> (keys, items, k - 1, k);
- }
- }
-
- continue;
- }
-
- // calculate the middle element
- mid = low + ((high - low) / 2);
-
- // once we re-order the low, mid, and high elements to be in
- // ascending order, we'll use mid as our pivot.
- QSortArrange<K, V> (keys, items, low, mid, comparer);
- if (QSortArrange<K, V> (keys, items, mid, high, comparer))
- QSortArrange<K, V> (keys, items, low, mid, comparer);
-
- key = keys[mid];
- gcmp = key as IComparable<K>;
- cmp = key as IComparable;
-
- // since we've already guaranteed that lo <= mid and mid <= hi,
- // we can skip comparing them again.
- k = high - 1;
- i = low + 1;
-
- do {
- // Move the walls in
- if (comparer != null) {
- // find the first element with a value >= pivot value
- while (i < k && comparer.Compare (key, keys[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && comparer.Compare (key, keys[k]) < 0)
- k--;
- } else {
- if (gcmp != null) {
- // find the first element with a value >= pivot value
- while (i < k && gcmp.CompareTo (keys[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && gcmp.CompareTo (keys[k]) < 0)
- k--;
- } else if (cmp != null) {
- // find the first element with a value >= pivot value
- while (i < k && cmp.CompareTo (keys[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && cmp.CompareTo (keys[k]) < 0)
- k--;
- } else {
- while (i < k && keys[i] == null)
- i++;
-
- while (k > i && keys[k] != null)
- k--;
- }
- }
-
- if (k <= i)
- break;
-
- swap<K, V> (keys, items, i, k);
-
- i++;
- k--;
- } while (true);
-
- // push our partitions onto the stack, largest first
- // (to make sure we don't run out of stack space)
- if ((high - k) >= (k - low)) {
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
-
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
- } else {
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
-
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
- }
- } while (sp > 0);
- }
-
- // Specialized version for items==null
- unsafe static void qsort<K> (K [] keys, int low0, int high0, IComparer<K> comparer)
- {
- QSortStack* stack = stackalloc QSortStack [32];
- const int QSORT_THRESHOLD = 7;
- int high, low, mid, i, k;
- IComparable<K> gcmp;
- IComparable cmp;
- int sp = 1;
- K key;
-
- // initialize our stack
- stack[0].high = high0;
- stack[0].low = low0;
-
- do {
- // pop the stack
- sp--;
- high = stack[sp].high;
- low = stack[sp].low;
-
- if ((low + QSORT_THRESHOLD) > high) {
- // switch to insertion sort
- for (i = low + 1; i <= high; i++) {
- for (k = i; k > low; k--) {
- // if keys[k] >= keys[k-1], break
- if (comparer != null) {
- if (comparer.Compare (keys[k], keys[k-1]) >= 0)
- break;
- } else {
- if (keys[k-1] == null)
- break;
-
- if (keys[k] != null) {
- gcmp = keys[k] as IComparable<K>;
- cmp = keys[k] as IComparable;
- if (gcmp != null) {
- if (gcmp.CompareTo (keys[k-1]) >= 0)
- break;
- } else {
- if (cmp.CompareTo (keys[k-1]) >= 0)
- break;
- }
- }
- }
-
- swap<K> (keys, k - 1, k);
- }
- }
-
- continue;
- }
-
- // calculate the middle element
- mid = low + ((high - low) / 2);
-
- // once we re-order the low, mid, and high elements to be in
- // ascending order, we'll use mid as our pivot.
- QSortArrange<K> (keys, low, mid, comparer);
- if (QSortArrange<K> (keys, mid, high, comparer))
- QSortArrange<K> (keys, low, mid, comparer);
-
- key = keys[mid];
- gcmp = key as IComparable<K>;
- cmp = key as IComparable;
-
- // since we've already guaranteed that lo <= mid and mid <= hi,
- // we can skip comparing them again.
- k = high - 1;
- i = low + 1;
-
- do {
- // Move the walls in
- if (comparer != null) {
- // find the first element with a value >= pivot value
- while (i < k && comparer.Compare (key, keys[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && comparer.Compare (key, keys[k]) < 0)
- k--;
- } else {
- if (gcmp != null) {
- // find the first element with a value >= pivot value
- while (i < k && gcmp.CompareTo (keys[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && gcmp.CompareTo (keys[k]) < 0)
- k--;
- } else if (cmp != null) {
- // find the first element with a value >= pivot value
- while (i < k && cmp.CompareTo (keys[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && cmp.CompareTo (keys[k]) < 0)
- k--;
- } else {
- while (i < k && keys[i] == null)
- i++;
-
- while (k > i && keys[k] != null)
- k--;
- }
- }
-
- if (k <= i)
- break;
-
- swap<K> (keys, i, k);
-
- i++;
- k--;
- } while (true);
-
- // push our partitions onto the stack, largest first
- // (to make sure we don't run out of stack space)
- if ((high - k) >= (k - low)) {
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
-
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
- } else {
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
-
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
- }
- } while (sp > 0);
- }
-
- static bool QSortArrange<T> (T [] array, int lo, int hi, Comparison<T> compare)
- {
- if (array[lo] != null) {
- if (array[hi] == null || compare (array[hi], array[lo]) < 0) {
- swap<T> (array, lo, hi);
- return true;
- }
- }
-
- return false;
- }
-
- unsafe static void qsort<T> (T [] array, int low0, int high0, Comparison<T> compare)
- {
- QSortStack* stack = stackalloc QSortStack [32];
- const int QSORT_THRESHOLD = 7;
- int high, low, mid, i, k;
- int sp = 1;
- T key;
-
- // initialize our stack
- stack[0].high = high0;
- stack[0].low = low0;
-
- do {
- // pop the stack
- sp--;
- high = stack[sp].high;
- low = stack[sp].low;
-
- if ((low + QSORT_THRESHOLD) > high) {
- // switch to insertion sort
- for (i = low + 1; i <= high; i++) {
- for (k = i; k > low; k--) {
- if (compare (array[k], array[k-1]) >= 0)
- break;
-
- swap<T> (array, k - 1, k);
- }
- }
-
- continue;
- }
-
- // calculate the middle element
- mid = low + ((high - low) / 2);
-
- // once we re-order the lo, mid, and hi elements to be in
- // ascending order, we'll use mid as our pivot.
- QSortArrange<T> (array, low, mid, compare);
- if (QSortArrange<T> (array, mid, high, compare))
- QSortArrange<T> (array, low, mid, compare);
-
- key = array[mid];
-
- // since we've already guaranteed that lo <= mid and mid <= hi,
- // we can skip comparing them again
- k = high - 1;
- i = low + 1;
-
- do {
- // Move the walls in
- if (key != null) {
- // find the first element with a value >= pivot value
- while (i < k && compare (key, array[i]) > 0)
- i++;
-
- // find the last element with a value <= pivot value
- while (k > i && compare (key, array[k]) < 0)
- k--;
- } else {
- while (i < k && array[i] == null)
- i++;
-
- while (k > i && array[k] != null)
- k--;
- }
-
- if (k <= i)
- break;
-
- swap<T> (array, i, k);
-
- i++;
- k--;
- } while (true);
-
- // push our partitions onto the stack, largest first
- // (to make sure we don't run out of stack space)
- if ((high - k) >= (k - low)) {
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
-
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
- } else {
- if ((k - 1) > low) {
- stack[sp].high = k;
- stack[sp].low = low;
- sp++;
- }
-
- if ((k + 1) < high) {
- stack[sp].high = high;
- stack[sp].low = k;
- sp++;
- }
- }
- } while (sp > 0);
- }
-
- private static void CheckComparerAvailable<K> (K [] keys, int low, int high)
- {
- // move null keys to beginning of array,
- // ensure that non-null keys implement IComparable
- for (int i = low; i < high; i++) {
- K key = keys [i];
- if (key != null) {
- if (!(key is IComparable<K>) && !(key is IComparable)) {
- string msg = Locale.GetText ("No IComparable<T> or IComparable interface found for type '{0}'.");
- throw new InvalidOperationException (String.Format (msg, key.GetType ()));
- }
- }
- }
- }
-
- [MethodImpl ((MethodImplOptions)256)]
- private static void swap<K, V> (K [] keys, V [] items, int i, int j)
- {
- K tmp;
-
- tmp = keys [i];
- keys [i] = keys [j];
- keys [j] = tmp;
-
- if (items != null) {
- V itmp;
- itmp = items [i];
- items [i] = items [j];
- items [j] = itmp;
- }
- }
-
- [MethodImpl ((MethodImplOptions)256)]
- private static void swap<T> (T [] array, int i, int j)
- {
- T tmp = array [i];
- array [i] = array [j];
- array [j] = tmp;
- }
-
- public void CopyTo (Array array, int index)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- // The order of these exception checks may look strange,
- // but that's how the microsoft runtime does it.
- if (this.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
- if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
- throw new ArgumentException ("Destination array was not long " +
- "enough. Check destIndex and length, and the array's " +
- "lower bounds.");
- if (array.Rank > 1)
- throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
- if (index < 0)
- throw new ArgumentOutOfRangeException ("index", Locale.GetText (
- "Value has to be >= 0."));
-
- Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
- }
-
- [ComVisible (false)]
- public void CopyTo (Array array, long index)
- {
- if (index < 0 || index > Int32.MaxValue)
- throw new ArgumentOutOfRangeException ("index", Locale.GetText (
- "Value must be >= 0 and <= Int32.MaxValue."));
-
- CopyTo (array, (int) index);
- }
-
- internal class SimpleEnumerator : IEnumerator, ICloneable
- {
- Array enumeratee;
- int currentpos;
- int length;
-
- public SimpleEnumerator (Array arrayToEnumerate)
- {
- this.enumeratee = arrayToEnumerate;
- this.currentpos = -1;
- this.length = arrayToEnumerate.Length;
- }
-
- public object Current {
- get {
- // Exception messages based on MS implementation
- if (currentpos < 0 )
- throw new InvalidOperationException (Locale.GetText (
- "Enumeration has not started."));
- if (currentpos >= length)
- throw new InvalidOperationException (Locale.GetText (
- "Enumeration has already ended"));
- // Current should not increase the position. So no ++ over here.
- return enumeratee.GetValueImpl (currentpos);
- }
- }
-
- public bool MoveNext()
- {
- //The docs say Current should throw an exception if last
- //call to MoveNext returned false. This means currentpos
- //should be set to length when returning false.
- if (currentpos < length)
- currentpos++;
- if(currentpos < length)
- return true;
- else
- return false;
- }
-
- public void Reset()
- {
- currentpos = -1;
- }
-
- public object Clone ()
- {
- return MemberwiseClone ();
- }
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static void Resize<T> (ref T [] array, int newSize)
- {
- if (newSize < 0)
- throw new ArgumentOutOfRangeException ("newSize");
-
- if (array == null) {
- array = new T [newSize];
- return;
- }
-
- var arr = array;
- int length = arr.Length;
- if (length == newSize)
- return;
-
- T [] a = new T [newSize];
- int tocopy = Math.Min (newSize, length);
-
- if (tocopy < 9) {
- for (int i = 0; i < tocopy; ++i)
- UnsafeStore (a, i, UnsafeLoad (arr, i));
- } else {
- FastCopy (arr, 0, a, 0, tocopy);
- }
- array = a;
- }
-
- public static bool TrueForAll <T> (T [] array, Predicate <T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
- if (match == null)
- throw new ArgumentNullException ("match");
-
- foreach (T t in array)
- if (! match (t))
- return false;
-
- return true;
- }
-
- public static void ForEach<T> (T [] array, Action <T> action)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
- if (action == null)
- throw new ArgumentNullException ("action");
-
- foreach (T t in array)
- action (t);
- }
-
- public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
- if (converter == null)
- throw new ArgumentNullException ("converter");
-
- TOutput [] output = new TOutput [array.Length];
- for (int i = 0; i < array.Length; i ++)
- output [i] = converter (array [i]);
-
- return output;
- }
-
- public static int FindLastIndex<T> (T [] array, Predicate <T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- return GetLastIndex (array, 0, array.Length, match);
- }
-
- public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
- {
- if (array == null)
- throw new ArgumentNullException ();
-
- if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
- throw new ArgumentOutOfRangeException ("startIndex");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- return GetLastIndex (array, 0, startIndex + 1, match);
- }
-
- public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
- throw new ArgumentOutOfRangeException ("startIndex");
-
- if (count < 0)
- throw new ArgumentOutOfRangeException ("count");
-
- if (startIndex - count + 1 < 0)
- throw new ArgumentOutOfRangeException ("count must refer to a location within the array");
-
- return GetLastIndex (array, startIndex - count + 1, count, match);
- }
-
- internal static int GetLastIndex<T> (T[] array, int startIndex, int count, Predicate<T> match)
- {
- // unlike FindLastIndex, takes regular params for search range
- for (int i = startIndex + count; i != startIndex;)
- if (match (array [--i]))
- return i;
-
- return -1;
- }
-
- public static int FindIndex<T> (T [] array, Predicate<T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- return GetIndex (array, 0, array.Length, match);
- }
-
- public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
- throw new ArgumentOutOfRangeException ("startIndex");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- return GetIndex (array, startIndex, array.Length - startIndex, match);
- }
-
- public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (startIndex < 0)
- throw new ArgumentOutOfRangeException ("startIndex");
-
- if (count < 0)
- throw new ArgumentOutOfRangeException ("count");
-
- if ((uint) startIndex + (uint) count > (uint) array.Length)
- throw new ArgumentOutOfRangeException ("index and count exceed length of list");
-
- return GetIndex (array, startIndex, count, match);
- }
-
- internal static int GetIndex<T> (T[] array, int startIndex, int count, Predicate<T> match)
- {
- int end = startIndex + count;
- for (int i = startIndex; i < end; i ++)
- if (match (array [i]))
- return i;
-
- return -1;
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int BinarySearch<T> (T [] array, T value)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return BinarySearch<T> (array, 0, array.Length, value, null);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return BinarySearch<T> (array, 0, array.Length, value, comparer);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int BinarySearch<T> (T [] array, int index, int length, T value)
- {
- return BinarySearch<T> (array, index, length, value, null);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
- public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
- if (index < 0)
- throw new ArgumentOutOfRangeException ("index", Locale.GetText (
- "index is less than the lower bound of array."));
- if (length < 0)
- throw new ArgumentOutOfRangeException ("length", Locale.GetText (
- "Value has to be >= 0."));
- // re-ordered to avoid possible integer overflow
- if (index > array.Length - length)
- throw new ArgumentException (Locale.GetText (
- "index and length do not specify a valid range in array."));
- if (comparer == null)
- comparer = Comparer <T>.Default;
-
- int iMin = index;
- int iMax = index + length - 1;
- int iCmp = 0;
- try {
- while (iMin <= iMax) {
- // Be careful with overflows
- int iMid = iMin + ((iMax - iMin) / 2);
- iCmp = comparer.Compare (array [iMid], value);
-
- if (iCmp == 0)
- return iMid;
-
- if (iCmp > 0)
- iMax = iMid - 1;
- else
- iMin = iMid + 1; // compensate for the rounding down
- }
- } catch (Exception e) {
- throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
- }
-
- return ~iMin;
- }
-
- public static int IndexOf<T> (T [] array, T value)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return IndexOf<T> (array, value, 0, array.Length);
- }
-
- public static int IndexOf<T> (T [] array, T value, int startIndex)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return IndexOf<T> (array, value, startIndex, array.Length - startIndex);
- }
-
- public static int IndexOf<T> (T[] array, T value, int startIndex, int count)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- // re-ordered to avoid possible integer overflow
- if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
- throw new ArgumentOutOfRangeException ();
-
- return EqualityComparer<T>.Default.IndexOf (array, value, startIndex, count);
- }
-
- public static int LastIndexOf<T> (T [] array, T value)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (array.Length == 0)
- return -1;
- return LastIndexOf<T> (array, value, array.Length - 1);
- }
-
- public static int LastIndexOf<T> (T [] array, T value, int startIndex)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return LastIndexOf<T> (array, value, startIndex, startIndex + 1);
- }
-
- public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (count < 0 || startIndex < array.GetLowerBound (0) ||
- startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
- throw new ArgumentOutOfRangeException ();
-
- EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
- for (int i = startIndex; i >= startIndex - count + 1; i--) {
- if (equalityComparer.Equals (array [i], value))
- return i;
- }
-
- return -1;
- }
-
- public static T [] FindAll<T> (T [] array, Predicate <T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- int pos = 0;
- T [] d = new T [array.Length];
- foreach (T t in array)
- if (match (t))
- d [pos++] = t;
-
- Resize <T> (ref d, pos);
- return d;
- }
-
- [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
- public static T[] Empty<T>()
- {
- return EmptyArray<T>.Value;
- }
-
- public static bool Exists<T> (T [] array, Predicate <T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- foreach (T t in array)
- if (match (t))
- return true;
- return false;
- }
-
- public static ReadOnlyCollection<T> AsReadOnly<T> (T[] array)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- return new ReadOnlyCollection<T> (array);
- }
-
- public static void Fill<T> (T[] array, T value)
- {
- if (array == null)
- throw new ArgumentNullException (nameof (array));
-
- for (int i = 0; i < array.Length; i++)
- array [i] = value;
- }
-
- public static void Fill<T> (T[] array, T value, int startIndex, int count)
- {
- if (array == null)
- throw new ArgumentNullException (nameof (array));
-
- if (startIndex < 0 || startIndex > array.Length)
- throw new ArgumentOutOfRangeException (nameof (startIndex));
-
- if (count < 0 || startIndex > array.Length - count)
- throw new ArgumentOutOfRangeException (nameof (count));
-
- for (int i = startIndex; i < startIndex + count; i++)
- array [i] = value;
- }
-
- public static T Find<T> (T [] array, Predicate<T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- foreach (T t in array)
- if (match (t))
- return t;
-
- return default (T);
- }
-
- public static T FindLast<T> (T [] array, Predicate <T> match)
- {
- if (array == null)
- throw new ArgumentNullException ("array");
-
- if (match == null)
- throw new ArgumentNullException ("match");
-
- for (int i = array.Length - 1; i >= 0; i--)
- if (match (array [i]))
- return array [i];
-
- return default (T);
- }
-
- [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
- //
- // The constrained copy should guarantee that if there is an exception thrown
- // during the copy, the destination array remains unchanged.
- // This is related to System.Runtime.Reliability.CER
- public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
- {
- Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length);
+ return GetValueImpl (flattenedIndex);
}
#region Unsafe array operations
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
+using System.Linq;
using NUnit.Framework;
}
}
+ [Test]
+ public void SortTestTrickyPivot ()
+ {
+ int[] array = new int[] { 1, 3, 5, 2, 6, 6, 6, 6, 6, 6, 6,7 ,4 };
+
+ var list = array.ToList<int>();
+
+ list.Sort(delegate (int x, int y)
+ {
+ return x < y ? -1 : 1;
+ });
+
+ var res = string.Join (",", list);
+ Assert.AreEqual ("1,2,3,4,5,6,6,6,6,6,6,6,7", res);
+ }
+
[Test]
public void ClearTest ()
{
public void Test_Contains_After_Remove ()
{
List<int> list = new List<int> ();
- list.Add (2);
+ list.Add (2);
- list.Remove (2);
+ list.Remove (2);
Assert.AreEqual (false, list.Contains (2), "#0");
}
}
[Test]
- public void Check_InvalidOperationException() {
- object[] arr = new object[] {new SomeComparable (), new SomeIncomparable (), new SomeComparable ()};
+ public void Check_NoInvalidOperationException ()
+ {
+ Array arr = new object[] {new SomeComparable (), new SomeIncomparable (), new SomeComparable ()};
- try {
- Array.Sort (arr);
- Assert.Fail ("#1");
- } catch (InvalidOperationException) {}
+ Array.Sort (arr);
- try {
- Array.Sort (arr, (Array)null);
- Assert.Fail ("#2");
- } catch (InvalidOperationException) {}
+ Array.Sort (arr, (Array)null);
- try {
- Array.Sort (arr, (IComparer)null);
- Assert.Fail ("#3");
- } catch (InvalidOperationException) {}
+ Array.Sort (arr, (IComparer)null);
- try {
- Array.Sort (arr, 0, 3);
- Assert.Fail ("#4");
- } catch (InvalidOperationException) {}
+ Array.Sort (arr, 0, 3);
- try {
- Array.Sort (arr, null, null);
- Assert.Fail ("#5");
- } catch (InvalidOperationException) {}
+ Array.Sort (arr, null, null);
- try {
- Array.Sort (arr, null, 0, 3);
- Assert.Fail ("#6");
- } catch (InvalidOperationException) {}
+ Array.Sort (arr, null, 0, 3);
- try {
- Array.Sort (arr, 0, 3, null);
- Assert.Fail ("#7");
- } catch (InvalidOperationException) {}
+ Array.Sort (arr, 0, 3, null);
- try {
- Array.Sort (arr, null, 0, 3, null);
- Assert.Fail ("#8");
- } catch (InvalidOperationException) {}
-
- try {
- Array.Sort<object> (arr);
- Assert.Fail ("#9");
- } catch (InvalidOperationException) {}
+ Array.Sort (arr, null, 0, 3, null);
+ }
+
+ [Test]
+ public void Check_NoInvalidOperationException_Generic ()
+ {
+ object[] arr = new object[] {new SomeComparable (), new SomeIncomparable (), new SomeComparable ()};
+
+ Array.Sort<object> (arr);
- try {
- Array.Sort<object, object> (arr, null);
- Assert.Fail ("#10");
- } catch (InvalidOperationException) {}
+ Array.Sort<object, object> (arr, null);
- try {
- Array.Sort<object> (arr, (IComparer<object>)null);
- Assert.Fail ("#11");
- } catch (InvalidOperationException) {}
+ Array.Sort<object> (arr, (IComparer<object>)null);
- try {
- Array.Sort<object, object> (arr, null, null);
- Assert.Fail ("#12");
- } catch (InvalidOperationException) {}
+ Array.Sort<object, object> (arr, null, null);
- try {
- Array.Sort<object> (arr, 0, 3);
- Assert.Fail ("#13");
- } catch (InvalidOperationException) {}
+ Array.Sort<object> (arr, 0, 3);
- try {
- Array.Sort<object, object> (arr, null, 0, 3);
- Assert.Fail ("#14");
- } catch (InvalidOperationException) {}
+ Array.Sort<object, object> (arr, null, 0, 3);
- try {
- Array.Sort<object> (arr, 0, 3, null);
- Assert.Fail ("#15");
- } catch (InvalidOperationException) {}
+ Array.Sort<object> (arr, 0, 3, null);
- try {
- Array.Sort<object, object> (arr, null, 0, 3, null);
- Assert.Fail ("#16");
- } catch (InvalidOperationException) {}
+ Array.Sort<object, object> (arr, null, 0, 3, null);
}
}
}
int[] myBoundArray = new int[1] { Int32.MinValue };
Array myExtremeArray=Array.CreateInstance ( typeof(String), myLengthArray, myBoundArray );
Assert.AreEqual (Int32.MaxValue, ((IList)myExtremeArray).IndexOf (42), "AD04");
-
}
[Test]
--- /dev/null
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+
+/*============================================================
+**
+**
+**
+**
+**
+** Purpose: class to sort arrays
+**
+**
+===========================================================*/
+
+using System;
+using System.Globalization;
+using System.Runtime.CompilerServices;
+using System.Diagnostics;
+using System.Diagnostics.Contracts;
+using System.Runtime.Versioning;
+#if MONO
+using System.Diagnostics.Private;
+#endif
+
+namespace System.Collections.Generic
+{
+ #region ArraySortHelper for single arrays
+
+ internal interface IArraySortHelper<TKey>
+ {
+ void Sort(TKey[] keys, int index, int length, IComparer<TKey> comparer);
+ int BinarySearch(TKey[] keys, int index, int length, TKey value, IComparer<TKey> comparer);
+ }
+
+ internal static class IntrospectiveSortUtilities
+ {
+ // This is the threshold where Introspective sort switches to Insertion sort.
+ // Imperically, 16 seems to speed up most cases without slowing down others, at least for integers.
+ // Large value types may benefit from a smaller number.
+ internal const int IntrosortSizeThreshold = 16;
+
+ internal static int FloorLog2(int n)
+ {
+ int result = 0;
+ while (n >= 1)
+ {
+ result++;
+ n = n / 2;
+ }
+ return result;
+ }
+
+ internal static void ThrowOrIgnoreBadComparer(Object comparer)
+ {
+ throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer));
+ }
+ }
+
+ [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")]
+ internal class ArraySortHelper<T>
+ : IArraySortHelper<T>
+ {
+ private static volatile IArraySortHelper<T> defaultArraySortHelper;
+
+ public static IArraySortHelper<T> Default
+ {
+ get
+ {
+ IArraySortHelper<T> sorter = defaultArraySortHelper;
+ if (sorter == null)
+ sorter = CreateArraySortHelper();
+
+ return sorter;
+ }
+ }
+
+ private static IArraySortHelper<T> CreateArraySortHelper()
+ {
+#if !MONO
+ if (typeof(IComparable<T>).IsAssignableFrom(typeof(T)))
+ {
+ defaultArraySortHelper = (IArraySortHelper<T>)RuntimeTypeHandle.Allocate(typeof(GenericArraySortHelper<string>).TypeHandle.Instantiate(new Type[] { typeof(T) }));
+ }
+ else
+#endif
+ {
+ defaultArraySortHelper = new ArraySortHelper<T>();
+ }
+ return defaultArraySortHelper;
+ }
+
+ #region IArraySortHelper<T> Members
+
+ public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
+ {
+ Debug.Assert(keys != null, "Check the arguments in the caller!");
+ Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+
+ // Add a try block here to detect IComparers (or their
+ // underlying IComparables, etc) that are bogus.
+ try
+ {
+ if (comparer == null)
+ {
+ comparer = Comparer<T>.Default;
+ }
+
+ IntrospectiveSort(keys, index, length, comparer.Compare);
+ }
+ catch (IndexOutOfRangeException)
+ {
+ IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
+ }
+ }
+
+ public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
+ {
+ try
+ {
+ if (comparer == null)
+ {
+ comparer = Comparer<T>.Default;
+ }
+
+ return InternalBinarySearch(array, index, length, value, comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
+ }
+ }
+
+ #endregion
+
+ internal static void Sort(T[] keys, int index, int length, Comparison<T> comparer)
+ {
+ Debug.Assert(keys != null, "Check the arguments in the caller!");
+ Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+ Debug.Assert(comparer != null, "Check the arguments in the caller!");
+
+ // Add a try block here to detect bogus comparisons
+ try
+ {
+ IntrospectiveSort(keys, index, length, comparer);
+ }
+ catch (IndexOutOfRangeException)
+ {
+ IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
+ }
+ }
+
+ internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
+ {
+ Contract.Requires(array != null, "Check the arguments in the caller!");
+ Contract.Requires(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
+
+ int lo = index;
+ int hi = index + length - 1;
+ while (lo <= hi)
+ {
+ int i = lo + ((hi - lo) >> 1);
+ int order = comparer.Compare(array[i], value);
+
+ if (order == 0) return i;
+ if (order < 0)
+ {
+ lo = i + 1;
+ }
+ else
+ {
+ hi = i - 1;
+ }
+ }
+
+ return ~lo;
+ }
+
+ private static void SwapIfGreater(T[] keys, Comparison<T> comparer, int a, int b)
+ {
+ if (a != b)
+ {
+ if (comparer(keys[a], keys[b]) > 0)
+ {
+ T key = keys[a];
+ keys[a] = keys[b];
+ keys[b] = key;
+ }
+ }
+ }
+
+ private static void Swap(T[] a, int i, int j)
+ {
+ if (i != j)
+ {
+ T t = a[i];
+ a[i] = a[j];
+ a[j] = t;
+ }
+ }
+
+ internal static void IntrospectiveSort(T[] keys, int left, int length, Comparison<T> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(left >= 0);
+ Contract.Requires(length >= 0);
+ Contract.Requires(length <= keys.Length);
+ Contract.Requires(length + left <= keys.Length);
+
+ if (length < 2)
+ return;
+
+ IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
+ }
+
+ private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, Comparison<T> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi < keys.Length);
+
+ while (hi > lo)
+ {
+ int partitionSize = hi - lo + 1;
+ if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
+ {
+ if (partitionSize == 1)
+ {
+ return;
+ }
+ if (partitionSize == 2)
+ {
+ SwapIfGreater(keys, comparer, lo, hi);
+ return;
+ }
+ if (partitionSize == 3)
+ {
+ SwapIfGreater(keys, comparer, lo, hi - 1);
+ SwapIfGreater(keys, comparer, lo, hi);
+ SwapIfGreater(keys, comparer, hi - 1, hi);
+ return;
+ }
+
+ InsertionSort(keys, lo, hi, comparer);
+ return;
+ }
+
+ if (depthLimit == 0)
+ {
+ Heapsort(keys, lo, hi, comparer);
+ return;
+ }
+ depthLimit--;
+
+ int p = PickPivotAndPartition(keys, lo, hi, comparer);
+ // Note we've already partitioned around the pivot and do not have to move the pivot again.
+ IntroSort(keys, p + 1, hi, depthLimit, comparer);
+ hi = p - 1;
+ }
+ }
+
+ private static int PickPivotAndPartition(T[] keys, int lo, int hi, Comparison<T> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi > lo);
+ Contract.Requires(hi < keys.Length);
+ Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
+
+ // Compute median-of-three. But also partition them, since we've done the comparison.
+ int middle = lo + ((hi - lo) / 2);
+
+ // Sort lo, mid and hi appropriately, then pick mid as the pivot.
+ SwapIfGreater(keys, comparer, lo, middle); // swap the low with the mid point
+ SwapIfGreater(keys, comparer, lo, hi); // swap the low with the high
+ SwapIfGreater(keys, comparer, middle, hi); // swap the middle with the high
+
+ T pivot = keys[middle];
+ Swap(keys, middle, hi - 1);
+ int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
+
+ while (left < right)
+ {
+ while (comparer(keys[++left], pivot) < 0) ;
+ while (comparer(pivot, keys[--right]) < 0) ;
+
+ if (left >= right)
+ break;
+
+ Swap(keys, left, right);
+ }
+
+ // Put pivot in the right location.
+ Swap(keys, left, (hi - 1));
+ return left;
+ }
+
+ private static void Heapsort(T[] keys, int lo, int hi, Comparison<T> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi > lo);
+ Contract.Requires(hi < keys.Length);
+
+ int n = hi - lo + 1;
+ for (int i = n / 2; i >= 1; i = i - 1)
+ {
+ DownHeap(keys, i, n, lo, comparer);
+ }
+ for (int i = n; i > 1; i = i - 1)
+ {
+ Swap(keys, lo, lo + i - 1);
+ DownHeap(keys, 1, i - 1, lo, comparer);
+ }
+ }
+
+ private static void DownHeap(T[] keys, int i, int n, int lo, Comparison<T> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(lo < keys.Length);
+
+ T d = keys[lo + i - 1];
+ int child;
+ while (i <= n / 2)
+ {
+ child = 2 * i;
+ if (child < n && comparer(keys[lo + child - 1], keys[lo + child]) < 0)
+ {
+ child++;
+ }
+ if (!(comparer(d, keys[lo + child - 1]) < 0))
+ break;
+ keys[lo + i - 1] = keys[lo + child - 1];
+ i = child;
+ }
+ keys[lo + i - 1] = d;
+ }
+
+ private static void InsertionSort(T[] keys, int lo, int hi, Comparison<T> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi >= lo);
+ Contract.Requires(hi <= keys.Length);
+
+ int i, j;
+ T t;
+ for (i = lo; i < hi; i++)
+ {
+ j = i;
+ t = keys[i + 1];
+ while (j >= lo && comparer(t, keys[j]) < 0)
+ {
+ keys[j + 1] = keys[j];
+ j--;
+ }
+ keys[j + 1] = t;
+ }
+ }
+ }
+
+ [Serializable()]
+ internal class GenericArraySortHelper<T>
+ : IArraySortHelper<T>
+ where T : IComparable<T>
+ {
+ // Do not add a constructor to this class because ArraySortHelper<T>.CreateSortHelper will not execute it
+
+ #region IArraySortHelper<T> Members
+
+ public void Sort(T[] keys, int index, int length, IComparer<T> comparer)
+ {
+ Debug.Assert(keys != null, "Check the arguments in the caller!");
+ Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+
+ try
+ {
+ if (comparer == null || comparer == Comparer<T>.Default)
+ {
+ IntrospectiveSort(keys, index, length);
+ }
+ else
+ {
+ ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer.Compare);
+ }
+ }
+ catch (IndexOutOfRangeException)
+ {
+ IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
+ }
+ }
+
+ public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
+ {
+ Debug.Assert(array != null, "Check the arguments in the caller!");
+ Debug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
+
+ try
+ {
+ if (comparer == null || comparer == Comparer<T>.Default)
+ {
+ return BinarySearch(array, index, length, value);
+ }
+ else
+ {
+ return ArraySortHelper<T>.InternalBinarySearch(array, index, length, value, comparer);
+ }
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
+ }
+ }
+
+ #endregion
+
+ // This function is called when the user doesn't specify any comparer.
+ // Since T is constrained here, we can call IComparable<T>.CompareTo here.
+ // We can avoid boxing for value type and casting for reference types.
+ private static int BinarySearch(T[] array, int index, int length, T value)
+ {
+ int lo = index;
+ int hi = index + length - 1;
+ while (lo <= hi)
+ {
+ int i = lo + ((hi - lo) >> 1);
+ int order;
+ if (array[i] == null)
+ {
+ order = (value == null) ? 0 : -1;
+ }
+ else
+ {
+ order = array[i].CompareTo(value);
+ }
+
+ if (order == 0)
+ {
+ return i;
+ }
+
+ if (order < 0)
+ {
+ lo = i + 1;
+ }
+ else
+ {
+ hi = i - 1;
+ }
+ }
+
+ return ~lo;
+ }
+
+ private static void SwapIfGreaterWithItems(T[] keys, int a, int b)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(0 <= a && a < keys.Length);
+ Contract.Requires(0 <= b && b < keys.Length);
+
+ if (a != b)
+ {
+ if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0)
+ {
+ T key = keys[a];
+ keys[a] = keys[b];
+ keys[b] = key;
+ }
+ }
+ }
+
+ private static void Swap(T[] a, int i, int j)
+ {
+ if (i != j)
+ {
+ T t = a[i];
+ a[i] = a[j];
+ a[j] = t;
+ }
+ }
+
+ internal static void IntrospectiveSort(T[] keys, int left, int length)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(left >= 0);
+ Contract.Requires(length >= 0);
+ Contract.Requires(length <= keys.Length);
+ Contract.Requires(length + left <= keys.Length);
+
+ if (length < 2)
+ return;
+
+ IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
+ }
+
+ private static void IntroSort(T[] keys, int lo, int hi, int depthLimit)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi < keys.Length);
+
+ while (hi > lo)
+ {
+ int partitionSize = hi - lo + 1;
+ if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
+ {
+ if (partitionSize == 1)
+ {
+ return;
+ }
+ if (partitionSize == 2)
+ {
+ SwapIfGreaterWithItems(keys, lo, hi);
+ return;
+ }
+ if (partitionSize == 3)
+ {
+ SwapIfGreaterWithItems(keys, lo, hi - 1);
+ SwapIfGreaterWithItems(keys, lo, hi);
+ SwapIfGreaterWithItems(keys, hi - 1, hi);
+ return;
+ }
+
+ InsertionSort(keys, lo, hi);
+ return;
+ }
+
+ if (depthLimit == 0)
+ {
+ Heapsort(keys, lo, hi);
+ return;
+ }
+ depthLimit--;
+
+ int p = PickPivotAndPartition(keys, lo, hi);
+ // Note we've already partitioned around the pivot and do not have to move the pivot again.
+ IntroSort(keys, p + 1, hi, depthLimit);
+ hi = p - 1;
+ }
+ }
+
+ private static int PickPivotAndPartition(T[] keys, int lo, int hi)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi > lo);
+ Contract.Requires(hi < keys.Length);
+ Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
+
+ // Compute median-of-three. But also partition them, since we've done the comparison.
+ int middle = lo + ((hi - lo) / 2);
+
+ // Sort lo, mid and hi appropriately, then pick mid as the pivot.
+ SwapIfGreaterWithItems(keys, lo, middle); // swap the low with the mid point
+ SwapIfGreaterWithItems(keys, lo, hi); // swap the low with the high
+ SwapIfGreaterWithItems(keys, middle, hi); // swap the middle with the high
+
+ T pivot = keys[middle];
+ Swap(keys, middle, hi - 1);
+ int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
+
+ while (left < right)
+ {
+ if (pivot == null)
+ {
+ while (left < (hi - 1) && keys[++left] == null) ;
+ while (right > lo && keys[--right] != null) ;
+ }
+ else
+ {
+ while (pivot.CompareTo(keys[++left]) > 0) ;
+ while (pivot.CompareTo(keys[--right]) < 0) ;
+ }
+
+ if (left >= right)
+ break;
+
+ Swap(keys, left, right);
+ }
+
+ // Put pivot in the right location.
+ Swap(keys, left, (hi - 1));
+ return left;
+ }
+
+ private static void Heapsort(T[] keys, int lo, int hi)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi > lo);
+ Contract.Requires(hi < keys.Length);
+
+ int n = hi - lo + 1;
+ for (int i = n / 2; i >= 1; i = i - 1)
+ {
+ DownHeap(keys, i, n, lo);
+ }
+ for (int i = n; i > 1; i = i - 1)
+ {
+ Swap(keys, lo, lo + i - 1);
+ DownHeap(keys, 1, i - 1, lo);
+ }
+ }
+
+ private static void DownHeap(T[] keys, int i, int n, int lo)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(lo < keys.Length);
+
+ T d = keys[lo + i - 1];
+ int child;
+ while (i <= n / 2)
+ {
+ child = 2 * i;
+ if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0))
+ {
+ child++;
+ }
+ if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0)
+ break;
+ keys[lo + i - 1] = keys[lo + child - 1];
+ i = child;
+ }
+ keys[lo + i - 1] = d;
+ }
+
+ private static void InsertionSort(T[] keys, int lo, int hi)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi >= lo);
+ Contract.Requires(hi <= keys.Length);
+
+ int i, j;
+ T t;
+ for (i = lo; i < hi; i++)
+ {
+ j = i;
+ t = keys[i + 1];
+ while (j >= lo && (t == null || t.CompareTo(keys[j]) < 0))
+ {
+ keys[j + 1] = keys[j];
+ j--;
+ }
+ keys[j + 1] = t;
+ }
+ }
+ }
+
+ #endregion
+
+ #region ArraySortHelper for paired key and value arrays
+
+ internal interface IArraySortHelper<TKey, TValue>
+ {
+ void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer);
+ }
+
+ [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`2")]
+ internal class ArraySortHelper<TKey, TValue>
+ : IArraySortHelper<TKey, TValue>
+ {
+ private static volatile IArraySortHelper<TKey, TValue> defaultArraySortHelper;
+
+ public static IArraySortHelper<TKey, TValue> Default
+ {
+ get
+ {
+ IArraySortHelper<TKey, TValue> sorter = defaultArraySortHelper;
+ if (sorter == null)
+ sorter = CreateArraySortHelper();
+
+ return sorter;
+ }
+ }
+
+ private static IArraySortHelper<TKey, TValue> CreateArraySortHelper()
+ {
+#if !MONO
+ if (typeof(IComparable<TKey>).IsAssignableFrom(typeof(TKey)))
+ {
+ defaultArraySortHelper = (IArraySortHelper<TKey, TValue>)RuntimeTypeHandle.Allocate(typeof(GenericArraySortHelper<string, string>).TypeHandle.Instantiate(new Type[] { typeof(TKey), typeof(TValue) }));
+ }
+ else
+#endif
+ {
+ defaultArraySortHelper = new ArraySortHelper<TKey, TValue>();
+ }
+ return defaultArraySortHelper;
+ }
+
+ public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer)
+ {
+ Debug.Assert(keys != null, "Check the arguments in the caller!"); // Precondition on interface method
+ Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+
+ // Add a try block here to detect IComparers (or their
+ // underlying IComparables, etc) that are bogus.
+ try
+ {
+ if (comparer == null || comparer == Comparer<TKey>.Default)
+ {
+ comparer = Comparer<TKey>.Default;
+ }
+
+ IntrospectiveSort(keys, values, index, length, comparer);
+ }
+ catch (IndexOutOfRangeException)
+ {
+ IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
+ }
+ }
+
+ private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, IComparer<TKey> comparer, int a, int b)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values == null || values.Length >= keys.Length);
+ Contract.Requires(comparer != null);
+ Contract.Requires(0 <= a && a < keys.Length);
+ Contract.Requires(0 <= b && b < keys.Length);
+
+ if (a != b)
+ {
+ if (comparer.Compare(keys[a], keys[b]) > 0)
+ {
+ TKey key = keys[a];
+ keys[a] = keys[b];
+ keys[b] = key;
+ if (values != null)
+ {
+ TValue value = values[a];
+ values[a] = values[b];
+ values[b] = value;
+ }
+ }
+ }
+ }
+
+ private static void Swap(TKey[] keys, TValue[] values, int i, int j)
+ {
+ if (i != j)
+ {
+ TKey k = keys[i];
+ keys[i] = keys[j];
+ keys[j] = k;
+ if (values != null)
+ {
+ TValue v = values[i];
+ values[i] = values[j];
+ values[j] = v;
+ }
+ }
+ }
+
+ internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length, IComparer<TKey> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(left >= 0);
+ Contract.Requires(length >= 0);
+ Contract.Requires(length <= keys.Length);
+ Contract.Requires(length + left <= keys.Length);
+ Contract.Requires(length + left <= values.Length);
+
+ if (length < 2)
+ return;
+
+ IntroSort(keys, values, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer);
+ }
+
+ private static void IntroSort(TKey[] keys, TValue[] values, int lo, int hi, int depthLimit, IComparer<TKey> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi < keys.Length);
+
+ while (hi > lo)
+ {
+ int partitionSize = hi - lo + 1;
+ if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
+ {
+ if (partitionSize == 1)
+ {
+ return;
+ }
+ if (partitionSize == 2)
+ {
+ SwapIfGreaterWithItems(keys, values, comparer, lo, hi);
+ return;
+ }
+ if (partitionSize == 3)
+ {
+ SwapIfGreaterWithItems(keys, values, comparer, lo, hi - 1);
+ SwapIfGreaterWithItems(keys, values, comparer, lo, hi);
+ SwapIfGreaterWithItems(keys, values, comparer, hi - 1, hi);
+ return;
+ }
+
+ InsertionSort(keys, values, lo, hi, comparer);
+ return;
+ }
+
+ if (depthLimit == 0)
+ {
+ Heapsort(keys, values, lo, hi, comparer);
+ return;
+ }
+ depthLimit--;
+
+ int p = PickPivotAndPartition(keys, values, lo, hi, comparer);
+ // Note we've already partitioned around the pivot and do not have to move the pivot again.
+ IntroSort(keys, values, p + 1, hi, depthLimit, comparer);
+ hi = p - 1;
+ }
+ }
+
+ private static int PickPivotAndPartition(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi > lo);
+ Contract.Requires(hi < keys.Length);
+ Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
+
+ // Compute median-of-three. But also partition them, since we've done the comparison.
+ int middle = lo + ((hi - lo) / 2);
+
+ // Sort lo, mid and hi appropriately, then pick mid as the pivot.
+ SwapIfGreaterWithItems(keys, values, comparer, lo, middle); // swap the low with the mid point
+ SwapIfGreaterWithItems(keys, values, comparer, lo, hi); // swap the low with the high
+ SwapIfGreaterWithItems(keys, values, comparer, middle, hi); // swap the middle with the high
+
+ TKey pivot = keys[middle];
+ Swap(keys, values, middle, hi - 1);
+ int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
+
+ while (left < right)
+ {
+ while (comparer.Compare(keys[++left], pivot) < 0) ;
+ while (comparer.Compare(pivot, keys[--right]) < 0) ;
+
+ if (left >= right)
+ break;
+
+ Swap(keys, values, left, right);
+ }
+
+ // Put pivot in the right location.
+ Swap(keys, values, left, (hi - 1));
+ return left;
+ }
+
+ private static void Heapsort(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi > lo);
+ Contract.Requires(hi < keys.Length);
+
+ int n = hi - lo + 1;
+ for (int i = n / 2; i >= 1; i = i - 1)
+ {
+ DownHeap(keys, values, i, n, lo, comparer);
+ }
+ for (int i = n; i > 1; i = i - 1)
+ {
+ Swap(keys, values, lo, lo + i - 1);
+ DownHeap(keys, values, 1, i - 1, lo, comparer);
+ }
+ }
+
+ private static void DownHeap(TKey[] keys, TValue[] values, int i, int n, int lo, IComparer<TKey> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(lo < keys.Length);
+
+ TKey d = keys[lo + i - 1];
+ TValue dValue = (values != null) ? values[lo + i - 1] : default(TValue);
+ int child;
+ while (i <= n / 2)
+ {
+ child = 2 * i;
+ if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
+ {
+ child++;
+ }
+ if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
+ break;
+ keys[lo + i - 1] = keys[lo + child - 1];
+ if (values != null)
+ values[lo + i - 1] = values[lo + child - 1];
+ i = child;
+ }
+ keys[lo + i - 1] = d;
+ if (values != null)
+ values[lo + i - 1] = dValue;
+ }
+
+ private static void InsertionSort(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(comparer != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi >= lo);
+ Contract.Requires(hi <= keys.Length);
+
+ int i, j;
+ TKey t;
+ TValue tValue;
+ for (i = lo; i < hi; i++)
+ {
+ j = i;
+ t = keys[i + 1];
+ tValue = (values != null) ? values[i + 1] : default(TValue);
+ while (j >= lo && comparer.Compare(t, keys[j]) < 0)
+ {
+ keys[j + 1] = keys[j];
+ if (values != null)
+ values[j + 1] = values[j];
+ j--;
+ }
+ keys[j + 1] = t;
+ if (values != null)
+ values[j + 1] = tValue;
+ }
+ }
+ }
+
+ internal class GenericArraySortHelper<TKey, TValue>
+ : IArraySortHelper<TKey, TValue>
+ where TKey : IComparable<TKey>
+ {
+ public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer)
+ {
+ Debug.Assert(keys != null, "Check the arguments in the caller!");
+ Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
+
+ // Add a try block here to detect IComparers (or their
+ // underlying IComparables, etc) that are bogus.
+ try
+ {
+ if (comparer == null || comparer == Comparer<TKey>.Default)
+ {
+ IntrospectiveSort(keys, values, index, length);
+ }
+ else
+ {
+ ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer);
+ }
+ }
+ catch (IndexOutOfRangeException)
+ {
+ IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
+ }
+ }
+
+ private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, int a, int b)
+ {
+ if (a != b)
+ {
+ if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0)
+ {
+ TKey key = keys[a];
+ keys[a] = keys[b];
+ keys[b] = key;
+ if (values != null)
+ {
+ TValue value = values[a];
+ values[a] = values[b];
+ values[b] = value;
+ }
+ }
+ }
+ }
+
+ private static void Swap(TKey[] keys, TValue[] values, int i, int j)
+ {
+ if (i != j)
+ {
+ TKey k = keys[i];
+ keys[i] = keys[j];
+ keys[j] = k;
+ if (values != null)
+ {
+ TValue v = values[i];
+ values[i] = values[j];
+ values[j] = v;
+ }
+ }
+ }
+
+ internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(left >= 0);
+ Contract.Requires(length >= 0);
+ Contract.Requires(length <= keys.Length);
+ Contract.Requires(length + left <= keys.Length);
+ Contract.Requires(length + left <= values.Length);
+
+ if (length < 2)
+ return;
+
+ IntroSort(keys, values, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
+ }
+
+ private static void IntroSort(TKey[] keys, TValue[] values, int lo, int hi, int depthLimit)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi < keys.Length);
+
+ while (hi > lo)
+ {
+ int partitionSize = hi - lo + 1;
+ if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
+ {
+ if (partitionSize == 1)
+ {
+ return;
+ }
+ if (partitionSize == 2)
+ {
+ SwapIfGreaterWithItems(keys, values, lo, hi);
+ return;
+ }
+ if (partitionSize == 3)
+ {
+ SwapIfGreaterWithItems(keys, values, lo, hi - 1);
+ SwapIfGreaterWithItems(keys, values, lo, hi);
+ SwapIfGreaterWithItems(keys, values, hi - 1, hi);
+ return;
+ }
+
+ InsertionSort(keys, values, lo, hi);
+ return;
+ }
+
+ if (depthLimit == 0)
+ {
+ Heapsort(keys, values, lo, hi);
+ return;
+ }
+ depthLimit--;
+
+ int p = PickPivotAndPartition(keys, values, lo, hi);
+ // Note we've already partitioned around the pivot and do not have to move the pivot again.
+ IntroSort(keys, values, p + 1, hi, depthLimit);
+ hi = p - 1;
+ }
+ }
+
+ private static int PickPivotAndPartition(TKey[] keys, TValue[] values, int lo, int hi)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi > lo);
+ Contract.Requires(hi < keys.Length);
+ Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi);
+
+ // Compute median-of-three. But also partition them, since we've done the comparison.
+ int middle = lo + ((hi - lo) / 2);
+
+ // Sort lo, mid and hi appropriately, then pick mid as the pivot.
+ SwapIfGreaterWithItems(keys, values, lo, middle); // swap the low with the mid point
+ SwapIfGreaterWithItems(keys, values, lo, hi); // swap the low with the high
+ SwapIfGreaterWithItems(keys, values, middle, hi); // swap the middle with the high
+
+ TKey pivot = keys[middle];
+ Swap(keys, values, middle, hi - 1);
+ int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
+
+ while (left < right)
+ {
+ if (pivot == null)
+ {
+ while (left < (hi - 1) && keys[++left] == null) ;
+ while (right > lo && keys[--right] != null) ;
+ }
+ else
+ {
+ while (pivot.CompareTo(keys[++left]) > 0) ;
+ while (pivot.CompareTo(keys[--right]) < 0) ;
+ }
+
+ if (left >= right)
+ break;
+
+ Swap(keys, values, left, right);
+ }
+
+ // Put pivot in the right location.
+ Swap(keys, values, left, (hi - 1));
+ return left;
+ }
+
+ private static void Heapsort(TKey[] keys, TValue[] values, int lo, int hi)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi > lo);
+ Contract.Requires(hi < keys.Length);
+
+ int n = hi - lo + 1;
+ for (int i = n / 2; i >= 1; i = i - 1)
+ {
+ DownHeap(keys, values, i, n, lo);
+ }
+ for (int i = n; i > 1; i = i - 1)
+ {
+ Swap(keys, values, lo, lo + i - 1);
+ DownHeap(keys, values, 1, i - 1, lo);
+ }
+ }
+
+ private static void DownHeap(TKey[] keys, TValue[] values, int i, int n, int lo)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(lo < keys.Length);
+
+ TKey d = keys[lo + i - 1];
+ TValue dValue = (values != null) ? values[lo + i - 1] : default(TValue);
+ int child;
+ while (i <= n / 2)
+ {
+ child = 2 * i;
+ if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0))
+ {
+ child++;
+ }
+ if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0)
+ break;
+ keys[lo + i - 1] = keys[lo + child - 1];
+ if (values != null)
+ values[lo + i - 1] = values[lo + child - 1];
+ i = child;
+ }
+ keys[lo + i - 1] = d;
+ if (values != null)
+ values[lo + i - 1] = dValue;
+ }
+
+ private static void InsertionSort(TKey[] keys, TValue[] values, int lo, int hi)
+ {
+ Contract.Requires(keys != null);
+ Contract.Requires(values != null);
+ Contract.Requires(lo >= 0);
+ Contract.Requires(hi >= lo);
+ Contract.Requires(hi <= keys.Length);
+
+ int i, j;
+ TKey t;
+ TValue tValue;
+ for (i = lo; i < hi; i++)
+ {
+ j = i;
+ t = keys[i + 1];
+ tValue = (values != null) ? values[i + 1] : default(TValue);
+ while (j >= lo && (t == null || t.CompareTo(keys[j]) < 0))
+ {
+ keys[j + 1] = keys[j];
+ if (values != null)
+ values[j + 1] = values[j];
+ j--;
+ }
+ keys[j + 1] = t;
+ if (values != null)
+ values[j + 1] = tValue;
+ }
+ }
+ }
+
+ #endregion
+}
--- /dev/null
+using System.Collections;
+using System.Collections.Generic;
+
+namespace System
+{
+ partial class Array
+ {
+ // Private value type used by the Sort methods.
+ private struct SorterObjectArray
+ {
+ private Object[] keys;
+ private Object[] items;
+ private IComparer comparer;
+
+ internal SorterObjectArray(Object[] keys, Object[] items, IComparer comparer)
+ {
+ if (comparer == null) comparer = Comparer.Default;
+ this.keys = keys;
+ this.items = items;
+ this.comparer = comparer;
+ }
+
+ internal void SwapIfGreaterWithItems(int a, int b)
+ {
+ if (a != b)
+ {
+ if (comparer.Compare(keys[a], keys[b]) > 0)
+ {
+ Object temp = keys[a];
+ keys[a] = keys[b];
+ keys[b] = temp;
+ if (items != null)
+ {
+ Object item = items[a];
+ items[a] = items[b];
+ items[b] = item;
+ }
+ }
+ }
+ }
+
+ private void Swap(int i, int j)
+ {
+ Object t = keys[i];
+ keys[i] = keys[j];
+ keys[j] = t;
+
+ if (items != null)
+ {
+ Object item = items[i];
+ items[i] = items[j];
+ items[j] = item;
+ }
+ }
+
+ internal void Sort(int left, int length)
+ {
+ IntrospectiveSort(left, length);
+ }
+
+ private void IntrospectiveSort(int left, int length)
+ {
+ if (length < 2)
+ return;
+
+ try
+ {
+ IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
+ }
+ catch (IndexOutOfRangeException)
+ {
+ IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
+ }
+ }
+
+ private void IntroSort(int lo, int hi, int depthLimit)
+ {
+ while (hi > lo)
+ {
+ int partitionSize = hi - lo + 1;
+ if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
+ {
+ if (partitionSize == 1)
+ {
+ return;
+ }
+ if (partitionSize == 2)
+ {
+ SwapIfGreaterWithItems(lo, hi);
+ return;
+ }
+ if (partitionSize == 3)
+ {
+ SwapIfGreaterWithItems(lo, hi - 1);
+ SwapIfGreaterWithItems(lo, hi);
+ SwapIfGreaterWithItems(hi - 1, hi);
+ return;
+ }
+
+ InsertionSort(lo, hi);
+ return;
+ }
+
+ if (depthLimit == 0)
+ {
+ Heapsort(lo, hi);
+ return;
+ }
+ depthLimit--;
+
+ int p = PickPivotAndPartition(lo, hi);
+ IntroSort(p + 1, hi, depthLimit);
+ hi = p - 1;
+ }
+ }
+
+ private int PickPivotAndPartition(int lo, int hi)
+ {
+ // Compute median-of-three. But also partition them, since we've done the comparison.
+ int mid = lo + (hi - lo) / 2;
+ // Sort lo, mid and hi appropriately, then pick mid as the pivot.
+ SwapIfGreaterWithItems(lo, mid);
+ SwapIfGreaterWithItems(lo, hi);
+ SwapIfGreaterWithItems(mid, hi);
+
+ Object pivot = keys[mid];
+ Swap(mid, hi - 1);
+ int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
+
+ while (left < right)
+ {
+ while (comparer.Compare(keys[++left], pivot) < 0) ;
+ while (comparer.Compare(pivot, keys[--right]) < 0) ;
+
+ if (left >= right)
+ break;
+
+ Swap(left, right);
+ }
+
+ // Put pivot in the right location.
+ Swap(left, (hi - 1));
+ return left;
+ }
+
+ private void Heapsort(int lo, int hi)
+ {
+ int n = hi - lo + 1;
+ for (int i = n / 2; i >= 1; i = i - 1)
+ {
+ DownHeap(i, n, lo);
+ }
+ for (int i = n; i > 1; i = i - 1)
+ {
+ Swap(lo, lo + i - 1);
+
+ DownHeap(1, i - 1, lo);
+ }
+ }
+
+ private void DownHeap(int i, int n, int lo)
+ {
+ Object d = keys[lo + i - 1];
+ Object dt = (items != null) ? items[lo + i - 1] : null;
+ int child;
+ while (i <= n / 2)
+ {
+ child = 2 * i;
+ if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
+ {
+ child++;
+ }
+ if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
+ break;
+ keys[lo + i - 1] = keys[lo + child - 1];
+ if (items != null)
+ items[lo + i - 1] = items[lo + child - 1];
+ i = child;
+ }
+ keys[lo + i - 1] = d;
+ if (items != null)
+ items[lo + i - 1] = dt;
+ }
+
+ private void InsertionSort(int lo, int hi)
+ {
+ int i, j;
+ Object t, ti;
+ for (i = lo; i < hi; i++)
+ {
+ j = i;
+ t = keys[i + 1];
+ ti = (items != null) ? items[i + 1] : null;
+ while (j >= lo && comparer.Compare(t, keys[j]) < 0)
+ {
+ keys[j + 1] = keys[j];
+ if (items != null)
+ items[j + 1] = items[j];
+ j--;
+ }
+ keys[j + 1] = t;
+ if (items != null)
+ items[j + 1] = ti;
+ }
+ }
+ }
+
+ // Private value used by the Sort methods for instances of Array.
+ // This is slower than the one for Object[], since we can't use the JIT helpers
+ // to access the elements. We must use GetValue & SetValue.
+ private struct SorterGenericArray
+ {
+ private Array keys;
+ private Array items;
+ private IComparer comparer;
+
+ internal SorterGenericArray(Array keys, Array items, IComparer comparer)
+ {
+ if (comparer == null) comparer = Comparer.Default;
+ this.keys = keys;
+ this.items = items;
+ this.comparer = comparer;
+ }
+
+ internal void SwapIfGreaterWithItems(int a, int b)
+ {
+ if (a != b)
+ {
+ if (comparer.Compare(keys.GetValue(a), keys.GetValue(b)) > 0)
+ {
+ Object key = keys.GetValue(a);
+ keys.SetValue(keys.GetValue(b), a);
+ keys.SetValue(key, b);
+ if (items != null)
+ {
+ Object item = items.GetValue(a);
+ items.SetValue(items.GetValue(b), a);
+ items.SetValue(item, b);
+ }
+ }
+ }
+ }
+
+ private void Swap(int i, int j)
+ {
+ Object t1 = keys.GetValue(i);
+ keys.SetValue(keys.GetValue(j), i);
+ keys.SetValue(t1, j);
+
+ if (items != null)
+ {
+ Object t2 = items.GetValue(i);
+ items.SetValue(items.GetValue(j), i);
+ items.SetValue(t2, j);
+ }
+ }
+
+ internal void Sort(int left, int length)
+ {
+ IntrospectiveSort(left, length);
+ }
+
+ private void IntrospectiveSort(int left, int length)
+ {
+ if (length < 2)
+ return;
+
+ try
+ {
+ IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
+ }
+ catch (IndexOutOfRangeException)
+ {
+ IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
+ }
+ }
+
+ private void IntroSort(int lo, int hi, int depthLimit)
+ {
+ while (hi > lo)
+ {
+ int partitionSize = hi - lo + 1;
+ if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
+ {
+ if (partitionSize == 1)
+ {
+ return;
+ }
+ if (partitionSize == 2)
+ {
+ SwapIfGreaterWithItems(lo, hi);
+ return;
+ }
+ if (partitionSize == 3)
+ {
+ SwapIfGreaterWithItems(lo, hi - 1);
+ SwapIfGreaterWithItems(lo, hi);
+ SwapIfGreaterWithItems(hi - 1, hi);
+ return;
+ }
+
+ InsertionSort(lo, hi);
+ return;
+ }
+
+ if (depthLimit == 0)
+ {
+ Heapsort(lo, hi);
+ return;
+ }
+ depthLimit--;
+
+ int p = PickPivotAndPartition(lo, hi);
+ IntroSort(p + 1, hi, depthLimit);
+ hi = p - 1;
+ }
+ }
+
+ private int PickPivotAndPartition(int lo, int hi)
+ {
+ // Compute median-of-three. But also partition them, since we've done the comparison.
+ int mid = lo + (hi - lo) / 2;
+
+ SwapIfGreaterWithItems(lo, mid);
+ SwapIfGreaterWithItems(lo, hi);
+ SwapIfGreaterWithItems(mid, hi);
+
+ Object pivot = keys.GetValue(mid);
+ Swap(mid, hi - 1);
+ int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
+
+ while (left < right)
+ {
+ while (comparer.Compare(keys.GetValue(++left), pivot) < 0) ;
+ while (comparer.Compare(pivot, keys.GetValue(--right)) < 0) ;
+
+ if (left >= right)
+ break;
+
+ Swap(left, right);
+ }
+
+ // Put pivot in the right location.
+ Swap(left, (hi - 1));
+ return left;
+ }
+
+ private void Heapsort(int lo, int hi)
+ {
+ int n = hi - lo + 1;
+ for (int i = n / 2; i >= 1; i = i - 1)
+ {
+ DownHeap(i, n, lo);
+ }
+ for (int i = n; i > 1; i = i - 1)
+ {
+ Swap(lo, lo + i - 1);
+
+ DownHeap(1, i - 1, lo);
+ }
+ }
+
+ private void DownHeap(int i, int n, int lo)
+ {
+ Object d = keys.GetValue(lo + i - 1);
+ Object dt = (items != null) ? items.GetValue(lo + i - 1) : null;
+ int child;
+ while (i <= n / 2)
+ {
+ child = 2 * i;
+ if (child < n && comparer.Compare(keys.GetValue(lo + child - 1), keys.GetValue(lo + child)) < 0)
+ {
+ child++;
+ }
+
+ if (!(comparer.Compare(d, keys.GetValue(lo + child - 1)) < 0))
+ break;
+
+ keys.SetValue(keys.GetValue(lo + child - 1), lo + i - 1);
+ if (items != null)
+ items.SetValue(items.GetValue(lo + child - 1), lo + i - 1);
+ i = child;
+ }
+ keys.SetValue(d, lo + i - 1);
+ if (items != null)
+ items.SetValue(dt, lo + i - 1);
+ }
+
+ private void InsertionSort(int lo, int hi)
+ {
+ int i, j;
+ Object t, dt;
+ for (i = lo; i < hi; i++)
+ {
+ j = i;
+ t = keys.GetValue(i + 1);
+ dt = (items != null) ? items.GetValue(i + 1) : null;
+
+ while (j >= lo && comparer.Compare(t, keys.GetValue(j)) < 0)
+ {
+ keys.SetValue(keys.GetValue(j), j + 1);
+ if (items != null)
+ items.SetValue(items.GetValue(j), j + 1);
+ j--;
+ }
+
+ keys.SetValue(t, j + 1);
+ if (items != null)
+ items.SetValue(dt, j + 1);
+ }
+ }
+ }
+ }
+}
\ No newline at end of file
--- /dev/null
+// Licensed to the .NET Foundation under one or more agreements.
+// The .NET Foundation licenses this file to you under the MIT license.
+// See the LICENSE file in the project root for more information.
+
+using System.Runtime;
+using System.Threading;
+using System.Collections;
+using System.Diagnostics;
+using System.Collections.Generic;
+using System.Collections.ObjectModel;
+using System.Runtime.InteropServices;
+using System.Runtime.CompilerServices;
+using System.Diagnostics.Contracts;
+#if MONO
+using System.Diagnostics.Private;
+#endif
+
+namespace System
+{
+ public abstract partial class Array : ICollection, IEnumerable, IList, IStructuralComparable, IStructuralEquatable, ICloneable
+ {
+ public static ReadOnlyCollection<T> AsReadOnly<T>(T[] array)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ // T[] implements IList<T>.
+ return new ReadOnlyCollection<T>(array);
+ }
+
+ public static void Resize<T>(ref T[] array, int newSize)
+ {
+ if (newSize < 0)
+ throw new ArgumentOutOfRangeException(nameof(newSize), SR.ArgumentOutOfRange_NeedNonNegNum);
+
+ T[] larray = array;
+ if (larray == null)
+ {
+ array = new T[newSize];
+ return;
+ }
+
+ if (larray.Length != newSize)
+ {
+ T[] newArray = new T[newSize];
+ Copy(larray, 0, newArray, 0, larray.Length > newSize ? newSize : larray.Length);
+ array = newArray;
+ }
+ }
+
+ // Number of elements in the Array.
+ int ICollection.Count
+ { get { return Length; } }
+
+ // Is this Array read-only?
+ bool IList.IsReadOnly
+ { get { return false; } }
+
+ Object IList.this[int index]
+ {
+ get
+ {
+ return GetValue(index);
+ }
+
+ set
+ {
+ SetValue(value, index);
+ }
+ }
+
+ int IList.Add(Object value)
+ {
+ throw new NotSupportedException(SR.NotSupported_FixedSizeCollection);
+ }
+
+ bool IList.Contains(Object value)
+ {
+ return Array.IndexOf(this, value) >= 0;
+ }
+
+ void IList.Clear()
+ {
+ Array.Clear(this, 0, this.Length);
+ }
+
+ void IList.Insert(int index, Object value)
+ {
+ throw new NotSupportedException(SR.NotSupported_FixedSizeCollection);
+ }
+
+ void IList.Remove(Object value)
+ {
+ throw new NotSupportedException(SR.NotSupported_FixedSizeCollection);
+ }
+
+ void IList.RemoveAt(int index)
+ {
+ throw new NotSupportedException(SR.NotSupported_FixedSizeCollection);
+ }
+
+ // CopyTo copies a collection into an Array, starting at a particular
+ // index into the array.
+ //
+ // This method is to support the ICollection interface, and calls
+ // Array.Copy internally. If you aren't using ICollection explicitly,
+ // call Array.Copy to avoid an extra indirection.
+ //
+ public void CopyTo(Array array, int index)
+ {
+ // Note: Array.Copy throws a RankException and we want a consistent ArgumentException for all the IList CopyTo methods.
+ if (array != null && array.Rank != 1)
+ throw new ArgumentException(SR.Arg_RankMultiDimNotSupported);
+
+ Array.Copy(this, 0, array, index, Length);
+ }
+
+ // Make a new array which is a deep copy of the original array.
+ //
+ public Object Clone()
+ {
+ return MemberwiseClone();
+ }
+
+ Int32 IStructuralComparable.CompareTo(Object other, IComparer comparer)
+ {
+ if (other == null)
+ {
+ return 1;
+ }
+
+ Array o = other as Array;
+
+ if (o == null || this.Length != o.Length)
+ {
+ throw new ArgumentException(SR.ArgumentException_OtherNotArrayOfCorrectLength, nameof(other));
+ }
+
+ int i = 0;
+ int c = 0;
+
+ while (i < o.Length && c == 0)
+ {
+ object left = GetValue(i);
+ object right = o.GetValue(i);
+
+ c = comparer.Compare(left, right);
+ i++;
+ }
+
+ return c;
+ }
+
+ Boolean IStructuralEquatable.Equals(Object other, IEqualityComparer comparer)
+ {
+ if (other == null)
+ {
+ return false;
+ }
+
+ if (Object.ReferenceEquals(this, other))
+ {
+ return true;
+ }
+
+ Array o = other as Array;
+
+ if (o == null || o.Length != this.Length)
+ {
+ return false;
+ }
+
+ int i = 0;
+ while (i < o.Length)
+ {
+ object left = GetValue(i);
+ object right = o.GetValue(i);
+
+ if (!comparer.Equals(left, right))
+ {
+ return false;
+ }
+ i++;
+ }
+
+ return true;
+ }
+
+ // From System.Web.Util.HashCodeCombiner
+ internal static int CombineHashCodes(int h1, int h2)
+ {
+ return (((h1 << 5) + h1) ^ h2);
+ }
+
+ int IStructuralEquatable.GetHashCode(IEqualityComparer comparer)
+ {
+ if (comparer == null)
+ throw new ArgumentNullException(nameof(comparer));
+
+ int ret = 0;
+
+ for (int i = (this.Length >= 8 ? this.Length - 8 : 0); i < this.Length; i++)
+ {
+ ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue(i)));
+ }
+
+ return ret;
+ }
+
+ // Searches an array for a given element using a binary search algorithm.
+ // Elements of the array are compared to the search value using the
+ // IComparable interface, which must be implemented by all elements
+ // of the array and the given search value. This method assumes that the
+ // array is already sorted according to the IComparable interface;
+ // if this is not the case, the result will be incorrect.
+ //
+ // The method returns the index of the given value in the array. If the
+ // array does not contain the given value, the method returns a negative
+ // integer. The bitwise complement operator (~) can be applied to a
+ // negative result to produce the index of the first element (if any) that
+ // is larger than the given search value.
+ //
+ public static int BinarySearch(Array array, Object value)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ return BinarySearch(array, 0, array.Length, value, null);
+ }
+
+ public static TOutput[] ConvertAll<TInput, TOutput>(TInput[] array, Converter<TInput, TOutput> converter)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ if (converter == null)
+ throw new ArgumentNullException(nameof(converter));
+
+ Contract.Ensures(Contract.Result<TOutput[]>() != null);
+ Contract.Ensures(Contract.Result<TOutput[]>().Length == array.Length);
+ Contract.EndContractBlock();
+
+ TOutput[] newArray = new TOutput[array.Length];
+ for (int i = 0; i < array.Length; i++)
+ {
+ newArray[i] = converter(array[i]);
+ }
+ return newArray;
+ }
+
+ public static void Copy(Array sourceArray, Array destinationArray, long length)
+ {
+ if (length > Int32.MaxValue || length < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+
+ Array.Copy(sourceArray, destinationArray, (int)length);
+ }
+
+ public static void Copy(Array sourceArray, long sourceIndex, Array destinationArray, long destinationIndex, long length)
+ {
+ if (sourceIndex > Int32.MaxValue || sourceIndex < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(sourceIndex), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ if (destinationIndex > Int32.MaxValue || destinationIndex < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(destinationIndex), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ if (length > Int32.MaxValue || length < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+
+ Array.Copy(sourceArray, (int)sourceIndex, destinationArray, (int)destinationIndex, (int)length);
+ }
+
+ public void CopyTo(Array array, long index)
+ {
+ if (index > Int32.MaxValue || index < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ Contract.EndContractBlock();
+
+ this.CopyTo(array, (int)index);
+ }
+
+ public static void ForEach<T>(T[] array, Action<T> action)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ if (action == null)
+ throw new ArgumentNullException(nameof(action));
+
+ Contract.EndContractBlock();
+
+ for (int i = 0; i < array.Length; i++)
+ {
+ action(array[i]);
+ }
+ }
+
+ public long LongLength
+ {
+ get
+ {
+ long ret = GetLength(0);
+
+ for (int i = 1; i < Rank; ++i)
+ {
+ ret = ret * GetLength(i);
+ }
+
+ return ret;
+ }
+ }
+
+ public long GetLongLength(int dimension)
+ {
+ // This method does throw an IndexOutOfRangeException for compat if dimension < 0 or >= Rank
+ // by calling GetUpperBound
+ return GetLength(dimension);
+ }
+
+ public Object GetValue(long index)
+ {
+ if (index > Int32.MaxValue || index < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ Contract.EndContractBlock();
+
+ return this.GetValue((int)index);
+ }
+
+ public Object GetValue(long index1, long index2)
+ {
+ if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(index1), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(index2), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ Contract.EndContractBlock();
+
+ return this.GetValue((int)index1, (int)index2);
+ }
+
+ public Object GetValue(long index1, long index2, long index3)
+ {
+ if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(index1), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(index2), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ if (index3 > Int32.MaxValue || index3 < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(index3), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ Contract.EndContractBlock();
+
+ return this.GetValue((int)index1, (int)index2, (int)index3);
+ }
+
+ public Object GetValue(params long[] indices)
+ {
+ if (indices == null)
+ throw new ArgumentNullException(nameof(indices));
+ if (Rank != indices.Length)
+ throw new ArgumentException(SR.Arg_RankIndices);
+ Contract.EndContractBlock();
+
+ int[] intIndices = new int[indices.Length];
+
+ for (int i = 0; i < indices.Length; ++i)
+ {
+ long index = indices[i];
+ if (index > Int32.MaxValue || index < Int32.MinValue)
+ throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_HugeArrayNotSupported);
+ intIndices[i] = (int)index;
+ }
+
+ return this.GetValue(intIndices);
+ }
+
+ public void Initialize()
+ {
+ // Project N port note: On the desktop, this api is a nop unless the array element type is a value type with
+ // an explicit nullary constructor. Such a type cannot be expressed in C# so Project N does not support this.
+ // The ILC toolchain fails the build if it encounters such a type.
+ return;
+ }
+
+ public bool IsFixedSize { get { return true; } }
+
+ // Is this Array synchronized (i.e., thread-safe)? If you want a synchronized
+ // collection, you can use SyncRoot as an object to synchronize your
+ // collection with. You could also call GetSynchronized()
+ // to get a synchronized wrapper around the Array.
+ public bool IsSynchronized { get { return false; } }
+
+ // Returns an object appropriate for synchronizing access to this
+ // Array.
+ public Object SyncRoot { get { return this; } }
+
+ // Searches a section of an array for a given element using a binary search
+ // algorithm. Elements of the array are compared to the search value using
+ // the IComparable interface, which must be implemented by all
+ // elements of the array and the given search value. This method assumes
+ // that the array is already sorted according to the IComparable
+ // interface; if this is not the case, the result will be incorrect.
+ //
+ // The method returns the index of the given value in the array. If the
+ // array does not contain the given value, the method returns a negative
+ // integer. The bitwise complement operator (~) can be applied to a
+ // negative result to produce the index of the first element (if any) that
+ // is larger than the given search value.
+ //
+ public static int BinarySearch(Array array, int index, int length, Object value)
+ {
+ return BinarySearch(array, index, length, value, null);
+ }
+
+ // Searches an array for a given element using a binary search algorithm.
+ // Elements of the array are compared to the search value using the given
+ // IComparer interface. If comparer is null, elements of the
+ // array are compared to the search value using the IComparable
+ // interface, which in that case must be implemented by all elements of the
+ // array and the given search value. This method assumes that the array is
+ // already sorted; if this is not the case, the result will be incorrect.
+ //
+ // The method returns the index of the given value in the array. If the
+ // array does not contain the given value, the method returns a negative
+ // integer. The bitwise complement operator (~) can be applied to a
+ // negative result to produce the index of the first element (if any) that
+ // is larger than the given search value.
+ //
+ public static int BinarySearch(Array array, Object value, IComparer comparer)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ return BinarySearch(array, 0, array.Length, value, comparer);
+ }
+
+ // Searches a section of an array for a given element using a binary search
+ // algorithm. Elements of the array are compared to the search value using
+ // the given IComparer interface. If comparer is null,
+ // elements of the array are compared to the search value using the
+ // IComparable interface, which in that case must be implemented by
+ // all elements of the array and the given search value. This method
+ // assumes that the array is already sorted; if this is not the case, the
+ // result will be incorrect.
+ //
+ // The method returns the index of the given value in the array. If the
+ // array does not contain the given value, the method returns a negative
+ // integer. The bitwise complement operator (~) can be applied to a
+ // negative result to produce the index of the first element (if any) that
+ // is larger than the given search value.
+ //
+ public static int BinarySearch(Array array, int index, int length, Object value, IComparer comparer)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ if (index < 0 || length < 0)
+ throw new ArgumentOutOfRangeException((index < 0 ? nameof(index) : nameof(length)), SR.ArgumentOutOfRange_NeedNonNegNum);
+ if (array.Length - index < length)
+ throw new ArgumentException(SR.Argument_InvalidOffLen);
+ if (array.Rank != 1)
+ throw new RankException(SR.Rank_MultiDimNotSupported);
+
+ if (comparer == null) comparer = LowLevelComparer.Default;
+
+ int lo = index;
+ int hi = index + length - 1;
+ Object[] objArray = array as Object[];
+ if (objArray != null)
+ {
+ while (lo <= hi)
+ {
+ // i might overflow if lo and hi are both large positive numbers.
+ int i = GetMedian(lo, hi);
+
+ int c;
+ try
+ {
+ c = comparer.Compare(objArray[i], value);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
+ }
+ if (c == 0) return i;
+ if (c < 0)
+ {
+ lo = i + 1;
+ }
+ else
+ {
+ hi = i - 1;
+ }
+ }
+ }
+ else
+ {
+ while (lo <= hi)
+ {
+ int i = GetMedian(lo, hi);
+
+ int c;
+ try
+ {
+ c = comparer.Compare(array.GetValue(i), value);
+ }
+ catch (Exception e)
+ {
+ throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
+ }
+ if (c == 0) return i;
+ if (c < 0)
+ {
+ lo = i + 1;
+ }
+ else
+ {
+ hi = i - 1;
+ }
+ }
+ }
+ return ~lo;
+ }
+
+ private static int GetMedian(int low, int hi)
+ {
+ // Note both may be negative, if we are dealing with arrays w/ negative lower bounds.
+ return low + ((hi - low) >> 1);
+ }
+
+ public static int BinarySearch<T>(T[] array, T value)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ return BinarySearch<T>(array, 0, array.Length, value, null);
+ }
+
+ public static int BinarySearch<T>(T[] array, T value, System.Collections.Generic.IComparer<T> comparer)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ return BinarySearch<T>(array, 0, array.Length, value, comparer);
+ }
+
+ public static int BinarySearch<T>(T[] array, int index, int length, T value)
+ {
+ return BinarySearch<T>(array, index, length, value, null);
+ }
+
+ public static int BinarySearch<T>(T[] array, int index, int length, T value, System.Collections.Generic.IComparer<T> comparer)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ if (index < 0 || length < 0)
+ throw new ArgumentOutOfRangeException((index < 0 ? nameof(index) : nameof(length)), SR.ArgumentOutOfRange_NeedNonNegNum);
+ if (array.Length - index < length)
+ throw new ArgumentException(SR.Argument_InvalidOffLen);
+
+ return ArraySortHelper<T>.BinarySearch(array, index, length, value, comparer);
+ }
+
+ // Returns the index of the first occurrence of a given value in an array.
+ // The array is searched forwards, and the elements of the array are
+ // compared to the given value using the Object.Equals method.
+ //
+ public static int IndexOf(Array array, Object value)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ return IndexOf(array, value, 0, array.Length);
+ }
+
+ // Returns the index of the first occurrence of a given value in a range of
+ // an array. The array is searched forwards, starting at index
+ // startIndex and ending at the last element of the array. The
+ // elements of the array are compared to the given value using the
+ // Object.Equals method.
+ //
+ public static int IndexOf(Array array, Object value, int startIndex)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ return IndexOf(array, value, startIndex, array.Length - startIndex);
+ }
+
+ // Returns the index of the first occurrence of a given value in a range of
+ // an array. The array is searched forwards, starting at index
+ // startIndex and upto count elements. The
+ // elements of the array are compared to the given value using the
+ // Object.Equals method.
+ //
+ public static int IndexOf(Array array, Object value, int startIndex, int count)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ if (array.Rank != 1)
+ throw new RankException(SR.Rank_MultiDimNotSupported);
+ if (startIndex < 0 || startIndex > array.Length)
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ if (count < 0 || count > array.Length - startIndex)
+ throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
+
+ Object[] objArray = array as Object[];
+ int endIndex = startIndex + count;
+ if (objArray != null)
+ {
+ if (value == null)
+ {
+ for (int i = startIndex; i < endIndex; i++)
+ {
+ if (objArray[i] == null) return i;
+ }
+ }
+ else
+ {
+ for (int i = startIndex; i < endIndex; i++)
+ {
+ Object obj = objArray[i];
+ if (obj != null && obj.Equals(value)) return i;
+ }
+ }
+ }
+ else
+ {
+ for (int i = startIndex; i < endIndex; i++)
+ {
+ Object obj = array.GetValue(i);
+ if (obj == null)
+ {
+ if (value == null) return i;
+ }
+ else
+ {
+ if (obj.Equals(value)) return i;
+ }
+ }
+ }
+ return -1;
+ }
+
+ /// <summary>
+ /// This version is called from Array<T>.IndexOf and Contains<T>, so it's in every unique array instance due to array interface implementation.
+ /// Do not call into IndexOf<T>(Array array, Object value, int startIndex, int count) for size and space reasons.
+ /// Otherwise there will be two IndexOf methods for each unique array instance, and extra parameter checking which are not needed for the common case.
+ /// </summary>
+ public static int IndexOf<T>(T[] array, T value)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ // See comment above Array.GetComparerForReferenceTypesOnly for details
+ EqualityComparer<T> comparer = GetComparerForReferenceTypesOnly<T>();
+
+ if (comparer != null)
+ {
+ for (int i = 0; i < array.Length; i++)
+ {
+ if (comparer.Equals(array[i], value))
+ return i;
+ }
+ }
+ else
+ {
+ for (int i = 0; i < array.Length; i++)
+ {
+ if (StructOnlyEquals<T>(array[i], value))
+ return i;
+ }
+ }
+
+ return -1;
+ }
+
+ public static int IndexOf<T>(T[] array, T value, int startIndex)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ return IndexOf(array, value, startIndex, array.Length - startIndex);
+ }
+
+ public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (startIndex < 0 || startIndex > array.Length)
+ {
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ }
+
+ if (count < 0 || count > array.Length - startIndex)
+ {
+ throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
+ }
+
+ int endIndex = startIndex + count;
+
+ // See comment above Array.GetComparerForReferenceTypesOnly for details
+ EqualityComparer<T> comparer = GetComparerForReferenceTypesOnly<T>();
+
+ if (comparer != null)
+ {
+ for (int i = startIndex; i < endIndex; i++)
+ {
+ if (comparer.Equals(array[i], value))
+ return i;
+ }
+ }
+ else
+ {
+ for (int i = startIndex; i < endIndex; i++)
+ {
+ if (StructOnlyEquals<T>(array[i], value))
+ return i;
+ }
+ }
+
+ return -1;
+ }
+
+ public static int LastIndexOf(Array array, Object value)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ return LastIndexOf(array, value, array.Length - 1, array.Length);
+ }
+
+ // Returns the index of the last occurrence of a given value in a range of
+ // an array. The array is searched backwards, starting at index
+ // startIndex and ending at index 0. The elements of the array are
+ // compared to the given value using the Object.Equals method.
+ //
+ public static int LastIndexOf(Array array, Object value, int startIndex)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ return LastIndexOf(array, value, startIndex, startIndex + 1);
+ }
+
+ // Returns the index of the last occurrence of a given value in a range of
+ // an array. The array is searched backwards, starting at index
+ // startIndex and counting uptocount elements. The elements of
+ // the array are compared to the given value using the Object.Equals
+ // method.
+ //
+ public static int LastIndexOf(Array array, Object value, int startIndex, int count)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ if (array.Length == 0)
+ {
+ return -1;
+ }
+
+ if (startIndex < 0 || startIndex >= array.Length)
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ if (count < 0)
+ throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
+ if (count > startIndex + 1)
+ throw new ArgumentOutOfRangeException("endIndex", SR.ArgumentOutOfRange_EndIndexStartIndex);
+ if (array.Rank != 1)
+ throw new RankException(SR.Rank_MultiDimNotSupported);
+
+ Object[] objArray = array as Object[];
+ int endIndex = startIndex - count + 1;
+ if (objArray != null)
+ {
+ if (value == null)
+ {
+ for (int i = startIndex; i >= endIndex; i--)
+ {
+ if (objArray[i] == null) return i;
+ }
+ }
+ else
+ {
+ for (int i = startIndex; i >= endIndex; i--)
+ {
+ Object obj = objArray[i];
+ if (obj != null && obj.Equals(value)) return i;
+ }
+ }
+ }
+ else
+ {
+ for (int i = startIndex; i >= endIndex; i--)
+ {
+ Object obj = array.GetValue(i);
+ if (obj == null)
+ {
+ if (value == null) return i;
+ }
+ else
+ {
+ if (obj.Equals(value)) return i;
+ }
+ }
+ }
+ return -1; // Return lb-1 for arrays with negative lower bounds.
+ }
+
+ public static int LastIndexOf<T>(T[] array, T value)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ return LastIndexOf(array, value, array.Length - 1, array.Length);
+ }
+
+ public static int LastIndexOf<T>(T[] array, T value, int startIndex)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ // if array is empty and startIndex is 0, we need to pass 0 as count
+ return LastIndexOf(array, value, startIndex, (array.Length == 0) ? 0 : (startIndex + 1));
+ }
+
+ public static int LastIndexOf<T>(T[] array, T value, int startIndex, int count)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (array.Length == 0)
+ {
+ //
+ // Special case for 0 length List
+ // accept -1 and 0 as valid startIndex for compablility reason.
+ //
+ if (startIndex != -1 && startIndex != 0)
+ {
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ }
+
+ // only 0 is a valid value for count if array is empty
+ if (count != 0)
+ {
+ throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
+ }
+ return -1;
+ }
+
+ // Make sure we're not out of range
+ if (startIndex < 0 || startIndex >= array.Length)
+ {
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ }
+
+ // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
+ if (count < 0 || startIndex - count + 1 < 0)
+ {
+ throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
+ }
+
+ // See comment above Array.GetComparerForReferenceTypesOnly for details
+ EqualityComparer<T> comparer = GetComparerForReferenceTypesOnly<T>();
+
+ int endIndex = startIndex - count + 1;
+ if (comparer != null)
+ {
+ for (int i = startIndex; i >= endIndex; i--)
+ {
+ if (comparer.Equals(array[i], value))
+ return i;
+ }
+ }
+ else
+ {
+ for (int i = startIndex; i >= endIndex; i--)
+ {
+ if (StructOnlyEquals<T>(array[i], value))
+ return i;
+ }
+ }
+
+ return -1;
+ }
+
+ // Reverses all elements of the given array. Following a call to this
+ // method, an element previously located at index i will now be
+ // located at index length - i - 1, where length is the
+ // length of the array.
+ //
+ public static void Reverse(Array array)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ Reverse(array, 0, array.Length);
+ }
+
+ // Reverses the elements in a range of an array. Following a call to this
+ // method, an element in the range given by index and count
+ // which was previously located at index i will now be located at
+ // index index + (index + count - i - 1).
+ // Reliability note: This may fail because it may have to box objects.
+ //
+ public static void Reverse(Array array, int index, int length)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ int lowerBound = array.GetLowerBound(0);
+ if (index < lowerBound || length < 0)
+ throw new ArgumentOutOfRangeException((index < lowerBound ? nameof(index) : nameof(length)), SR.ArgumentOutOfRange_NeedNonNegNum);
+ if (array.Length - (index - lowerBound) < length)
+ throw new ArgumentException(SR.Argument_InvalidOffLen);
+ if (array.Rank != 1)
+ throw new RankException(SR.Rank_MultiDimNotSupported);
+
+ int i = index;
+ int j = index + length - 1;
+ Object[] objArray = array as Object[];
+ if (objArray != null)
+ {
+ while (i < j)
+ {
+ Object temp = objArray[i];
+ objArray[i] = objArray[j];
+ objArray[j] = temp;
+ i++;
+ j--;
+ }
+ }
+ else
+ {
+ while (i < j)
+ {
+ Object temp = array.GetValue(i);
+ array.SetValue(array.GetValue(j), i);
+ array.SetValue(temp, j);
+ i++;
+ j--;
+ }
+ }
+ }
+
+ public static void Reverse<T>(T[] array)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ Reverse(array, 0, array.Length);
+ }
+
+ public static void Reverse<T>(T[] array, int index, int length)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ if (index < 0 || length < 0)
+ throw new ArgumentOutOfRangeException((index < 0 ? nameof(index) : nameof(length)), SR.ArgumentOutOfRange_NeedNonNegNum);
+ if (array.Length - index < length)
+ throw new ArgumentException(SR.Argument_InvalidOffLen);
+
+ int i = index;
+ int j = index + length - 1;
+ while (i < j)
+ {
+ T temp = array[i];
+ array[i] = array[j];
+ array[j] = temp;
+ i++;
+ j--;
+ }
+ }
+
+ // Sorts the elements of an array. The sort compares the elements to each
+ // other using the IComparable interface, which must be implemented
+ // by all elements of the array.
+ //
+ public static void Sort(Array array)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ Sort(array, null, 0, array.Length, null);
+ }
+
+ // Sorts the elements in a section of an array. The sort compares the
+ // elements to each other using the IComparable interface, which
+ // must be implemented by all elements in the given section of the array.
+ //
+ public static void Sort(Array array, int index, int length)
+ {
+ Sort(array, null, index, length, null);
+ }
+
+ // Sorts the elements of an array. The sort compares the elements to each
+ // other using the given IComparer interface. If comparer is
+ // null, the elements are compared to each other using the
+ // IComparable interface, which in that case must be implemented by
+ // all elements of the array.
+ //
+ public static void Sort(Array array, IComparer comparer)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ Sort(array, null, 0, array.Length, comparer);
+ }
+
+ // Sorts the elements in a section of an array. The sort compares the
+ // elements to each other using the given IComparer interface. If
+ // comparer is null, the elements are compared to each other using
+ // the IComparable interface, which in that case must be implemented
+ // by all elements in the given section of the array.
+ //
+ public static void Sort(Array array, int index, int length, IComparer comparer)
+ {
+ Sort(array, null, index, length, comparer);
+ }
+
+ public static void Sort(Array keys, Array items)
+ {
+ if (keys == null)
+ {
+ throw new ArgumentNullException(nameof(keys));
+ }
+
+ Sort(keys, items, keys.GetLowerBound(0), keys.Length, null);
+ }
+
+ public static void Sort(Array keys, Array items, IComparer comparer)
+ {
+ if (keys == null)
+ {
+ throw new ArgumentNullException(nameof(keys));
+ }
+
+ Sort(keys, items, keys.GetLowerBound(0), keys.Length, comparer);
+ }
+
+ public static void Sort(Array keys, Array items, int index, int length)
+ {
+ Sort(keys, items, index, length, null);
+ }
+
+ public static void Sort(Array keys, Array items, int index, int length, IComparer comparer)
+ {
+ if (keys == null)
+ throw new ArgumentNullException(nameof(keys));
+ if (keys.Rank != 1 || (items != null && items.Rank != 1))
+ throw new RankException(SR.Rank_MultiDimNotSupported);
+ int keysLowerBound = keys.GetLowerBound(0);
+ if (items != null && keysLowerBound != items.GetLowerBound(0))
+ throw new ArgumentException(SR.Arg_LowerBoundsMustMatch);
+ if (index < keysLowerBound || length < 0)
+ throw new ArgumentOutOfRangeException((length < 0 ? nameof(length) : nameof(index)), SR.ArgumentOutOfRange_NeedNonNegNum);
+ if (keys.Length - (index - keysLowerBound) < length || (items != null && (index - keysLowerBound) > items.Length - length))
+ throw new ArgumentException(SR.Argument_InvalidOffLen);
+
+ if (length > 1)
+ {
+#if CORERT
+ IComparer<Object> comparerT = new ComparerAsComparerT(comparer);
+ Object[] objKeys = keys as Object[];
+ Object[] objItems = items as Object[];
+
+ // Unfortunately, on Project N, we don't have the ability to specialize ArraySortHelper<> on demand
+ // for value types. Rather than incur a boxing cost on every compare and every swap (and maintain a separate introsort algorithm
+ // just for this), box them all, sort them as an Object[] array and unbox them back.
+
+ // Check if either of the arrays need to be copied.
+ if (objKeys == null)
+ {
+ objKeys = new Object[index + length];
+ Array.CopyImplValueTypeArrayToReferenceArray(keys, index, objKeys, index, length, reliable: false);
+ }
+ if (objItems == null && items != null)
+ {
+ objItems = new Object[index + length];
+ Array.CopyImplValueTypeArrayToReferenceArray(items, index, objItems, index, length, reliable: false);
+ }
+
+ Sort<Object, Object>(objKeys, objItems, index, length, comparerT);
+
+ // If either array was copied, copy it back into the original
+ if (objKeys != keys)
+ {
+ Array.CopyImplReferenceArrayToValueTypeArray(objKeys, index, keys, index, length, reliable: false);
+ }
+ if (objItems != items)
+ {
+ Array.CopyImplReferenceArrayToValueTypeArray(objItems, index, items, index, length, reliable: false);
+ }
+#else
+ Object[] objKeys = keys as Object[];
+ Object[] objItems = null;
+ if (objKeys != null)
+ objItems = items as Object[];
+ if (objKeys != null && (items == null || objItems != null))
+ {
+ SorterObjectArray sorter = new SorterObjectArray(objKeys, objItems, comparer);
+ sorter.Sort(index, length);
+ }
+ else
+ {
+ SorterGenericArray sorter = new SorterGenericArray(keys, items, comparer);
+ sorter.Sort(index, length);
+ }
+#endif
+ }
+ }
+
+ // Wraps an IComparer inside an IComparer<Object>.
+ private sealed class ComparerAsComparerT : IComparer<Object>
+ {
+ public ComparerAsComparerT(IComparer comparer)
+ {
+ _comparer = (comparer == null) ? LowLevelComparer.Default : comparer;
+ }
+
+ public int Compare(Object x, Object y)
+ {
+ return _comparer.Compare(x, y);
+ }
+
+ private IComparer _comparer;
+ }
+
+ public static void Sort<T>(T[] array)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+
+ Sort<T>(array, 0, array.Length, null);
+ }
+
+ public static void Sort<T>(T[] array, int index, int length)
+ {
+ Sort<T>(array, index, length, null);
+ }
+
+ public static void Sort<T>(T[] array, System.Collections.Generic.IComparer<T> comparer)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ Sort<T>(array, 0, array.Length, comparer);
+ }
+
+ public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer)
+ {
+ if (array == null)
+ throw new ArgumentNullException(nameof(array));
+ if (index < 0 || length < 0)
+ throw new ArgumentOutOfRangeException((length < 0 ? nameof(length) : nameof(index)), SR.ArgumentOutOfRange_NeedNonNegNum);
+ if (array.Length - index < length)
+ throw new ArgumentException(SR.Argument_InvalidOffLen);
+
+ if (length > 1)
+ ArraySortHelper<T>.Sort(array, index, length, comparer);
+ }
+
+ public static void Sort<T>(T[] array, Comparison<T> comparison)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (comparison == null)
+ {
+ throw new ArgumentNullException(nameof(comparison));
+ }
+
+ ArraySortHelper<T>.Sort(array, 0, array.Length, comparison);
+ }
+
+ public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items)
+ {
+ if (keys == null)
+ throw new ArgumentNullException(nameof(keys));
+ Contract.EndContractBlock();
+ Sort<TKey, TValue>(keys, items, 0, keys.Length, null);
+ }
+
+ public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length)
+ {
+ Sort<TKey, TValue>(keys, items, index, length, null);
+ }
+
+ public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, IComparer<TKey> comparer)
+ {
+ if (keys == null)
+ throw new ArgumentNullException(nameof(keys));
+ Contract.EndContractBlock();
+ Sort<TKey, TValue>(keys, items, 0, keys.Length, comparer);
+ }
+
+ public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, IComparer<TKey> comparer)
+ {
+ if (keys == null)
+ throw new ArgumentNullException(nameof(keys));
+ if (index < 0 || length < 0)
+ throw new ArgumentOutOfRangeException((length < 0 ? nameof(length) : nameof(index)), SR.ArgumentOutOfRange_NeedNonNegNum);
+ if (keys.Length - index < length || (items != null && index > items.Length - length))
+ throw new ArgumentException(SR.Argument_InvalidOffLen);
+ Contract.EndContractBlock();
+
+ if (length > 1)
+ {
+ if (items == null)
+ {
+ Sort<TKey>(keys, index, length, comparer);
+ return;
+ }
+
+ ArraySortHelper<TKey, TValue>.Default.Sort(keys, items, index, length, comparer);
+ }
+ }
+
+ public static T[] Empty<T>()
+ {
+ return EmptyArray<T>.Value;
+ }
+
+ public static bool Exists<T>(T[] array, Predicate<T> match)
+ {
+ return Array.FindIndex(array, match) != -1;
+ }
+
+ public static void Fill<T>(T[] array, T value)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ for (int i = 0; i < array.Length; i++)
+ {
+ array[i] = value;
+ }
+ }
+
+ public static void Fill<T>(T[] array, T value, int startIndex, int count)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (startIndex < 0 || startIndex > array.Length)
+ {
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ }
+
+ if (count < 0 || startIndex > array.Length - count)
+ {
+ throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
+ }
+
+ for (int i = startIndex; i < startIndex + count; i++)
+ {
+ array[i] = value;
+ }
+ }
+
+ public static T Find<T>(T[] array, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (match == null)
+ {
+ throw new ArgumentNullException(nameof(match));
+ }
+
+ for (int i = 0; i < array.Length; i++)
+ {
+ if (match(array[i]))
+ {
+ return array[i];
+ }
+ }
+ return default(T);
+ }
+
+ public static int FindIndex<T>(T[] array, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ return FindIndex(array, 0, array.Length, match);
+ }
+
+ public static int FindIndex<T>(T[] array, int startIndex, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ return FindIndex(array, startIndex, array.Length - startIndex, match);
+ }
+
+ public static int FindIndex<T>(T[] array, int startIndex, int count, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (startIndex < 0 || startIndex > array.Length)
+ {
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ }
+
+ if (count < 0 || startIndex > array.Length - count)
+ {
+ throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
+ }
+
+ if (match == null)
+ {
+ throw new ArgumentNullException(nameof(match));
+ }
+
+ int endIndex = startIndex + count;
+ for (int i = startIndex; i < endIndex; i++)
+ {
+ if (match(array[i])) return i;
+ }
+ return -1;
+ }
+
+ public static T FindLast<T>(T[] array, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (match == null)
+ {
+ throw new ArgumentNullException(nameof(match));
+ }
+
+ for (int i = array.Length - 1; i >= 0; i--)
+ {
+ if (match(array[i]))
+ {
+ return array[i];
+ }
+ }
+ return default(T);
+ }
+
+ public static int FindLastIndex<T>(T[] array, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ return FindLastIndex(array, array.Length - 1, array.Length, match);
+ }
+
+ public static int FindLastIndex<T>(T[] array, int startIndex, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ return FindLastIndex(array, startIndex, startIndex + 1, match);
+ }
+
+ public static int FindLastIndex<T>(T[] array, int startIndex, int count, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (match == null)
+ {
+ throw new ArgumentNullException(nameof(match));
+ }
+
+ if (array.Length == 0)
+ {
+ // Special case for 0 length List
+ if (startIndex != -1)
+ {
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ }
+ }
+ else
+ {
+ // Make sure we're not out of range
+ if (startIndex < 0 || startIndex >= array.Length)
+ {
+ throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
+ }
+ }
+
+ // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
+ if (count < 0 || startIndex - count + 1 < 0)
+ {
+ throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
+ }
+
+ int endIndex = startIndex - count;
+ for (int i = startIndex; i > endIndex; i--)
+ {
+ if (match(array[i]))
+ {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ public static bool TrueForAll<T>(T[] array, Predicate<T> match)
+ {
+ if (array == null)
+ {
+ throw new ArgumentNullException(nameof(array));
+ }
+
+ if (match == null)
+ {
+ throw new ArgumentNullException(nameof(match));
+ }
+
+ for (int i = 0; i < array.Length; i++)
+ {
+ if (!match(array[i]))
+ {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public IEnumerator GetEnumerator()
+ {
+ return new ArrayEnumerator(this);
+ }
+
+ // These functions look odd, as they are part of a complex series of compiler intrinsics
+ // designed to produce very high quality code for equality comparison cases without utilizing
+ // reflection like other platforms. The major complication is that the specification of
+ // IndexOf is that it is supposed to use IEquatable<T> if possible, but that requirement
+ // cannot be expressed in IL directly due to the lack of constraints.
+ // Instead, specialization at call time is used within the compiler.
+ //
+ // General Approach
+ // - Perform fancy redirection for Array.GetComparerForReferenceTypesOnly<T>(). If T is a reference
+ // type or UniversalCanon, have this redirect to EqualityComparer<T>.get_Default, Otherwise, use
+ // the function as is. (will return null in that case)
+ // - Change the contents of the IndexOf functions to have a pair of loops. One for if
+ // GetComparerForReferenceTypesOnly returns null, and one for when it does not.
+ // - If it does not return null, call the EqualityComparer<T> code.
+ // - If it does return null, use a special function StructOnlyEquals<T>().
+ // - Calls to that function result in calls to a pair of helper function in
+ // EqualityComparerHelpers (StructOnlyEqualsIEquatable, or StructOnlyEqualsNullable)
+ // depending on whether or not they are the right function to call.
+ // - The end result is that in optimized builds, we have the same single function compiled size
+ // characteristics that the old EqualsOnlyComparer<T>.Equals function had, but we maintain
+ // correctness as well.
+ private static EqualityComparer<T> GetComparerForReferenceTypesOnly<T>()
+ {
+#if !CORERT
+ return System.Runtime.CompilerServices.RuntimeHelpers.IsReferenceOrContainsReferences<T> () ? EqualityComparer<T>.Default : null;
+#else
+ return EqualityComparer<T>.Default;
+#endif
+ }
+
+ private static bool StructOnlyEquals<T>(T left, T right)
+ {
+ return left.Equals(right);
+ }
+
+ private sealed class ArrayEnumerator : IEnumerator, ICloneable
+ {
+ private Array _array;
+ private int _index;
+ private int _endIndex; // cache array length, since it's a little slow.
+
+ internal ArrayEnumerator(Array array)
+ {
+ _array = array;
+ _index = -1;
+ _endIndex = array.Length;
+ }
+
+ public bool MoveNext()
+ {
+ if (_index < _endIndex)
+ {
+ _index++;
+ return (_index < _endIndex);
+ }
+ return false;
+ }
+
+ public Object Current
+ {
+ get
+ {
+ if (_index < 0) throw new InvalidOperationException(SR.InvalidOperation_EnumNotStarted);
+ if (_index >= _endIndex) throw new InvalidOperationException(SR.InvalidOperation_EnumEnded);
+ return _array.GetValueWithFlattenedIndex_NoErrorCheck(_index);
+ }
+ }
+
+ public void Reset()
+ {
+ _index = -1;
+ }
+
+ public object Clone()
+ {
+ return MemberwiseClone();
+ }
+ }
+ }
+}
\ No newline at end of file
../referencesource/mscorlib/microsoft/win32/safehandles/safewaithandle.cs
../referencesource/mscorlib/microsoft/win32/safehandles/win32safehandles.cs
+coreclr/SorterArray.cs
+
corert/AddrofIntrinsics.cs
+corert/Array.Portable.cs
corert/Debug.cs
corert/Interop.cs
corert/Interop.MemAllocFree.cs
../../../external/corert/src/System.Private.CoreLib/src/System/Collections/LowLevelComparer.cs
../../../external/corert/src/System.Private.CoreLib/src/System/Collections/ObjectEqualityComparer.cs
+../../../external/corert/src/System.Private.CoreLib/src/System/Collections/Generic/ArraySortHelper.cs
+
../../../external/corert/src/System.Private.CoreLib/src/System/IO/Win32Marshal.cs
../../../external/corert/src/System.Private.CoreLib/src/System/Runtime/CompilerServices/ITuple.cs
projects / mono.git / commitdiff