1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
6 using System.Threading;
7 using System.Collections;
8 using System.Diagnostics;
9 using System.Collections.Generic;
10 using System.Collections.ObjectModel;
11 using System.Runtime.InteropServices;
12 using System.Runtime.CompilerServices;
13 using System.Diagnostics.Contracts;
15 using System.Diagnostics.Private;
20 public abstract partial class Array : ICollection, IEnumerable, IList, IStructuralComparable, IStructuralEquatable, ICloneable
22 public static Array CreateInstance(Type elementType, params long[] lengths)
25 throw new ArgumentNullException(nameof(lengths));
26 if (lengths.Length == 0)
27 throw new ArgumentException(SR.Arg_NeedAtLeast1Rank);
29 int[] intLengths = new int[lengths.Length];
31 for (int i = 0; i < lengths.Length; ++i)
33 long len = lengths[i];
34 if (len > int.MaxValue || len < int.MinValue)
35 throw new ArgumentOutOfRangeException("len", SR.ArgumentOutOfRange_HugeArrayNotSupported);
36 intLengths[i] = (int)len;
39 return Array.CreateInstance(elementType, intLengths);
42 public static ReadOnlyCollection<T> AsReadOnly<T>(T[] array)
46 throw new ArgumentNullException(nameof(array));
49 // T[] implements IList<T>.
50 return new ReadOnlyCollection<T>(array);
53 public static void Resize<T>(ref T[] array, int newSize)
56 throw new ArgumentOutOfRangeException(nameof(newSize), SR.ArgumentOutOfRange_NeedNonNegNum);
61 array = new T[newSize];
65 if (larray.Length != newSize)
67 T[] newArray = new T[newSize];
68 Copy(larray, 0, newArray, 0, larray.Length > newSize ? newSize : larray.Length);
73 // Number of elements in the Array.
75 { get { return Length; } }
77 // Is this Array read-only?
79 { get { return false; } }
81 Object IList.this[int index]
85 return GetValue(index);
90 SetValue(value, index);
94 int IList.Add(Object value)
96 throw new NotSupportedException(SR.NotSupported_FixedSizeCollection);
99 bool IList.Contains(Object value)
101 return Array.IndexOf(this, value) >= 0;
106 Array.Clear(this, GetLowerBound(0), this.Length);
109 int IList.IndexOf(Object value)
111 return Array.IndexOf(this, value);
114 void IList.Insert(int index, Object value)
116 throw new NotSupportedException(SR.NotSupported_FixedSizeCollection);
119 void IList.Remove(Object value)
121 throw new NotSupportedException(SR.NotSupported_FixedSizeCollection);
124 void IList.RemoveAt(int index)
126 throw new NotSupportedException(SR.NotSupported_FixedSizeCollection);
129 // CopyTo copies a collection into an Array, starting at a particular
130 // index into the array.
132 // This method is to support the ICollection interface, and calls
133 // Array.Copy internally. If you aren't using ICollection explicitly,
134 // call Array.Copy to avoid an extra indirection.
136 public void CopyTo(Array array, int index)
138 // Note: Array.Copy throws a RankException and we want a consistent ArgumentException for all the IList CopyTo methods.
139 if (array != null && array.Rank != 1)
140 throw new ArgumentException(SR.Arg_RankMultiDimNotSupported);
142 Array.Copy(this, GetLowerBound(0), array, index, Length);
145 // Make a new array which is a deep copy of the original array.
147 public Object Clone()
149 return MemberwiseClone();
152 Int32 IStructuralComparable.CompareTo(Object other, IComparer comparer)
159 Array o = other as Array;
161 if (o == null || this.Length != o.Length)
163 throw new ArgumentException(SR.ArgumentException_OtherNotArrayOfCorrectLength, nameof(other));
169 while (i < o.Length && c == 0)
171 object left = GetValue(i);
172 object right = o.GetValue(i);
174 c = comparer.Compare(left, right);
181 Boolean IStructuralEquatable.Equals(Object other, IEqualityComparer comparer)
188 if (Object.ReferenceEquals(this, other))
193 Array o = other as Array;
195 if (o == null || o.Length != this.Length)
203 object left = GetValue(i);
204 object right = o.GetValue(i);
206 if (!comparer.Equals(left, right))
216 // From System.Web.Util.HashCodeCombiner
217 internal static int CombineHashCodes(int h1, int h2)
219 return (((h1 << 5) + h1) ^ h2);
222 int IStructuralEquatable.GetHashCode(IEqualityComparer comparer)
224 if (comparer == null)
225 throw new ArgumentNullException(nameof(comparer));
229 for (int i = (this.Length >= 8 ? this.Length - 8 : 0); i < this.Length; i++)
231 ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue(i)));
237 // Searches an array for a given element using a binary search algorithm.
238 // Elements of the array are compared to the search value using the
239 // IComparable interface, which must be implemented by all elements
240 // of the array and the given search value. This method assumes that the
241 // array is already sorted according to the IComparable interface;
242 // if this is not the case, the result will be incorrect.
244 // The method returns the index of the given value in the array. If the
245 // array does not contain the given value, the method returns a negative
246 // integer. The bitwise complement operator (~) can be applied to a
247 // negative result to produce the index of the first element (if any) that
248 // is larger than the given search value.
250 public static int BinarySearch(Array array, Object value)
253 throw new ArgumentNullException(nameof(array));
254 return BinarySearch(array, array.GetLowerBound(0), array.Length, value, null);
257 public static TOutput[] ConvertAll<TInput, TOutput>(TInput[] array, Converter<TInput, TOutput> converter)
260 throw new ArgumentNullException(nameof(array));
262 if (converter == null)
263 throw new ArgumentNullException(nameof(converter));
265 Contract.Ensures(Contract.Result<TOutput[]>() != null);
266 Contract.Ensures(Contract.Result<TOutput[]>().Length == array.Length);
267 Contract.EndContractBlock();
269 TOutput[] newArray = new TOutput[array.Length];
270 for (int i = 0; i < array.Length; i++)
272 newArray[i] = converter(array[i]);
277 public static void Copy(Array sourceArray, Array destinationArray, long length)
279 if (length > Int32.MaxValue || length < Int32.MinValue)
280 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_HugeArrayNotSupported);
282 Array.Copy(sourceArray, destinationArray, (int)length);
285 public static void Copy(Array sourceArray, long sourceIndex, Array destinationArray, long destinationIndex, long length)
287 if (sourceIndex > Int32.MaxValue || sourceIndex < Int32.MinValue)
288 throw new ArgumentOutOfRangeException(nameof(sourceIndex), SR.ArgumentOutOfRange_HugeArrayNotSupported);
289 if (destinationIndex > Int32.MaxValue || destinationIndex < Int32.MinValue)
290 throw new ArgumentOutOfRangeException(nameof(destinationIndex), SR.ArgumentOutOfRange_HugeArrayNotSupported);
291 if (length > Int32.MaxValue || length < Int32.MinValue)
292 throw new ArgumentOutOfRangeException(nameof(length), SR.ArgumentOutOfRange_HugeArrayNotSupported);
294 Array.Copy(sourceArray, (int)sourceIndex, destinationArray, (int)destinationIndex, (int)length);
297 public void CopyTo(Array array, long index)
299 if (index > Int32.MaxValue || index < Int32.MinValue)
300 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_HugeArrayNotSupported);
301 Contract.EndContractBlock();
303 this.CopyTo(array, (int)index);
306 public static void ForEach<T>(T[] array, Action<T> action)
309 throw new ArgumentNullException(nameof(array));
312 throw new ArgumentNullException(nameof(action));
314 Contract.EndContractBlock();
316 for (int i = 0; i < array.Length; i++)
322 public long LongLength
326 long ret = GetLength(0);
328 for (int i = 1; i < Rank; ++i)
330 ret = ret * GetLength(i);
337 public long GetLongLength(int dimension)
339 // This method does throw an IndexOutOfRangeException for compat if dimension < 0 or >= Rank
340 // by calling GetUpperBound
341 return GetLength(dimension);
344 public Object GetValue(long index)
346 if (index > Int32.MaxValue || index < Int32.MinValue)
347 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_HugeArrayNotSupported);
348 Contract.EndContractBlock();
350 return this.GetValue((int)index);
353 public Object GetValue(long index1, long index2)
355 if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
356 throw new ArgumentOutOfRangeException(nameof(index1), SR.ArgumentOutOfRange_HugeArrayNotSupported);
357 if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
358 throw new ArgumentOutOfRangeException(nameof(index2), SR.ArgumentOutOfRange_HugeArrayNotSupported);
359 Contract.EndContractBlock();
361 return this.GetValue((int)index1, (int)index2);
364 public Object GetValue(long index1, long index2, long index3)
366 if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
367 throw new ArgumentOutOfRangeException(nameof(index1), SR.ArgumentOutOfRange_HugeArrayNotSupported);
368 if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
369 throw new ArgumentOutOfRangeException(nameof(index2), SR.ArgumentOutOfRange_HugeArrayNotSupported);
370 if (index3 > Int32.MaxValue || index3 < Int32.MinValue)
371 throw new ArgumentOutOfRangeException(nameof(index3), SR.ArgumentOutOfRange_HugeArrayNotSupported);
372 Contract.EndContractBlock();
374 return this.GetValue((int)index1, (int)index2, (int)index3);
377 public Object GetValue(params long[] indices)
380 throw new ArgumentNullException(nameof(indices));
381 if (Rank != indices.Length)
382 throw new ArgumentException(SR.Arg_RankIndices);
383 Contract.EndContractBlock();
385 int[] intIndices = new int[indices.Length];
387 for (int i = 0; i < indices.Length; ++i)
389 long index = indices[i];
390 if (index > Int32.MaxValue || index < Int32.MinValue)
391 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_HugeArrayNotSupported);
392 intIndices[i] = (int)index;
395 return this.GetValue(intIndices);
398 public void Initialize()
400 // Project N port note: On the desktop, this api is a nop unless the array element type is a value type with
401 // an explicit nullary constructor. Such a type cannot be expressed in C# so Project N does not support this.
402 // The ILC toolchain fails the build if it encounters such a type.
406 public bool IsFixedSize { get { return true; } }
408 public bool IsReadOnly { get { return false; } }
410 // Is this Array synchronized (i.e., thread-safe)? If you want a synchronized
411 // collection, you can use SyncRoot as an object to synchronize your
412 // collection with. You could also call GetSynchronized()
413 // to get a synchronized wrapper around the Array.
414 public bool IsSynchronized { get { return false; } }
416 // Returns an object appropriate for synchronizing access to this
418 public Object SyncRoot { get { return this; } }
420 // Searches a section of an array for a given element using a binary search
421 // algorithm. Elements of the array are compared to the search value using
422 // the IComparable interface, which must be implemented by all
423 // elements of the array and the given search value. This method assumes
424 // that the array is already sorted according to the IComparable
425 // interface; if this is not the case, the result will be incorrect.
427 // The method returns the index of the given value in the array. If the
428 // array does not contain the given value, the method returns a negative
429 // integer. The bitwise complement operator (~) can be applied to a
430 // negative result to produce the index of the first element (if any) that
431 // is larger than the given search value.
433 public static int BinarySearch(Array array, int index, int length, Object value)
435 return BinarySearch(array, index, length, value, null);
438 // Searches an array for a given element using a binary search algorithm.
439 // Elements of the array are compared to the search value using the given
440 // IComparer interface. If comparer is null, elements of the
441 // array are compared to the search value using the IComparable
442 // interface, which in that case must be implemented by all elements of the
443 // array and the given search value. This method assumes that the array is
444 // already sorted; if this is not the case, the result will be incorrect.
446 // The method returns the index of the given value in the array. If the
447 // array does not contain the given value, the method returns a negative
448 // integer. The bitwise complement operator (~) can be applied to a
449 // negative result to produce the index of the first element (if any) that
450 // is larger than the given search value.
452 public static int BinarySearch(Array array, Object value, IComparer comparer)
455 throw new ArgumentNullException(nameof(array));
456 return BinarySearch(array, array.GetLowerBound(0), array.Length, value, comparer);
459 // Searches a section of an array for a given element using a binary search
460 // algorithm. Elements of the array are compared to the search value using
461 // the given IComparer interface. If comparer is null,
462 // elements of the array are compared to the search value using the
463 // IComparable interface, which in that case must be implemented by
464 // all elements of the array and the given search value. This method
465 // assumes that the array is already sorted; if this is not the case, the
466 // result will be incorrect.
468 // The method returns the index of the given value in the array. If the
469 // array does not contain the given value, the method returns a negative
470 // integer. The bitwise complement operator (~) can be applied to a
471 // negative result to produce the index of the first element (if any) that
472 // is larger than the given search value.
474 public static int BinarySearch(Array array, int index, int length, Object value, IComparer comparer)
477 throw new ArgumentNullException(nameof(array));
479 if (index < 0 || length < 0)
480 throw new ArgumentOutOfRangeException((index < 0 ? nameof(index) : nameof(length)), SR.ArgumentOutOfRange_NeedNonNegNum);
481 if (array.Length - index < length)
482 throw new ArgumentException(SR.Argument_InvalidOffLen);
484 throw new RankException(SR.Rank_MultiDimNotSupported);
486 if (comparer == null) comparer = LowLevelComparer.Default;
489 int hi = index + length - 1;
490 Object[] objArray = array as Object[];
491 if (objArray != null)
495 // i might overflow if lo and hi are both large positive numbers.
496 int i = GetMedian(lo, hi);
501 c = comparer.Compare(objArray[i], value);
505 throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
507 if (c == 0) return i;
522 int i = GetMedian(lo, hi);
527 c = comparer.Compare(array.GetValue(i), value);
531 throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
533 if (c == 0) return i;
547 private static int GetMedian(int low, int hi)
549 // Note both may be negative, if we are dealing with arrays w/ negative lower bounds.
550 return low + ((hi - low) >> 1);
553 public static int BinarySearch<T>(T[] array, T value)
556 throw new ArgumentNullException(nameof(array));
557 return BinarySearch<T>(array, 0, array.Length, value, null);
560 public static int BinarySearch<T>(T[] array, T value, System.Collections.Generic.IComparer<T> comparer)
563 throw new ArgumentNullException(nameof(array));
564 return BinarySearch<T>(array, 0, array.Length, value, comparer);
567 public static int BinarySearch<T>(T[] array, int index, int length, T value)
569 return BinarySearch<T>(array, index, length, value, null);
572 public static int BinarySearch<T>(T[] array, int index, int length, T value, System.Collections.Generic.IComparer<T> comparer)
575 throw new ArgumentNullException(nameof(array));
576 if (index < 0 || length < 0)
577 throw new ArgumentOutOfRangeException((index < 0 ? nameof(index) : nameof(length)), SR.ArgumentOutOfRange_NeedNonNegNum);
578 if (array.Length - index < length)
579 throw new ArgumentException(SR.Argument_InvalidOffLen);
581 return ArraySortHelper<T>.BinarySearch(array, index, length, value, comparer);
584 // Returns the index of the first occurrence of a given value in an array.
585 // The array is searched forwards, and the elements of the array are
586 // compared to the given value using the Object.Equals method.
588 public static int IndexOf(Array array, Object value)
592 throw new ArgumentNullException(nameof(array));
595 return IndexOf(array, value, array.GetLowerBound(0), array.Length);
598 // Returns the index of the first occurrence of a given value in a range of
599 // an array. The array is searched forwards, starting at index
600 // startIndex and ending at the last element of the array. The
601 // elements of the array are compared to the given value using the
602 // Object.Equals method.
604 public static int IndexOf(Array array, Object value, int startIndex)
608 throw new ArgumentNullException(nameof(array));
611 int lb = array.GetLowerBound(0);
612 return IndexOf(array, value, startIndex, array.Length - startIndex + lb);
615 // Returns the index of the first occurrence of a given value in a range of
616 // an array. The array is searched forwards, starting at index
617 // startIndex and upto count elements. The
618 // elements of the array are compared to the given value using the
619 // Object.Equals method.
621 public static int IndexOf(Array array, Object value, int startIndex, int count)
624 throw new ArgumentNullException(nameof(array));
626 throw new RankException(SR.Rank_MultiDimNotSupported);
627 int lb = array.GetLowerBound(0);
628 if (startIndex < lb || startIndex > array.Length + lb)
629 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
630 if (count < 0 || count > array.Length - startIndex + lb)
631 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
633 Object[] objArray = array as Object[];
634 int endIndex = startIndex + count;
635 if (objArray != null)
639 for (int i = startIndex; i < endIndex; i++)
641 if (objArray[i] == null) return i;
646 for (int i = startIndex; i < endIndex; i++)
648 Object obj = objArray[i];
649 if (obj != null && obj.Equals(value)) return i;
655 for (int i = startIndex; i < endIndex; i++)
657 Object obj = array.GetValue(i);
660 if (value == null) return i;
664 if (obj.Equals(value)) return i;
672 /// This version is called from Array<T>.IndexOf and Contains<T>, so it's in every unique array instance due to array interface implementation.
673 /// Do not call into IndexOf<T>(Array array, Object value, int startIndex, int count) for size and space reasons.
674 /// Otherwise there will be two IndexOf methods for each unique array instance, and extra parameter checking which are not needed for the common case.
676 public static int IndexOf<T>(T[] array, T value)
680 throw new ArgumentNullException(nameof(array));
683 // See comment above Array.GetComparerForReferenceTypesOnly for details
684 EqualityComparer<T> comparer = GetComparerForReferenceTypesOnly<T>();
686 if (comparer != null)
688 for (int i = 0; i < array.Length; i++)
690 if (comparer.Equals(array[i], value))
696 for (int i = 0; i < array.Length; i++)
698 if (StructOnlyEquals<T>(array[i], value))
706 public static int IndexOf<T>(T[] array, T value, int startIndex)
710 throw new ArgumentNullException(nameof(array));
713 return IndexOf(array, value, startIndex, array.Length - startIndex);
716 public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
720 throw new ArgumentNullException(nameof(array));
723 if (startIndex < 0 || startIndex > array.Length)
725 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
728 if (count < 0 || count > array.Length - startIndex)
730 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
733 int endIndex = startIndex + count;
735 // See comment above Array.GetComparerForReferenceTypesOnly for details
736 EqualityComparer<T> comparer = GetComparerForReferenceTypesOnly<T>();
738 if (comparer != null)
740 for (int i = startIndex; i < endIndex; i++)
742 if (comparer.Equals(array[i], value))
748 for (int i = startIndex; i < endIndex; i++)
750 if (StructOnlyEquals<T>(array[i], value))
758 public static int LastIndexOf(Array array, Object value)
761 throw new ArgumentNullException(nameof(array));
763 return LastIndexOf(array, value, array.Length - 1, array.Length);
766 // Returns the index of the last occurrence of a given value in a range of
767 // an array. The array is searched backwards, starting at index
768 // startIndex and ending at index 0. The elements of the array are
769 // compared to the given value using the Object.Equals method.
771 public static int LastIndexOf(Array array, Object value, int startIndex)
774 throw new ArgumentNullException(nameof(array));
776 return LastIndexOf(array, value, startIndex, startIndex + 1);
779 // Returns the index of the last occurrence of a given value in a range of
780 // an array. The array is searched backwards, starting at index
781 // startIndex and counting uptocount elements. The elements of
782 // the array are compared to the given value using the Object.Equals
785 public static int LastIndexOf(Array array, Object value, int startIndex, int count)
788 throw new ArgumentNullException(nameof(array));
790 if (array.Length == 0)
795 if (startIndex < 0 || startIndex >= array.Length)
796 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
798 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
799 if (count > startIndex + 1)
800 throw new ArgumentOutOfRangeException("endIndex", SR.ArgumentOutOfRange_EndIndexStartIndex);
802 throw new RankException(SR.Rank_MultiDimNotSupported);
804 Object[] objArray = array as Object[];
805 int endIndex = startIndex - count + 1;
806 if (objArray != null)
810 for (int i = startIndex; i >= endIndex; i--)
812 if (objArray[i] == null) return i;
817 for (int i = startIndex; i >= endIndex; i--)
819 Object obj = objArray[i];
820 if (obj != null && obj.Equals(value)) return i;
826 for (int i = startIndex; i >= endIndex; i--)
828 Object obj = array.GetValue(i);
831 if (value == null) return i;
835 if (obj.Equals(value)) return i;
839 return -1; // Return lb-1 for arrays with negative lower bounds.
842 public static int LastIndexOf<T>(T[] array, T value)
846 throw new ArgumentNullException(nameof(array));
849 return LastIndexOf(array, value, array.Length - 1, array.Length);
852 public static int LastIndexOf<T>(T[] array, T value, int startIndex)
856 throw new ArgumentNullException(nameof(array));
859 // if array is empty and startIndex is 0, we need to pass 0 as count
860 return LastIndexOf(array, value, startIndex, (array.Length == 0) ? 0 : (startIndex + 1));
863 public static int LastIndexOf<T>(T[] array, T value, int startIndex, int count)
867 throw new ArgumentNullException(nameof(array));
870 if (array.Length == 0)
873 // Special case for 0 length List
874 // accept -1 and 0 as valid startIndex for compablility reason.
876 if (startIndex != -1 && startIndex != 0)
878 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
881 // only 0 is a valid value for count if array is empty
884 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
889 // Make sure we're not out of range
890 if (startIndex < 0 || startIndex >= array.Length)
892 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
895 // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
896 if (count < 0 || startIndex - count + 1 < 0)
898 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
901 // See comment above Array.GetComparerForReferenceTypesOnly for details
902 EqualityComparer<T> comparer = GetComparerForReferenceTypesOnly<T>();
904 int endIndex = startIndex - count + 1;
905 if (comparer != null)
907 for (int i = startIndex; i >= endIndex; i--)
909 if (comparer.Equals(array[i], value))
915 for (int i = startIndex; i >= endIndex; i--)
917 if (StructOnlyEquals<T>(array[i], value))
925 // Reverses all elements of the given array. Following a call to this
926 // method, an element previously located at index i will now be
927 // located at index length - i - 1, where length is the
928 // length of the array.
930 public static void Reverse(Array array)
933 throw new ArgumentNullException(nameof(array));
935 Reverse(array, array.GetLowerBound(0), array.Length);
938 // Reverses the elements in a range of an array. Following a call to this
939 // method, an element in the range given by index and count
940 // which was previously located at index i will now be located at
941 // index index + (index + count - i - 1).
942 // Reliability note: This may fail because it may have to box objects.
944 public static void Reverse(Array array, int index, int length)
947 throw new ArgumentNullException(nameof(array));
948 int lowerBound = array.GetLowerBound(0);
949 if (index < lowerBound || length < 0)
950 throw new ArgumentOutOfRangeException((index < lowerBound ? nameof(index) : nameof(length)), SR.ArgumentOutOfRange_NeedNonNegNum);
951 if (array.Length - (index - lowerBound) < length)
952 throw new ArgumentException(SR.Argument_InvalidOffLen);
954 throw new RankException(SR.Rank_MultiDimNotSupported);
957 int j = index + length - 1;
958 Object[] objArray = array as Object[];
959 if (objArray != null)
963 Object temp = objArray[i];
964 objArray[i] = objArray[j];
974 Object temp = array.GetValue(i);
975 array.SetValue(array.GetValue(j), i);
976 array.SetValue(temp, j);
983 public static void Reverse<T>(T[] array)
986 throw new ArgumentNullException(nameof(array));
988 Reverse(array, 0, array.Length);
991 public static void Reverse<T>(T[] array, int index, int length)
994 throw new ArgumentNullException(nameof(array));
995 if (index < 0 || length < 0)
996 throw new ArgumentOutOfRangeException((index < 0 ? nameof(index) : nameof(length)), SR.ArgumentOutOfRange_NeedNonNegNum);
997 if (array.Length - index < length)
998 throw new ArgumentException(SR.Argument_InvalidOffLen);
1001 int j = index + length - 1;
1005 array[i] = array[j];
1012 public void SetValue(object value, long index)
1014 if (index > int.MaxValue || index < int.MinValue)
1015 throw new ArgumentOutOfRangeException(nameof(index), SR.ArgumentOutOfRange_HugeArrayNotSupported);
1017 SetValue(value, (int)index);
1020 public void SetValue(object value, long index1, long index2)
1022 if (index1 > int.MaxValue || index1 < int.MinValue)
1023 throw new ArgumentOutOfRangeException(nameof(index1), SR.ArgumentOutOfRange_HugeArrayNotSupported);
1024 if (index2 > int.MaxValue || index2 < int.MinValue)
1025 throw new ArgumentOutOfRangeException(nameof(index2), SR.ArgumentOutOfRange_HugeArrayNotSupported);
1027 SetValue(value, (int)index1, (int)index2);
1030 public void SetValue(object value, long index1, long index2, long index3)
1032 if (index1 > int.MaxValue || index1 < int.MinValue)
1033 throw new ArgumentOutOfRangeException(nameof(index1), SR.ArgumentOutOfRange_HugeArrayNotSupported);
1034 if (index2 > int.MaxValue || index2 < int.MinValue)
1035 throw new ArgumentOutOfRangeException(nameof(index2), SR.ArgumentOutOfRange_HugeArrayNotSupported);
1036 if (index3 > int.MaxValue || index3 < int.MinValue)
1037 throw new ArgumentOutOfRangeException(nameof(index3), SR.ArgumentOutOfRange_HugeArrayNotSupported);
1039 SetValue(value, (int)index1, (int)index2, (int)index3);
1042 public void SetValue(object value, params long[] indices)
1044 if (indices == null)
1045 throw new ArgumentNullException(nameof(indices));
1046 if (Rank != indices.Length)
1047 throw new ArgumentException(SR.Arg_RankIndices);
1049 int[] intIndices = new int[indices.Length];
1051 for (int i = 0; i < indices.Length; ++i)
1053 long index = indices[i];
1054 if (index > int.MaxValue || index < int.MinValue)
1055 throw new ArgumentOutOfRangeException("index", SR.ArgumentOutOfRange_HugeArrayNotSupported);
1056 intIndices[i] = (int)index;
1059 SetValue(value, intIndices);
1062 // Sorts the elements of an array. The sort compares the elements to each
1063 // other using the IComparable interface, which must be implemented
1064 // by all elements of the array.
1066 public static void Sort(Array array)
1069 throw new ArgumentNullException(nameof(array));
1071 Sort(array, null, array.GetLowerBound(0), array.Length, null);
1074 // Sorts the elements in a section of an array. The sort compares the
1075 // elements to each other using the IComparable interface, which
1076 // must be implemented by all elements in the given section of the array.
1078 public static void Sort(Array array, int index, int length)
1080 Sort(array, null, index, length, null);
1083 // Sorts the elements of an array. The sort compares the elements to each
1084 // other using the given IComparer interface. If comparer is
1085 // null, the elements are compared to each other using the
1086 // IComparable interface, which in that case must be implemented by
1087 // all elements of the array.
1089 public static void Sort(Array array, IComparer comparer)
1092 throw new ArgumentNullException(nameof(array));
1094 Sort(array, null, array.GetLowerBound(0), array.Length, comparer);
1097 // Sorts the elements in a section of an array. The sort compares the
1098 // elements to each other using the given IComparer interface. If
1099 // comparer is null, the elements are compared to each other using
1100 // the IComparable interface, which in that case must be implemented
1101 // by all elements in the given section of the array.
1103 public static void Sort(Array array, int index, int length, IComparer comparer)
1105 Sort(array, null, index, length, comparer);
1108 public static void Sort(Array keys, Array items)
1112 throw new ArgumentNullException(nameof(keys));
1115 Sort(keys, items, keys.GetLowerBound(0), keys.Length, null);
1118 public static void Sort(Array keys, Array items, IComparer comparer)
1122 throw new ArgumentNullException(nameof(keys));
1125 Sort(keys, items, keys.GetLowerBound(0), keys.Length, comparer);
1128 public static void Sort(Array keys, Array items, int index, int length)
1130 Sort(keys, items, index, length, null);
1133 public static void Sort(Array keys, Array items, int index, int length, IComparer comparer)
1136 throw new ArgumentNullException(nameof(keys));
1137 if (keys.Rank != 1 || (items != null && items.Rank != 1))
1138 throw new RankException(SR.Rank_MultiDimNotSupported);
1139 int keysLowerBound = keys.GetLowerBound(0);
1140 if (items != null && keysLowerBound != items.GetLowerBound(0))
1141 throw new ArgumentException(SR.Arg_LowerBoundsMustMatch);
1142 if (index < keysLowerBound || length < 0)
1143 throw new ArgumentOutOfRangeException((length < 0 ? nameof(length) : nameof(index)), SR.ArgumentOutOfRange_NeedNonNegNum);
1144 if (keys.Length - (index - keysLowerBound) < length || (items != null && (index - keysLowerBound) > items.Length - length))
1145 throw new ArgumentException(SR.Argument_InvalidOffLen);
1150 IComparer<Object> comparerT = new ComparerAsComparerT(comparer);
1151 Object[] objKeys = keys as Object[];
1152 Object[] objItems = items as Object[];
1154 // Unfortunately, on Project N, we don't have the ability to specialize ArraySortHelper<> on demand
1155 // for value types. Rather than incur a boxing cost on every compare and every swap (and maintain a separate introsort algorithm
1156 // just for this), box them all, sort them as an Object[] array and unbox them back.
1158 // Check if either of the arrays need to be copied.
1159 if (objKeys == null)
1161 objKeys = new Object[index + length];
1162 Array.CopyImplValueTypeArrayToReferenceArray(keys, index, objKeys, index, length, reliable: false);
1164 if (objItems == null && items != null)
1166 objItems = new Object[index + length];
1167 Array.CopyImplValueTypeArrayToReferenceArray(items, index, objItems, index, length, reliable: false);
1170 Sort<Object, Object>(objKeys, objItems, index, length, comparerT);
1172 // If either array was copied, copy it back into the original
1173 if (objKeys != keys)
1175 Array.CopyImplReferenceArrayToValueTypeArray(objKeys, index, keys, index, length, reliable: false);
1177 if (objItems != items)
1179 Array.CopyImplReferenceArrayToValueTypeArray(objItems, index, items, index, length, reliable: false);
1182 Object[] objKeys = keys as Object[];
1183 Object[] objItems = null;
1184 if (objKeys != null)
1185 objItems = items as Object[];
1186 if (objKeys != null && (items == null || objItems != null))
1188 SorterObjectArray sorter = new SorterObjectArray(objKeys, objItems, comparer);
1189 sorter.Sort(index, length);
1193 SorterGenericArray sorter = new SorterGenericArray(keys, items, comparer);
1194 sorter.Sort(index, length);
1200 // Wraps an IComparer inside an IComparer<Object>.
1201 private sealed class ComparerAsComparerT : IComparer<Object>
1203 public ComparerAsComparerT(IComparer comparer)
1205 _comparer = (comparer == null) ? LowLevelComparer.Default : comparer;
1208 public int Compare(Object x, Object y)
1210 return _comparer.Compare(x, y);
1213 private IComparer _comparer;
1216 public static void Sort<T>(T[] array)
1219 throw new ArgumentNullException(nameof(array));
1221 Sort<T>(array, 0, array.Length, null);
1224 public static void Sort<T>(T[] array, int index, int length)
1226 Sort<T>(array, index, length, null);
1229 public static void Sort<T>(T[] array, System.Collections.Generic.IComparer<T> comparer)
1232 throw new ArgumentNullException(nameof(array));
1233 Sort<T>(array, 0, array.Length, comparer);
1236 public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer)
1239 throw new ArgumentNullException(nameof(array));
1240 if (index < 0 || length < 0)
1241 throw new ArgumentOutOfRangeException((length < 0 ? nameof(length) : nameof(index)), SR.ArgumentOutOfRange_NeedNonNegNum);
1242 if (array.Length - index < length)
1243 throw new ArgumentException(SR.Argument_InvalidOffLen);
1246 ArraySortHelper<T>.Sort(array, index, length, comparer);
1249 public static void Sort<T>(T[] array, Comparison<T> comparison)
1253 throw new ArgumentNullException(nameof(array));
1256 if (comparison == null)
1258 throw new ArgumentNullException(nameof(comparison));
1261 ArraySortHelper<T>.Sort(array, 0, array.Length, comparison);
1264 public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items)
1267 throw new ArgumentNullException(nameof(keys));
1268 Contract.EndContractBlock();
1269 Sort<TKey, TValue>(keys, items, 0, keys.Length, null);
1272 public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length)
1274 Sort<TKey, TValue>(keys, items, index, length, null);
1277 public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, IComparer<TKey> comparer)
1280 throw new ArgumentNullException(nameof(keys));
1281 Contract.EndContractBlock();
1282 Sort<TKey, TValue>(keys, items, 0, keys.Length, comparer);
1285 public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, IComparer<TKey> comparer)
1288 throw new ArgumentNullException(nameof(keys));
1289 if (index < 0 || length < 0)
1290 throw new ArgumentOutOfRangeException((length < 0 ? nameof(length) : nameof(index)), SR.ArgumentOutOfRange_NeedNonNegNum);
1291 if (keys.Length - index < length || (items != null && index > items.Length - length))
1292 throw new ArgumentException(SR.Argument_InvalidOffLen);
1293 Contract.EndContractBlock();
1299 Sort<TKey>(keys, index, length, comparer);
1303 ArraySortHelper<TKey, TValue>.Default.Sort(keys, items, index, length, comparer);
1307 public static T[] Empty<T>()
1309 return EmptyArray<T>.Value;
1312 public static bool Exists<T>(T[] array, Predicate<T> match)
1314 return Array.FindIndex(array, match) != -1;
1317 public static void Fill<T>(T[] array, T value)
1321 throw new ArgumentNullException(nameof(array));
1324 for (int i = 0; i < array.Length; i++)
1330 public static void Fill<T>(T[] array, T value, int startIndex, int count)
1334 throw new ArgumentNullException(nameof(array));
1337 if (startIndex < 0 || startIndex > array.Length)
1339 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
1342 if (count < 0 || startIndex > array.Length - count)
1344 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
1347 for (int i = startIndex; i < startIndex + count; i++)
1353 public static T Find<T>(T[] array, Predicate<T> match)
1357 throw new ArgumentNullException(nameof(array));
1362 throw new ArgumentNullException(nameof(match));
1365 for (int i = 0; i < array.Length; i++)
1367 if (match(array[i]))
1375 public static int FindIndex<T>(T[] array, Predicate<T> match)
1379 throw new ArgumentNullException(nameof(array));
1382 return FindIndex(array, 0, array.Length, match);
1385 public static int FindIndex<T>(T[] array, int startIndex, Predicate<T> match)
1389 throw new ArgumentNullException(nameof(array));
1392 return FindIndex(array, startIndex, array.Length - startIndex, match);
1395 public static int FindIndex<T>(T[] array, int startIndex, int count, Predicate<T> match)
1399 throw new ArgumentNullException(nameof(array));
1402 if (startIndex < 0 || startIndex > array.Length)
1404 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
1407 if (count < 0 || startIndex > array.Length - count)
1409 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
1414 throw new ArgumentNullException(nameof(match));
1417 int endIndex = startIndex + count;
1418 for (int i = startIndex; i < endIndex; i++)
1420 if (match(array[i])) return i;
1425 public static T FindLast<T>(T[] array, Predicate<T> match)
1429 throw new ArgumentNullException(nameof(array));
1434 throw new ArgumentNullException(nameof(match));
1437 for (int i = array.Length - 1; i >= 0; i--)
1439 if (match(array[i]))
1447 public static int FindLastIndex<T>(T[] array, Predicate<T> match)
1451 throw new ArgumentNullException(nameof(array));
1454 return FindLastIndex(array, array.Length - 1, array.Length, match);
1457 public static int FindLastIndex<T>(T[] array, int startIndex, Predicate<T> match)
1461 throw new ArgumentNullException(nameof(array));
1464 return FindLastIndex(array, startIndex, startIndex + 1, match);
1467 public static int FindLastIndex<T>(T[] array, int startIndex, int count, Predicate<T> match)
1471 throw new ArgumentNullException(nameof(array));
1476 throw new ArgumentNullException(nameof(match));
1479 if (array.Length == 0)
1481 // Special case for 0 length List
1482 if (startIndex != -1)
1484 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
1489 // Make sure we're not out of range
1490 if (startIndex < 0 || startIndex >= array.Length)
1492 throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index);
1496 // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
1497 if (count < 0 || startIndex - count + 1 < 0)
1499 throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count);
1502 int endIndex = startIndex - count;
1503 for (int i = startIndex; i > endIndex; i--)
1505 if (match(array[i]))
1513 public static bool TrueForAll<T>(T[] array, Predicate<T> match)
1517 throw new ArgumentNullException(nameof(array));
1522 throw new ArgumentNullException(nameof(match));
1525 for (int i = 0; i < array.Length; i++)
1527 if (!match(array[i]))
1535 public IEnumerator GetEnumerator()
1537 return new ArrayEnumerator(this);
1540 // These functions look odd, as they are part of a complex series of compiler intrinsics
1541 // designed to produce very high quality code for equality comparison cases without utilizing
1542 // reflection like other platforms. The major complication is that the specification of
1543 // IndexOf is that it is supposed to use IEquatable<T> if possible, but that requirement
1544 // cannot be expressed in IL directly due to the lack of constraints.
1545 // Instead, specialization at call time is used within the compiler.
1548 // - Perform fancy redirection for Array.GetComparerForReferenceTypesOnly<T>(). If T is a reference
1549 // type or UniversalCanon, have this redirect to EqualityComparer<T>.get_Default, Otherwise, use
1550 // the function as is. (will return null in that case)
1551 // - Change the contents of the IndexOf functions to have a pair of loops. One for if
1552 // GetComparerForReferenceTypesOnly returns null, and one for when it does not.
1553 // - If it does not return null, call the EqualityComparer<T> code.
1554 // - If it does return null, use a special function StructOnlyEquals<T>().
1555 // - Calls to that function result in calls to a pair of helper function in
1556 // EqualityComparerHelpers (StructOnlyEqualsIEquatable, or StructOnlyEqualsNullable)
1557 // depending on whether or not they are the right function to call.
1558 // - The end result is that in optimized builds, we have the same single function compiled size
1559 // characteristics that the old EqualsOnlyComparer<T>.Equals function had, but we maintain
1560 // correctness as well.
1561 private static EqualityComparer<T> GetComparerForReferenceTypesOnly<T>()
1564 return System.Runtime.CompilerServices.RuntimeHelpers.IsReferenceOrContainsReferences<T> () ? EqualityComparer<T>.Default : null;
1566 return EqualityComparer<T>.Default;
1570 private static bool StructOnlyEquals<T>(T left, T right)
1572 return left.Equals(right);
1575 private sealed class ArrayEnumerator : IEnumerator, ICloneable
1577 private Array _array;
1579 private int _endIndex; // cache array length, since it's a little slow.
1581 internal ArrayEnumerator(Array array)
1585 _endIndex = array.Length;
1588 public bool MoveNext()
1590 if (_index < _endIndex)
1593 return (_index < _endIndex);
1598 public Object Current
1602 if (_index < 0) throw new InvalidOperationException(SR.InvalidOperation_EnumNotStarted);
1603 if (_index >= _endIndex) throw new InvalidOperationException(SR.InvalidOperation_EnumEnded);
1604 return _array.GetValueWithFlattenedIndex_NoErrorCheck(_index);
1613 public object Clone()
1615 return MemberwiseClone();