5 // Joe Shaw (joe@ximian.com)
6 // Martin Baulig (martin@gnome.org)
7 // Dietmar Maurer (dietmar@ximian.com)
8 // Gonzalo Paniagua Javier (gonzalo@ximian.com)
9 // Jeffrey Stedfast (fejj@novell.com)
10 // Marek Safar (marek.safar@gmail.com)
12 // (C) 2001-2003 Ximian, Inc. http://www.ximian.com
13 // Copyright (C) 2004-2011 Novell, Inc (http://www.novell.com)
14 // Copyright (C) 2011 Xamarin Inc (http://www.xamarin.com)
16 // Permission is hereby granted, free of charge, to any person obtaining
17 // a copy of this software and associated documentation files (the
18 // "Software"), to deal in the Software without restriction, including
19 // without limitation the rights to use, copy, modify, merge, publish,
20 // distribute, sublicense, and/or sell copies of the Software, and to
21 // permit persons to whom the Software is furnished to do so, subject to
22 // the following conditions:
24 // The above copyright notice and this permission notice shall be
25 // included in all copies or substantial portions of the Software.
27 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
28 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
29 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
30 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
31 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
32 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
33 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 using System.Collections;
37 using System.Runtime.CompilerServices;
38 using System.Runtime.InteropServices;
40 using System.Collections.Generic;
41 using System.Collections.ObjectModel;
42 using System.Runtime.ConstrainedExecution;
44 using System.Reflection.Emit;
51 // FIXME: We are doing way to many double/triple exception checks for the overloaded functions"
52 public abstract class Array : ICloneable, ICollection, IList, IEnumerable
53 , IStructuralComparable, IStructuralEquatable
61 * These methods are used to implement the implicit generic interfaces
62 * implemented by arrays in NET 2.0.
63 * Only make those methods generic which really need it, to avoid
64 * creating useless instantiations.
66 internal int InternalArray__ICollection_get_Count ()
71 internal bool InternalArray__ICollection_get_IsReadOnly ()
76 internal IEnumerator<T> InternalArray__IEnumerable_GetEnumerator<T> ()
78 return new InternalEnumerator<T> (this);
81 internal void InternalArray__ICollection_Clear ()
83 throw new NotSupportedException ("Collection is read-only");
86 internal void InternalArray__ICollection_Add<T> (T item)
88 throw new NotSupportedException ("Collection is of a fixed size");
91 internal bool InternalArray__ICollection_Remove<T> (T item)
93 throw new NotSupportedException ("Collection is of a fixed size");
96 internal bool InternalArray__ICollection_Contains<T> (T item)
99 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
101 int length = this.Length;
102 for (int i = 0; i < length; i++) {
104 GetGenericValueImpl (i, out value);
113 if (item.Equals (value)) {
121 internal void InternalArray__ICollection_CopyTo<T> (T[] array, int index)
124 throw new ArgumentNullException ("array");
126 // The order of these exception checks may look strange,
127 // but that's how the microsoft runtime does it.
129 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
130 if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
131 throw new ArgumentException ("Destination array was not long " +
132 "enough. Check destIndex and length, and the array's " +
135 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
137 throw new ArgumentOutOfRangeException (
138 "index", Locale.GetText ("Value has to be >= 0."));
140 Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
143 internal T InternalArray__IReadOnlyList_get_Item<T> (int index)
145 if (unchecked ((uint) index) >= unchecked ((uint) Length))
146 throw new ArgumentOutOfRangeException ("index");
149 GetGenericValueImpl (index, out value);
153 internal int InternalArray__IReadOnlyCollection_get_Count ()
158 internal void InternalArray__Insert<T> (int index, T item)
160 throw new NotSupportedException ("Collection is of a fixed size");
163 internal void InternalArray__RemoveAt (int index)
165 throw new NotSupportedException ("Collection is of a fixed size");
168 internal int InternalArray__IndexOf<T> (T item)
171 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
173 int length = this.Length;
174 for (int i = 0; i < length; i++) {
176 GetGenericValueImpl (i, out value);
179 return i + this.GetLowerBound (0);
183 if (value.Equals (item))
184 // array index may not be zero-based.
186 return i + this.GetLowerBound (0);
190 // lower bound may be MinValue
191 return this.GetLowerBound (0) - 1;
195 internal T InternalArray__get_Item<T> (int index)
197 if (unchecked ((uint) index) >= unchecked ((uint) Length))
198 throw new ArgumentOutOfRangeException ("index");
201 GetGenericValueImpl (index, out value);
205 internal void InternalArray__set_Item<T> (int index, T item)
207 if (unchecked ((uint) index) >= unchecked ((uint) Length))
208 throw new ArgumentOutOfRangeException ("index");
210 object[] oarray = this as object [];
211 if (oarray != null) {
212 oarray [index] = (object)item;
215 SetGenericValueImpl (index, ref item);
218 // CAUTION! No bounds checking!
219 [MethodImplAttribute (MethodImplOptions.InternalCall)]
220 internal extern void GetGenericValueImpl<T> (int pos, out T value);
222 // CAUTION! No bounds checking!
223 [MethodImplAttribute (MethodImplOptions.InternalCall)]
224 internal extern void SetGenericValueImpl<T> (int pos, ref T value);
226 internal struct InternalEnumerator<T> : IEnumerator<T>
228 const int NOT_STARTED = -2;
230 // this MUST be -1, because we depend on it in move next.
231 // we just decr the size, so, 0 - 1 == FINISHED
232 const int FINISHED = -1;
237 internal InternalEnumerator (Array array)
243 public void Dispose ()
248 public bool MoveNext ()
250 if (idx == NOT_STARTED)
253 return idx != FINISHED && -- idx != FINISHED;
258 if (idx == NOT_STARTED)
259 throw new InvalidOperationException ("Enumeration has not started. Call MoveNext");
261 throw new InvalidOperationException ("Enumeration already finished");
263 return array.InternalArray__get_Item<T> (array.Length - 1 - idx);
267 void IEnumerator.Reset ()
272 object IEnumerator.Current {
281 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
283 int length = this.GetLength (0);
285 for (int i = 1; i < this.Rank; i++) {
286 length *= this.GetLength (i);
293 public long LongLength {
294 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
295 get { return Length; }
299 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
301 return this.GetRank ();
306 object IList.this [int index] {
308 if (unchecked ((uint) index) >= unchecked ((uint) Length))
309 throw new IndexOutOfRangeException ("index");
311 throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported."));
312 return GetValueImpl (index);
315 if (unchecked ((uint) index) >= unchecked ((uint) Length))
316 throw new IndexOutOfRangeException ("index");
318 throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported."));
319 SetValueImpl (value, index);
323 int IList.Add (object value)
325 throw new NotSupportedException ();
330 Array.Clear (this, this.GetLowerBound (0), this.Length);
333 bool IList.Contains (object value)
336 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
338 int length = this.Length;
339 for (int i = 0; i < length; i++) {
340 if (Object.Equals (this.GetValueImpl (i), value))
346 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
347 int IList.IndexOf (object value)
350 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
352 int length = this.Length;
353 for (int i = 0; i < length; i++) {
354 if (Object.Equals (this.GetValueImpl (i), value))
355 // array index may not be zero-based.
357 return i + this.GetLowerBound (0);
361 // lower bound may be MinValue
362 return this.GetLowerBound (0) - 1;
366 void IList.Insert (int index, object value)
368 throw new NotSupportedException ();
371 void IList.Remove (object value)
373 throw new NotSupportedException ();
376 void IList.RemoveAt (int index)
378 throw new NotSupportedException ();
381 // InternalCall Methods
382 [MethodImplAttribute (MethodImplOptions.InternalCall)]
383 extern int GetRank ();
385 [MethodImplAttribute (MethodImplOptions.InternalCall)]
386 public extern int GetLength (int dimension);
389 public long GetLongLength (int dimension)
391 return GetLength (dimension);
394 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
395 [MethodImplAttribute (MethodImplOptions.InternalCall)]
396 public extern int GetLowerBound (int dimension);
398 [MethodImplAttribute (MethodImplOptions.InternalCall)]
399 public extern object GetValue (params int[] indices);
401 [MethodImplAttribute (MethodImplOptions.InternalCall)]
402 public extern void SetValue (object value, params int[] indices);
404 // CAUTION! No bounds checking!
405 [MethodImplAttribute (MethodImplOptions.InternalCall)]
406 internal extern object GetValueImpl (int pos);
408 // CAUTION! No bounds checking!
409 [MethodImplAttribute (MethodImplOptions.InternalCall)]
410 internal extern void SetValueImpl (object value, int pos);
412 [MethodImplAttribute (MethodImplOptions.InternalCall)]
413 internal extern static bool FastCopy (Array source, int source_idx, Array dest, int dest_idx, int length);
415 [MethodImplAttribute (MethodImplOptions.InternalCall)]
416 internal extern static Array CreateInstanceImpl (Type elementType, int[] lengths, int[] bounds);
419 int ICollection.Count {
425 public bool IsSynchronized {
431 public object SyncRoot {
437 public bool IsFixedSize {
443 public bool IsReadOnly {
449 public IEnumerator GetEnumerator ()
451 return new SimpleEnumerator (this);
454 int IStructuralComparable.CompareTo (object other, IComparer comparer)
459 Array arr = other as Array;
461 throw new ArgumentException ("Not an array", "other");
463 int len = GetLength (0);
464 if (len != arr.GetLength (0))
465 throw new ArgumentException ("Not of the same length", "other");
468 throw new ArgumentException ("Array must be single dimensional");
471 throw new ArgumentException ("Array must be single dimensional", "other");
473 for (int i = 0; i < len; ++i) {
474 object a = GetValue (i);
475 object b = arr.GetValue (i);
476 int r = comparer.Compare (a, b);
483 bool IStructuralEquatable.Equals (object other, IEqualityComparer comparer)
485 Array o = other as Array;
486 if (o == null || o.Length != Length)
489 if (Object.ReferenceEquals (other, this))
492 for (int i = 0; i < Length; i++) {
493 object this_item = this.GetValue (i);
494 object other_item = o.GetValue (i);
495 if (!comparer.Equals (this_item, other_item))
502 int IStructuralEquatable.GetHashCode (IEqualityComparer comparer)
504 if (comparer == null)
505 throw new ArgumentNullException ("comparer");
508 for (int i = 0; i < Length; i++)
509 hash = ((hash << 7) + hash) ^ comparer.GetHashCode (GetValueImpl (i));
513 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
514 public int GetUpperBound (int dimension)
516 return GetLowerBound (dimension) + GetLength (dimension) - 1;
519 public object GetValue (int index)
522 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
523 if (index < GetLowerBound (0) || index > GetUpperBound (0))
524 throw new IndexOutOfRangeException (Locale.GetText (
525 "Index has to be between upper and lower bound of the array."));
527 return GetValueImpl (index - GetLowerBound (0));
530 public object GetValue (int index1, int index2)
532 int[] ind = {index1, index2};
533 return GetValue (ind);
536 public object GetValue (int index1, int index2, int index3)
538 int[] ind = {index1, index2, index3};
539 return GetValue (ind);
543 public object GetValue (long index)
545 if (index < 0 || index > Int32.MaxValue)
546 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
547 "Value must be >= 0 and <= Int32.MaxValue."));
549 return GetValue ((int) index);
553 public object GetValue (long index1, long index2)
555 if (index1 < 0 || index1 > Int32.MaxValue)
556 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
557 "Value must be >= 0 and <= Int32.MaxValue."));
559 if (index2 < 0 || index2 > Int32.MaxValue)
560 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
561 "Value must be >= 0 and <= Int32.MaxValue."));
563 return GetValue ((int) index1, (int) index2);
567 public object GetValue (long index1, long index2, long index3)
569 if (index1 < 0 || index1 > Int32.MaxValue)
570 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
571 "Value must be >= 0 and <= Int32.MaxValue."));
573 if (index2 < 0 || index2 > Int32.MaxValue)
574 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
575 "Value must be >= 0 and <= Int32.MaxValue."));
577 if (index3 < 0 || index3 > Int32.MaxValue)
578 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
579 "Value must be >= 0 and <= Int32.MaxValue."));
581 return GetValue ((int) index1, (int) index2, (int) index3);
585 public void SetValue (object value, long index)
587 if (index < 0 || index > Int32.MaxValue)
588 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
589 "Value must be >= 0 and <= Int32.MaxValue."));
591 SetValue (value, (int) index);
595 public void SetValue (object value, long index1, long index2)
597 if (index1 < 0 || index1 > Int32.MaxValue)
598 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
599 "Value must be >= 0 and <= Int32.MaxValue."));
601 if (index2 < 0 || index2 > Int32.MaxValue)
602 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
603 "Value must be >= 0 and <= Int32.MaxValue."));
605 int[] ind = {(int) index1, (int) index2};
606 SetValue (value, ind);
610 public void SetValue (object value, long index1, long index2, long index3)
612 if (index1 < 0 || index1 > Int32.MaxValue)
613 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
614 "Value must be >= 0 and <= Int32.MaxValue."));
616 if (index2 < 0 || index2 > Int32.MaxValue)
617 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
618 "Value must be >= 0 and <= Int32.MaxValue."));
620 if (index3 < 0 || index3 > Int32.MaxValue)
621 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
622 "Value must be >= 0 and <= Int32.MaxValue."));
624 int[] ind = {(int) index1, (int) index2, (int) index3};
625 SetValue (value, ind);
628 public void SetValue (object value, int index)
631 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
632 if (index < GetLowerBound (0) || index > GetUpperBound (0))
633 throw new IndexOutOfRangeException (Locale.GetText (
634 "Index has to be >= lower bound and <= upper bound of the array."));
636 SetValueImpl (value, index - GetLowerBound (0));
639 public void SetValue (object value, int index1, int index2)
641 int[] ind = {index1, index2};
642 SetValue (value, ind);
645 public void SetValue (object value, int index1, int index2, int index3)
647 int[] ind = {index1, index2, index3};
648 SetValue (value, ind);
651 internal static Array UnsafeCreateInstance (Type elementType, int length)
653 return CreateInstance (elementType, length);
656 internal static Array UnsafeCreateInstance(Type elementType, int[] lengths, int[] lowerBounds)
658 return CreateInstance(elementType, lengths, lowerBounds);
661 internal static Array UnsafeCreateInstance (Type elementType, int length1, int length2)
663 return CreateInstance (elementType, length1, length2);
666 internal static Array UnsafeCreateInstance (Type elementType, params int[] lengths)
668 return CreateInstance(elementType, lengths);
671 public static Array CreateInstance (Type elementType, int length)
673 int[] lengths = {length};
675 return CreateInstance (elementType, lengths);
678 public static Array CreateInstance (Type elementType, int length1, int length2)
680 int[] lengths = {length1, length2};
682 return CreateInstance (elementType, lengths);
685 public static Array CreateInstance (Type elementType, int length1, int length2, int length3)
687 int[] lengths = {length1, length2, length3};
689 return CreateInstance (elementType, lengths);
692 public static Array CreateInstance (Type elementType, params int[] lengths)
694 if (elementType == null)
695 throw new ArgumentNullException ("elementType");
697 throw new ArgumentNullException ("lengths");
699 if (lengths.Length > 255)
700 throw new TypeLoadException ();
704 elementType = elementType.UnderlyingSystemType as RuntimeType;
705 if (elementType == null)
706 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
707 if (elementType.Equals (typeof (void)))
708 throw new NotSupportedException ("Array type can not be void");
709 if (elementType.ContainsGenericParameters)
710 throw new NotSupportedException ("Array type can not be an open generic type");
711 #if !FULL_AOT_RUNTIME
712 if ((elementType is TypeBuilder) && !(elementType as TypeBuilder).IsCreated ())
713 throw new NotSupportedException ("Can't create an array of the unfinished type '" + elementType + "'.");
716 return CreateInstanceImpl (elementType, lengths, bounds);
719 public static Array CreateInstance (Type elementType, int[] lengths, int [] lowerBounds)
721 if (elementType == null)
722 throw new ArgumentNullException ("elementType");
724 throw new ArgumentNullException ("lengths");
725 if (lowerBounds == null)
726 throw new ArgumentNullException ("lowerBounds");
728 elementType = elementType.UnderlyingSystemType as RuntimeType;
729 if (elementType == null)
730 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
731 if (elementType.Equals (typeof (void)))
732 throw new NotSupportedException ("Array type can not be void");
733 if (elementType.ContainsGenericParameters)
734 throw new NotSupportedException ("Array type can not be an open generic type");
736 if (lengths.Length < 1)
737 throw new ArgumentException (Locale.GetText ("Arrays must contain >= 1 elements."));
739 if (lengths.Length != lowerBounds.Length)
740 throw new ArgumentException (Locale.GetText ("Arrays must be of same size."));
742 for (int j = 0; j < lowerBounds.Length; j ++) {
744 throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
745 "Each value has to be >= 0."));
746 if ((long)lowerBounds [j] + (long)lengths [j] > (long)Int32.MaxValue)
747 throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
748 "Length + bound must not exceed Int32.MaxValue."));
751 if (lengths.Length > 255)
752 throw new TypeLoadException ();
754 return CreateInstanceImpl (elementType, lengths, lowerBounds);
757 static int [] GetIntArray (long [] values)
759 int len = values.Length;
760 int [] ints = new int [len];
761 for (int i = 0; i < len; i++) {
762 long current = values [i];
763 if (current < 0 || current > (long) Int32.MaxValue)
764 throw new ArgumentOutOfRangeException ("values", Locale.GetText (
765 "Each value has to be >= 0 and <= Int32.MaxValue."));
767 ints [i] = (int) current;
772 public static Array CreateInstance (Type elementType, params long [] lengths)
775 throw new ArgumentNullException ("lengths");
776 return CreateInstance (elementType, GetIntArray (lengths));
780 public object GetValue (params long [] indices)
783 throw new ArgumentNullException ("indices");
784 return GetValue (GetIntArray (indices));
788 public void SetValue (object value, params long [] indices)
791 throw new ArgumentNullException ("indices");
792 SetValue (value, GetIntArray (indices));
795 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
796 public static int BinarySearch (Array array, object value)
798 return BinarySearch (array, value, null);
801 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
802 public static int BinarySearch (Array array, object value, IComparer comparer)
805 throw new ArgumentNullException ("array");
808 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
810 if (array.Length == 0)
813 return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer);
816 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
817 public static int BinarySearch (Array array, int index, int length, object value)
819 return BinarySearch (array, index, length, value, null);
822 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
823 public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
826 throw new ArgumentNullException ("array");
829 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
831 if (index < array.GetLowerBound (0))
832 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
833 "index is less than the lower bound of array."));
835 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
836 "Value has to be >= 0."));
837 // re-ordered to avoid possible integer overflow
838 if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
839 throw new ArgumentException (Locale.GetText (
840 "index and length do not specify a valid range in array."));
842 if (array.Length == 0)
845 return DoBinarySearch (array, index, length, value, comparer);
848 static int DoBinarySearch (Array array, int index, int length, object value, IComparer comparer)
850 // cache this in case we need it
851 if (comparer == null)
852 comparer = Comparer.Default;
855 // Comment from Tum (tum@veridicus.com):
856 // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
857 int iMax = index + length - 1;
860 while (iMin <= iMax) {
861 // Be careful with overflow
862 // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
863 int iMid = iMin + ((iMax - iMin) / 2);
864 object elt = array.GetValueImpl (iMid);
866 iCmp = comparer.Compare (elt, value);
873 iMin = iMid + 1; // compensate for the rounding down
876 catch (Exception e) {
877 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
883 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
884 public static void Clear (Array array, int index, int length)
887 throw new ArgumentNullException ("array");
889 throw new IndexOutOfRangeException ("length < 0");
891 int low = array.GetLowerBound (0);
893 throw new IndexOutOfRangeException ("index < lower bound");
896 // re-ordered to avoid possible integer overflow
897 if (index > array.Length - length)
898 throw new IndexOutOfRangeException ("index + length > size");
900 ClearInternal (array, index, length);
903 [MethodImplAttribute (MethodImplOptions.InternalCall)]
904 static extern void ClearInternal (Array a, int index, int count);
906 [MethodImplAttribute (MethodImplOptions.InternalCall)]
907 public extern object Clone ();
909 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
910 public static void Copy (Array sourceArray, Array destinationArray, int length)
912 // need these checks here because we are going to use
913 // GetLowerBound() on source and dest.
914 if (sourceArray == null)
915 throw new ArgumentNullException ("sourceArray");
917 if (destinationArray == null)
918 throw new ArgumentNullException ("destinationArray");
920 Copy (sourceArray, sourceArray.GetLowerBound (0), destinationArray,
921 destinationArray.GetLowerBound (0), length);
924 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
925 public static void Copy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
927 if (sourceArray == null)
928 throw new ArgumentNullException ("sourceArray");
930 if (destinationArray == null)
931 throw new ArgumentNullException ("destinationArray");
934 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
935 "Value has to be >= 0."));;
938 throw new ArgumentOutOfRangeException ("sourceIndex", Locale.GetText (
939 "Value has to be >= 0."));;
941 if (destinationIndex < 0)
942 throw new ArgumentOutOfRangeException ("destinationIndex", Locale.GetText (
943 "Value has to be >= 0."));;
945 if (FastCopy (sourceArray, sourceIndex, destinationArray, destinationIndex, length))
948 int source_pos = sourceIndex - sourceArray.GetLowerBound (0);
949 int dest_pos = destinationIndex - destinationArray.GetLowerBound (0);
952 throw new ArgumentOutOfRangeException ("destinationIndex", "Index was less than the array's lower bound in the first dimension.");
954 // re-ordered to avoid possible integer overflow
955 if (source_pos > sourceArray.Length - length)
956 throw new ArgumentException ("length");
958 if (dest_pos > destinationArray.Length - length) {
959 string msg = "Destination array was not long enough. Check " +
960 "destIndex and length, and the array's lower bounds";
961 throw new ArgumentException (msg, string.Empty);
964 if (sourceArray.Rank != destinationArray.Rank)
965 throw new RankException (Locale.GetText ("Arrays must be of same size."));
967 Type src_type = sourceArray.GetType ().GetElementType ();
968 Type dst_type = destinationArray.GetType ().GetElementType ();
970 if (!Object.ReferenceEquals (sourceArray, destinationArray) || source_pos > dest_pos) {
971 for (int i = 0; i < length; i++) {
972 Object srcval = sourceArray.GetValueImpl (source_pos + i);
975 destinationArray.SetValueImpl (srcval, dest_pos + i);
976 } catch (ArgumentException) {
977 throw CreateArrayTypeMismatchException ();
979 if (CanAssignArrayElement (src_type, dst_type))
982 throw CreateArrayTypeMismatchException ();
987 for (int i = length - 1; i >= 0; i--) {
988 Object srcval = sourceArray.GetValueImpl (source_pos + i);
991 destinationArray.SetValueImpl (srcval, dest_pos + i);
992 } catch (ArgumentException) {
993 throw CreateArrayTypeMismatchException ();
995 if (CanAssignArrayElement (src_type, dst_type))
998 throw CreateArrayTypeMismatchException ();
1004 static Exception CreateArrayTypeMismatchException ()
1006 return new ArrayTypeMismatchException ();
1009 static bool CanAssignArrayElement (Type source, Type target)
1011 if (source.IsValueType)
1012 return source.IsAssignableFrom (target);
1014 if (source.IsInterface)
1015 return !target.IsValueType;
1017 if (target.IsInterface)
1018 return !source.IsValueType;
1020 return source.IsAssignableFrom (target) || target.IsAssignableFrom (source);
1023 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1024 public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray,
1025 long destinationIndex, long length)
1027 if (sourceArray == null)
1028 throw new ArgumentNullException ("sourceArray");
1030 if (destinationArray == null)
1031 throw new ArgumentNullException ("destinationArray");
1033 if (sourceIndex < Int32.MinValue || sourceIndex > Int32.MaxValue)
1034 throw new ArgumentOutOfRangeException ("sourceIndex",
1035 Locale.GetText ("Must be in the Int32 range."));
1037 if (destinationIndex < Int32.MinValue || destinationIndex > Int32.MaxValue)
1038 throw new ArgumentOutOfRangeException ("destinationIndex",
1039 Locale.GetText ("Must be in the Int32 range."));
1041 if (length < 0 || length > Int32.MaxValue)
1042 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1043 "Value must be >= 0 and <= Int32.MaxValue."));
1045 Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
1048 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1049 public static void Copy (Array sourceArray, Array destinationArray, long length)
1051 if (length < 0 || length > Int32.MaxValue)
1052 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1053 "Value must be >= 0 and <= Int32.MaxValue."));
1055 Copy (sourceArray, destinationArray, (int) length);
1058 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1059 public static int IndexOf (Array array, object value)
1062 throw new ArgumentNullException ("array");
1064 return IndexOf (array, value, 0, array.Length);
1067 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1068 public static int IndexOf (Array array, object value, int startIndex)
1071 throw new ArgumentNullException ("array");
1073 return IndexOf (array, value, startIndex, array.Length - startIndex);
1076 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1077 public static int IndexOf (Array array, object value, int startIndex, int count)
1080 throw new ArgumentNullException ("array");
1083 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1085 // re-ordered to avoid possible integer overflow
1086 if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
1087 throw new ArgumentOutOfRangeException ();
1089 int max = startIndex + count;
1090 for (int i = startIndex; i < max; i++) {
1091 if (Object.Equals (array.GetValueImpl (i), value))
1095 return array.GetLowerBound (0) - 1;
1098 public void Initialize()
1100 //FIXME: We would like to find a compiler that uses
1101 // this method. It looks like this method do nothing
1102 // in C# so no exception is trown by the moment.
1105 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1106 public static int LastIndexOf (Array array, object value)
1109 throw new ArgumentNullException ("array");
1111 if (array.Length == 0)
1112 return array.GetLowerBound (0) - 1;
1113 return LastIndexOf (array, value, array.Length - 1);
1116 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1117 public static int LastIndexOf (Array array, object value, int startIndex)
1120 throw new ArgumentNullException ("array");
1122 return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1);
1125 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1126 public static int LastIndexOf (Array array, object value, int startIndex, int count)
1129 throw new ArgumentNullException ("array");
1132 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1134 int lb = array.GetLowerBound (0);
1135 // Empty arrays do not throw ArgumentOutOfRangeException
1136 if (array.Length == 0)
1139 if (count < 0 || startIndex < lb ||
1140 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < lb)
1141 throw new ArgumentOutOfRangeException ();
1143 for (int i = startIndex; i >= startIndex - count + 1; i--) {
1144 if (Object.Equals (array.GetValueImpl (i), value))
1151 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1152 public static void Reverse (Array array)
1155 throw new ArgumentNullException ("array");
1157 Reverse (array, array.GetLowerBound (0), array.Length);
1160 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1161 public static void Reverse (Array array, int index, int length)
1164 throw new ArgumentNullException ("array");
1167 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1169 if (index < array.GetLowerBound (0) || length < 0)
1170 throw new ArgumentOutOfRangeException ();
1172 // re-ordered to avoid possible integer overflow
1173 if (index > array.GetUpperBound (0) + 1 - length)
1174 throw new ArgumentException ();
1176 int end = index + length - 1;
1177 var et = array.GetType ().GetElementType ();
1178 switch (Type.GetTypeCode (et)) {
1179 case TypeCode.Boolean:
1180 while (index < end) {
1183 array.GetGenericValueImpl (index, out a);
1184 array.GetGenericValueImpl (end, out b);
1185 array.SetGenericValueImpl (index, ref b);
1186 array.SetGenericValueImpl (end, ref a);
1193 case TypeCode.SByte:
1194 while (index < end) {
1197 array.GetGenericValueImpl (index, out a);
1198 array.GetGenericValueImpl (end, out b);
1199 array.SetGenericValueImpl (index, ref b);
1200 array.SetGenericValueImpl (end, ref a);
1206 case TypeCode.Int16:
1207 case TypeCode.UInt16:
1209 while (index < end) {
1212 array.GetGenericValueImpl (index, out a);
1213 array.GetGenericValueImpl (end, out b);
1214 array.SetGenericValueImpl (index, ref b);
1215 array.SetGenericValueImpl (end, ref a);
1221 case TypeCode.Int32:
1222 case TypeCode.UInt32:
1223 case TypeCode.Single:
1224 while (index < end) {
1227 array.GetGenericValueImpl (index, out a);
1228 array.GetGenericValueImpl (end, out b);
1229 array.SetGenericValueImpl (index, ref b);
1230 array.SetGenericValueImpl (end, ref a);
1236 case TypeCode.Int64:
1237 case TypeCode.UInt64:
1238 case TypeCode.Double:
1239 while (index < end) {
1242 array.GetGenericValueImpl (index, out a);
1243 array.GetGenericValueImpl (end, out b);
1244 array.SetGenericValueImpl (index, ref b);
1245 array.SetGenericValueImpl (end, ref a);
1251 case TypeCode.Decimal:
1252 while (index < end) {
1255 array.GetGenericValueImpl (index, out a);
1256 array.GetGenericValueImpl (end, out b);
1257 array.SetGenericValueImpl (index, ref b);
1258 array.SetGenericValueImpl (end, ref a);
1264 case TypeCode.String:
1265 while (index < end) {
1268 array.GetGenericValueImpl (index, out a);
1269 array.GetGenericValueImpl (end, out b);
1270 array.SetGenericValueImpl (index, ref b);
1271 array.SetGenericValueImpl (end, ref a);
1277 if (array is object[])
1278 goto case TypeCode.String;
1280 // Very slow fallback
1281 while (index < end) {
1282 object val = array.GetValueImpl (index);
1283 array.SetValueImpl (array.GetValueImpl (end), index);
1284 array.SetValueImpl (val, end);
1293 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1294 public static void Sort (Array array)
1296 Sort (array, (IComparer)null);
1299 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1300 public static void Sort (Array keys, Array items)
1302 Sort (keys, items, (IComparer)null);
1305 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1306 public static void Sort (Array array, IComparer comparer)
1309 throw new ArgumentNullException ("array");
1312 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1314 SortImpl (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
1317 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1318 public static void Sort (Array array, int index, int length)
1320 Sort (array, index, length, (IComparer)null);
1323 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1324 public static void Sort (Array keys, Array items, IComparer comparer)
1326 if (items == null) {
1327 Sort (keys, comparer);
1332 throw new ArgumentNullException ("keys");
1334 if (keys.Rank > 1 || items.Rank > 1)
1335 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1337 SortImpl (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
1340 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1341 public static void Sort (Array keys, Array items, int index, int length)
1343 Sort (keys, items, index, length, (IComparer)null);
1346 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1347 public static void Sort (Array array, int index, int length, IComparer comparer)
1350 throw new ArgumentNullException ("array");
1353 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1355 if (index < array.GetLowerBound (0))
1356 throw new ArgumentOutOfRangeException ("index");
1359 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1360 "Value has to be >= 0."));
1362 if (array.Length - (array.GetLowerBound (0) + index) < length)
1363 throw new ArgumentException ();
1365 SortImpl (array, null, index, length, comparer);
1368 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1369 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
1371 if (items == null) {
1372 Sort (keys, index, length, comparer);
1377 throw new ArgumentNullException ("keys");
1379 if (keys.Rank > 1 || items.Rank > 1)
1380 throw new RankException ();
1382 if (keys.GetLowerBound (0) != items.GetLowerBound (0))
1383 throw new ArgumentException ();
1385 if (index < keys.GetLowerBound (0))
1386 throw new ArgumentOutOfRangeException ("index");
1389 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1390 "Value has to be >= 0."));
1392 if (items.Length - (index + items.GetLowerBound (0)) < length || keys.Length - (index + keys.GetLowerBound (0)) < length)
1393 throw new ArgumentException ();
1395 SortImpl (keys, items, index, length, comparer);
1398 private static void SortImpl (Array keys, Array items, int index, int length, IComparer comparer)
1404 int high = index + length - 1;
1406 #if !BOOTSTRAP_BASIC
1407 if (comparer == null && items is object[]) {
1408 /* Its better to compare typecodes as casts treat long/ulong/long based enums the same */
1409 switch (Type.GetTypeCode (keys.GetType ().GetElementType ())) {
1410 case TypeCode.Int32:
1411 qsort (keys as Int32[], items as object[], low, high);
1413 case TypeCode.Int64:
1414 qsort (keys as Int64[], items as object[], low, high);
1417 qsort (keys as byte[], items as object[], low, high);
1420 qsort (keys as char[], items as object[], low, high);
1422 case TypeCode.DateTime:
1423 qsort (keys as DateTime[], items as object[], low, high);
1425 case TypeCode.Decimal:
1426 qsort (keys as decimal[], items as object[], low, high);
1428 case TypeCode.Double:
1429 qsort (keys as double[], items as object[], low, high);
1431 case TypeCode.Int16:
1432 qsort (keys as Int16[], items as object[], low, high);
1434 case TypeCode.SByte:
1435 qsort (keys as SByte[], items as object[], low, high);
1437 case TypeCode.Single:
1438 qsort (keys as Single[], items as object[], low, high);
1440 case TypeCode.UInt16:
1441 qsort (keys as UInt16[], items as object[], low, high);
1443 case TypeCode.UInt32:
1444 qsort (keys as UInt32[], items as object[], low, high);
1446 case TypeCode.UInt64:
1447 qsort (keys as UInt64[], items as object[], low, high);
1455 if (comparer == null)
1456 CheckComparerAvailable (keys, low, high);
1459 qsort (keys, items, low, high, comparer);
1460 } catch (Exception e) {
1461 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1470 static bool QSortArrange (Array keys, Array items, int lo, ref object v0, int hi, ref object v1, IComparer comparer)
1475 if (comparer != null) {
1476 if (comparer.Compare (v1, v0) < 0) {
1477 swap (keys, items, lo, hi);
1484 } else if (v0 != null) {
1485 cmp = v1 as IComparable;
1487 if (v1 == null || cmp.CompareTo (v0) < 0) {
1488 swap (keys, items, lo, hi);
1500 unsafe static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
1502 QSortStack* stack = stackalloc QSortStack [32];
1503 const int QSORT_THRESHOLD = 7;
1504 int high, low, mid, i, k;
1509 // initialize our stack
1510 stack[0].high = high0;
1511 stack[0].low = low0;
1516 high = stack[sp].high;
1517 low = stack[sp].low;
1519 if ((low + QSORT_THRESHOLD) > high) {
1520 // switch to insertion sort
1521 for (i = low + 1; i <= high; i++) {
1522 for (k = i; k > low; k--) {
1523 lo = keys.GetValueImpl (k - 1);
1524 hi = keys.GetValueImpl (k);
1525 if (comparer != null) {
1526 if (comparer.Compare (hi, lo) >= 0)
1533 cmp = hi as IComparable;
1534 if (cmp.CompareTo (lo) >= 0)
1539 swap (keys, items, k - 1, k);
1546 // calculate the middle element
1547 mid = low + ((high - low) / 2);
1550 key = keys.GetValueImpl (mid);
1551 hi = keys.GetValueImpl (high);
1552 lo = keys.GetValueImpl (low);
1554 // once we re-order the low, mid, and high elements to be in
1555 // ascending order, we'll use mid as our pivot.
1556 QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1557 if (QSortArrange (keys, items, mid, ref key, high, ref hi, comparer))
1558 QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1560 cmp = key as IComparable;
1562 // since we've already guaranteed that lo <= mid and mid <= hi,
1563 // we can skip comparing them again.
1568 // Move the walls in
1569 if (comparer != null) {
1570 // find the first element with a value >= pivot value
1571 while (i < k && comparer.Compare (key, keys.GetValueImpl (i)) > 0)
1574 // find the last element with a value <= pivot value
1575 while (k > i && comparer.Compare (key, keys.GetValueImpl (k)) < 0)
1577 } else if (cmp != null) {
1578 // find the first element with a value >= pivot value
1579 while (i < k && cmp.CompareTo (keys.GetValueImpl (i)) > 0)
1582 // find the last element with a value <= pivot value
1583 while (k > i && cmp.CompareTo (keys.GetValueImpl (k)) < 0)
1586 // This has the effect of moving the null values to the front if comparer is null
1587 while (i < k && keys.GetValueImpl (i) == null)
1590 while (k > i && keys.GetValueImpl (k) != null)
1597 swap (keys, items, i, k);
1603 // push our partitions onto the stack, largest first
1604 // (to make sure we don't run out of stack space)
1605 if ((high - k) >= (k - low)) {
1606 if ((k + 1) < high) {
1607 stack[sp].high = high;
1612 if ((k - 1) > low) {
1614 stack[sp].low = low;
1618 if ((k - 1) > low) {
1620 stack[sp].low = low;
1624 if ((k + 1) < high) {
1625 stack[sp].high = high;
1633 private static void CheckComparerAvailable (Array keys, int low, int high)
1635 // move null keys to beginning of array,
1636 // ensure that non-null keys implement IComparable
1637 for (int i = 0; i < high; i++) {
1638 object obj = keys.GetValueImpl (i);
1641 if (!(obj is IComparable)) {
1642 string msg = Locale.GetText ("No IComparable interface found for type '{0}'.");
1643 throw new InvalidOperationException (String.Format (msg, obj.GetType ()));
1648 private static void swap (Array keys, Array items, int i, int j)
1650 object tmp = keys.GetValueImpl (i);
1651 keys.SetValueImpl (keys.GetValueImpl (j), i);
1652 keys.SetValueImpl (tmp, j);
1654 if (items != null) {
1655 tmp = items.GetValueImpl (i);
1656 items.SetValueImpl (items.GetValueImpl (j), i);
1657 items.SetValueImpl (tmp, j);
1661 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1662 public static void Sort<T> (T [] array)
1664 Sort<T> (array, (IComparer<T>)null);
1667 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1668 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items)
1670 Sort<TKey, TValue> (keys, items, (IComparer<TKey>)null);
1673 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1674 public static void Sort<T> (T [] array, IComparer<T> comparer)
1677 throw new ArgumentNullException ("array");
1679 SortImpl<T> (array, 0, array.Length, comparer);
1682 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1683 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, IComparer<TKey> comparer)
1685 if (items == null) {
1686 Sort<TKey> (keys, comparer);
1691 throw new ArgumentNullException ("keys");
1693 if (keys.Length > items.Length)
1694 throw new ArgumentException ("Length of keys is larger than length of items.");
1696 SortImpl<TKey, TValue> (keys, items, 0, keys.Length, comparer);
1699 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1700 public static void Sort<T> (T [] array, int index, int length)
1702 Sort<T> (array, index, length, (IComparer<T>)null);
1705 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1706 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length)
1708 Sort<TKey, TValue> (keys, items, index, length, (IComparer<TKey>)null);
1711 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1712 public static void Sort<T> (T [] array, int index, int length, IComparer<T> comparer)
1715 throw new ArgumentNullException ("array");
1718 throw new ArgumentOutOfRangeException ("index");
1721 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1722 "Value has to be >= 0."));
1724 if (index + length > array.Length)
1725 throw new ArgumentException ();
1727 SortImpl<T> (array, index, length, comparer);
1730 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1731 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1733 if (items == null) {
1734 Sort<TKey> (keys, index, length, comparer);
1739 throw new ArgumentNullException ("keys");
1742 throw new ArgumentOutOfRangeException ("index");
1745 throw new ArgumentOutOfRangeException ("length");
1747 if (items.Length - index < length || keys.Length - index < length)
1748 throw new ArgumentException ();
1750 SortImpl<TKey, TValue> (keys, items, index, length, comparer);
1753 private static void SortImpl<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1755 if (keys.Length <= 1)
1759 int high = index + length - 1;
1762 // Check for value types which can be sorted without Compare () method
1764 if (comparer == null) {
1765 /* Avoid this when using full-aot to prevent the generation of many unused qsort<K,T> instantiations */
1766 #if !FULL_AOT_RUNTIME
1767 #if !BOOTSTRAP_BASIC
1768 switch (Type.GetTypeCode (typeof (TKey))) {
1769 case TypeCode.Int32:
1770 qsort (keys as Int32[], items, low, high);
1772 case TypeCode.Int64:
1773 qsort (keys as Int64[], items, low, high);
1776 qsort (keys as byte[], items, low, high);
1779 qsort (keys as char[], items, low, high);
1781 case TypeCode.DateTime:
1782 qsort (keys as DateTime[], items, low, high);
1784 case TypeCode.Decimal:
1785 qsort (keys as decimal[], items, low, high);
1787 case TypeCode.Double:
1788 qsort (keys as double[], items, low, high);
1790 case TypeCode.Int16:
1791 qsort (keys as Int16[], items, low, high);
1793 case TypeCode.SByte:
1794 qsort (keys as SByte[], items, low, high);
1796 case TypeCode.Single:
1797 qsort (keys as Single[], items, low, high);
1799 case TypeCode.UInt16:
1800 qsort (keys as UInt16[], items, low, high);
1802 case TypeCode.UInt32:
1803 qsort (keys as UInt32[], items, low, high);
1805 case TypeCode.UInt64:
1806 qsort (keys as UInt64[], items, low, high);
1811 // Using Comparer<TKey> adds a small overload, but with value types it
1812 // helps us to not box them.
1813 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1814 typeof (TKey).IsValueType)
1815 comparer = Comparer<TKey>.Default;
1818 if (comparer == null)
1819 CheckComparerAvailable<TKey> (keys, low, high);
1822 qsort (keys, items, low, high, comparer);
1823 //} catch (Exception e) {
1824 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1828 // Specialized version for items==null
1829 private static void SortImpl<TKey> (TKey [] keys, int index, int length, IComparer<TKey> comparer)
1831 if (keys.Length <= 1)
1835 int high = index + length - 1;
1838 // Check for value types which can be sorted without Compare () method
1840 if (comparer == null) {
1841 #if !BOOTSTRAP_BASIC
1842 switch (Type.GetTypeCode (typeof (TKey))) {
1843 case TypeCode.Int32:
1844 qsort (keys as Int32[], low, high);
1846 case TypeCode.Int64:
1847 qsort (keys as Int64[], low, high);
1850 qsort (keys as byte[], low, high);
1853 qsort (keys as char[], low, high);
1855 case TypeCode.DateTime:
1856 qsort (keys as DateTime[], low, high);
1858 case TypeCode.Decimal:
1859 qsort (keys as decimal[], low, high);
1861 case TypeCode.Double:
1862 qsort (keys as double[], low, high);
1864 case TypeCode.Int16:
1865 qsort (keys as Int16[], low, high);
1867 case TypeCode.SByte:
1868 qsort (keys as SByte[], low, high);
1870 case TypeCode.Single:
1871 qsort (keys as Single[], low, high);
1873 case TypeCode.UInt16:
1874 qsort (keys as UInt16[], low, high);
1876 case TypeCode.UInt32:
1877 qsort (keys as UInt32[], low, high);
1879 case TypeCode.UInt64:
1880 qsort (keys as UInt64[], low, high);
1884 // Using Comparer<TKey> adds a small overload, but with value types it
1885 // helps us to not box them.
1886 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1887 typeof (TKey).IsValueType)
1888 comparer = Comparer<TKey>.Default;
1891 if (comparer == null)
1892 CheckComparerAvailable<TKey> (keys, low, high);
1895 qsort<TKey> (keys, low, high, comparer);
1896 //} catch (Exception e) {
1897 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1901 public static void Sort<T> (T [] array, Comparison<T> comparison)
1904 throw new ArgumentNullException ("array");
1906 if (comparison == null)
1907 throw new ArgumentNullException ("comparison");
1909 SortImpl<T> (array, array.Length, comparison);
1912 // used by List<T>.Sort (Comparison <T>)
1913 internal static void SortImpl<T> (T [] array, int length, Comparison<T> comparison)
1920 int high0 = length - 1;
1921 qsort<T> (array, low0, high0, comparison);
1922 } catch (InvalidOperationException) {
1924 } catch (Exception e) {
1925 throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e);
1929 static bool QSortArrange<T, U> (T [] keys, U [] items, int lo, int hi) where T : IComparable<T>
1931 if (keys[lo] != null) {
1932 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1933 swap (keys, items, lo, hi);
1941 // Specialized version for items==null
1942 static bool QSortArrange<T> (T [] keys, int lo, int hi) where T : IComparable<T>
1944 if (keys[lo] != null) {
1945 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1946 swap (keys, lo, hi);
1954 unsafe static void qsort<T, U> (T[] keys, U[] items, int low0, int high0) where T : IComparable<T>
1956 QSortStack* stack = stackalloc QSortStack [32];
1957 const int QSORT_THRESHOLD = 7;
1958 int high, low, mid, i, k;
1962 // initialize our stack
1963 stack[0].high = high0;
1964 stack[0].low = low0;
1969 high = stack[sp].high;
1970 low = stack[sp].low;
1972 if ((low + QSORT_THRESHOLD) > high) {
1973 // switch to insertion sort
1974 for (i = low + 1; i <= high; i++) {
1975 for (k = i; k > low; k--) {
1976 // if keys[k] >= keys[k-1], break
1977 if (keys[k-1] == null)
1980 if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
1983 swap (keys, items, k - 1, k);
1990 // calculate the middle element
1991 mid = low + ((high - low) / 2);
1993 // once we re-order the lo, mid, and hi elements to be in
1994 // ascending order, we'll use mid as our pivot.
1995 QSortArrange<T, U> (keys, items, low, mid);
1996 if (QSortArrange<T, U> (keys, items, mid, high))
1997 QSortArrange<T, U> (keys, items, low, mid);
2001 // since we've already guaranteed that lo <= mid and mid <= hi,
2002 // we can skip comparing them again
2008 // find the first element with a value >= pivot value
2009 while (i < k && key.CompareTo (keys[i]) > 0)
2012 // find the last element with a value <= pivot value
2013 while (k > i && key.CompareTo (keys[k]) < 0)
2016 while (i < k && keys[i] == null)
2019 while (k > i && keys[k] != null)
2026 swap (keys, items, i, k);
2032 // push our partitions onto the stack, largest first
2033 // (to make sure we don't run out of stack space)
2034 if ((high - k) >= (k - low)) {
2035 if ((k + 1) < high) {
2036 stack[sp].high = high;
2041 if ((k - 1) > low) {
2043 stack[sp].low = low;
2047 if ((k - 1) > low) {
2049 stack[sp].low = low;
2053 if ((k + 1) < high) {
2054 stack[sp].high = high;
2062 // Specialized version for items==null
2063 unsafe static void qsort<T> (T[] keys, int low0, int high0) where T : IComparable<T>
2065 QSortStack* stack = stackalloc QSortStack [32];
2066 const int QSORT_THRESHOLD = 7;
2067 int high, low, mid, i, k;
2071 // initialize our stack
2072 stack[0].high = high0;
2073 stack[0].low = low0;
2078 high = stack[sp].high;
2079 low = stack[sp].low;
2081 if ((low + QSORT_THRESHOLD) > high) {
2082 // switch to insertion sort
2083 for (i = low + 1; i <= high; i++) {
2084 for (k = i; k > low; k--) {
2085 // if keys[k] >= keys[k-1], break
2086 if (keys[k-1] == null)
2089 if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
2092 swap (keys, k - 1, k);
2099 // calculate the middle element
2100 mid = low + ((high - low) / 2);
2102 // once we re-order the lo, mid, and hi elements to be in
2103 // ascending order, we'll use mid as our pivot.
2104 QSortArrange<T> (keys, low, mid);
2105 if (QSortArrange<T> (keys, mid, high))
2106 QSortArrange<T> (keys, low, mid);
2110 // since we've already guaranteed that lo <= mid and mid <= hi,
2111 // we can skip comparing them again
2117 // find the first element with a value >= pivot value
2118 while (i < k && key.CompareTo (keys[i]) > 0)
2121 // find the last element with a value <= pivot value
2122 while (k >= i && key.CompareTo (keys[k]) < 0)
2125 while (i < k && keys[i] == null)
2128 while (k >= i && keys[k] != null)
2141 // push our partitions onto the stack, largest first
2142 // (to make sure we don't run out of stack space)
2143 if ((high - k) >= (k - low)) {
2144 if ((k + 1) < high) {
2145 stack[sp].high = high;
2150 if ((k - 1) > low) {
2152 stack[sp].low = low;
2156 if ((k - 1) > low) {
2158 stack[sp].low = low;
2162 if ((k + 1) < high) {
2163 stack[sp].high = high;
2171 static bool QSortArrange<K, V> (K [] keys, V [] items, int lo, int hi, IComparer<K> comparer)
2173 IComparable<K> gcmp;
2176 if (comparer != null) {
2177 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2178 swap<K, V> (keys, items, lo, hi);
2181 } else if (keys[lo] != null) {
2182 if (keys[hi] == null) {
2183 swap<K, V> (keys, items, lo, hi);
2187 gcmp = keys[hi] as IComparable<K>;
2189 if (gcmp.CompareTo (keys[lo]) < 0) {
2190 swap<K, V> (keys, items, lo, hi);
2197 cmp = keys[hi] as IComparable;
2199 if (cmp.CompareTo (keys[lo]) < 0) {
2200 swap<K, V> (keys, items, lo, hi);
2211 // Specialized version for items==null
2212 static bool QSortArrange<K> (K [] keys, int lo, int hi, IComparer<K> comparer)
2214 IComparable<K> gcmp;
2217 if (comparer != null) {
2218 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2219 swap<K> (keys, lo, hi);
2222 } else if (keys[lo] != null) {
2223 if (keys[hi] == null) {
2224 swap<K> (keys, lo, hi);
2228 gcmp = keys[hi] as IComparable<K>;
2230 if (gcmp.CompareTo (keys[lo]) < 0) {
2231 swap<K> (keys, lo, hi);
2238 cmp = keys[hi] as IComparable;
2240 if (cmp.CompareTo (keys[lo]) < 0) {
2241 swap<K> (keys, lo, hi);
2252 unsafe static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
2254 QSortStack* stack = stackalloc QSortStack [32];
2255 const int QSORT_THRESHOLD = 7;
2256 int high, low, mid, i, k;
2257 IComparable<K> gcmp;
2262 // initialize our stack
2263 stack[0].high = high0;
2264 stack[0].low = low0;
2269 high = stack[sp].high;
2270 low = stack[sp].low;
2272 if ((low + QSORT_THRESHOLD) > high) {
2273 // switch to insertion sort
2274 for (i = low + 1; i <= high; i++) {
2275 for (k = i; k > low; k--) {
2276 // if keys[k] >= keys[k-1], break
2277 if (comparer != null) {
2278 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2281 if (keys[k-1] == null)
2284 if (keys[k] != null) {
2285 gcmp = keys[k] as IComparable<K>;
2286 cmp = keys[k] as IComparable;
2288 if (gcmp.CompareTo (keys[k-1]) >= 0)
2291 if (cmp.CompareTo (keys[k-1]) >= 0)
2297 swap<K, V> (keys, items, k - 1, k);
2304 // calculate the middle element
2305 mid = low + ((high - low) / 2);
2307 // once we re-order the low, mid, and high elements to be in
2308 // ascending order, we'll use mid as our pivot.
2309 QSortArrange<K, V> (keys, items, low, mid, comparer);
2310 if (QSortArrange<K, V> (keys, items, mid, high, comparer))
2311 QSortArrange<K, V> (keys, items, low, mid, comparer);
2314 gcmp = key as IComparable<K>;
2315 cmp = key as IComparable;
2317 // since we've already guaranteed that lo <= mid and mid <= hi,
2318 // we can skip comparing them again.
2323 // Move the walls in
2324 if (comparer != null) {
2325 // find the first element with a value >= pivot value
2326 while (i < k && comparer.Compare (key, keys[i]) > 0)
2329 // find the last element with a value <= pivot value
2330 while (k > i && comparer.Compare (key, keys[k]) < 0)
2334 // find the first element with a value >= pivot value
2335 while (i < k && gcmp.CompareTo (keys[i]) > 0)
2338 // find the last element with a value <= pivot value
2339 while (k > i && gcmp.CompareTo (keys[k]) < 0)
2341 } else if (cmp != null) {
2342 // find the first element with a value >= pivot value
2343 while (i < k && cmp.CompareTo (keys[i]) > 0)
2346 // find the last element with a value <= pivot value
2347 while (k > i && cmp.CompareTo (keys[k]) < 0)
2350 while (i < k && keys[i] == null)
2353 while (k > i && keys[k] != null)
2361 swap<K, V> (keys, items, i, k);
2367 // push our partitions onto the stack, largest first
2368 // (to make sure we don't run out of stack space)
2369 if ((high - k) >= (k - low)) {
2370 if ((k + 1) < high) {
2371 stack[sp].high = high;
2376 if ((k - 1) > low) {
2378 stack[sp].low = low;
2382 if ((k - 1) > low) {
2384 stack[sp].low = low;
2388 if ((k + 1) < high) {
2389 stack[sp].high = high;
2397 // Specialized version for items==null
2398 unsafe static void qsort<K> (K [] keys, int low0, int high0, IComparer<K> comparer)
2400 QSortStack* stack = stackalloc QSortStack [32];
2401 const int QSORT_THRESHOLD = 7;
2402 int high, low, mid, i, k;
2403 IComparable<K> gcmp;
2408 // initialize our stack
2409 stack[0].high = high0;
2410 stack[0].low = low0;
2415 high = stack[sp].high;
2416 low = stack[sp].low;
2418 if ((low + QSORT_THRESHOLD) > high) {
2419 // switch to insertion sort
2420 for (i = low + 1; i <= high; i++) {
2421 for (k = i; k > low; k--) {
2422 // if keys[k] >= keys[k-1], break
2423 if (comparer != null) {
2424 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2427 if (keys[k-1] == null)
2430 if (keys[k] != null) {
2431 gcmp = keys[k] as IComparable<K>;
2432 cmp = keys[k] as IComparable;
2434 if (gcmp.CompareTo (keys[k-1]) >= 0)
2437 if (cmp.CompareTo (keys[k-1]) >= 0)
2443 swap<K> (keys, k - 1, k);
2450 // calculate the middle element
2451 mid = low + ((high - low) / 2);
2453 // once we re-order the low, mid, and high elements to be in
2454 // ascending order, we'll use mid as our pivot.
2455 QSortArrange<K> (keys, low, mid, comparer);
2456 if (QSortArrange<K> (keys, mid, high, comparer))
2457 QSortArrange<K> (keys, low, mid, comparer);
2460 gcmp = key as IComparable<K>;
2461 cmp = key as IComparable;
2463 // since we've already guaranteed that lo <= mid and mid <= hi,
2464 // we can skip comparing them again.
2469 // Move the walls in
2470 if (comparer != null) {
2471 // find the first element with a value >= pivot value
2472 while (i < k && comparer.Compare (key, keys[i]) > 0)
2475 // find the last element with a value <= pivot value
2476 while (k > i && comparer.Compare (key, keys[k]) < 0)
2480 // find the first element with a value >= pivot value
2481 while (i < k && gcmp.CompareTo (keys[i]) > 0)
2484 // find the last element with a value <= pivot value
2485 while (k > i && gcmp.CompareTo (keys[k]) < 0)
2487 } else if (cmp != null) {
2488 // find the first element with a value >= pivot value
2489 while (i < k && cmp.CompareTo (keys[i]) > 0)
2492 // find the last element with a value <= pivot value
2493 while (k > i && cmp.CompareTo (keys[k]) < 0)
2496 while (i < k && keys[i] == null)
2499 while (k > i && keys[k] != null)
2507 swap<K> (keys, i, k);
2513 // push our partitions onto the stack, largest first
2514 // (to make sure we don't run out of stack space)
2515 if ((high - k) >= (k - low)) {
2516 if ((k + 1) < high) {
2517 stack[sp].high = high;
2522 if ((k - 1) > low) {
2524 stack[sp].low = low;
2528 if ((k - 1) > low) {
2530 stack[sp].low = low;
2534 if ((k + 1) < high) {
2535 stack[sp].high = high;
2543 static bool QSortArrange<T> (T [] array, int lo, int hi, Comparison<T> compare)
2545 if (array[lo] != null) {
2546 if (array[hi] == null || compare (array[hi], array[lo]) < 0) {
2547 swap<T> (array, lo, hi);
2555 unsafe static void qsort<T> (T [] array, int low0, int high0, Comparison<T> compare)
2557 QSortStack* stack = stackalloc QSortStack [32];
2558 const int QSORT_THRESHOLD = 7;
2559 int high, low, mid, i, k;
2563 // initialize our stack
2564 stack[0].high = high0;
2565 stack[0].low = low0;
2570 high = stack[sp].high;
2571 low = stack[sp].low;
2573 if ((low + QSORT_THRESHOLD) > high) {
2574 // switch to insertion sort
2575 for (i = low + 1; i <= high; i++) {
2576 for (k = i; k > low; k--) {
2577 if (compare (array[k], array[k-1]) >= 0)
2580 swap<T> (array, k - 1, k);
2587 // calculate the middle element
2588 mid = low + ((high - low) / 2);
2590 // once we re-order the lo, mid, and hi elements to be in
2591 // ascending order, we'll use mid as our pivot.
2592 QSortArrange<T> (array, low, mid, compare);
2593 if (QSortArrange<T> (array, mid, high, compare))
2594 QSortArrange<T> (array, low, mid, compare);
2598 // since we've already guaranteed that lo <= mid and mid <= hi,
2599 // we can skip comparing them again
2604 // Move the walls in
2606 // find the first element with a value >= pivot value
2607 while (i < k && compare (key, array[i]) > 0)
2610 // find the last element with a value <= pivot value
2611 while (k > i && compare (key, array[k]) < 0)
2614 while (i < k && array[i] == null)
2617 while (k > i && array[k] != null)
2624 swap<T> (array, i, k);
2630 // push our partitions onto the stack, largest first
2631 // (to make sure we don't run out of stack space)
2632 if ((high - k) >= (k - low)) {
2633 if ((k + 1) < high) {
2634 stack[sp].high = high;
2639 if ((k - 1) > low) {
2641 stack[sp].low = low;
2645 if ((k - 1) > low) {
2647 stack[sp].low = low;
2651 if ((k + 1) < high) {
2652 stack[sp].high = high;
2660 private static void CheckComparerAvailable<K> (K [] keys, int low, int high)
2662 // move null keys to beginning of array,
2663 // ensure that non-null keys implement IComparable
2664 for (int i = low; i < high; i++) {
2667 if (!(key is IComparable<K>) && !(key is IComparable)) {
2668 string msg = Locale.GetText ("No IComparable<T> or IComparable interface found for type '{0}'.");
2669 throw new InvalidOperationException (String.Format (msg, key.GetType ()));
2675 [MethodImpl ((MethodImplOptions)256)]
2676 private static void swap<K, V> (K [] keys, V [] items, int i, int j)
2681 keys [i] = keys [j];
2684 if (items != null) {
2687 items [i] = items [j];
2692 [MethodImpl ((MethodImplOptions)256)]
2693 private static void swap<T> (T [] array, int i, int j)
2696 array [i] = array [j];
2700 public void CopyTo (Array array, int index)
2703 throw new ArgumentNullException ("array");
2705 // The order of these exception checks may look strange,
2706 // but that's how the microsoft runtime does it.
2708 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2709 if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
2710 throw new ArgumentException ("Destination array was not long " +
2711 "enough. Check destIndex and length, and the array's " +
2714 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2716 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2717 "Value has to be >= 0."));
2719 Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
2722 [ComVisible (false)]
2723 public void CopyTo (Array array, long index)
2725 if (index < 0 || index > Int32.MaxValue)
2726 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2727 "Value must be >= 0 and <= Int32.MaxValue."));
2729 CopyTo (array, (int) index);
2732 internal class SimpleEnumerator : IEnumerator, ICloneable
2738 public SimpleEnumerator (Array arrayToEnumerate)
2740 this.enumeratee = arrayToEnumerate;
2741 this.currentpos = -1;
2742 this.length = arrayToEnumerate.Length;
2745 public object Current {
2747 // Exception messages based on MS implementation
2748 if (currentpos < 0 )
2749 throw new InvalidOperationException (Locale.GetText (
2750 "Enumeration has not started."));
2751 if (currentpos >= length)
2752 throw new InvalidOperationException (Locale.GetText (
2753 "Enumeration has already ended"));
2754 // Current should not increase the position. So no ++ over here.
2755 return enumeratee.GetValueImpl (currentpos);
2759 public bool MoveNext()
2761 //The docs say Current should throw an exception if last
2762 //call to MoveNext returned false. This means currentpos
2763 //should be set to length when returning false.
2764 if (currentpos < length)
2766 if(currentpos < length)
2777 public object Clone ()
2779 return MemberwiseClone ();
2783 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2784 public static void Resize<T> (ref T [] array, int newSize)
2787 throw new ArgumentOutOfRangeException ("newSize");
2789 if (array == null) {
2790 array = new T [newSize];
2795 int length = arr.Length;
2796 if (length == newSize)
2799 T [] a = new T [newSize];
2800 int tocopy = Math.Min (newSize, length);
2803 for (int i = 0; i < tocopy; ++i)
2804 UnsafeStore (a, i, UnsafeLoad (arr, i));
2806 FastCopy (arr, 0, a, 0, tocopy);
2811 public static bool TrueForAll <T> (T [] array, Predicate <T> match)
2814 throw new ArgumentNullException ("array");
2816 throw new ArgumentNullException ("match");
2818 foreach (T t in array)
2825 public static void ForEach<T> (T [] array, Action <T> action)
2828 throw new ArgumentNullException ("array");
2830 throw new ArgumentNullException ("action");
2832 foreach (T t in array)
2836 public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
2839 throw new ArgumentNullException ("array");
2840 if (converter == null)
2841 throw new ArgumentNullException ("converter");
2843 TOutput [] output = new TOutput [array.Length];
2844 for (int i = 0; i < array.Length; i ++)
2845 output [i] = converter (array [i]);
2850 public static int FindLastIndex<T> (T [] array, Predicate <T> match)
2853 throw new ArgumentNullException ("array");
2856 throw new ArgumentNullException ("match");
2858 return GetLastIndex (array, 0, array.Length, match);
2861 public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
2864 throw new ArgumentNullException ();
2866 if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2867 throw new ArgumentOutOfRangeException ("startIndex");
2870 throw new ArgumentNullException ("match");
2872 return GetLastIndex (array, 0, startIndex + 1, match);
2875 public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2878 throw new ArgumentNullException ("array");
2881 throw new ArgumentNullException ("match");
2883 if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2884 throw new ArgumentOutOfRangeException ("startIndex");
2887 throw new ArgumentOutOfRangeException ("count");
2889 if (startIndex - count + 1 < 0)
2890 throw new ArgumentOutOfRangeException ("count must refer to a location within the array");
2892 return GetLastIndex (array, startIndex - count + 1, count, match);
2895 internal static int GetLastIndex<T> (T[] array, int startIndex, int count, Predicate<T> match)
2897 // unlike FindLastIndex, takes regular params for search range
2898 for (int i = startIndex + count; i != startIndex;)
2899 if (match (array [--i]))
2905 public static int FindIndex<T> (T [] array, Predicate<T> match)
2908 throw new ArgumentNullException ("array");
2911 throw new ArgumentNullException ("match");
2913 return GetIndex (array, 0, array.Length, match);
2916 public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
2919 throw new ArgumentNullException ("array");
2921 if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2922 throw new ArgumentOutOfRangeException ("startIndex");
2925 throw new ArgumentNullException ("match");
2927 return GetIndex (array, startIndex, array.Length - startIndex, match);
2930 public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2933 throw new ArgumentNullException ("array");
2936 throw new ArgumentOutOfRangeException ("startIndex");
2939 throw new ArgumentOutOfRangeException ("count");
2941 if ((uint) startIndex + (uint) count > (uint) array.Length)
2942 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
2944 return GetIndex (array, startIndex, count, match);
2947 internal static int GetIndex<T> (T[] array, int startIndex, int count, Predicate<T> match)
2949 int end = startIndex + count;
2950 for (int i = startIndex; i < end; i ++)
2951 if (match (array [i]))
2957 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2958 public static int BinarySearch<T> (T [] array, T value)
2961 throw new ArgumentNullException ("array");
2963 return BinarySearch<T> (array, 0, array.Length, value, null);
2966 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2967 public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
2970 throw new ArgumentNullException ("array");
2972 return BinarySearch<T> (array, 0, array.Length, value, comparer);
2975 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2976 public static int BinarySearch<T> (T [] array, int index, int length, T value)
2978 return BinarySearch<T> (array, index, length, value, null);
2981 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2982 public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
2985 throw new ArgumentNullException ("array");
2987 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2988 "index is less than the lower bound of array."));
2990 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
2991 "Value has to be >= 0."));
2992 // re-ordered to avoid possible integer overflow
2993 if (index > array.Length - length)
2994 throw new ArgumentException (Locale.GetText (
2995 "index and length do not specify a valid range in array."));
2996 if (comparer == null)
2997 comparer = Comparer <T>.Default;
3000 int iMax = index + length - 1;
3003 while (iMin <= iMax) {
3004 // Be careful with overflows
3005 int iMid = iMin + ((iMax - iMin) / 2);
3006 iCmp = comparer.Compare (array [iMid], value);
3014 iMin = iMid + 1; // compensate for the rounding down
3016 } catch (Exception e) {
3017 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
3023 public static int IndexOf<T> (T [] array, T value)
3026 throw new ArgumentNullException ("array");
3028 return IndexOf<T> (array, value, 0, array.Length);
3031 public static int IndexOf<T> (T [] array, T value, int startIndex)
3034 throw new ArgumentNullException ("array");
3036 return IndexOf<T> (array, value, startIndex, array.Length - startIndex);
3039 public static int IndexOf<T> (T[] array, T value, int startIndex, int count)
3042 throw new ArgumentNullException ("array");
3044 // re-ordered to avoid possible integer overflow
3045 if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
3046 throw new ArgumentOutOfRangeException ();
3048 return EqualityComparer<T>.Default.IndexOf (array, value, startIndex, count);
3051 public static int LastIndexOf<T> (T [] array, T value)
3054 throw new ArgumentNullException ("array");
3056 if (array.Length == 0)
3058 return LastIndexOf<T> (array, value, array.Length - 1);
3061 public static int LastIndexOf<T> (T [] array, T value, int startIndex)
3064 throw new ArgumentNullException ("array");
3066 return LastIndexOf<T> (array, value, startIndex, startIndex + 1);
3069 public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
3072 throw new ArgumentNullException ("array");
3074 if (count < 0 || startIndex < array.GetLowerBound (0) ||
3075 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
3076 throw new ArgumentOutOfRangeException ();
3078 EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
3079 for (int i = startIndex; i >= startIndex - count + 1; i--) {
3080 if (equalityComparer.Equals (array [i], value))
3087 public static T [] FindAll<T> (T [] array, Predicate <T> match)
3090 throw new ArgumentNullException ("array");
3093 throw new ArgumentNullException ("match");
3096 T [] d = new T [array.Length];
3097 foreach (T t in array)
3101 Resize <T> (ref d, pos);
3105 [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
3106 public static T[] Empty<T>()
3108 return EmptyArray<T>.Value;
3111 public static bool Exists<T> (T [] array, Predicate <T> match)
3114 throw new ArgumentNullException ("array");
3117 throw new ArgumentNullException ("match");
3119 foreach (T t in array)
3125 public static ReadOnlyCollection<T> AsReadOnly<T> (T[] array)
3128 throw new ArgumentNullException ("array");
3130 return new ReadOnlyCollection<T> (array);
3133 public static T Find<T> (T [] array, Predicate<T> match)
3136 throw new ArgumentNullException ("array");
3139 throw new ArgumentNullException ("match");
3141 foreach (T t in array)
3148 public static T FindLast<T> (T [] array, Predicate <T> match)
3151 throw new ArgumentNullException ("array");
3154 throw new ArgumentNullException ("match");
3156 for (int i = array.Length - 1; i >= 0; i--)
3157 if (match (array [i]))
3163 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
3165 // The constrained copy should guarantee that if there is an exception thrown
3166 // during the copy, the destination array remains unchanged.
3167 // This is related to System.Runtime.Reliability.CER
3168 public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
3170 Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length);
3173 #region Unsafe array operations
3176 // Loads array index with no safety checks (JIT intristics)
3178 internal static T UnsafeLoad<T> (T[] array, int index) {
3179 return array [index];
3183 // Stores values at specified array index with no safety checks (JIT intristics)
3185 internal static void UnsafeStore<T> (T[] array, int index, T value) {
3186 array [index] = value;
3190 // Moved value from instance into target of different type with no checks (JIT intristics)
3194 // S and R must either:
3195 // both be blitable valuetypes
3196 // both be reference types (IOW, an unsafe cast)
3197 // S and R cannot be float or double
3198 // S and R must either:
3201 // S and R must either:
3203 // both be a scalar of size <= 4
3205 internal static R UnsafeMov<S,R> (S instance) {
3206 return (R)(object) instance;
3211 internal sealed class FunctorComparer<T> : IComparer<T> {
3212 Comparison<T> comparison;
3214 public FunctorComparer(Comparison<T> comparison) {
3215 this.comparison = comparison;
3218 public int Compare(T x, T y) {
3219 return comparison(x, y);