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)
784 return BinarySearch (array, value, null);
787 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
788 public static int BinarySearch (Array array, object value, IComparer comparer)
791 throw new ArgumentNullException ("array");
794 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
796 if (array.Length == 0)
799 return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer);
802 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
803 public static int BinarySearch (Array array, int index, int length, object value)
805 return BinarySearch (array, index, length, value, null);
808 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
809 public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
812 throw new ArgumentNullException ("array");
815 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
817 if (index < array.GetLowerBound (0))
818 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
819 "index is less than the lower bound of array."));
821 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
822 "Value has to be >= 0."));
823 // re-ordered to avoid possible integer overflow
824 if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
825 throw new ArgumentException (Locale.GetText (
826 "index and length do not specify a valid range in array."));
828 if (array.Length == 0)
831 return DoBinarySearch (array, index, length, value, comparer);
834 static int DoBinarySearch (Array array, int index, int length, object value, IComparer comparer)
836 // cache this in case we need it
837 if (comparer == null)
838 comparer = Comparer.Default;
841 // Comment from Tum (tum@veridicus.com):
842 // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
843 int iMax = index + length - 1;
846 while (iMin <= iMax) {
847 // Be careful with overflow
848 // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
849 int iMid = iMin + ((iMax - iMin) / 2);
850 object elt = array.GetValueImpl (iMid);
852 iCmp = comparer.Compare (elt, value);
859 iMin = iMid + 1; // compensate for the rounding down
862 catch (Exception e) {
863 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
869 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
870 public static void Clear (Array array, int index, int length)
873 throw new ArgumentNullException ("array");
875 throw new IndexOutOfRangeException ("length < 0");
877 int low = array.GetLowerBound (0);
879 throw new IndexOutOfRangeException ("index < lower bound");
882 // re-ordered to avoid possible integer overflow
883 if (index > array.Length - length)
884 throw new IndexOutOfRangeException ("index + length > size");
886 ClearInternal (array, index, length);
889 [MethodImplAttribute (MethodImplOptions.InternalCall)]
890 static extern void ClearInternal (Array a, int index, int count);
892 [MethodImplAttribute (MethodImplOptions.InternalCall)]
893 public extern object Clone ();
895 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
896 public static void Copy (Array sourceArray, Array destinationArray, int length)
898 // need these checks here because we are going to use
899 // GetLowerBound() on source and dest.
900 if (sourceArray == null)
901 throw new ArgumentNullException ("sourceArray");
903 if (destinationArray == null)
904 throw new ArgumentNullException ("destinationArray");
906 Copy (sourceArray, sourceArray.GetLowerBound (0), destinationArray,
907 destinationArray.GetLowerBound (0), length);
910 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
911 public static void Copy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
913 if (sourceArray == null)
914 throw new ArgumentNullException ("sourceArray");
916 if (destinationArray == null)
917 throw new ArgumentNullException ("destinationArray");
920 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
921 "Value has to be >= 0."));;
924 throw new ArgumentOutOfRangeException ("sourceIndex", Locale.GetText (
925 "Value has to be >= 0."));;
927 if (destinationIndex < 0)
928 throw new ArgumentOutOfRangeException ("destinationIndex", Locale.GetText (
929 "Value has to be >= 0."));;
931 if (FastCopy (sourceArray, sourceIndex, destinationArray, destinationIndex, length))
934 int source_pos = sourceIndex - sourceArray.GetLowerBound (0);
935 int dest_pos = destinationIndex - destinationArray.GetLowerBound (0);
937 // re-ordered to avoid possible integer overflow
938 if (source_pos > sourceArray.Length - length)
939 throw new ArgumentException ("length");
941 if (dest_pos > destinationArray.Length - length) {
942 string msg = "Destination array was not long enough. Check " +
943 "destIndex and length, and the array's lower bounds";
944 throw new ArgumentException (msg, string.Empty);
947 if (sourceArray.Rank != destinationArray.Rank)
948 throw new RankException (Locale.GetText ("Arrays must be of same size."));
950 Type src_type = sourceArray.GetType ().GetElementType ();
951 Type dst_type = destinationArray.GetType ().GetElementType ();
953 if (!Object.ReferenceEquals (sourceArray, destinationArray) || source_pos > dest_pos) {
954 for (int i = 0; i < length; i++) {
955 Object srcval = sourceArray.GetValueImpl (source_pos + i);
958 destinationArray.SetValueImpl (srcval, dest_pos + i);
959 } catch (ArgumentException) {
960 throw CreateArrayTypeMismatchException ();
962 if (CanAssignArrayElement (src_type, dst_type))
965 throw CreateArrayTypeMismatchException ();
970 for (int i = length - 1; i >= 0; i--) {
971 Object srcval = sourceArray.GetValueImpl (source_pos + i);
974 destinationArray.SetValueImpl (srcval, dest_pos + i);
975 } catch (ArgumentException) {
976 throw CreateArrayTypeMismatchException ();
978 if (CanAssignArrayElement (src_type, dst_type))
981 throw CreateArrayTypeMismatchException ();
987 static Exception CreateArrayTypeMismatchException ()
989 return new ArrayTypeMismatchException ();
992 static bool CanAssignArrayElement (Type source, Type target)
994 if (source.IsValueType)
995 return source.IsAssignableFrom (target);
997 if (source.IsInterface)
998 return !target.IsValueType;
1000 if (target.IsInterface)
1001 return !source.IsValueType;
1003 return source.IsAssignableFrom (target) || target.IsAssignableFrom (source);
1006 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1007 public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray,
1008 long destinationIndex, long length)
1010 if (sourceArray == null)
1011 throw new ArgumentNullException ("sourceArray");
1013 if (destinationArray == null)
1014 throw new ArgumentNullException ("destinationArray");
1016 if (sourceIndex < Int32.MinValue || sourceIndex > Int32.MaxValue)
1017 throw new ArgumentOutOfRangeException ("sourceIndex",
1018 Locale.GetText ("Must be in the Int32 range."));
1020 if (destinationIndex < Int32.MinValue || destinationIndex > Int32.MaxValue)
1021 throw new ArgumentOutOfRangeException ("destinationIndex",
1022 Locale.GetText ("Must be in the Int32 range."));
1024 if (length < 0 || length > Int32.MaxValue)
1025 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1026 "Value must be >= 0 and <= Int32.MaxValue."));
1028 Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
1031 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1032 public static void Copy (Array sourceArray, Array destinationArray, long length)
1034 if (length < 0 || length > Int32.MaxValue)
1035 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1036 "Value must be >= 0 and <= Int32.MaxValue."));
1038 Copy (sourceArray, destinationArray, (int) length);
1041 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1042 public static int IndexOf (Array array, object value)
1045 throw new ArgumentNullException ("array");
1047 return IndexOf (array, value, 0, array.Length);
1050 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1051 public static int IndexOf (Array array, object value, int startIndex)
1054 throw new ArgumentNullException ("array");
1056 return IndexOf (array, value, startIndex, array.Length - startIndex);
1059 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1060 public static int IndexOf (Array array, object value, int startIndex, int count)
1063 throw new ArgumentNullException ("array");
1066 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1068 // re-ordered to avoid possible integer overflow
1069 if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
1070 throw new ArgumentOutOfRangeException ();
1072 int max = startIndex + count;
1073 for (int i = startIndex; i < max; i++) {
1074 if (Object.Equals (array.GetValueImpl (i), value))
1078 return array.GetLowerBound (0) - 1;
1081 public void Initialize()
1083 //FIXME: We would like to find a compiler that uses
1084 // this method. It looks like this method do nothing
1085 // in C# so no exception is trown by the moment.
1088 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1089 public static int LastIndexOf (Array array, object value)
1092 throw new ArgumentNullException ("array");
1094 if (array.Length == 0)
1095 return array.GetLowerBound (0) - 1;
1096 return LastIndexOf (array, value, array.Length - 1);
1099 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1100 public static int LastIndexOf (Array array, object value, int startIndex)
1103 throw new ArgumentNullException ("array");
1105 return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1);
1108 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1109 public static int LastIndexOf (Array array, object value, int startIndex, int count)
1112 throw new ArgumentNullException ("array");
1115 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1117 int lb = array.GetLowerBound (0);
1118 // Empty arrays do not throw ArgumentOutOfRangeException
1119 if (array.Length == 0)
1122 if (count < 0 || startIndex < lb ||
1123 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < lb)
1124 throw new ArgumentOutOfRangeException ();
1126 for (int i = startIndex; i >= startIndex - count + 1; i--) {
1127 if (Object.Equals (array.GetValueImpl (i), value))
1134 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1135 public static void Reverse (Array array)
1138 throw new ArgumentNullException ("array");
1140 Reverse (array, array.GetLowerBound (0), array.Length);
1143 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1144 public static void Reverse (Array array, int index, int length)
1147 throw new ArgumentNullException ("array");
1150 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1152 if (index < array.GetLowerBound (0) || length < 0)
1153 throw new ArgumentOutOfRangeException ();
1155 // re-ordered to avoid possible integer overflow
1156 if (index > array.GetUpperBound (0) + 1 - length)
1157 throw new ArgumentException ();
1159 int end = index + length - 1;
1160 var et = array.GetType ().GetElementType ();
1161 switch (Type.GetTypeCode (et)) {
1162 case TypeCode.Boolean:
1163 while (index < end) {
1166 array.GetGenericValueImpl (index, out a);
1167 array.GetGenericValueImpl (end, out b);
1168 array.SetGenericValueImpl (index, ref b);
1169 array.SetGenericValueImpl (end, ref a);
1176 case TypeCode.SByte:
1177 while (index < end) {
1180 array.GetGenericValueImpl (index, out a);
1181 array.GetGenericValueImpl (end, out b);
1182 array.SetGenericValueImpl (index, ref b);
1183 array.SetGenericValueImpl (end, ref a);
1189 case TypeCode.Int16:
1190 case TypeCode.UInt16:
1192 while (index < end) {
1195 array.GetGenericValueImpl (index, out a);
1196 array.GetGenericValueImpl (end, out b);
1197 array.SetGenericValueImpl (index, ref b);
1198 array.SetGenericValueImpl (end, ref a);
1204 case TypeCode.Int32:
1205 case TypeCode.UInt32:
1206 case TypeCode.Single:
1207 while (index < end) {
1210 array.GetGenericValueImpl (index, out a);
1211 array.GetGenericValueImpl (end, out b);
1212 array.SetGenericValueImpl (index, ref b);
1213 array.SetGenericValueImpl (end, ref a);
1219 case TypeCode.Int64:
1220 case TypeCode.UInt64:
1221 case TypeCode.Double:
1222 while (index < end) {
1225 array.GetGenericValueImpl (index, out a);
1226 array.GetGenericValueImpl (end, out b);
1227 array.SetGenericValueImpl (index, ref b);
1228 array.SetGenericValueImpl (end, ref a);
1234 case TypeCode.Decimal:
1235 while (index < end) {
1238 array.GetGenericValueImpl (index, out a);
1239 array.GetGenericValueImpl (end, out b);
1240 array.SetGenericValueImpl (index, ref b);
1241 array.SetGenericValueImpl (end, ref a);
1247 case TypeCode.String:
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 if (array is object[])
1261 goto case TypeCode.String;
1263 // Very slow fallback
1264 while (index < end) {
1265 object val = array.GetValueImpl (index);
1266 array.SetValueImpl (array.GetValueImpl (end), index);
1267 array.SetValueImpl (val, end);
1276 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1277 public static void Sort (Array array)
1279 Sort (array, (IComparer)null);
1282 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1283 public static void Sort (Array keys, Array items)
1285 Sort (keys, items, (IComparer)null);
1288 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1289 public static void Sort (Array array, IComparer comparer)
1292 throw new ArgumentNullException ("array");
1295 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1297 SortImpl (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
1300 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1301 public static void Sort (Array array, int index, int length)
1303 Sort (array, index, length, (IComparer)null);
1306 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1307 public static void Sort (Array keys, Array items, IComparer comparer)
1309 if (items == null) {
1310 Sort (keys, comparer);
1315 throw new ArgumentNullException ("keys");
1317 if (keys.Rank > 1 || items.Rank > 1)
1318 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1320 SortImpl (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
1323 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1324 public static void Sort (Array keys, Array items, int index, int length)
1326 Sort (keys, items, index, length, (IComparer)null);
1329 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1330 public static void Sort (Array array, int index, int length, IComparer comparer)
1333 throw new ArgumentNullException ("array");
1336 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1338 if (index < array.GetLowerBound (0))
1339 throw new ArgumentOutOfRangeException ("index");
1342 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1343 "Value has to be >= 0."));
1345 if (array.Length - (array.GetLowerBound (0) + index) < length)
1346 throw new ArgumentException ();
1348 SortImpl (array, null, index, length, comparer);
1351 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1352 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
1354 if (items == null) {
1355 Sort (keys, index, length, comparer);
1360 throw new ArgumentNullException ("keys");
1362 if (keys.Rank > 1 || items.Rank > 1)
1363 throw new RankException ();
1365 if (keys.GetLowerBound (0) != items.GetLowerBound (0))
1366 throw new ArgumentException ();
1368 if (index < keys.GetLowerBound (0))
1369 throw new ArgumentOutOfRangeException ("index");
1372 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1373 "Value has to be >= 0."));
1375 if (items.Length - (index + items.GetLowerBound (0)) < length || keys.Length - (index + keys.GetLowerBound (0)) < length)
1376 throw new ArgumentException ();
1378 SortImpl (keys, items, index, length, comparer);
1381 private static void SortImpl (Array keys, Array items, int index, int length, IComparer comparer)
1387 int high = index + length - 1;
1389 #if !BOOTSTRAP_BASIC
1390 if (comparer == null && items is object[]) {
1391 /* Its better to compare typecodes as casts treat long/ulong/long based enums the same */
1392 switch (Type.GetTypeCode (keys.GetType ().GetElementType ())) {
1393 case TypeCode.Int32:
1394 qsort (keys as Int32[], items as object[], low, high);
1396 case TypeCode.Int64:
1397 qsort (keys as Int64[], items as object[], low, high);
1400 qsort (keys as byte[], items as object[], low, high);
1403 qsort (keys as char[], items as object[], low, high);
1405 case TypeCode.DateTime:
1406 qsort (keys as DateTime[], items as object[], low, high);
1408 case TypeCode.Decimal:
1409 qsort (keys as decimal[], items as object[], low, high);
1411 case TypeCode.Double:
1412 qsort (keys as double[], items as object[], low, high);
1414 case TypeCode.Int16:
1415 qsort (keys as Int16[], items as object[], low, high);
1417 case TypeCode.SByte:
1418 qsort (keys as SByte[], items as object[], low, high);
1420 case TypeCode.Single:
1421 qsort (keys as Single[], items as object[], low, high);
1423 case TypeCode.UInt16:
1424 qsort (keys as UInt16[], items as object[], low, high);
1426 case TypeCode.UInt32:
1427 qsort (keys as UInt32[], items as object[], low, high);
1429 case TypeCode.UInt64:
1430 qsort (keys as UInt64[], items as object[], low, high);
1438 if (comparer == null)
1439 CheckComparerAvailable (keys, low, high);
1442 qsort (keys, items, low, high, comparer);
1443 } catch (Exception e) {
1444 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1453 static bool QSortArrange (Array keys, Array items, int lo, ref object v0, int hi, ref object v1, IComparer comparer)
1458 if (comparer != null) {
1459 if (comparer.Compare (v1, v0) < 0) {
1460 swap (keys, items, lo, hi);
1467 } else if (v0 != null) {
1468 cmp = v1 as IComparable;
1470 if (v1 == null || cmp.CompareTo (v0) < 0) {
1471 swap (keys, items, lo, hi);
1483 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
1485 QSortStack[] stack = new QSortStack[32];
1486 const int QSORT_THRESHOLD = 7;
1487 int high, low, mid, i, k;
1492 // initialize our stack
1493 stack[0].high = high0;
1494 stack[0].low = low0;
1499 high = stack[sp].high;
1500 low = stack[sp].low;
1502 if ((low + QSORT_THRESHOLD) > high) {
1503 // switch to insertion sort
1504 for (i = low + 1; i <= high; i++) {
1505 for (k = i; k > low; k--) {
1506 lo = keys.GetValueImpl (k - 1);
1507 hi = keys.GetValueImpl (k);
1508 if (comparer != null) {
1509 if (comparer.Compare (hi, lo) >= 0)
1516 cmp = hi as IComparable;
1517 if (cmp.CompareTo (lo) >= 0)
1522 swap (keys, items, k - 1, k);
1529 // calculate the middle element
1530 mid = low + ((high - low) / 2);
1533 key = keys.GetValueImpl (mid);
1534 hi = keys.GetValueImpl (high);
1535 lo = keys.GetValueImpl (low);
1537 // once we re-order the low, mid, and high elements to be in
1538 // ascending order, we'll use mid as our pivot.
1539 QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1540 if (QSortArrange (keys, items, mid, ref key, high, ref hi, comparer))
1541 QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1543 cmp = key as IComparable;
1545 // since we've already guaranteed that lo <= mid and mid <= hi,
1546 // we can skip comparing them again.
1551 // Move the walls in
1552 if (comparer != null) {
1553 // find the first element with a value >= pivot value
1554 while (i < k && comparer.Compare (key, keys.GetValueImpl (i)) > 0)
1557 // find the last element with a value <= pivot value
1558 while (k > i && comparer.Compare (key, keys.GetValueImpl (k)) < 0)
1560 } else if (cmp != null) {
1561 // find the first element with a value >= pivot value
1562 while (i < k && cmp.CompareTo (keys.GetValueImpl (i)) > 0)
1565 // find the last element with a value <= pivot value
1566 while (k > i && cmp.CompareTo (keys.GetValueImpl (k)) < 0)
1569 // This has the effect of moving the null values to the front if comparer is null
1570 while (i < k && keys.GetValueImpl (i) == null)
1573 while (k > i && keys.GetValueImpl (k) != null)
1580 swap (keys, items, i, k);
1586 // push our partitions onto the stack, largest first
1587 // (to make sure we don't run out of stack space)
1588 if ((high - k) >= (k - low)) {
1589 if ((k + 1) < high) {
1590 stack[sp].high = high;
1595 if ((k - 1) > low) {
1597 stack[sp].low = low;
1601 if ((k - 1) > low) {
1603 stack[sp].low = low;
1607 if ((k + 1) < high) {
1608 stack[sp].high = high;
1616 private static void CheckComparerAvailable (Array keys, int low, int high)
1618 // move null keys to beginning of array,
1619 // ensure that non-null keys implement IComparable
1620 for (int i = 0; i < high; i++) {
1621 object obj = keys.GetValueImpl (i);
1624 if (!(obj is IComparable)) {
1625 string msg = Locale.GetText ("No IComparable interface found for type '{0}'.");
1626 throw new InvalidOperationException (String.Format (msg, obj.GetType ()));
1631 private static void swap (Array keys, Array items, int i, int j)
1633 object tmp = keys.GetValueImpl (i);
1634 keys.SetValueImpl (keys.GetValueImpl (j), i);
1635 keys.SetValueImpl (tmp, j);
1637 if (items != null) {
1638 tmp = items.GetValueImpl (i);
1639 items.SetValueImpl (items.GetValueImpl (j), i);
1640 items.SetValueImpl (tmp, j);
1644 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1645 public static void Sort<T> (T [] array)
1647 Sort<T> (array, (IComparer<T>)null);
1650 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1651 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items)
1653 Sort<TKey, TValue> (keys, items, (IComparer<TKey>)null);
1656 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1657 public static void Sort<T> (T [] array, IComparer<T> comparer)
1660 throw new ArgumentNullException ("array");
1662 SortImpl<T> (array, 0, array.Length, comparer);
1665 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1666 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, IComparer<TKey> comparer)
1668 if (items == null) {
1669 Sort<TKey> (keys, comparer);
1674 throw new ArgumentNullException ("keys");
1676 if (keys.Length != items.Length)
1677 throw new ArgumentException ("Length of keys and items does not match.");
1679 SortImpl<TKey, TValue> (keys, items, 0, keys.Length, comparer);
1682 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1683 public static void Sort<T> (T [] array, int index, int length)
1685 Sort<T> (array, index, length, (IComparer<T>)null);
1688 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1689 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length)
1691 Sort<TKey, TValue> (keys, items, index, length, (IComparer<TKey>)null);
1694 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1695 public static void Sort<T> (T [] array, int index, int length, IComparer<T> comparer)
1698 throw new ArgumentNullException ("array");
1701 throw new ArgumentOutOfRangeException ("index");
1704 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1705 "Value has to be >= 0."));
1707 if (index + length > array.Length)
1708 throw new ArgumentException ();
1710 SortImpl<T> (array, index, length, comparer);
1713 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1714 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1716 if (items == null) {
1717 Sort<TKey> (keys, index, length, comparer);
1722 throw new ArgumentNullException ("keys");
1725 throw new ArgumentOutOfRangeException ("index");
1728 throw new ArgumentOutOfRangeException ("length");
1730 if (items.Length - index < length || keys.Length - index < length)
1731 throw new ArgumentException ();
1733 SortImpl<TKey, TValue> (keys, items, index, length, comparer);
1736 private static void SortImpl<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1738 if (keys.Length <= 1)
1742 int high = index + length - 1;
1745 // Check for value types which can be sorted without Compare () method
1747 if (comparer == null) {
1748 /* Avoid this when using full-aot to prevent the generation of many unused qsort<K,T> instantiations */
1749 #if !FULL_AOT_RUNTIME
1750 #if !BOOTSTRAP_BASIC
1751 switch (Type.GetTypeCode (typeof (TKey))) {
1752 case TypeCode.Int32:
1753 qsort (keys as Int32[], items, low, high);
1755 case TypeCode.Int64:
1756 qsort (keys as Int64[], items, low, high);
1759 qsort (keys as byte[], items, low, high);
1762 qsort (keys as char[], items, low, high);
1764 case TypeCode.DateTime:
1765 qsort (keys as DateTime[], items, low, high);
1767 case TypeCode.Decimal:
1768 qsort (keys as decimal[], items, low, high);
1770 case TypeCode.Double:
1771 qsort (keys as double[], items, low, high);
1773 case TypeCode.Int16:
1774 qsort (keys as Int16[], items, low, high);
1776 case TypeCode.SByte:
1777 qsort (keys as SByte[], items, low, high);
1779 case TypeCode.Single:
1780 qsort (keys as Single[], items, low, high);
1782 case TypeCode.UInt16:
1783 qsort (keys as UInt16[], items, low, high);
1785 case TypeCode.UInt32:
1786 qsort (keys as UInt32[], items, low, high);
1788 case TypeCode.UInt64:
1789 qsort (keys as UInt64[], items, low, high);
1794 // Using Comparer<TKey> adds a small overload, but with value types it
1795 // helps us to not box them.
1796 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1797 typeof (TKey).IsValueType)
1798 comparer = Comparer<TKey>.Default;
1801 if (comparer == null)
1802 CheckComparerAvailable<TKey> (keys, low, high);
1805 qsort (keys, items, low, high, comparer);
1806 //} catch (Exception e) {
1807 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1811 // Specialized version for items==null
1812 private static void SortImpl<TKey> (TKey [] keys, int index, int length, IComparer<TKey> comparer)
1814 if (keys.Length <= 1)
1818 int high = index + length - 1;
1821 // Check for value types which can be sorted without Compare () method
1823 if (comparer == null) {
1824 #if !BOOTSTRAP_BASIC
1825 switch (Type.GetTypeCode (typeof (TKey))) {
1826 case TypeCode.Int32:
1827 qsort (keys as Int32[], low, high);
1829 case TypeCode.Int64:
1830 qsort (keys as Int64[], low, high);
1833 qsort (keys as byte[], low, high);
1836 qsort (keys as char[], low, high);
1838 case TypeCode.DateTime:
1839 qsort (keys as DateTime[], low, high);
1841 case TypeCode.Decimal:
1842 qsort (keys as decimal[], low, high);
1844 case TypeCode.Double:
1845 qsort (keys as double[], low, high);
1847 case TypeCode.Int16:
1848 qsort (keys as Int16[], low, high);
1850 case TypeCode.SByte:
1851 qsort (keys as SByte[], low, high);
1853 case TypeCode.Single:
1854 qsort (keys as Single[], low, high);
1856 case TypeCode.UInt16:
1857 qsort (keys as UInt16[], low, high);
1859 case TypeCode.UInt32:
1860 qsort (keys as UInt32[], low, high);
1862 case TypeCode.UInt64:
1863 qsort (keys as UInt64[], low, high);
1867 // Using Comparer<TKey> adds a small overload, but with value types it
1868 // helps us to not box them.
1869 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1870 typeof (TKey).IsValueType)
1871 comparer = Comparer<TKey>.Default;
1874 if (comparer == null)
1875 CheckComparerAvailable<TKey> (keys, low, high);
1878 qsort<TKey> (keys, low, high, comparer);
1879 //} catch (Exception e) {
1880 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1884 public static void Sort<T> (T [] array, Comparison<T> comparison)
1887 throw new ArgumentNullException ("array");
1889 if (comparison == null)
1890 throw new ArgumentNullException ("comparison");
1892 SortImpl<T> (array, array.Length, comparison);
1895 // used by List<T>.Sort (Comparison <T>)
1896 internal static void SortImpl<T> (T [] array, int length, Comparison<T> comparison)
1903 int high0 = length - 1;
1904 qsort<T> (array, low0, high0, comparison);
1905 } catch (InvalidOperationException) {
1907 } catch (Exception e) {
1908 throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e);
1912 static bool QSortArrange<T, U> (T [] keys, U [] items, int lo, int hi) where T : IComparable<T>
1914 if (keys[lo] != null) {
1915 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1916 swap (keys, items, lo, hi);
1924 // Specialized version for items==null
1925 static bool QSortArrange<T> (T [] keys, int lo, int hi) where T : IComparable<T>
1927 if (keys[lo] != null) {
1928 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1929 swap (keys, lo, hi);
1937 private static void qsort<T, U> (T[] keys, U[] items, int low0, int high0) where T : IComparable<T>
1939 QSortStack[] stack = new QSortStack[32];
1940 const int QSORT_THRESHOLD = 7;
1941 int high, low, mid, i, k;
1945 // initialize our stack
1946 stack[0].high = high0;
1947 stack[0].low = low0;
1952 high = stack[sp].high;
1953 low = stack[sp].low;
1955 if ((low + QSORT_THRESHOLD) > high) {
1956 // switch to insertion sort
1957 for (i = low + 1; i <= high; i++) {
1958 for (k = i; k > low; k--) {
1959 // if keys[k] >= keys[k-1], break
1960 if (keys[k-1] == null)
1963 if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
1966 swap (keys, items, k - 1, k);
1973 // calculate the middle element
1974 mid = low + ((high - low) / 2);
1976 // once we re-order the lo, mid, and hi elements to be in
1977 // ascending order, we'll use mid as our pivot.
1978 QSortArrange<T, U> (keys, items, low, mid);
1979 if (QSortArrange<T, U> (keys, items, mid, high))
1980 QSortArrange<T, U> (keys, items, low, mid);
1984 // since we've already guaranteed that lo <= mid and mid <= hi,
1985 // we can skip comparing them again
1991 // find the first element with a value >= pivot value
1992 while (i < k && key.CompareTo (keys[i]) > 0)
1995 // find the last element with a value <= pivot value
1996 while (k > i && key.CompareTo (keys[k]) < 0)
1999 while (i < k && keys[i] == null)
2002 while (k > i && keys[k] != null)
2009 swap (keys, items, i, k);
2015 // push our partitions onto the stack, largest first
2016 // (to make sure we don't run out of stack space)
2017 if ((high - k) >= (k - low)) {
2018 if ((k + 1) < high) {
2019 stack[sp].high = high;
2024 if ((k - 1) > low) {
2026 stack[sp].low = low;
2030 if ((k - 1) > low) {
2032 stack[sp].low = low;
2036 if ((k + 1) < high) {
2037 stack[sp].high = high;
2045 // Specialized version for items==null
2046 private static void qsort<T> (T[] keys, int low0, int high0) where T : IComparable<T>
2048 QSortStack[] stack = new QSortStack[32];
2049 const int QSORT_THRESHOLD = 7;
2050 int high, low, mid, i, k;
2054 // initialize our stack
2055 stack[0].high = high0;
2056 stack[0].low = low0;
2061 high = stack[sp].high;
2062 low = stack[sp].low;
2064 if ((low + QSORT_THRESHOLD) > high) {
2065 // switch to insertion sort
2066 for (i = low + 1; i <= high; i++) {
2067 for (k = i; k > low; k--) {
2068 // if keys[k] >= keys[k-1], break
2069 if (keys[k-1] == null)
2072 if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
2075 swap (keys, k - 1, k);
2082 // calculate the middle element
2083 mid = low + ((high - low) / 2);
2085 // once we re-order the lo, mid, and hi elements to be in
2086 // ascending order, we'll use mid as our pivot.
2087 QSortArrange<T> (keys, low, mid);
2088 if (QSortArrange<T> (keys, mid, high))
2089 QSortArrange<T> (keys, low, mid);
2093 // since we've already guaranteed that lo <= mid and mid <= hi,
2094 // we can skip comparing them again
2100 // find the first element with a value >= pivot value
2101 while (i < k && key.CompareTo (keys[i]) > 0)
2104 // find the last element with a value <= pivot value
2105 while (k >= i && key.CompareTo (keys[k]) < 0)
2108 while (i < k && keys[i] == null)
2111 while (k >= i && keys[k] != null)
2124 // push our partitions onto the stack, largest first
2125 // (to make sure we don't run out of stack space)
2126 if ((high - k) >= (k - low)) {
2127 if ((k + 1) < high) {
2128 stack[sp].high = high;
2133 if ((k - 1) > low) {
2135 stack[sp].low = low;
2139 if ((k - 1) > low) {
2141 stack[sp].low = low;
2145 if ((k + 1) < high) {
2146 stack[sp].high = high;
2154 static bool QSortArrange<K, V> (K [] keys, V [] items, int lo, int hi, IComparer<K> comparer)
2156 IComparable<K> gcmp;
2159 if (comparer != null) {
2160 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2161 swap<K, V> (keys, items, lo, hi);
2164 } else if (keys[lo] != null) {
2165 if (keys[hi] == null) {
2166 swap<K, V> (keys, items, lo, hi);
2170 gcmp = keys[hi] as IComparable<K>;
2172 if (gcmp.CompareTo (keys[lo]) < 0) {
2173 swap<K, V> (keys, items, lo, hi);
2180 cmp = keys[hi] as IComparable;
2182 if (cmp.CompareTo (keys[lo]) < 0) {
2183 swap<K, V> (keys, items, lo, hi);
2194 // Specialized version for items==null
2195 static bool QSortArrange<K> (K [] keys, int lo, int hi, IComparer<K> comparer)
2197 IComparable<K> gcmp;
2200 if (comparer != null) {
2201 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2202 swap<K> (keys, lo, hi);
2205 } else if (keys[lo] != null) {
2206 if (keys[hi] == null) {
2207 swap<K> (keys, lo, hi);
2211 gcmp = keys[hi] as IComparable<K>;
2213 if (gcmp.CompareTo (keys[lo]) < 0) {
2214 swap<K> (keys, lo, hi);
2221 cmp = keys[hi] as IComparable;
2223 if (cmp.CompareTo (keys[lo]) < 0) {
2224 swap<K> (keys, lo, hi);
2235 private static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
2237 QSortStack[] stack = new QSortStack[32];
2238 const int QSORT_THRESHOLD = 7;
2239 int high, low, mid, i, k;
2240 IComparable<K> gcmp;
2245 // initialize our stack
2246 stack[0].high = high0;
2247 stack[0].low = low0;
2252 high = stack[sp].high;
2253 low = stack[sp].low;
2255 if ((low + QSORT_THRESHOLD) > high) {
2256 // switch to insertion sort
2257 for (i = low + 1; i <= high; i++) {
2258 for (k = i; k > low; k--) {
2259 // if keys[k] >= keys[k-1], break
2260 if (comparer != null) {
2261 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2264 if (keys[k-1] == null)
2267 if (keys[k] != null) {
2268 gcmp = keys[k] as IComparable<K>;
2269 cmp = keys[k] as IComparable;
2271 if (gcmp.CompareTo (keys[k-1]) >= 0)
2274 if (cmp.CompareTo (keys[k-1]) >= 0)
2280 swap<K, V> (keys, items, k - 1, k);
2287 // calculate the middle element
2288 mid = low + ((high - low) / 2);
2290 // once we re-order the low, mid, and high elements to be in
2291 // ascending order, we'll use mid as our pivot.
2292 QSortArrange<K, V> (keys, items, low, mid, comparer);
2293 if (QSortArrange<K, V> (keys, items, mid, high, comparer))
2294 QSortArrange<K, V> (keys, items, low, mid, comparer);
2297 gcmp = key as IComparable<K>;
2298 cmp = key as IComparable;
2300 // since we've already guaranteed that lo <= mid and mid <= hi,
2301 // we can skip comparing them again.
2306 // Move the walls in
2307 if (comparer != null) {
2308 // find the first element with a value >= pivot value
2309 while (i < k && comparer.Compare (key, keys[i]) > 0)
2312 // find the last element with a value <= pivot value
2313 while (k > i && comparer.Compare (key, keys[k]) < 0)
2317 // find the first element with a value >= pivot value
2318 while (i < k && gcmp.CompareTo (keys[i]) > 0)
2321 // find the last element with a value <= pivot value
2322 while (k > i && gcmp.CompareTo (keys[k]) < 0)
2324 } else if (cmp != null) {
2325 // find the first element with a value >= pivot value
2326 while (i < k && cmp.CompareTo (keys[i]) > 0)
2329 // find the last element with a value <= pivot value
2330 while (k > i && cmp.CompareTo (keys[k]) < 0)
2333 while (i < k && keys[i] == null)
2336 while (k > i && keys[k] != null)
2344 swap<K, V> (keys, items, i, k);
2350 // push our partitions onto the stack, largest first
2351 // (to make sure we don't run out of stack space)
2352 if ((high - k) >= (k - low)) {
2353 if ((k + 1) < high) {
2354 stack[sp].high = high;
2359 if ((k - 1) > low) {
2361 stack[sp].low = low;
2365 if ((k - 1) > low) {
2367 stack[sp].low = low;
2371 if ((k + 1) < high) {
2372 stack[sp].high = high;
2380 // Specialized version for items==null
2381 private static void qsort<K> (K [] keys, int low0, int high0, IComparer<K> comparer)
2383 QSortStack[] stack = new QSortStack[32];
2384 const int QSORT_THRESHOLD = 7;
2385 int high, low, mid, i, k;
2386 IComparable<K> gcmp;
2391 // initialize our stack
2392 stack[0].high = high0;
2393 stack[0].low = low0;
2398 high = stack[sp].high;
2399 low = stack[sp].low;
2401 if ((low + QSORT_THRESHOLD) > high) {
2402 // switch to insertion sort
2403 for (i = low + 1; i <= high; i++) {
2404 for (k = i; k > low; k--) {
2405 // if keys[k] >= keys[k-1], break
2406 if (comparer != null) {
2407 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2410 if (keys[k-1] == null)
2413 if (keys[k] != null) {
2414 gcmp = keys[k] as IComparable<K>;
2415 cmp = keys[k] as IComparable;
2417 if (gcmp.CompareTo (keys[k-1]) >= 0)
2420 if (cmp.CompareTo (keys[k-1]) >= 0)
2426 swap<K> (keys, k - 1, k);
2433 // calculate the middle element
2434 mid = low + ((high - low) / 2);
2436 // once we re-order the low, mid, and high elements to be in
2437 // ascending order, we'll use mid as our pivot.
2438 QSortArrange<K> (keys, low, mid, comparer);
2439 if (QSortArrange<K> (keys, mid, high, comparer))
2440 QSortArrange<K> (keys, low, mid, comparer);
2443 gcmp = key as IComparable<K>;
2444 cmp = key as IComparable;
2446 // since we've already guaranteed that lo <= mid and mid <= hi,
2447 // we can skip comparing them again.
2452 // Move the walls in
2453 if (comparer != null) {
2454 // find the first element with a value >= pivot value
2455 while (i < k && comparer.Compare (key, keys[i]) > 0)
2458 // find the last element with a value <= pivot value
2459 while (k > i && comparer.Compare (key, keys[k]) < 0)
2463 // find the first element with a value >= pivot value
2464 while (i < k && gcmp.CompareTo (keys[i]) > 0)
2467 // find the last element with a value <= pivot value
2468 while (k > i && gcmp.CompareTo (keys[k]) < 0)
2470 } else if (cmp != null) {
2471 // find the first element with a value >= pivot value
2472 while (i < k && cmp.CompareTo (keys[i]) > 0)
2475 // find the last element with a value <= pivot value
2476 while (k > i && cmp.CompareTo (keys[k]) < 0)
2479 while (i < k && keys[i] == null)
2482 while (k > i && keys[k] != null)
2490 swap<K> (keys, i, k);
2496 // push our partitions onto the stack, largest first
2497 // (to make sure we don't run out of stack space)
2498 if ((high - k) >= (k - low)) {
2499 if ((k + 1) < high) {
2500 stack[sp].high = high;
2505 if ((k - 1) > low) {
2507 stack[sp].low = low;
2511 if ((k - 1) > low) {
2513 stack[sp].low = low;
2517 if ((k + 1) < high) {
2518 stack[sp].high = high;
2526 static bool QSortArrange<T> (T [] array, int lo, int hi, Comparison<T> compare)
2528 if (array[lo] != null) {
2529 if (array[hi] == null || compare (array[hi], array[lo]) < 0) {
2530 swap<T> (array, lo, hi);
2538 private static void qsort<T> (T [] array, int low0, int high0, Comparison<T> compare)
2540 QSortStack[] stack = new QSortStack[32];
2541 const int QSORT_THRESHOLD = 7;
2542 int high, low, mid, i, k;
2546 // initialize our stack
2547 stack[0].high = high0;
2548 stack[0].low = low0;
2553 high = stack[sp].high;
2554 low = stack[sp].low;
2556 if ((low + QSORT_THRESHOLD) > high) {
2557 // switch to insertion sort
2558 for (i = low + 1; i <= high; i++) {
2559 for (k = i; k > low; k--) {
2560 if (compare (array[k], array[k-1]) >= 0)
2563 swap<T> (array, k - 1, k);
2570 // calculate the middle element
2571 mid = low + ((high - low) / 2);
2573 // once we re-order the lo, mid, and hi elements to be in
2574 // ascending order, we'll use mid as our pivot.
2575 QSortArrange<T> (array, low, mid, compare);
2576 if (QSortArrange<T> (array, mid, high, compare))
2577 QSortArrange<T> (array, low, mid, compare);
2581 // since we've already guaranteed that lo <= mid and mid <= hi,
2582 // we can skip comparing them again
2587 // Move the walls in
2589 // find the first element with a value >= pivot value
2590 while (i < k && compare (key, array[i]) > 0)
2593 // find the last element with a value <= pivot value
2594 while (k > i && compare (key, array[k]) < 0)
2597 while (i < k && array[i] == null)
2600 while (k > i && array[k] != null)
2607 swap<T> (array, i, k);
2613 // push our partitions onto the stack, largest first
2614 // (to make sure we don't run out of stack space)
2615 if ((high - k) >= (k - low)) {
2616 if ((k + 1) < high) {
2617 stack[sp].high = high;
2622 if ((k - 1) > low) {
2624 stack[sp].low = low;
2628 if ((k - 1) > low) {
2630 stack[sp].low = low;
2634 if ((k + 1) < high) {
2635 stack[sp].high = high;
2643 private static void CheckComparerAvailable<K> (K [] keys, int low, int high)
2645 // move null keys to beginning of array,
2646 // ensure that non-null keys implement IComparable
2647 for (int i = low; i < high; i++) {
2650 if (!(key is IComparable<K>) && !(key is IComparable)) {
2651 string msg = Locale.GetText ("No IComparable<T> or IComparable interface found for type '{0}'.");
2652 throw new InvalidOperationException (String.Format (msg, key.GetType ()));
2658 [MethodImpl ((MethodImplOptions)256)]
2659 private static void swap<K, V> (K [] keys, V [] items, int i, int j)
2664 keys [i] = keys [j];
2667 if (items != null) {
2670 items [i] = items [j];
2675 [MethodImpl ((MethodImplOptions)256)]
2676 private static void swap<T> (T [] array, int i, int j)
2679 array [i] = array [j];
2683 public void CopyTo (Array array, int index)
2686 throw new ArgumentNullException ("array");
2688 // The order of these exception checks may look strange,
2689 // but that's how the microsoft runtime does it.
2691 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2692 if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
2693 throw new ArgumentException ("Destination array was not long " +
2694 "enough. Check destIndex and length, and the array's " +
2697 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2699 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2700 "Value has to be >= 0."));
2702 Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
2705 [ComVisible (false)]
2706 public void CopyTo (Array array, long index)
2708 if (index < 0 || index > Int32.MaxValue)
2709 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2710 "Value must be >= 0 and <= Int32.MaxValue."));
2712 CopyTo (array, (int) index);
2715 internal class SimpleEnumerator : IEnumerator, ICloneable
2721 public SimpleEnumerator (Array arrayToEnumerate)
2723 this.enumeratee = arrayToEnumerate;
2724 this.currentpos = -1;
2725 this.length = arrayToEnumerate.Length;
2728 public object Current {
2730 // Exception messages based on MS implementation
2731 if (currentpos < 0 )
2732 throw new InvalidOperationException (Locale.GetText (
2733 "Enumeration has not started."));
2734 if (currentpos >= length)
2735 throw new InvalidOperationException (Locale.GetText (
2736 "Enumeration has already ended"));
2737 // Current should not increase the position. So no ++ over here.
2738 return enumeratee.GetValueImpl (currentpos);
2742 public bool MoveNext()
2744 //The docs say Current should throw an exception if last
2745 //call to MoveNext returned false. This means currentpos
2746 //should be set to length when returning false.
2747 if (currentpos < length)
2749 if(currentpos < length)
2760 public object Clone ()
2762 return MemberwiseClone ();
2766 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2767 public static void Resize<T> (ref T [] array, int newSize)
2770 throw new ArgumentOutOfRangeException ("newSize");
2772 if (array == null) {
2773 array = new T [newSize];
2778 int length = arr.Length;
2779 if (length == newSize)
2782 T [] a = new T [newSize];
2783 int tocopy = Math.Min (newSize, length);
2786 for (int i = 0; i < tocopy; ++i)
2787 UnsafeStore (a, i, UnsafeLoad (arr, i));
2789 FastCopy (arr, 0, a, 0, tocopy);
2794 public static bool TrueForAll <T> (T [] array, Predicate <T> match)
2797 throw new ArgumentNullException ("array");
2799 throw new ArgumentNullException ("match");
2801 foreach (T t in array)
2808 public static void ForEach<T> (T [] array, Action <T> action)
2811 throw new ArgumentNullException ("array");
2813 throw new ArgumentNullException ("action");
2815 foreach (T t in array)
2819 public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
2822 throw new ArgumentNullException ("array");
2823 if (converter == null)
2824 throw new ArgumentNullException ("converter");
2826 TOutput [] output = new TOutput [array.Length];
2827 for (int i = 0; i < array.Length; i ++)
2828 output [i] = converter (array [i]);
2833 public static int FindLastIndex<T> (T [] array, Predicate <T> match)
2836 throw new ArgumentNullException ("array");
2839 throw new ArgumentNullException ("match");
2841 return GetLastIndex (array, 0, array.Length, match);
2844 public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
2847 throw new ArgumentNullException ();
2849 if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2850 throw new ArgumentOutOfRangeException ("startIndex");
2853 throw new ArgumentNullException ("match");
2855 return GetLastIndex (array, 0, startIndex + 1, match);
2858 public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2861 throw new ArgumentNullException ("array");
2864 throw new ArgumentNullException ("match");
2866 if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2867 throw new ArgumentOutOfRangeException ("startIndex");
2870 throw new ArgumentOutOfRangeException ("count");
2872 if (startIndex - count + 1 < 0)
2873 throw new ArgumentOutOfRangeException ("count must refer to a location within the array");
2875 return GetLastIndex (array, startIndex - count + 1, count, match);
2878 internal static int GetLastIndex<T> (T[] array, int startIndex, int count, Predicate<T> match)
2880 // unlike FindLastIndex, takes regular params for search range
2881 for (int i = startIndex + count; i != startIndex;)
2882 if (match (array [--i]))
2888 public static int FindIndex<T> (T [] array, Predicate<T> match)
2891 throw new ArgumentNullException ("array");
2894 throw new ArgumentNullException ("match");
2896 return GetIndex (array, 0, array.Length, match);
2899 public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
2902 throw new ArgumentNullException ("array");
2904 if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2905 throw new ArgumentOutOfRangeException ("startIndex");
2908 throw new ArgumentNullException ("match");
2910 return GetIndex (array, startIndex, array.Length - startIndex, match);
2913 public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2916 throw new ArgumentNullException ("array");
2919 throw new ArgumentOutOfRangeException ("startIndex");
2922 throw new ArgumentOutOfRangeException ("count");
2924 if ((uint) startIndex + (uint) count > (uint) array.Length)
2925 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
2927 return GetIndex (array, startIndex, count, match);
2930 internal static int GetIndex<T> (T[] array, int startIndex, int count, Predicate<T> match)
2932 int end = startIndex + count;
2933 for (int i = startIndex; i < end; i ++)
2934 if (match (array [i]))
2940 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2941 public static int BinarySearch<T> (T [] array, T value)
2944 throw new ArgumentNullException ("array");
2946 return BinarySearch<T> (array, 0, array.Length, value, null);
2949 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2950 public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
2953 throw new ArgumentNullException ("array");
2955 return BinarySearch<T> (array, 0, array.Length, value, comparer);
2958 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2959 public static int BinarySearch<T> (T [] array, int index, int length, T value)
2961 return BinarySearch<T> (array, index, length, value, null);
2964 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2965 public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
2968 throw new ArgumentNullException ("array");
2970 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2971 "index is less than the lower bound of array."));
2973 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
2974 "Value has to be >= 0."));
2975 // re-ordered to avoid possible integer overflow
2976 if (index > array.Length - length)
2977 throw new ArgumentException (Locale.GetText (
2978 "index and length do not specify a valid range in array."));
2979 if (comparer == null)
2980 comparer = Comparer <T>.Default;
2983 int iMax = index + length - 1;
2986 while (iMin <= iMax) {
2987 // Be careful with overflows
2988 int iMid = iMin + ((iMax - iMin) / 2);
2989 iCmp = comparer.Compare (array [iMid], value);
2997 iMin = iMid + 1; // compensate for the rounding down
2999 } catch (Exception e) {
3000 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
3006 public static int IndexOf<T> (T [] array, T value)
3009 throw new ArgumentNullException ("array");
3011 return IndexOf<T> (array, value, 0, array.Length);
3014 public static int IndexOf<T> (T [] array, T value, int startIndex)
3017 throw new ArgumentNullException ("array");
3019 return IndexOf<T> (array, value, startIndex, array.Length - startIndex);
3022 public static int IndexOf<T> (T[] array, T value, int startIndex, int count)
3025 throw new ArgumentNullException ("array");
3027 // re-ordered to avoid possible integer overflow
3028 if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
3029 throw new ArgumentOutOfRangeException ();
3031 return EqualityComparer<T>.Default.IndexOf (array, value, startIndex, startIndex + count);
3034 public static int LastIndexOf<T> (T [] array, T value)
3037 throw new ArgumentNullException ("array");
3039 if (array.Length == 0)
3041 return LastIndexOf<T> (array, value, array.Length - 1);
3044 public static int LastIndexOf<T> (T [] array, T value, int startIndex)
3047 throw new ArgumentNullException ("array");
3049 return LastIndexOf<T> (array, value, startIndex, startIndex + 1);
3052 public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
3055 throw new ArgumentNullException ("array");
3057 if (count < 0 || startIndex < array.GetLowerBound (0) ||
3058 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
3059 throw new ArgumentOutOfRangeException ();
3061 EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
3062 for (int i = startIndex; i >= startIndex - count + 1; i--) {
3063 if (equalityComparer.Equals (array [i], value))
3070 public static T [] FindAll<T> (T [] array, Predicate <T> match)
3073 throw new ArgumentNullException ("array");
3076 throw new ArgumentNullException ("match");
3079 T [] d = new T [array.Length];
3080 foreach (T t in array)
3084 Resize <T> (ref d, pos);
3088 public static bool Exists<T> (T [] array, Predicate <T> match)
3091 throw new ArgumentNullException ("array");
3094 throw new ArgumentNullException ("match");
3096 foreach (T t in array)
3102 public static ReadOnlyCollection<T> AsReadOnly<T> (T[] array)
3105 throw new ArgumentNullException ("array");
3107 return new ReadOnlyCollection<T> (array);
3110 public static T Find<T> (T [] array, Predicate<T> match)
3113 throw new ArgumentNullException ("array");
3116 throw new ArgumentNullException ("match");
3118 foreach (T t in array)
3125 public static T FindLast<T> (T [] array, Predicate <T> match)
3128 throw new ArgumentNullException ("array");
3131 throw new ArgumentNullException ("match");
3133 for (int i = array.Length - 1; i >= 0; i--)
3134 if (match (array [i]))
3140 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
3142 // The constrained copy should guarantee that if there is an exception thrown
3143 // during the copy, the destination array remains unchanged.
3144 // This is related to System.Runtime.Reliability.CER
3145 public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
3147 Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length);
3150 #region Unsafe array operations
3153 // Loads array index with no safety checks (JIT intristics)
3155 internal static T UnsafeLoad<T> (T[] array, int index) {
3156 return array [index];
3160 // Stores values at specified array index with no safety checks (JIT intristics)
3162 internal static void UnsafeStore<T> (T[] array, int index, T value) {
3163 array [index] = value;
3167 // Moved value from instance into target of different type with no checks (JIT intristics)
3169 internal static R UnsafeMov<S,R> (S instance) {
3170 return (R)(object) instance;