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
54 , IStructuralComparable, IStructuralEquatable
63 * These methods are used to implement the implicit generic interfaces
64 * implemented by arrays in NET 2.0.
65 * Only make those methods generic which really need it, to avoid
66 * creating useless instantiations.
68 internal int InternalArray__ICollection_get_Count ()
73 internal bool InternalArray__ICollection_get_IsReadOnly ()
78 internal IEnumerator<T> InternalArray__IEnumerable_GetEnumerator<T> ()
80 return new InternalEnumerator<T> (this);
83 internal void InternalArray__ICollection_Clear ()
85 throw new NotSupportedException ("Collection is read-only");
88 internal void InternalArray__ICollection_Add<T> (T item)
90 throw new NotSupportedException ("Collection is of a fixed size");
93 internal bool InternalArray__ICollection_Remove<T> (T item)
95 throw new NotSupportedException ("Collection is of a fixed size");
98 internal bool InternalArray__ICollection_Contains<T> (T item)
101 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
103 int length = this.Length;
104 for (int i = 0; i < length; i++) {
106 GetGenericValueImpl (i, out value);
115 if (item.Equals (value)) {
123 internal void InternalArray__ICollection_CopyTo<T> (T[] array, int index)
126 throw new ArgumentNullException ("array");
128 // The order of these exception checks may look strange,
129 // but that's how the microsoft runtime does it.
131 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
132 if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
133 throw new ArgumentException ("Destination array was not long " +
134 "enough. Check destIndex and length, and the array's " +
137 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
139 throw new ArgumentOutOfRangeException (
140 "index", Locale.GetText ("Value has to be >= 0."));
142 Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
146 internal T InternalArray__IReadOnlyList_get_Item<T> (int index)
148 if (unchecked ((uint) index) >= unchecked ((uint) Length))
149 throw new ArgumentOutOfRangeException ("index");
152 GetGenericValueImpl (index, out value);
156 internal int InternalArray__IReadOnlyCollection_get_Count ()
162 internal void InternalArray__Insert<T> (int index, T item)
164 throw new NotSupportedException ("Collection is of a fixed size");
167 internal void InternalArray__RemoveAt (int index)
169 throw new NotSupportedException ("Collection is of a fixed size");
172 internal int InternalArray__IndexOf<T> (T item)
175 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
177 int length = this.Length;
178 for (int i = 0; i < length; i++) {
180 GetGenericValueImpl (i, out value);
183 return i + this.GetLowerBound (0);
187 if (value.Equals (item))
188 // array index may not be zero-based.
190 return i + this.GetLowerBound (0);
194 // lower bound may be MinValue
195 return this.GetLowerBound (0) - 1;
199 internal T InternalArray__get_Item<T> (int index)
201 if (unchecked ((uint) index) >= unchecked ((uint) Length))
202 throw new ArgumentOutOfRangeException ("index");
205 GetGenericValueImpl (index, out value);
209 internal void InternalArray__set_Item<T> (int index, T item)
211 if (unchecked ((uint) index) >= unchecked ((uint) Length))
212 throw new ArgumentOutOfRangeException ("index");
214 object[] oarray = this as object [];
215 if (oarray != null) {
216 oarray [index] = (object)item;
219 SetGenericValueImpl (index, ref item);
222 // CAUTION! No bounds checking!
223 [MethodImplAttribute (MethodImplOptions.InternalCall)]
224 internal extern void GetGenericValueImpl<T> (int pos, out T value);
226 // CAUTION! No bounds checking!
227 [MethodImplAttribute (MethodImplOptions.InternalCall)]
228 internal extern void SetGenericValueImpl<T> (int pos, ref T value);
230 internal struct InternalEnumerator<T> : IEnumerator<T>
232 const int NOT_STARTED = -2;
234 // this MUST be -1, because we depend on it in move next.
235 // we just decr the size, so, 0 - 1 == FINISHED
236 const int FINISHED = -1;
241 internal InternalEnumerator (Array array)
247 public void Dispose ()
252 public bool MoveNext ()
254 if (idx == NOT_STARTED)
257 return idx != FINISHED && -- idx != FINISHED;
262 if (idx == NOT_STARTED)
263 throw new InvalidOperationException ("Enumeration has not started. Call MoveNext");
265 throw new InvalidOperationException ("Enumeration already finished");
267 return array.InternalArray__get_Item<T> (array.Length - 1 - idx);
271 void IEnumerator.Reset ()
276 object IEnumerator.Current {
285 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
287 int length = this.GetLength (0);
289 for (int i = 1; i < this.Rank; i++) {
290 length *= this.GetLength (i);
297 public long LongLength {
298 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
299 get { return Length; }
303 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
305 return this.GetRank ();
310 object IList.this [int index] {
312 if (unchecked ((uint) index) >= unchecked ((uint) Length))
313 throw new IndexOutOfRangeException ("index");
315 throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported."));
316 return GetValueImpl (index);
319 if (unchecked ((uint) index) >= unchecked ((uint) Length))
320 throw new IndexOutOfRangeException ("index");
322 throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported."));
323 SetValueImpl (value, index);
327 int IList.Add (object value)
329 throw new NotSupportedException ();
334 Array.Clear (this, this.GetLowerBound (0), this.Length);
337 bool IList.Contains (object value)
340 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
342 int length = this.Length;
343 for (int i = 0; i < length; i++) {
344 if (Object.Equals (this.GetValueImpl (i), value))
350 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
351 int IList.IndexOf (object value)
354 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
356 int length = this.Length;
357 for (int i = 0; i < length; i++) {
358 if (Object.Equals (this.GetValueImpl (i), value))
359 // array index may not be zero-based.
361 return i + this.GetLowerBound (0);
365 // lower bound may be MinValue
366 return this.GetLowerBound (0) - 1;
370 void IList.Insert (int index, object value)
372 throw new NotSupportedException ();
375 void IList.Remove (object value)
377 throw new NotSupportedException ();
380 void IList.RemoveAt (int index)
382 throw new NotSupportedException ();
385 // InternalCall Methods
386 [MethodImplAttribute (MethodImplOptions.InternalCall)]
387 extern int GetRank ();
389 [MethodImplAttribute (MethodImplOptions.InternalCall)]
390 public extern int GetLength (int dimension);
393 public long GetLongLength (int dimension)
395 return GetLength (dimension);
398 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
399 [MethodImplAttribute (MethodImplOptions.InternalCall)]
400 public extern int GetLowerBound (int dimension);
402 [MethodImplAttribute (MethodImplOptions.InternalCall)]
403 public extern object GetValue (params int[] indices);
405 [MethodImplAttribute (MethodImplOptions.InternalCall)]
406 public extern void SetValue (object value, params int[] indices);
408 // CAUTION! No bounds checking!
409 [MethodImplAttribute (MethodImplOptions.InternalCall)]
410 internal extern object GetValueImpl (int pos);
412 // CAUTION! No bounds checking!
413 [MethodImplAttribute (MethodImplOptions.InternalCall)]
414 internal extern void SetValueImpl (object value, int pos);
416 [MethodImplAttribute (MethodImplOptions.InternalCall)]
417 internal extern static bool FastCopy (Array source, int source_idx, Array dest, int dest_idx, int length);
419 [MethodImplAttribute (MethodImplOptions.InternalCall)]
420 internal extern static Array CreateInstanceImpl (Type elementType, int[] lengths, int[] bounds);
423 int ICollection.Count {
429 public bool IsSynchronized {
435 public object SyncRoot {
441 public bool IsFixedSize {
447 public bool IsReadOnly {
453 public IEnumerator GetEnumerator ()
455 return new SimpleEnumerator (this);
459 int IStructuralComparable.CompareTo (object other, IComparer comparer)
464 Array arr = other as Array;
466 throw new ArgumentException ("Not an array", "other");
468 int len = GetLength (0);
469 if (len != arr.GetLength (0))
470 throw new ArgumentException ("Not of the same length", "other");
473 throw new ArgumentException ("Array must be single dimensional");
476 throw new ArgumentException ("Array must be single dimensional", "other");
478 for (int i = 0; i < len; ++i) {
479 object a = GetValue (i);
480 object b = arr.GetValue (i);
481 int r = comparer.Compare (a, b);
488 bool IStructuralEquatable.Equals (object other, IEqualityComparer comparer)
490 Array o = other as Array;
491 if (o == null || o.Length != Length)
494 if (Object.ReferenceEquals (other, this))
497 for (int i = 0; i < Length; i++) {
498 object this_item = this.GetValue (i);
499 object other_item = o.GetValue (i);
500 if (!comparer.Equals (this_item, other_item))
507 int IStructuralEquatable.GetHashCode (IEqualityComparer comparer)
509 if (comparer == null)
510 throw new ArgumentNullException ("comparer");
513 for (int i = 0; i < Length; i++)
514 hash = ((hash << 7) + hash) ^ comparer.GetHashCode (GetValueImpl (i));
519 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
520 public int GetUpperBound (int dimension)
522 return GetLowerBound (dimension) + GetLength (dimension) - 1;
525 public object GetValue (int index)
528 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
529 if (index < GetLowerBound (0) || index > GetUpperBound (0))
530 throw new IndexOutOfRangeException (Locale.GetText (
531 "Index has to be between upper and lower bound of the array."));
533 return GetValueImpl (index - GetLowerBound (0));
536 public object GetValue (int index1, int index2)
538 int[] ind = {index1, index2};
539 return GetValue (ind);
542 public object GetValue (int index1, int index2, int index3)
544 int[] ind = {index1, index2, index3};
545 return GetValue (ind);
549 public object GetValue (long index)
551 if (index < 0 || index > Int32.MaxValue)
552 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
553 "Value must be >= 0 and <= Int32.MaxValue."));
555 return GetValue ((int) index);
559 public object GetValue (long index1, long index2)
561 if (index1 < 0 || index1 > Int32.MaxValue)
562 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
563 "Value must be >= 0 and <= Int32.MaxValue."));
565 if (index2 < 0 || index2 > Int32.MaxValue)
566 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
567 "Value must be >= 0 and <= Int32.MaxValue."));
569 return GetValue ((int) index1, (int) index2);
573 public object GetValue (long index1, long index2, long index3)
575 if (index1 < 0 || index1 > Int32.MaxValue)
576 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
577 "Value must be >= 0 and <= Int32.MaxValue."));
579 if (index2 < 0 || index2 > Int32.MaxValue)
580 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
581 "Value must be >= 0 and <= Int32.MaxValue."));
583 if (index3 < 0 || index3 > Int32.MaxValue)
584 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
585 "Value must be >= 0 and <= Int32.MaxValue."));
587 return GetValue ((int) index1, (int) index2, (int) index3);
591 public void SetValue (object value, long index)
593 if (index < 0 || index > Int32.MaxValue)
594 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
595 "Value must be >= 0 and <= Int32.MaxValue."));
597 SetValue (value, (int) index);
601 public void SetValue (object value, long index1, long index2)
603 if (index1 < 0 || index1 > Int32.MaxValue)
604 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
605 "Value must be >= 0 and <= Int32.MaxValue."));
607 if (index2 < 0 || index2 > Int32.MaxValue)
608 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
609 "Value must be >= 0 and <= Int32.MaxValue."));
611 int[] ind = {(int) index1, (int) index2};
612 SetValue (value, ind);
616 public void SetValue (object value, long index1, long index2, long index3)
618 if (index1 < 0 || index1 > Int32.MaxValue)
619 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
620 "Value must be >= 0 and <= Int32.MaxValue."));
622 if (index2 < 0 || index2 > Int32.MaxValue)
623 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
624 "Value must be >= 0 and <= Int32.MaxValue."));
626 if (index3 < 0 || index3 > Int32.MaxValue)
627 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
628 "Value must be >= 0 and <= Int32.MaxValue."));
630 int[] ind = {(int) index1, (int) index2, (int) index3};
631 SetValue (value, ind);
634 public void SetValue (object value, int index)
637 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
638 if (index < GetLowerBound (0) || index > GetUpperBound (0))
639 throw new IndexOutOfRangeException (Locale.GetText (
640 "Index has to be >= lower bound and <= upper bound of the array."));
642 SetValueImpl (value, index - GetLowerBound (0));
645 public void SetValue (object value, int index1, int index2)
647 int[] ind = {index1, index2};
648 SetValue (value, ind);
651 public void SetValue (object value, int index1, int index2, int index3)
653 int[] ind = {index1, index2, index3};
654 SetValue (value, ind);
657 public static Array CreateInstance (Type elementType, int length)
659 int[] lengths = {length};
661 return CreateInstance (elementType, lengths);
664 public static Array CreateInstance (Type elementType, int length1, int length2)
666 int[] lengths = {length1, length2};
668 return CreateInstance (elementType, lengths);
671 public static Array CreateInstance (Type elementType, int length1, int length2, int length3)
673 int[] lengths = {length1, length2, length3};
675 return CreateInstance (elementType, lengths);
678 public static Array CreateInstance (Type elementType, params int[] lengths)
680 if (elementType == null)
681 throw new ArgumentNullException ("elementType");
683 throw new ArgumentNullException ("lengths");
685 if (lengths.Length > 255)
686 throw new TypeLoadException ();
690 elementType = elementType.UnderlyingSystemType;
691 if (!elementType.IsSystemType)
692 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
693 if (elementType.Equals (typeof (void)))
694 throw new NotSupportedException ("Array type can not be void");
695 if (elementType.ContainsGenericParameters)
696 throw new NotSupportedException ("Array type can not be an open generic type");
697 #if !FULL_AOT_RUNTIME
698 if ((elementType is TypeBuilder) && !(elementType as TypeBuilder).IsCreated ())
699 throw new NotSupportedException ("Can't create an array of the unfinished type '" + elementType + "'.");
702 return CreateInstanceImpl (elementType, lengths, bounds);
705 public static Array CreateInstance (Type elementType, int[] lengths, int [] lowerBounds)
707 if (elementType == null)
708 throw new ArgumentNullException ("elementType");
710 throw new ArgumentNullException ("lengths");
711 if (lowerBounds == null)
712 throw new ArgumentNullException ("lowerBounds");
714 elementType = elementType.UnderlyingSystemType;
715 if (!elementType.IsSystemType)
716 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
717 if (elementType.Equals (typeof (void)))
718 throw new NotSupportedException ("Array type can not be void");
719 if (elementType.ContainsGenericParameters)
720 throw new NotSupportedException ("Array type can not be an open generic type");
722 if (lengths.Length < 1)
723 throw new ArgumentException (Locale.GetText ("Arrays must contain >= 1 elements."));
725 if (lengths.Length != lowerBounds.Length)
726 throw new ArgumentException (Locale.GetText ("Arrays must be of same size."));
728 for (int j = 0; j < lowerBounds.Length; j ++) {
730 throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
731 "Each value has to be >= 0."));
732 if ((long)lowerBounds [j] + (long)lengths [j] > (long)Int32.MaxValue)
733 throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
734 "Length + bound must not exceed Int32.MaxValue."));
737 if (lengths.Length > 255)
738 throw new TypeLoadException ();
740 return CreateInstanceImpl (elementType, lengths, lowerBounds);
743 static int [] GetIntArray (long [] values)
745 int len = values.Length;
746 int [] ints = new int [len];
747 for (int i = 0; i < len; i++) {
748 long current = values [i];
749 if (current < 0 || current > (long) Int32.MaxValue)
750 throw new ArgumentOutOfRangeException ("values", Locale.GetText (
751 "Each value has to be >= 0 and <= Int32.MaxValue."));
753 ints [i] = (int) current;
758 public static Array CreateInstance (Type elementType, params long [] lengths)
761 throw new ArgumentNullException ("lengths");
762 return CreateInstance (elementType, GetIntArray (lengths));
766 public object GetValue (params long [] indices)
769 throw new ArgumentNullException ("indices");
770 return GetValue (GetIntArray (indices));
774 public void SetValue (object value, params long [] indices)
777 throw new ArgumentNullException ("indices");
778 SetValue (value, GetIntArray (indices));
781 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
782 public static int BinarySearch (Array array, object value)
785 throw new ArgumentNullException ("array");
791 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
793 if (array.Length == 0)
796 if (!(value is IComparable))
797 throw new ArgumentException (Locale.GetText ("value does not support IComparable."));
799 return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, null);
802 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
803 public static int BinarySearch (Array array, object value, IComparer comparer)
806 throw new ArgumentNullException ("array");
809 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
811 if (array.Length == 0)
814 if ((comparer == null) && (value != null) && !(value is IComparable))
815 throw new ArgumentException (Locale.GetText (
816 "comparer is null and value does not support IComparable."));
818 return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer);
821 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
822 public static int BinarySearch (Array array, int index, int length, object value)
825 throw new ArgumentNullException ("array");
828 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
830 if (index < array.GetLowerBound (0))
831 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
832 "index is less than the lower bound of array."));
834 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
835 "Value has to be >= 0."));
836 // re-ordered to avoid possible integer overflow
837 if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
838 throw new ArgumentException (Locale.GetText (
839 "index and length do not specify a valid range in array."));
841 if (array.Length == 0)
844 if ((value != null) && (!(value is IComparable)))
845 throw new ArgumentException (Locale.GetText (
846 "value does not support IComparable"));
848 return DoBinarySearch (array, index, length, value, null);
851 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
852 public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
855 throw new ArgumentNullException ("array");
858 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
860 if (index < array.GetLowerBound (0))
861 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
862 "index is less than the lower bound of array."));
864 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
865 "Value has to be >= 0."));
866 // re-ordered to avoid possible integer overflow
867 if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
868 throw new ArgumentException (Locale.GetText (
869 "index and length do not specify a valid range in array."));
871 if (array.Length == 0)
874 if ((comparer == null) && (value != null) && !(value is IComparable))
875 throw new ArgumentException (Locale.GetText (
876 "comparer is null and value does not support IComparable."));
878 return DoBinarySearch (array, index, length, value, comparer);
881 static int DoBinarySearch (Array array, int index, int length, object value, IComparer comparer)
883 // cache this in case we need it
884 if (comparer == null)
885 comparer = Comparer.Default;
888 // Comment from Tum (tum@veridicus.com):
889 // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
890 int iMax = index + length - 1;
893 while (iMin <= iMax) {
894 // Be careful with overflow
895 // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
896 int iMid = iMin + ((iMax - iMin) / 2);
897 object elt = array.GetValueImpl (iMid);
899 iCmp = comparer.Compare (elt, value);
906 iMin = iMid + 1; // compensate for the rounding down
909 catch (Exception e) {
910 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
916 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
917 public static void Clear (Array array, int index, int length)
920 throw new ArgumentNullException ("array");
922 throw new IndexOutOfRangeException ("length < 0");
924 int low = array.GetLowerBound (0);
926 throw new IndexOutOfRangeException ("index < lower bound");
929 // re-ordered to avoid possible integer overflow
930 if (index > array.Length - length)
931 throw new IndexOutOfRangeException ("index + length > size");
933 ClearInternal (array, index, length);
936 [MethodImplAttribute (MethodImplOptions.InternalCall)]
937 static extern void ClearInternal (Array a, int index, int count);
939 [MethodImplAttribute (MethodImplOptions.InternalCall)]
940 public extern object Clone ();
942 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
943 public static void Copy (Array sourceArray, Array destinationArray, int length)
945 // need these checks here because we are going to use
946 // GetLowerBound() on source and dest.
947 if (sourceArray == null)
948 throw new ArgumentNullException ("sourceArray");
950 if (destinationArray == null)
951 throw new ArgumentNullException ("destinationArray");
953 Copy (sourceArray, sourceArray.GetLowerBound (0), destinationArray,
954 destinationArray.GetLowerBound (0), length);
957 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
958 public static void Copy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
960 if (sourceArray == null)
961 throw new ArgumentNullException ("sourceArray");
963 if (destinationArray == null)
964 throw new ArgumentNullException ("destinationArray");
967 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
968 "Value has to be >= 0."));;
971 throw new ArgumentOutOfRangeException ("sourceIndex", Locale.GetText (
972 "Value has to be >= 0."));;
974 if (destinationIndex < 0)
975 throw new ArgumentOutOfRangeException ("destinationIndex", Locale.GetText (
976 "Value has to be >= 0."));;
978 if (FastCopy (sourceArray, sourceIndex, destinationArray, destinationIndex, length))
981 int source_pos = sourceIndex - sourceArray.GetLowerBound (0);
982 int dest_pos = destinationIndex - destinationArray.GetLowerBound (0);
984 // re-ordered to avoid possible integer overflow
985 if (source_pos > sourceArray.Length - length)
986 throw new ArgumentException ("length");
988 if (dest_pos > destinationArray.Length - length) {
989 string msg = "Destination array was not long enough. Check " +
990 "destIndex and length, and the array's lower bounds";
991 throw new ArgumentException (msg, string.Empty);
994 if (sourceArray.Rank != destinationArray.Rank)
995 throw new RankException (Locale.GetText ("Arrays must be of same size."));
997 Type src_type = sourceArray.GetType ().GetElementType ();
998 Type dst_type = destinationArray.GetType ().GetElementType ();
1000 if (!Object.ReferenceEquals (sourceArray, destinationArray) || source_pos > dest_pos) {
1001 for (int i = 0; i < length; i++) {
1002 Object srcval = sourceArray.GetValueImpl (source_pos + i);
1005 destinationArray.SetValueImpl (srcval, dest_pos + i);
1007 if (src_type.Equals (typeof (Object)))
1008 throw new InvalidCastException ();
1010 throw new ArrayTypeMismatchException (String.Format (Locale.GetText (
1011 "(Types: source={0}; target={1})"), src_type.FullName, dst_type.FullName));
1016 for (int i = length - 1; i >= 0; i--) {
1017 Object srcval = sourceArray.GetValueImpl (source_pos + i);
1020 destinationArray.SetValueImpl (srcval, dest_pos + i);
1022 if (src_type.Equals (typeof (Object)))
1023 throw new InvalidCastException ();
1025 throw new ArrayTypeMismatchException (String.Format (Locale.GetText (
1026 "(Types: source={0}; target={1})"), src_type.FullName, dst_type.FullName));
1032 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1033 public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray,
1034 long destinationIndex, long length)
1036 if (sourceArray == null)
1037 throw new ArgumentNullException ("sourceArray");
1039 if (destinationArray == null)
1040 throw new ArgumentNullException ("destinationArray");
1042 if (sourceIndex < Int32.MinValue || sourceIndex > Int32.MaxValue)
1043 throw new ArgumentOutOfRangeException ("sourceIndex",
1044 Locale.GetText ("Must be in the Int32 range."));
1046 if (destinationIndex < Int32.MinValue || destinationIndex > Int32.MaxValue)
1047 throw new ArgumentOutOfRangeException ("destinationIndex",
1048 Locale.GetText ("Must be in the Int32 range."));
1050 if (length < 0 || length > Int32.MaxValue)
1051 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1052 "Value must be >= 0 and <= Int32.MaxValue."));
1054 Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
1057 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1058 public static void Copy (Array sourceArray, Array destinationArray, long length)
1060 if (length < 0 || length > Int32.MaxValue)
1061 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1062 "Value must be >= 0 and <= Int32.MaxValue."));
1064 Copy (sourceArray, destinationArray, (int) length);
1067 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1068 public static int IndexOf (Array array, object value)
1071 throw new ArgumentNullException ("array");
1073 return IndexOf (array, value, 0, array.Length);
1076 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1077 public static int IndexOf (Array array, object value, int startIndex)
1080 throw new ArgumentNullException ("array");
1082 return IndexOf (array, value, startIndex, array.Length - startIndex);
1085 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1086 public static int IndexOf (Array array, object value, int startIndex, int count)
1089 throw new ArgumentNullException ("array");
1092 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1094 // re-ordered to avoid possible integer overflow
1095 if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
1096 throw new ArgumentOutOfRangeException ();
1098 int max = startIndex + count;
1099 for (int i = startIndex; i < max; i++) {
1100 if (Object.Equals (array.GetValueImpl (i), value))
1104 return array.GetLowerBound (0) - 1;
1107 public void Initialize()
1109 //FIXME: We would like to find a compiler that uses
1110 // this method. It looks like this method do nothing
1111 // in C# so no exception is trown by the moment.
1114 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1115 public static int LastIndexOf (Array array, object value)
1118 throw new ArgumentNullException ("array");
1120 if (array.Length == 0)
1121 return array.GetLowerBound (0) - 1;
1122 return LastIndexOf (array, value, array.Length - 1);
1125 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1126 public static int LastIndexOf (Array array, object value, int startIndex)
1129 throw new ArgumentNullException ("array");
1131 return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1);
1134 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1135 public static int LastIndexOf (Array array, object value, int startIndex, int count)
1138 throw new ArgumentNullException ("array");
1141 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1143 int lb = array.GetLowerBound (0);
1144 // Empty arrays do not throw ArgumentOutOfRangeException
1145 if (array.Length == 0)
1148 if (count < 0 || startIndex < lb ||
1149 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < lb)
1150 throw new ArgumentOutOfRangeException ();
1152 for (int i = startIndex; i >= startIndex - count + 1; i--) {
1153 if (Object.Equals (array.GetValueImpl (i), value))
1160 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1161 public static void Reverse (Array array)
1164 throw new ArgumentNullException ("array");
1166 Reverse (array, array.GetLowerBound (0), array.Length);
1169 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1170 public static void Reverse (Array array, int index, int length)
1173 throw new ArgumentNullException ("array");
1176 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1178 if (index < array.GetLowerBound (0) || length < 0)
1179 throw new ArgumentOutOfRangeException ();
1181 // re-ordered to avoid possible integer overflow
1182 if (index > array.GetUpperBound (0) + 1 - length)
1183 throw new ArgumentException ();
1185 int end = index + length - 1;
1186 var et = array.GetType ().GetElementType ();
1187 switch (Type.GetTypeCode (et)) {
1188 case TypeCode.Boolean:
1189 while (index < end) {
1192 array.GetGenericValueImpl (index, out a);
1193 array.GetGenericValueImpl (end, out b);
1194 array.SetGenericValueImpl (index, ref b);
1195 array.SetGenericValueImpl (end, ref a);
1202 case TypeCode.SByte:
1203 while (index < end) {
1206 array.GetGenericValueImpl (index, out a);
1207 array.GetGenericValueImpl (end, out b);
1208 array.SetGenericValueImpl (index, ref b);
1209 array.SetGenericValueImpl (end, ref a);
1215 case TypeCode.Int16:
1216 case TypeCode.UInt16:
1218 while (index < end) {
1221 array.GetGenericValueImpl (index, out a);
1222 array.GetGenericValueImpl (end, out b);
1223 array.SetGenericValueImpl (index, ref b);
1224 array.SetGenericValueImpl (end, ref a);
1230 case TypeCode.Int32:
1231 case TypeCode.UInt32:
1232 case TypeCode.Single:
1233 while (index < end) {
1236 array.GetGenericValueImpl (index, out a);
1237 array.GetGenericValueImpl (end, out b);
1238 array.SetGenericValueImpl (index, ref b);
1239 array.SetGenericValueImpl (end, ref a);
1245 case TypeCode.Int64:
1246 case TypeCode.UInt64:
1247 case TypeCode.Double:
1248 while (index < end) {
1251 array.GetGenericValueImpl (index, out a);
1252 array.GetGenericValueImpl (end, out b);
1253 array.SetGenericValueImpl (index, ref b);
1254 array.SetGenericValueImpl (end, ref a);
1260 case TypeCode.Decimal:
1261 while (index < end) {
1264 array.GetGenericValueImpl (index, out a);
1265 array.GetGenericValueImpl (end, out b);
1266 array.SetGenericValueImpl (index, ref b);
1267 array.SetGenericValueImpl (end, ref a);
1273 case TypeCode.String:
1274 while (index < end) {
1277 array.GetGenericValueImpl (index, out a);
1278 array.GetGenericValueImpl (end, out b);
1279 array.SetGenericValueImpl (index, ref b);
1280 array.SetGenericValueImpl (end, ref a);
1286 if (array is object[])
1287 goto case TypeCode.String;
1289 // Very slow fallback
1290 while (index < end) {
1291 object val = array.GetValueImpl (index);
1292 array.SetValueImpl (array.GetValueImpl (end), index);
1293 array.SetValueImpl (val, end);
1302 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1303 public static void Sort (Array array)
1305 Sort (array, (IComparer)null);
1308 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1309 public static void Sort (Array keys, Array items)
1311 Sort (keys, items, (IComparer)null);
1314 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1315 public static void Sort (Array array, IComparer comparer)
1318 throw new ArgumentNullException ("array");
1321 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1323 SortImpl (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
1326 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1327 public static void Sort (Array array, int index, int length)
1329 Sort (array, index, length, (IComparer)null);
1332 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1333 public static void Sort (Array keys, Array items, IComparer comparer)
1335 if (items == null) {
1336 Sort (keys, comparer);
1341 throw new ArgumentNullException ("keys");
1343 if (keys.Rank > 1 || items.Rank > 1)
1344 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1346 SortImpl (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
1349 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1350 public static void Sort (Array keys, Array items, int index, int length)
1352 Sort (keys, items, index, length, (IComparer)null);
1355 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1356 public static void Sort (Array array, int index, int length, IComparer comparer)
1359 throw new ArgumentNullException ("array");
1362 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1364 if (index < array.GetLowerBound (0))
1365 throw new ArgumentOutOfRangeException ("index");
1368 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1369 "Value has to be >= 0."));
1371 if (array.Length - (array.GetLowerBound (0) + index) < length)
1372 throw new ArgumentException ();
1374 SortImpl (array, null, index, length, comparer);
1377 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1378 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
1380 if (items == null) {
1381 Sort (keys, index, length, comparer);
1386 throw new ArgumentNullException ("keys");
1388 if (keys.Rank > 1 || items.Rank > 1)
1389 throw new RankException ();
1391 if (keys.GetLowerBound (0) != items.GetLowerBound (0))
1392 throw new ArgumentException ();
1394 if (index < keys.GetLowerBound (0))
1395 throw new ArgumentOutOfRangeException ("index");
1398 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1399 "Value has to be >= 0."));
1401 if (items.Length - (index + items.GetLowerBound (0)) < length || keys.Length - (index + keys.GetLowerBound (0)) < length)
1402 throw new ArgumentException ();
1404 SortImpl (keys, items, index, length, comparer);
1407 private static void SortImpl (Array keys, Array items, int index, int length, IComparer comparer)
1413 int high = index + length - 1;
1415 #if !BOOTSTRAP_BASIC
1416 if (comparer == null && items is object[]) {
1417 /* Its better to compare typecodes as casts treat long/ulong/long based enums the same */
1418 switch (Type.GetTypeCode (keys.GetType ().GetElementType ())) {
1419 case TypeCode.Int32:
1420 qsort (keys as Int32[], items as object[], low, high);
1422 case TypeCode.Int64:
1423 qsort (keys as Int64[], items as object[], low, high);
1426 qsort (keys as byte[], items as object[], low, high);
1429 qsort (keys as char[], items as object[], low, high);
1431 case TypeCode.DateTime:
1432 qsort (keys as DateTime[], items as object[], low, high);
1434 case TypeCode.Decimal:
1435 qsort (keys as decimal[], items as object[], low, high);
1437 case TypeCode.Double:
1438 qsort (keys as double[], items as object[], low, high);
1440 case TypeCode.Int16:
1441 qsort (keys as Int16[], items as object[], low, high);
1443 case TypeCode.SByte:
1444 qsort (keys as SByte[], items as object[], low, high);
1446 case TypeCode.Single:
1447 qsort (keys as Single[], items as object[], low, high);
1449 case TypeCode.UInt16:
1450 qsort (keys as UInt16[], items as object[], low, high);
1452 case TypeCode.UInt32:
1453 qsort (keys as UInt32[], items as object[], low, high);
1455 case TypeCode.UInt64:
1456 qsort (keys as UInt64[], items as object[], low, high);
1464 if (comparer == null)
1465 CheckComparerAvailable (keys, low, high);
1468 qsort (keys, items, low, high, comparer);
1469 } catch (Exception e) {
1470 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1479 static bool QSortArrange (Array keys, Array items, int lo, ref object v0, int hi, ref object v1, IComparer comparer)
1484 if (comparer != null) {
1485 if (comparer.Compare (v1, v0) < 0) {
1486 swap (keys, items, lo, hi);
1493 } else if (v0 != null) {
1494 cmp = v1 as IComparable;
1496 if (v1 == null || cmp.CompareTo (v0) < 0) {
1497 swap (keys, items, lo, hi);
1509 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
1511 QSortStack[] stack = new QSortStack[32];
1512 const int QSORT_THRESHOLD = 7;
1513 int high, low, mid, i, k;
1518 // initialize our stack
1519 stack[0].high = high0;
1520 stack[0].low = low0;
1525 high = stack[sp].high;
1526 low = stack[sp].low;
1528 if ((low + QSORT_THRESHOLD) > high) {
1529 // switch to insertion sort
1530 for (i = low + 1; i <= high; i++) {
1531 for (k = i; k > low; k--) {
1532 lo = keys.GetValueImpl (k - 1);
1533 hi = keys.GetValueImpl (k);
1534 if (comparer != null) {
1535 if (comparer.Compare (hi, lo) >= 0)
1542 cmp = hi as IComparable;
1543 if (cmp.CompareTo (lo) >= 0)
1548 swap (keys, items, k - 1, k);
1555 // calculate the middle element
1556 mid = low + ((high - low) / 2);
1559 key = keys.GetValueImpl (mid);
1560 hi = keys.GetValueImpl (high);
1561 lo = keys.GetValueImpl (low);
1563 // once we re-order the low, mid, and high elements to be in
1564 // ascending order, we'll use mid as our pivot.
1565 QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1566 if (QSortArrange (keys, items, mid, ref key, high, ref hi, comparer))
1567 QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1569 cmp = key as IComparable;
1571 // since we've already guaranteed that lo <= mid and mid <= hi,
1572 // we can skip comparing them again.
1577 // Move the walls in
1578 if (comparer != null) {
1579 // find the first element with a value >= pivot value
1580 while (i < k && comparer.Compare (key, keys.GetValueImpl (i)) > 0)
1583 // find the last element with a value <= pivot value
1584 while (k > i && comparer.Compare (key, keys.GetValueImpl (k)) < 0)
1586 } else if (cmp != null) {
1587 // find the first element with a value >= pivot value
1588 while (i < k && cmp.CompareTo (keys.GetValueImpl (i)) > 0)
1591 // find the last element with a value <= pivot value
1592 while (k > i && cmp.CompareTo (keys.GetValueImpl (k)) < 0)
1595 // This has the effect of moving the null values to the front if comparer is null
1596 while (i < k && keys.GetValueImpl (i) == null)
1599 while (k > i && keys.GetValueImpl (k) != null)
1606 swap (keys, items, i, k);
1612 // push our partitions onto the stack, largest first
1613 // (to make sure we don't run out of stack space)
1614 if ((high - k) >= (k - low)) {
1615 if ((k + 1) < high) {
1616 stack[sp].high = high;
1621 if ((k - 1) > low) {
1623 stack[sp].low = low;
1627 if ((k - 1) > low) {
1629 stack[sp].low = low;
1633 if ((k + 1) < high) {
1634 stack[sp].high = high;
1642 private static void CheckComparerAvailable (Array keys, int low, int high)
1644 // move null keys to beginning of array,
1645 // ensure that non-null keys implement IComparable
1646 for (int i = 0; i < high; i++) {
1647 object obj = keys.GetValueImpl (i);
1650 if (!(obj is IComparable)) {
1651 string msg = Locale.GetText ("No IComparable interface found for type '{0}'.");
1652 throw new InvalidOperationException (String.Format (msg, obj.GetType ()));
1657 private static void swap (Array keys, Array items, int i, int j)
1659 object tmp = keys.GetValueImpl (i);
1660 keys.SetValueImpl (keys.GetValueImpl (j), i);
1661 keys.SetValueImpl (tmp, j);
1663 if (items != null) {
1664 tmp = items.GetValueImpl (i);
1665 items.SetValueImpl (items.GetValueImpl (j), i);
1666 items.SetValueImpl (tmp, j);
1670 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1671 public static void Sort<T> (T [] array)
1673 Sort<T> (array, (IComparer<T>)null);
1676 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1677 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items)
1679 Sort<TKey, TValue> (keys, items, (IComparer<TKey>)null);
1682 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1683 public static void Sort<T> (T [] array, IComparer<T> comparer)
1686 throw new ArgumentNullException ("array");
1688 SortImpl<T> (array, 0, array.Length, comparer);
1691 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1692 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, IComparer<TKey> comparer)
1694 if (items == null) {
1695 Sort<TKey> (keys, comparer);
1700 throw new ArgumentNullException ("keys");
1702 if (keys.Length != items.Length)
1703 throw new ArgumentException ("Length of keys and items does not match.");
1705 SortImpl<TKey, TValue> (keys, items, 0, keys.Length, comparer);
1708 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1709 public static void Sort<T> (T [] array, int index, int length)
1711 Sort<T> (array, index, length, (IComparer<T>)null);
1714 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1715 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length)
1717 Sort<TKey, TValue> (keys, items, index, length, (IComparer<TKey>)null);
1720 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1721 public static void Sort<T> (T [] array, int index, int length, IComparer<T> comparer)
1724 throw new ArgumentNullException ("array");
1727 throw new ArgumentOutOfRangeException ("index");
1730 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1731 "Value has to be >= 0."));
1733 if (index + length > array.Length)
1734 throw new ArgumentException ();
1736 SortImpl<T> (array, index, length, comparer);
1739 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1740 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1742 if (items == null) {
1743 Sort<TKey> (keys, index, length, comparer);
1748 throw new ArgumentNullException ("keys");
1751 throw new ArgumentOutOfRangeException ("index");
1754 throw new ArgumentOutOfRangeException ("length");
1756 if (items.Length - index < length || keys.Length - index < length)
1757 throw new ArgumentException ();
1759 SortImpl<TKey, TValue> (keys, items, index, length, comparer);
1762 private static void SortImpl<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1764 if (keys.Length <= 1)
1768 int high = index + length - 1;
1771 // Check for value types which can be sorted without Compare () method
1773 if (comparer == null) {
1774 /* Avoid this when using full-aot to prevent the generation of many unused qsort<K,T> instantiations */
1775 #if FULL_AOT_RUNTIME
1776 #if !BOOTSTRAP_BASIC
1777 switch (Type.GetTypeCode (typeof (TKey))) {
1778 case TypeCode.Int32:
1779 qsort (keys as Int32[], items, low, high);
1781 case TypeCode.Int64:
1782 qsort (keys as Int64[], items, low, high);
1785 qsort (keys as byte[], items, low, high);
1788 qsort (keys as char[], items, low, high);
1790 case TypeCode.DateTime:
1791 qsort (keys as DateTime[], items, low, high);
1793 case TypeCode.Decimal:
1794 qsort (keys as decimal[], items, low, high);
1796 case TypeCode.Double:
1797 qsort (keys as double[], items, low, high);
1799 case TypeCode.Int16:
1800 qsort (keys as Int16[], items, low, high);
1802 case TypeCode.SByte:
1803 qsort (keys as SByte[], items, low, high);
1805 case TypeCode.Single:
1806 qsort (keys as Single[], items, low, high);
1808 case TypeCode.UInt16:
1809 qsort (keys as UInt16[], items, low, high);
1811 case TypeCode.UInt32:
1812 qsort (keys as UInt32[], items, low, high);
1814 case TypeCode.UInt64:
1815 qsort (keys as UInt64[], items, low, high);
1820 // Using Comparer<TKey> adds a small overload, but with value types it
1821 // helps us to not box them.
1822 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1823 typeof (TKey).IsValueType)
1824 comparer = Comparer<TKey>.Default;
1827 if (comparer == null)
1828 CheckComparerAvailable<TKey> (keys, low, high);
1831 qsort (keys, items, low, high, comparer);
1832 //} catch (Exception e) {
1833 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1837 // Specialized version for items==null
1838 private static void SortImpl<TKey> (TKey [] keys, int index, int length, IComparer<TKey> comparer)
1840 if (keys.Length <= 1)
1844 int high = index + length - 1;
1847 // Check for value types which can be sorted without Compare () method
1849 if (comparer == null) {
1850 #if !BOOTSTRAP_BASIC
1851 switch (Type.GetTypeCode (typeof (TKey))) {
1852 case TypeCode.Int32:
1853 qsort (keys as Int32[], low, high);
1855 case TypeCode.Int64:
1856 qsort (keys as Int64[], low, high);
1859 qsort (keys as byte[], low, high);
1862 qsort (keys as char[], low, high);
1864 case TypeCode.DateTime:
1865 qsort (keys as DateTime[], low, high);
1867 case TypeCode.Decimal:
1868 qsort (keys as decimal[], low, high);
1870 case TypeCode.Double:
1871 qsort (keys as double[], low, high);
1873 case TypeCode.Int16:
1874 qsort (keys as Int16[], low, high);
1876 case TypeCode.SByte:
1877 qsort (keys as SByte[], low, high);
1879 case TypeCode.Single:
1880 qsort (keys as Single[], low, high);
1882 case TypeCode.UInt16:
1883 qsort (keys as UInt16[], low, high);
1885 case TypeCode.UInt32:
1886 qsort (keys as UInt32[], low, high);
1888 case TypeCode.UInt64:
1889 qsort (keys as UInt64[], low, high);
1893 // Using Comparer<TKey> adds a small overload, but with value types it
1894 // helps us to not box them.
1895 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1896 typeof (TKey).IsValueType)
1897 comparer = Comparer<TKey>.Default;
1900 if (comparer == null)
1901 CheckComparerAvailable<TKey> (keys, low, high);
1904 qsort<TKey> (keys, low, high, comparer);
1905 //} catch (Exception e) {
1906 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1910 public static void Sort<T> (T [] array, Comparison<T> comparison)
1913 throw new ArgumentNullException ("array");
1915 if (comparison == null)
1916 throw new ArgumentNullException ("comparison");
1918 SortImpl<T> (array, array.Length, comparison);
1921 // used by List<T>.Sort (Comparison <T>)
1922 internal static void SortImpl<T> (T [] array, int length, Comparison<T> comparison)
1929 int high0 = length - 1;
1930 qsort<T> (array, low0, high0, comparison);
1931 } catch (InvalidOperationException) {
1933 } catch (Exception e) {
1934 throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e);
1938 static bool QSortArrange<T, U> (T [] keys, U [] items, int lo, int hi) where T : IComparable<T>
1940 if (keys[lo] != null) {
1941 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1942 swap (keys, items, lo, hi);
1950 // Specialized version for items==null
1951 static bool QSortArrange<T> (T [] keys, int lo, int hi) where T : IComparable<T>
1953 if (keys[lo] != null) {
1954 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1955 swap (keys, lo, hi);
1963 private static void qsort<T, U> (T[] keys, U[] items, int low0, int high0) where T : IComparable<T>
1965 QSortStack[] stack = new QSortStack[32];
1966 const int QSORT_THRESHOLD = 7;
1967 int high, low, mid, i, k;
1971 // initialize our stack
1972 stack[0].high = high0;
1973 stack[0].low = low0;
1978 high = stack[sp].high;
1979 low = stack[sp].low;
1981 if ((low + QSORT_THRESHOLD) > high) {
1982 // switch to insertion sort
1983 for (i = low + 1; i <= high; i++) {
1984 for (k = i; k > low; k--) {
1985 // if keys[k] >= keys[k-1], break
1986 if (keys[k-1] == null)
1989 if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
1992 swap (keys, items, k - 1, k);
1999 // calculate the middle element
2000 mid = low + ((high - low) / 2);
2002 // once we re-order the lo, mid, and hi elements to be in
2003 // ascending order, we'll use mid as our pivot.
2004 QSortArrange<T, U> (keys, items, low, mid);
2005 if (QSortArrange<T, U> (keys, items, mid, high))
2006 QSortArrange<T, U> (keys, items, low, mid);
2010 // since we've already guaranteed that lo <= mid and mid <= hi,
2011 // we can skip comparing them again
2017 // find the first element with a value >= pivot value
2018 while (i < k && key.CompareTo (keys[i]) > 0)
2021 // find the last element with a value <= pivot value
2022 while (k > i && key.CompareTo (keys[k]) < 0)
2025 while (i < k && keys[i] == null)
2028 while (k > i && keys[k] != null)
2035 swap (keys, items, i, k);
2041 // push our partitions onto the stack, largest first
2042 // (to make sure we don't run out of stack space)
2043 if ((high - k) >= (k - low)) {
2044 if ((k + 1) < high) {
2045 stack[sp].high = high;
2050 if ((k - 1) > low) {
2052 stack[sp].low = low;
2056 if ((k - 1) > low) {
2058 stack[sp].low = low;
2062 if ((k + 1) < high) {
2063 stack[sp].high = high;
2071 // Specialized version for items==null
2072 private static void qsort<T> (T[] keys, int low0, int high0) where T : IComparable<T>
2074 QSortStack[] stack = new QSortStack[32];
2075 const int QSORT_THRESHOLD = 7;
2076 int high, low, mid, i, k;
2080 // initialize our stack
2081 stack[0].high = high0;
2082 stack[0].low = low0;
2087 high = stack[sp].high;
2088 low = stack[sp].low;
2090 if ((low + QSORT_THRESHOLD) > high) {
2091 // switch to insertion sort
2092 for (i = low + 1; i <= high; i++) {
2093 for (k = i; k > low; k--) {
2094 // if keys[k] >= keys[k-1], break
2095 if (keys[k-1] == null)
2098 if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
2101 swap (keys, k - 1, k);
2108 // calculate the middle element
2109 mid = low + ((high - low) / 2);
2111 // once we re-order the lo, mid, and hi elements to be in
2112 // ascending order, we'll use mid as our pivot.
2113 QSortArrange<T> (keys, low, mid);
2114 if (QSortArrange<T> (keys, mid, high))
2115 QSortArrange<T> (keys, low, mid);
2119 // since we've already guaranteed that lo <= mid and mid <= hi,
2120 // we can skip comparing them again
2126 // find the first element with a value >= pivot value
2127 while (i < k && key.CompareTo (keys[i]) > 0)
2130 // find the last element with a value <= pivot value
2131 while (k >= i && key.CompareTo (keys[k]) < 0)
2134 while (i < k && keys[i] == null)
2137 while (k >= i && keys[k] != null)
2150 // push our partitions onto the stack, largest first
2151 // (to make sure we don't run out of stack space)
2152 if ((high - k) >= (k - low)) {
2153 if ((k + 1) < high) {
2154 stack[sp].high = high;
2159 if ((k - 1) > low) {
2161 stack[sp].low = low;
2165 if ((k - 1) > low) {
2167 stack[sp].low = low;
2171 if ((k + 1) < high) {
2172 stack[sp].high = high;
2180 static bool QSortArrange<K, V> (K [] keys, V [] items, int lo, int hi, IComparer<K> comparer)
2182 IComparable<K> gcmp;
2185 if (comparer != null) {
2186 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2187 swap<K, V> (keys, items, lo, hi);
2190 } else if (keys[lo] != null) {
2191 if (keys[hi] == null) {
2192 swap<K, V> (keys, items, lo, hi);
2196 gcmp = keys[hi] as IComparable<K>;
2198 if (gcmp.CompareTo (keys[lo]) < 0) {
2199 swap<K, V> (keys, items, lo, hi);
2206 cmp = keys[hi] as IComparable;
2208 if (cmp.CompareTo (keys[lo]) < 0) {
2209 swap<K, V> (keys, items, lo, hi);
2220 // Specialized version for items==null
2221 static bool QSortArrange<K> (K [] keys, int lo, int hi, IComparer<K> comparer)
2223 IComparable<K> gcmp;
2226 if (comparer != null) {
2227 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2228 swap<K> (keys, lo, hi);
2231 } else if (keys[lo] != null) {
2232 if (keys[hi] == null) {
2233 swap<K> (keys, lo, hi);
2237 gcmp = keys[hi] as IComparable<K>;
2239 if (gcmp.CompareTo (keys[lo]) < 0) {
2240 swap<K> (keys, lo, hi);
2247 cmp = keys[hi] as IComparable;
2249 if (cmp.CompareTo (keys[lo]) < 0) {
2250 swap<K> (keys, lo, hi);
2261 private static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
2263 QSortStack[] stack = new QSortStack[32];
2264 const int QSORT_THRESHOLD = 7;
2265 int high, low, mid, i, k;
2266 IComparable<K> gcmp;
2271 // initialize our stack
2272 stack[0].high = high0;
2273 stack[0].low = low0;
2278 high = stack[sp].high;
2279 low = stack[sp].low;
2281 if ((low + QSORT_THRESHOLD) > high) {
2282 // switch to insertion sort
2283 for (i = low + 1; i <= high; i++) {
2284 for (k = i; k > low; k--) {
2285 // if keys[k] >= keys[k-1], break
2286 if (comparer != null) {
2287 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2290 if (keys[k-1] == null)
2293 if (keys[k] != null) {
2294 gcmp = keys[k] as IComparable<K>;
2295 cmp = keys[k] as IComparable;
2297 if (gcmp.CompareTo (keys[k-1]) >= 0)
2300 if (cmp.CompareTo (keys[k-1]) >= 0)
2306 swap<K, V> (keys, items, k - 1, k);
2313 // calculate the middle element
2314 mid = low + ((high - low) / 2);
2316 // once we re-order the low, mid, and high elements to be in
2317 // ascending order, we'll use mid as our pivot.
2318 QSortArrange<K, V> (keys, items, low, mid, comparer);
2319 if (QSortArrange<K, V> (keys, items, mid, high, comparer))
2320 QSortArrange<K, V> (keys, items, low, mid, comparer);
2323 gcmp = key as IComparable<K>;
2324 cmp = key as IComparable;
2326 // since we've already guaranteed that lo <= mid and mid <= hi,
2327 // we can skip comparing them again.
2332 // Move the walls in
2333 if (comparer != null) {
2334 // find the first element with a value >= pivot value
2335 while (i < k && comparer.Compare (key, keys[i]) > 0)
2338 // find the last element with a value <= pivot value
2339 while (k > i && comparer.Compare (key, keys[k]) < 0)
2343 // find the first element with a value >= pivot value
2344 while (i < k && gcmp.CompareTo (keys[i]) > 0)
2347 // find the last element with a value <= pivot value
2348 while (k > i && gcmp.CompareTo (keys[k]) < 0)
2350 } else if (cmp != null) {
2351 // find the first element with a value >= pivot value
2352 while (i < k && cmp.CompareTo (keys[i]) > 0)
2355 // find the last element with a value <= pivot value
2356 while (k > i && cmp.CompareTo (keys[k]) < 0)
2359 while (i < k && keys[i] == null)
2362 while (k > i && keys[k] != null)
2370 swap<K, V> (keys, items, i, k);
2376 // push our partitions onto the stack, largest first
2377 // (to make sure we don't run out of stack space)
2378 if ((high - k) >= (k - low)) {
2379 if ((k + 1) < high) {
2380 stack[sp].high = high;
2385 if ((k - 1) > low) {
2387 stack[sp].low = low;
2391 if ((k - 1) > low) {
2393 stack[sp].low = low;
2397 if ((k + 1) < high) {
2398 stack[sp].high = high;
2406 // Specialized version for items==null
2407 private static void qsort<K> (K [] keys, int low0, int high0, IComparer<K> comparer)
2409 QSortStack[] stack = new QSortStack[32];
2410 const int QSORT_THRESHOLD = 7;
2411 int high, low, mid, i, k;
2412 IComparable<K> gcmp;
2417 // initialize our stack
2418 stack[0].high = high0;
2419 stack[0].low = low0;
2424 high = stack[sp].high;
2425 low = stack[sp].low;
2427 if ((low + QSORT_THRESHOLD) > high) {
2428 // switch to insertion sort
2429 for (i = low + 1; i <= high; i++) {
2430 for (k = i; k > low; k--) {
2431 // if keys[k] >= keys[k-1], break
2432 if (comparer != null) {
2433 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2436 if (keys[k-1] == null)
2439 if (keys[k] != null) {
2440 gcmp = keys[k] as IComparable<K>;
2441 cmp = keys[k] as IComparable;
2443 if (gcmp.CompareTo (keys[k-1]) >= 0)
2446 if (cmp.CompareTo (keys[k-1]) >= 0)
2452 swap<K> (keys, k - 1, k);
2459 // calculate the middle element
2460 mid = low + ((high - low) / 2);
2462 // once we re-order the low, mid, and high elements to be in
2463 // ascending order, we'll use mid as our pivot.
2464 QSortArrange<K> (keys, low, mid, comparer);
2465 if (QSortArrange<K> (keys, mid, high, comparer))
2466 QSortArrange<K> (keys, low, mid, comparer);
2469 gcmp = key as IComparable<K>;
2470 cmp = key as IComparable;
2472 // since we've already guaranteed that lo <= mid and mid <= hi,
2473 // we can skip comparing them again.
2478 // Move the walls in
2479 if (comparer != null) {
2480 // find the first element with a value >= pivot value
2481 while (i < k && comparer.Compare (key, keys[i]) > 0)
2484 // find the last element with a value <= pivot value
2485 while (k > i && comparer.Compare (key, keys[k]) < 0)
2489 // find the first element with a value >= pivot value
2490 while (i < k && gcmp.CompareTo (keys[i]) > 0)
2493 // find the last element with a value <= pivot value
2494 while (k > i && gcmp.CompareTo (keys[k]) < 0)
2496 } else if (cmp != null) {
2497 // find the first element with a value >= pivot value
2498 while (i < k && cmp.CompareTo (keys[i]) > 0)
2501 // find the last element with a value <= pivot value
2502 while (k > i && cmp.CompareTo (keys[k]) < 0)
2505 while (i < k && keys[i] == null)
2508 while (k > i && keys[k] != null)
2516 swap<K> (keys, i, k);
2522 // push our partitions onto the stack, largest first
2523 // (to make sure we don't run out of stack space)
2524 if ((high - k) >= (k - low)) {
2525 if ((k + 1) < high) {
2526 stack[sp].high = high;
2531 if ((k - 1) > low) {
2533 stack[sp].low = low;
2537 if ((k - 1) > low) {
2539 stack[sp].low = low;
2543 if ((k + 1) < high) {
2544 stack[sp].high = high;
2552 static bool QSortArrange<T> (T [] array, int lo, int hi, Comparison<T> compare)
2554 if (array[lo] != null) {
2555 if (array[hi] == null || compare (array[hi], array[lo]) < 0) {
2556 swap<T> (array, lo, hi);
2564 private static void qsort<T> (T [] array, int low0, int high0, Comparison<T> compare)
2566 QSortStack[] stack = new QSortStack[32];
2567 const int QSORT_THRESHOLD = 7;
2568 int high, low, mid, i, k;
2572 // initialize our stack
2573 stack[0].high = high0;
2574 stack[0].low = low0;
2579 high = stack[sp].high;
2580 low = stack[sp].low;
2582 if ((low + QSORT_THRESHOLD) > high) {
2583 // switch to insertion sort
2584 for (i = low + 1; i <= high; i++) {
2585 for (k = i; k > low; k--) {
2586 // if keys[k] >= keys[k-1], break
2587 if (array[k-1] == null)
2590 if (array[k] != null && compare (array[k], array[k-1]) >= 0)
2593 swap<T> (array, k - 1, k);
2600 // calculate the middle element
2601 mid = low + ((high - low) / 2);
2603 // once we re-order the lo, mid, and hi elements to be in
2604 // ascending order, we'll use mid as our pivot.
2605 QSortArrange<T> (array, low, mid, compare);
2606 if (QSortArrange<T> (array, mid, high, compare))
2607 QSortArrange<T> (array, low, mid, compare);
2611 // since we've already guaranteed that lo <= mid and mid <= hi,
2612 // we can skip comparing them again
2617 // Move the walls in
2619 // find the first element with a value >= pivot value
2620 while (i < k && compare (key, array[i]) > 0)
2623 // find the last element with a value <= pivot value
2624 while (k > i && compare (key, array[k]) < 0)
2627 while (i < k && array[i] == null)
2630 while (k > i && array[k] != null)
2637 swap<T> (array, i, k);
2643 // push our partitions onto the stack, largest first
2644 // (to make sure we don't run out of stack space)
2645 if ((high - k) >= (k - low)) {
2646 if ((k + 1) < high) {
2647 stack[sp].high = high;
2652 if ((k - 1) > low) {
2654 stack[sp].low = low;
2658 if ((k - 1) > low) {
2660 stack[sp].low = low;
2664 if ((k + 1) < high) {
2665 stack[sp].high = high;
2673 private static void CheckComparerAvailable<K> (K [] keys, int low, int high)
2675 // move null keys to beginning of array,
2676 // ensure that non-null keys implement IComparable
2677 for (int i = low; i < high; i++) {
2680 if (!(key is IComparable<K>) && !(key is IComparable)) {
2681 string msg = Locale.GetText ("No IComparable<T> or IComparable interface found for type '{0}'.");
2682 throw new InvalidOperationException (String.Format (msg, key.GetType ()));
2688 [MethodImpl ((MethodImplOptions)256)]
2689 private static void swap<K, V> (K [] keys, V [] items, int i, int j)
2694 keys [i] = keys [j];
2697 if (items != null) {
2700 items [i] = items [j];
2705 [MethodImpl ((MethodImplOptions)256)]
2706 private static void swap<T> (T [] array, int i, int j)
2709 array [i] = array [j];
2713 public void CopyTo (Array array, int index)
2716 throw new ArgumentNullException ("array");
2718 // The order of these exception checks may look strange,
2719 // but that's how the microsoft runtime does it.
2721 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2722 if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
2723 throw new ArgumentException ("Destination array was not long " +
2724 "enough. Check destIndex and length, and the array's " +
2727 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2729 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2730 "Value has to be >= 0."));
2732 Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
2735 [ComVisible (false)]
2736 public void CopyTo (Array array, long index)
2738 if (index < 0 || index > Int32.MaxValue)
2739 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2740 "Value must be >= 0 and <= Int32.MaxValue."));
2742 CopyTo (array, (int) index);
2745 internal class SimpleEnumerator : IEnumerator, ICloneable
2751 public SimpleEnumerator (Array arrayToEnumerate)
2753 this.enumeratee = arrayToEnumerate;
2754 this.currentpos = -1;
2755 this.length = arrayToEnumerate.Length;
2758 public object Current {
2760 // Exception messages based on MS implementation
2761 if (currentpos < 0 )
2762 throw new InvalidOperationException (Locale.GetText (
2763 "Enumeration has not started."));
2764 if (currentpos >= length)
2765 throw new InvalidOperationException (Locale.GetText (
2766 "Enumeration has already ended"));
2767 // Current should not increase the position. So no ++ over here.
2768 return enumeratee.GetValueImpl (currentpos);
2772 public bool MoveNext()
2774 //The docs say Current should throw an exception if last
2775 //call to MoveNext returned false. This means currentpos
2776 //should be set to length when returning false.
2777 if (currentpos < length)
2779 if(currentpos < length)
2790 public object Clone ()
2792 return MemberwiseClone ();
2796 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2797 public static void Resize<T> (ref T [] array, int newSize)
2800 throw new ArgumentOutOfRangeException ("newSize");
2802 if (array == null) {
2803 array = new T [newSize];
2808 int length = arr.Length;
2809 if (length == newSize)
2812 T [] a = new T [newSize];
2813 int tocopy = Math.Min (newSize, length);
2816 for (int i = 0; i < tocopy; ++i)
2817 UnsafeStore (a, i, UnsafeLoad (arr, i));
2819 FastCopy (arr, 0, a, 0, tocopy);
2824 public static bool TrueForAll <T> (T [] array, Predicate <T> match)
2827 throw new ArgumentNullException ("array");
2829 throw new ArgumentNullException ("match");
2831 foreach (T t in array)
2838 public static void ForEach<T> (T [] array, Action <T> action)
2841 throw new ArgumentNullException ("array");
2843 throw new ArgumentNullException ("action");
2845 foreach (T t in array)
2849 public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
2852 throw new ArgumentNullException ("array");
2853 if (converter == null)
2854 throw new ArgumentNullException ("converter");
2856 TOutput [] output = new TOutput [array.Length];
2857 for (int i = 0; i < array.Length; i ++)
2858 output [i] = converter (array [i]);
2863 public static int FindLastIndex<T> (T [] array, Predicate <T> match)
2866 throw new ArgumentNullException ("array");
2868 return FindLastIndex<T> (array, 0, array.Length, match);
2871 public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
2874 throw new ArgumentNullException ();
2876 return FindLastIndex<T> (array, startIndex, array.Length - startIndex, match);
2879 public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2882 throw new ArgumentNullException ("array");
2884 throw new ArgumentNullException ("match");
2886 if (startIndex > array.Length || startIndex + count > array.Length)
2887 throw new ArgumentOutOfRangeException ();
2889 for (int i = startIndex + count - 1; i >= startIndex; i--)
2890 if (match (array [i]))
2896 public static int FindIndex<T> (T [] array, Predicate<T> match)
2899 throw new ArgumentNullException ("array");
2901 return FindIndex<T> (array, 0, array.Length, match);
2904 public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
2907 throw new ArgumentNullException ("array");
2909 return FindIndex<T> (array, startIndex, array.Length - startIndex, match);
2912 public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2915 throw new ArgumentNullException ("array");
2918 throw new ArgumentNullException ("match");
2920 if (startIndex > array.Length || startIndex + count > array.Length)
2921 throw new ArgumentOutOfRangeException ();
2923 for (int i = startIndex; i < startIndex + count; i ++)
2924 if (match (array [i]))
2930 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2931 public static int BinarySearch<T> (T [] array, T value)
2934 throw new ArgumentNullException ("array");
2936 return BinarySearch<T> (array, 0, array.Length, value, null);
2939 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2940 public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
2943 throw new ArgumentNullException ("array");
2945 return BinarySearch<T> (array, 0, array.Length, value, comparer);
2948 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2949 public static int BinarySearch<T> (T [] array, int index, int length, T value)
2951 return BinarySearch<T> (array, index, length, value, null);
2954 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2955 public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
2958 throw new ArgumentNullException ("array");
2960 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2961 "index is less than the lower bound of array."));
2963 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
2964 "Value has to be >= 0."));
2965 // re-ordered to avoid possible integer overflow
2966 if (index > array.Length - length)
2967 throw new ArgumentException (Locale.GetText (
2968 "index and length do not specify a valid range in array."));
2969 if (comparer == null)
2970 comparer = Comparer <T>.Default;
2973 int iMax = index + length - 1;
2976 while (iMin <= iMax) {
2977 // Be careful with overflows
2978 int iMid = iMin + ((iMax - iMin) / 2);
2979 iCmp = comparer.Compare (array [iMid], value);
2987 iMin = iMid + 1; // compensate for the rounding down
2989 } catch (Exception e) {
2990 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
2996 public static int IndexOf<T> (T [] array, T value)
2999 throw new ArgumentNullException ("array");
3001 return IndexOf<T> (array, value, 0, array.Length);
3004 public static int IndexOf<T> (T [] array, T value, int startIndex)
3007 throw new ArgumentNullException ("array");
3009 return IndexOf<T> (array, value, startIndex, array.Length - startIndex);
3012 public static int IndexOf<T> (T [] array, T value, int startIndex, int count)
3015 throw new ArgumentNullException ("array");
3017 // re-ordered to avoid possible integer overflow
3018 if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
3019 throw new ArgumentOutOfRangeException ();
3021 int max = startIndex + count;
3022 EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
3023 for (int i = startIndex; i < max; i++) {
3024 if (equalityComparer.Equals (array [i], value))
3031 public static int LastIndexOf<T> (T [] array, T value)
3034 throw new ArgumentNullException ("array");
3036 if (array.Length == 0)
3038 return LastIndexOf<T> (array, value, array.Length - 1);
3041 public static int LastIndexOf<T> (T [] array, T value, int startIndex)
3044 throw new ArgumentNullException ("array");
3046 return LastIndexOf<T> (array, value, startIndex, startIndex + 1);
3049 public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
3052 throw new ArgumentNullException ("array");
3054 if (count < 0 || startIndex < array.GetLowerBound (0) ||
3055 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
3056 throw new ArgumentOutOfRangeException ();
3058 EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
3059 for (int i = startIndex; i >= startIndex - count + 1; i--) {
3060 if (equalityComparer.Equals (array [i], value))
3067 public static T [] FindAll<T> (T [] array, Predicate <T> match)
3070 throw new ArgumentNullException ("array");
3073 throw new ArgumentNullException ("match");
3076 T [] d = new T [array.Length];
3077 foreach (T t in array)
3081 Resize <T> (ref d, pos);
3085 public static bool Exists<T> (T [] array, Predicate <T> match)
3088 throw new ArgumentNullException ("array");
3091 throw new ArgumentNullException ("match");
3093 foreach (T t in array)
3099 public static ReadOnlyCollection<T> AsReadOnly<T> (T[] array)
3102 throw new ArgumentNullException ("array");
3104 return new ReadOnlyCollection<T> (array);
3107 public static T Find<T> (T [] array, Predicate<T> match)
3110 throw new ArgumentNullException ("array");
3113 throw new ArgumentNullException ("match");
3115 foreach (T t in array)
3122 public static T FindLast<T> (T [] array, Predicate <T> match)
3125 throw new ArgumentNullException ("array");
3128 throw new ArgumentNullException ("match");
3130 for (int i = array.Length - 1; i >= 0; i--)
3131 if (match (array [i]))
3137 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
3139 // The constrained copy should guarantee that if there is an exception thrown
3140 // during the copy, the destination array remains unchanged.
3141 // This is related to System.Runtime.Reliability.CER
3142 public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
3144 Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length);
3147 internal static T UnsafeLoad<T> (T[] array, int index) {
3148 return array [index];
3151 internal static void UnsafeStore<T> (T[] array, int index, T value) {
3152 array [index] = value;