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)
10 // (C) 2001-2003 Ximian, Inc. http://www.ximian.com
11 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
13 // Permission is hereby granted, free of charge, to any person obtaining
14 // a copy of this software and associated documentation files (the
15 // "Software"), to deal in the Software without restriction, including
16 // without limitation the rights to use, copy, modify, merge, publish,
17 // distribute, sublicense, and/or sell copies of the Software, and to
18 // permit persons to whom the Software is furnished to do so, subject to
19 // the following conditions:
21 // The above copyright notice and this permission notice shall be
22 // included in all copies or substantial portions of the Software.
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 using System.Collections;
34 using System.Runtime.CompilerServices;
35 using System.Runtime.InteropServices;
38 using System.Collections.Generic;
39 using System.Collections.ObjectModel;
40 using System.Runtime.ConstrainedExecution;
46 // FIXME: We are doing way to many double/triple exception checks for the overloaded functions"
47 // FIXME: Sort overloads parameter checks are VERY inconsistent"
48 public abstract class Array : ICloneable, ICollection, IList, IEnumerable
56 protected int InternalArray__ICollection_get_Count<T> ()
61 protected IEnumerator<T> InternalArray__IEnumerable_GetEnumerator<T> ()
63 return new InternalEnumerator<T> (this);
66 protected void InternalArray__ICollection_Clear<T> ()
68 throw new NotSupportedException ("Collection is read-only");
71 protected void InternalArray__ICollection_Add<T> (T item)
73 throw new NotSupportedException ("Collection is read-only");
76 protected bool InternalArray__ICollection_Remove<T> (T item)
78 throw new NotSupportedException ("Collection is read-only");
81 protected bool InternalArray__ICollection_Contains<T> (T item)
84 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
86 int length = this.Length;
87 for (int i = 0; i < length; i++) {
89 GetGenericValueImpl (i, out value);
90 if (item.Equals (value))
97 protected void InternalArray__ICollection_CopyTo<T> (T[] array, int index)
100 throw new ArgumentNullException ("array");
102 // The order of these exception checks may look strange,
103 // but that's how the microsoft runtime does it.
105 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
106 if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
107 throw new ArgumentException ();
109 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
111 throw new ArgumentOutOfRangeException (
112 "index", Locale.GetText ("Value has to be >= 0."));
114 Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
117 protected void InternalArray__Insert<T> (int index, T item)
119 throw new NotSupportedException ("Collection is read-only");
122 protected void InternalArray__RemoveAt<T> (int index)
124 throw new NotSupportedException ("Collection is read-only");
127 protected int InternalArray__IndexOf<T> (T item)
130 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
132 int length = this.Length;
133 for (int i = 0; i < length; i++) {
135 GetGenericValueImpl (i, out value);
136 if (item.Equals (value))
137 // array index may not be zero-based.
139 return i + this.GetLowerBound (0);
144 // lower bound may be MinValue
145 retVal = this.GetLowerBound (0) - 1;
151 protected T InternalArray__get_Item<T> (int index)
153 if (unchecked ((uint) index) >= unchecked ((uint) Length))
154 throw new ArgumentOutOfRangeException ("index");
157 GetGenericValueImpl (index, out value);
161 protected void InternalArray__set_Item<T> (int index, T item)
163 throw new NotSupportedException ("Collection is read-only");
166 // CAUTION! No bounds checking!
167 [MethodImplAttribute (MethodImplOptions.InternalCall)]
168 internal extern void GetGenericValueImpl<T> (int pos, out T value);
170 internal struct InternalEnumerator<T> : IEnumerator<T>
172 const int NOT_STARTED = -2;
174 // this MUST be -1, because we depend on it in move next.
175 // we just decr the size, so, 0 - 1 == FINISHED
176 const int FINISHED = -1;
181 internal InternalEnumerator (Array array)
187 public void Dispose ()
192 public bool MoveNext ()
194 if (idx == NOT_STARTED)
197 return idx != FINISHED && -- idx != FINISHED;
203 throw new InvalidOperationException ();
205 return array.InternalArray__get_Item<T> (array.Length - 1 - idx);
209 void IEnumerator.Reset ()
211 throw new NotImplementedException ();
214 object IEnumerator.Current {
225 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
228 int length = this.GetLength (0);
230 for (int i = 1; i < this.Rank; i++) {
231 length *= this.GetLength (i);
239 public long LongLength {
241 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
243 get { return Length; }
249 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
252 return this.GetRank ();
257 object IList.this [int index] {
259 if (unchecked ((uint) index) >= unchecked ((uint) Length))
260 throw new ArgumentOutOfRangeException ("index");
261 return GetValueImpl (index);
264 if (unchecked ((uint) index) >= unchecked ((uint) Length))
265 throw new ArgumentOutOfRangeException ("index");
266 SetValueImpl (value, index);
270 int IList.Add (object value)
272 throw new NotSupportedException ();
277 Array.Clear (this, this.GetLowerBound (0), this.Length);
280 bool IList.Contains (object value)
283 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
285 int length = this.Length;
286 for (int i = 0; i < length; i++) {
287 if (Object.Equals (value, this.GetValueImpl (i)))
294 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
296 int IList.IndexOf (object value)
299 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
301 int length = this.Length;
302 for (int i = 0; i < length; i++) {
303 if (Object.Equals (value, this.GetValueImpl (i)))
304 // array index may not be zero-based.
306 return i + this.GetLowerBound (0);
311 // lower bound may be MinValue
312 retVal = this.GetLowerBound (0) - 1;
318 void IList.Insert (int index, object value)
320 throw new NotSupportedException ();
323 void IList.Remove (object value)
325 throw new NotSupportedException ();
328 void IList.RemoveAt (int index)
330 throw new NotSupportedException ();
333 // InternalCall Methods
334 [MethodImplAttribute (MethodImplOptions.InternalCall)]
335 protected extern int GetRank ();
337 [MethodImplAttribute (MethodImplOptions.InternalCall)]
338 public extern int GetLength (int dimension);
342 public long GetLongLength (int dimension)
344 return GetLength (dimension);
349 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
351 [MethodImplAttribute (MethodImplOptions.InternalCall)]
352 public extern int GetLowerBound (int dimension);
354 [MethodImplAttribute (MethodImplOptions.InternalCall)]
355 public extern object GetValue (params int[] indices);
357 [MethodImplAttribute (MethodImplOptions.InternalCall)]
358 public extern void SetValue (object value, params int[] indices);
360 // CAUTION! No bounds checking!
361 [MethodImplAttribute (MethodImplOptions.InternalCall)]
362 internal extern object GetValueImpl (int pos);
364 // CAUTION! No bounds checking!
365 [MethodImplAttribute (MethodImplOptions.InternalCall)]
366 internal extern void SetValueImpl (object value, int pos);
368 [MethodImplAttribute (MethodImplOptions.InternalCall)]
369 internal extern static bool FastCopy (Array source, int source_idx, Array dest, int dest_idx, int length);
371 [MethodImplAttribute (MethodImplOptions.InternalCall)]
372 internal extern static Array CreateInstanceImpl (Type elementType, int[] lengths, int[] bounds);
375 int ICollection.Count {
385 bool IsSynchronized {
425 IEnumerator GetEnumerator ()
427 return new SimpleEnumerator (this);
431 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
433 public int GetUpperBound (int dimension)
435 return GetLowerBound (dimension) + GetLength (dimension) - 1;
438 public object GetValue (int index)
441 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
442 if (index < GetLowerBound (0) || index > GetUpperBound (0))
443 throw new IndexOutOfRangeException (Locale.GetText (
444 "Index has to be between upper and lower bound of the array."));
446 return GetValueImpl (index - GetLowerBound (0));
449 public object GetValue (int index1, int index2)
451 int[] ind = {index1, index2};
452 return GetValue (ind);
455 public object GetValue (int index1, int index2, int index3)
457 int[] ind = {index1, index2, index3};
458 return GetValue (ind);
463 public object GetValue (long index)
465 if (index < 0 || index > Int32.MaxValue)
466 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
467 "Value must be >= 0 and <= Int32.MaxValue."));
469 return GetValue ((int) index);
473 public object GetValue (long index1, long index2)
475 if (index1 < 0 || index1 > Int32.MaxValue)
476 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
477 "Value must be >= 0 and <= Int32.MaxValue."));
479 if (index2 < 0 || index2 > Int32.MaxValue)
480 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
481 "Value must be >= 0 and <= Int32.MaxValue."));
483 return GetValue ((int) index1, (int) index2);
487 public object GetValue (long index1, long index2, long index3)
489 if (index1 < 0 || index1 > Int32.MaxValue)
490 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
491 "Value must be >= 0 and <= Int32.MaxValue."));
493 if (index2 < 0 || index2 > Int32.MaxValue)
494 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
495 "Value must be >= 0 and <= Int32.MaxValue."));
497 if (index3 < 0 || index3 > Int32.MaxValue)
498 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
499 "Value must be >= 0 and <= Int32.MaxValue."));
501 return GetValue ((int) index1, (int) index2, (int) index3);
505 public void SetValue (object value, long index)
507 if (index < 0 || index > Int32.MaxValue)
508 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
509 "Value must be >= 0 and <= Int32.MaxValue."));
511 SetValue (value, (int) index);
515 public void SetValue (object value, long index1, long index2)
517 if (index1 < 0 || index1 > Int32.MaxValue)
518 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
519 "Value must be >= 0 and <= Int32.MaxValue."));
521 if (index2 < 0 || index2 > Int32.MaxValue)
522 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
523 "Value must be >= 0 and <= Int32.MaxValue."));
525 int[] ind = {(int) index1, (int) index2};
526 SetValue (value, ind);
530 public void SetValue (object value, long index1, long index2, long index3)
532 if (index1 < 0 || index1 > Int32.MaxValue)
533 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
534 "Value must be >= 0 and <= Int32.MaxValue."));
536 if (index2 < 0 || index2 > Int32.MaxValue)
537 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
538 "Value must be >= 0 and <= Int32.MaxValue."));
540 if (index3 < 0 || index3 > Int32.MaxValue)
541 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
542 "Value must be >= 0 and <= Int32.MaxValue."));
544 int[] ind = {(int) index1, (int) index2, (int) index3};
545 SetValue (value, ind);
549 public void SetValue (object value, int index)
552 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
553 if (index < GetLowerBound (0) || index > GetUpperBound (0))
554 throw new IndexOutOfRangeException (Locale.GetText (
555 "Index has to be >= lower bound and <= upper bound of the array."));
557 SetValueImpl (value, index - GetLowerBound (0));
560 public void SetValue (object value, int index1, int index2)
562 int[] ind = {index1, index2};
563 SetValue (value, ind);
566 public void SetValue (object value, int index1, int index2, int index3)
568 int[] ind = {index1, index2, index3};
569 SetValue (value, ind);
572 public static Array CreateInstance (Type elementType, int length)
574 int[] lengths = {length};
576 return CreateInstance (elementType, lengths);
579 public static Array CreateInstance (Type elementType, int length1, int length2)
581 int[] lengths = {length1, length2};
583 return CreateInstance (elementType, lengths);
586 public static Array CreateInstance (Type elementType, int length1, int length2, int length3)
588 int[] lengths = {length1, length2, length3};
590 return CreateInstance (elementType, lengths);
593 public static Array CreateInstance (Type elementType, int[] lengths)
595 if (elementType == null)
596 throw new ArgumentNullException ("elementType");
598 throw new ArgumentNullException ("lengths");
600 if (lengths.Length > 255)
601 throw new TypeLoadException ();
605 elementType = elementType.UnderlyingSystemType;
606 if (!elementType.IsSystemType)
607 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
609 return CreateInstanceImpl (elementType, lengths, bounds);
612 public static Array CreateInstance (Type elementType, int[] lengths, int [] bounds)
614 if (elementType == null)
615 throw new ArgumentNullException ("elementType");
617 throw new ArgumentNullException ("lengths");
619 throw new ArgumentNullException ("bounds");
621 elementType = elementType.UnderlyingSystemType;
622 if (!elementType.IsSystemType)
623 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
625 if (lengths.Length < 1)
626 throw new ArgumentException (Locale.GetText ("Arrays must contain >= 1 elements."));
628 if (lengths.Length != bounds.Length)
629 throw new ArgumentException (Locale.GetText ("Arrays must be of same size."));
631 for (int j = 0; j < bounds.Length; j ++) {
633 throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
634 "Each value has to be >= 0."));
635 if ((long)bounds [j] + (long)lengths [j] > (long)Int32.MaxValue)
636 throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
637 "Length + bound must not exceed Int32.MaxValue."));
640 if (lengths.Length > 255)
641 throw new TypeLoadException ();
643 return CreateInstanceImpl (elementType, lengths, bounds);
647 static int [] GetIntArray (long [] values)
649 int len = values.Length;
650 int [] ints = new int [len];
651 for (int i = 0; i < len; i++) {
652 long current = values [i];
653 if (current < 0 || current > (long) Int32.MaxValue)
654 throw new ArgumentOutOfRangeException ("values", Locale.GetText (
655 "Each value has to be >= 0 and <= Int32.MaxValue."));
657 ints [i] = (int) current;
662 public static Array CreateInstance (Type elementType, params long [] lengths)
666 throw new ArgumentNullException ("lengths");
668 return CreateInstance (elementType, GetIntArray (lengths));
672 public object GetValue (params long [] indices)
676 throw new ArgumentNullException ("indices");
678 return GetValue (GetIntArray (indices));
682 public void SetValue (object value, params long [] indices)
686 throw new ArgumentNullException ("indices");
688 SetValue (value, GetIntArray (indices));
693 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
695 public static int BinarySearch (Array array, object value)
698 throw new ArgumentNullException ("array");
704 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
706 if (array.Length == 0)
709 if (!(value is IComparable))
710 throw new ArgumentException (Locale.GetText ("value does not support IComparable."));
712 return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, null);
716 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
718 public static int BinarySearch (Array array, object value, IComparer comparer)
721 throw new ArgumentNullException ("array");
724 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
726 if (array.Length == 0)
729 if ((comparer == null) && (value != null) && !(value is IComparable))
730 throw new ArgumentException (Locale.GetText (
731 "comparer is null and value does not support IComparable."));
733 return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer);
737 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
739 public static int BinarySearch (Array array, int index, int length, object value)
742 throw new ArgumentNullException ("array");
745 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
747 if (index < array.GetLowerBound (0))
748 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
749 "index is less than the lower bound of array."));
751 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
752 "Value has to be >= 0."));
753 // re-ordered to avoid possible integer overflow
754 if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
755 throw new ArgumentException (Locale.GetText (
756 "index and length do not specify a valid range in array."));
758 if (array.Length == 0)
761 if ((value != null) && (!(value is IComparable)))
762 throw new ArgumentException (Locale.GetText (
763 "value does not support IComparable"));
765 return DoBinarySearch (array, index, length, value, null);
769 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
771 public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
774 throw new ArgumentNullException ("array");
777 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
779 if (index < array.GetLowerBound (0))
780 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
781 "index is less than the lower bound of array."));
783 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
784 "Value has to be >= 0."));
785 // re-ordered to avoid possible integer overflow
786 if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
787 throw new ArgumentException (Locale.GetText (
788 "index and length do not specify a valid range in array."));
790 if (array.Length == 0)
793 if ((comparer == null) && (value != null) && !(value is IComparable))
794 throw new ArgumentException (Locale.GetText (
795 "comparer is null and value does not support IComparable."));
797 return DoBinarySearch (array, index, length, value, comparer);
800 static int DoBinarySearch (Array array, int index, int length, object value, IComparer comparer)
802 // cache this in case we need it
803 if (comparer == null)
804 comparer = Comparer.Default;
807 // Comment from Tum (tum@veridicus.com):
808 // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
809 int iMax = index + length - 1;
812 while (iMin <= iMax) {
813 int iMid = (iMin + iMax) / 2;
814 object elt = array.GetValueImpl (iMid);
816 iCmp = comparer.Compare (elt, value);
823 iMin = iMid + 1; // compensate for the rounding down
826 catch (Exception e) {
827 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
834 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
836 public static void Clear (Array array, int index, int length)
839 throw new ArgumentNullException ("array");
841 throw new ArgumentOutOfRangeException ("length < 0");
843 int low = array.GetLowerBound (0);
845 throw new IndexOutOfRangeException ("index < lower bound");
848 // re-ordered to avoid possible integer overflow
849 if (index > array.Length - length)
850 throw new IndexOutOfRangeException ("index + length > size");
852 ClearInternal (array, index, length);
855 [MethodImplAttribute (MethodImplOptions.InternalCall)]
856 static extern void ClearInternal (Array a, int index, int count);
858 [MethodImplAttribute (MethodImplOptions.InternalCall)]
863 extern object Clone ();
866 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
868 public static void Copy (Array sourceArray, Array destinationArray, int length)
870 // need these checks here because we are going to use
871 // GetLowerBound() on source and dest.
872 if (sourceArray == null)
873 throw new ArgumentNullException ("sourceArray");
875 if (destinationArray == null)
876 throw new ArgumentNullException ("destinationArray");
878 Copy (sourceArray, sourceArray.GetLowerBound (0), destinationArray,
879 destinationArray.GetLowerBound (0), length);
883 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
885 public static void Copy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
887 if (sourceArray == null)
888 throw new ArgumentNullException ("sourceArray");
890 if (destinationArray == null)
891 throw new ArgumentNullException ("destinationArray");
894 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
895 "Value has to be >= 0."));;
898 throw new ArgumentOutOfRangeException ("sourceIndex", Locale.GetText (
899 "Value has to be >= 0."));;
901 if (destinationIndex < 0)
902 throw new ArgumentOutOfRangeException ("destinationIndex", Locale.GetText (
903 "Value has to be >= 0."));;
905 if (FastCopy (sourceArray, sourceIndex, destinationArray, destinationIndex, length))
908 int source_pos = sourceIndex - sourceArray.GetLowerBound (0);
909 int dest_pos = destinationIndex - destinationArray.GetLowerBound (0);
911 // re-ordered to avoid possible integer overflow
912 if (source_pos > sourceArray.Length - length || dest_pos > destinationArray.Length - length)
913 throw new ArgumentException ("length");
915 if (sourceArray.Rank != destinationArray.Rank)
916 throw new RankException (Locale.GetText ("Arrays must be of same size."));
918 Type src_type = sourceArray.GetType ().GetElementType ();
919 Type dst_type = destinationArray.GetType ().GetElementType ();
921 if (!Object.ReferenceEquals (sourceArray, destinationArray) || source_pos > dest_pos) {
922 for (int i = 0; i < length; i++) {
923 Object srcval = sourceArray.GetValueImpl (source_pos + i);
926 destinationArray.SetValueImpl (srcval, dest_pos + i);
928 if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) &&
929 (src_type.Equals (typeof (Object))))
930 throw new InvalidCastException ();
932 throw new ArrayTypeMismatchException (String.Format (Locale.GetText (
933 "(Types: source={0}; target={1})"), src_type.FullName, dst_type.FullName));
938 for (int i = length - 1; i >= 0; i--) {
939 Object srcval = sourceArray.GetValueImpl (source_pos + i);
942 destinationArray.SetValueImpl (srcval, dest_pos + i);
944 if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) &&
945 (src_type.Equals (typeof (Object))))
946 throw new InvalidCastException ();
948 throw new ArrayTypeMismatchException (String.Format (Locale.GetText (
949 "(Types: source={0}; target={1})"), src_type.FullName, dst_type.FullName));
957 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
959 public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray,
960 long destinationIndex, long length)
962 if (sourceArray == null)
963 throw new ArgumentNullException ("sourceArray");
965 if (destinationArray == null)
966 throw new ArgumentNullException ("destinationArray");
968 if (sourceIndex < Int32.MinValue || sourceIndex > Int32.MaxValue)
969 throw new ArgumentOutOfRangeException ("sourceIndex",
970 Locale.GetText ("Must be in the Int32 range."));
972 if (destinationIndex < Int32.MinValue || destinationIndex > Int32.MaxValue)
973 throw new ArgumentOutOfRangeException ("destinationIndex",
974 Locale.GetText ("Must be in the Int32 range."));
976 if (length < 0 || length > Int32.MaxValue)
977 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
978 "Value must be >= 0 and <= Int32.MaxValue."));
980 Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
984 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
986 public static void Copy (Array sourceArray, Array destinationArray, long length)
988 if (length < 0 || length > Int32.MaxValue)
989 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
990 "Value must be >= 0 and <= Int32.MaxValue."));
992 Copy (sourceArray, destinationArray, (int) length);
997 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
999 public static int IndexOf (Array array, object value)
1002 throw new ArgumentNullException ("array");
1004 return IndexOf (array, value, 0, array.Length);
1008 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1010 public static int IndexOf (Array array, object value, int startIndex)
1013 throw new ArgumentNullException ("array");
1015 return IndexOf (array, value, startIndex, array.Length - startIndex);
1019 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1021 public static int IndexOf (Array array, object value, int startIndex, int count)
1024 throw new ArgumentNullException ("array");
1027 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1029 // re-ordered to avoid possible integer overflow
1030 if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
1031 throw new ArgumentOutOfRangeException ();
1033 int max = startIndex + count;
1034 for (int i = startIndex; i < max; i++) {
1035 if (Object.Equals (value, array.GetValueImpl (i)))
1039 return array.GetLowerBound (0) - 1;
1042 public void Initialize()
1044 //FIXME: We would like to find a compiler that uses
1045 // this method. It looks like this method do nothing
1046 // in C# so no exception is trown by the moment.
1050 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1052 public static int LastIndexOf (Array array, object value)
1055 throw new ArgumentNullException ("array");
1057 return LastIndexOf (array, value, array.Length - 1);
1061 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1063 public static int LastIndexOf (Array array, object value, int startIndex)
1066 throw new ArgumentNullException ("array");
1068 return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1);
1072 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1074 public static int LastIndexOf (Array array, object value, int startIndex, int count)
1077 throw new ArgumentNullException ("array");
1080 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1082 if (count < 0 || startIndex < array.GetLowerBound (0) ||
1083 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
1084 throw new ArgumentOutOfRangeException ();
1086 for (int i = startIndex; i >= startIndex - count + 1; i--) {
1087 if (Object.Equals (value, array.GetValueImpl (i)))
1091 return array.GetLowerBound (0) - 1;
1094 #if !BOOTSTRAP_WITH_OLDLIB
1095 /* delegate used to swap array elements */
1096 delegate void Swapper (int i, int j);
1099 static Swapper get_swapper (Array array)
1102 return new Swapper (array.int_swapper);
1103 if (array is double[])
1104 return new Swapper (array.double_swapper);
1105 if (array is object[]) {
1106 return new Swapper (array.obj_swapper);
1108 return new Swapper (array.slow_swapper);
1112 static Swapper get_swapper<T> (T [] array)
1115 return new Swapper (array.int_swapper);
1116 if (array is double[])
1117 return new Swapper (array.double_swapper);
1119 return new Swapper (array.obj_swapper);
1124 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1126 public static void Reverse (Array array)
1129 throw new ArgumentNullException ("array");
1131 Reverse (array, array.GetLowerBound (0), array.GetLength (0));
1135 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1137 public static void Reverse (Array array, int index, int length)
1140 throw new ArgumentNullException ("array");
1143 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1145 if (index < array.GetLowerBound (0) || length < 0)
1146 throw new ArgumentOutOfRangeException ();
1148 // re-ordered to avoid possible integer overflow
1149 if (index > array.GetUpperBound (0) + 1 - length)
1150 throw new ArgumentException ();
1152 int end = index + length - 1;
1153 object[] oarray = array as object[];
1154 if (oarray != null) {
1155 while (index < end) {
1156 object tmp = oarray [index];
1157 oarray [index] = oarray [end];
1164 int[] iarray = array as int[];
1165 if (iarray != null) {
1166 while (index < end) {
1167 int tmp = iarray [index];
1168 iarray [index] = iarray [end];
1175 double[] darray = array as double[];
1176 if (darray != null) {
1177 while (index < end) {
1178 double tmp = darray [index];
1179 darray [index] = darray [end];
1187 Swapper swapper = get_swapper (array);
1188 while (index < end) {
1189 swapper (index, end);
1196 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1198 public static void Sort (Array array)
1201 throw new ArgumentNullException ("array");
1203 Sort (array, null, array.GetLowerBound (0), array.GetLength (0), null);
1207 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1209 public static void Sort (Array keys, Array items)
1212 throw new ArgumentNullException ("keys");
1214 Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), null);
1218 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1220 public static void Sort (Array array, IComparer comparer)
1223 throw new ArgumentNullException ("array");
1225 Sort (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
1229 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1231 public static void Sort (Array array, int index, int length)
1233 Sort (array, null, index, length, null);
1237 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1239 public static void Sort (Array keys, Array items, IComparer comparer)
1242 throw new ArgumentNullException ("keys");
1244 Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
1248 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1250 public static void Sort (Array keys, Array items, int index, int length)
1252 Sort (keys, items, index, length, null);
1256 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1258 public static void Sort (Array array, int index, int length, IComparer comparer)
1260 Sort (array, null, index, length, comparer);
1264 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1267 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
1270 throw new ArgumentNullException ("keys");
1272 if (keys.Rank > 1 || (items != null && items.Rank > 1))
1273 throw new RankException ();
1275 if (items != null && keys.GetLowerBound (0) != items.GetLowerBound (0))
1276 throw new ArgumentException ();
1278 if (index < keys.GetLowerBound (0))
1279 throw new ArgumentOutOfRangeException ("index");
1282 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1283 "Value has to be >= 0."));
1285 if (keys.Length - (index + keys.GetLowerBound (0)) < length || (items != null && index > items.Length - length))
1286 throw new ArgumentException ();
1291 if (comparer == null) {
1296 iswapper = get_swapper (items);
1297 if (keys is double[]) {
1298 combsort (keys as double[], index, length, iswapper);
1301 if (keys is int[]) {
1302 combsort (keys as int[], index, length, iswapper);
1305 if (keys is char[]) {
1306 combsort (keys as char[], index, length, iswapper);
1312 int high0 = index + length - 1;
1313 qsort (keys, items, low0, high0, comparer);
1315 catch (Exception e) {
1316 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1320 /* note, these are instance methods */
1321 void int_swapper (int i, int j) {
1322 int[] array = this as int[];
1323 int val = array [i];
1324 array [i] = array [j];
1328 void obj_swapper (int i, int j) {
1329 object[] array = this as object[];
1330 object val = array [i];
1331 array [i] = array [j];
1335 void slow_swapper (int i, int j) {
1336 object val = GetValueImpl (i);
1337 SetValueImpl (GetValue (j), i);
1338 SetValueImpl (val, j);
1341 void double_swapper (int i, int j) {
1342 double[] array = this as double[];
1343 double val = array [i];
1344 array [i] = array [j];
1348 static int new_gap (int gap)
1350 gap = (gap * 10) / 13;
1351 if (gap == 9 || gap == 10)
1358 /* we use combsort because it's fast enough and very small, since we have
1359 * several specialized versions here.
1361 static void combsort (double[] array, int start, int size, Swapper swap_items)
1365 gap = new_gap (gap);
1366 bool swapped = false;
1367 int end = start + size - gap;
1368 for (int i = start; i < end; i++) {
1370 if (array [i] > array [j]) {
1371 double val = array [i];
1372 array [i] = array [j];
1375 if (swap_items != null)
1379 if (gap == 1 && !swapped)
1384 static void combsort (int[] array, int start, int size, Swapper swap_items)
1388 gap = new_gap (gap);
1389 bool swapped = false;
1390 int end = start + size - gap;
1391 for (int i = start; i < end; i++) {
1393 if (array [i] > array [j]) {
1394 int val = array [i];
1395 array [i] = array [j];
1398 if (swap_items != null)
1402 if (gap == 1 && !swapped)
1407 static void combsort (char[] array, int start, int size, Swapper swap_items)
1411 gap = new_gap (gap);
1412 bool swapped = false;
1413 int end = start + size - gap;
1414 for (int i = start; i < end; i++) {
1416 if (array [i] > array [j]) {
1417 char val = array [i];
1418 array [i] = array [j];
1421 if (swap_items != null)
1425 if (gap == 1 && !swapped)
1430 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
1438 object objPivot = keys.GetValueImpl ((low + high) / 2);
1440 while (low <= high) {
1441 // Move the walls in
1442 while (low < high0 && compare (keys.GetValueImpl (low), objPivot, comparer) < 0)
1444 while (high > low0 && compare (objPivot, keys.GetValueImpl (high), comparer) < 0)
1448 swap (keys, items, low, high);
1455 qsort (keys, items, low0, high, comparer);
1457 qsort (keys, items, low, high0, comparer);
1460 private static void swap (Array keys, Array items, int i, int j)
1464 tmp = keys.GetValueImpl (i);
1465 keys.SetValueImpl (keys.GetValue (j), i);
1466 keys.SetValueImpl (tmp, j);
1468 if (items != null) {
1469 tmp = items.GetValueImpl (i);
1470 items.SetValueImpl (items.GetValueImpl (j), i);
1471 items.SetValueImpl (tmp, j);
1475 private static int compare (object value1, object value2, IComparer comparer)
1478 return value2 == null ? 0 : -1;
1479 else if (value2 == null)
1481 else if (comparer == null)
1482 return ((IComparable) value1).CompareTo (value2);
1484 return comparer.Compare (value1, value2);
1488 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1489 public static void Sort<T> (T [] array)
1492 throw new ArgumentNullException ("array");
1494 Sort<T, T> (array, null, 0, array.Length, null);
1497 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1498 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items)
1501 throw new ArgumentNullException ("keys");
1503 Sort<TKey, TValue> (keys, items, 0, keys.Length, null);
1506 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1507 public static void Sort<T> (T [] array, IComparer<T> comparer)
1510 throw new ArgumentNullException ("array");
1512 Sort<T, T> (array, null, 0, array.Length, comparer);
1515 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1516 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, IComparer<TKey> comparer)
1519 throw new ArgumentNullException ("keys");
1521 Sort<TKey, TValue> (keys, items, 0, keys.Length, comparer);
1524 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1525 public static void Sort<T> (T [] array, int index, int length)
1528 throw new ArgumentNullException ("array");
1530 Sort<T, T> (array, null, index, length, null);
1533 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1534 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length)
1536 Sort<TKey, TValue> (keys, items, index, length, null);
1539 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1540 public static void Sort<T> (T [] array, int index, int length, IComparer<T> comparer)
1543 throw new ArgumentNullException ("array");
1545 Sort<T, T> (array, null, index, length, comparer);
1548 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1549 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1552 throw new ArgumentNullException ("keys");
1555 throw new ArgumentOutOfRangeException ("index");
1558 throw new ArgumentOutOfRangeException ("length");
1560 if (keys.Length - index < length
1561 || (items != null && index > items.Length - length))
1562 throw new ArgumentException ();
1568 // Check for value types which can be sorted without Compare () method
1570 if (comparer == null) {
1575 iswapper = get_swapper<TValue> (items);
1576 if (keys is double[]) {
1577 combsort (keys as double[], index, length, iswapper);
1580 if (keys is int[]) {
1581 combsort (keys as int[], index, length, iswapper);
1584 if (keys is char[]) {
1585 combsort (keys as char[], index, length, iswapper);
1589 // Use Comparer<T>.Default instead
1590 // comparer = Comparer<K>.Default;
1595 int high0 = index + length - 1;
1596 qsort<TKey, TValue> (keys, items, low0, high0, comparer);
1598 catch (Exception e) {
1599 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1603 public static void Sort<T> (T [] array, Comparison<T> comparison)
1606 throw new ArgumentNullException ("array");
1607 Sort<T> (array, array.Length, comparison);
1610 internal static void Sort<T> (T [] array, int length, Comparison<T> comparison)
1612 if (comparison == null)
1613 throw new ArgumentNullException ("comparison");
1615 if (length <= 1 || array.Length <= 1)
1620 int high0 = length - 1;
1621 qsort<T> (array, low0, high0, comparison);
1623 catch (Exception e) {
1624 throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e);
1628 private static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
1636 K keyPivot = keys [(low + high) / 2];
1638 while (low <= high) {
1639 // Move the walls in
1640 //while (low < high0 && comparer.Compare (keys [low], keyPivot) < 0)
1641 while (low < high0 && compare (keys [low], keyPivot, comparer) < 0)
1643 //while (high > low0 && comparer.Compare (keyPivot, keys [high]) < 0)
1644 while (high > low0 && compare (keyPivot, keys [high], comparer) < 0)
1648 swap<K, V> (keys, items, low, high);
1655 qsort<K, V> (keys, items, low0, high, comparer);
1657 qsort<K, V> (keys, items, low, high0, comparer);
1660 private static int compare<T> (T value1, T value2, IComparer<T> comparer)
1662 if (comparer != null)
1663 return comparer.Compare (value1, value2);
1664 else if (value1 == null)
1665 return value2 == null ? 0 : -1;
1666 else if (value2 == null)
1668 else if (value1 is IComparable<T>)
1669 return ((IComparable<T>) value1).CompareTo (value2);
1670 else if (value1 is IComparable)
1671 return ((IComparable) value1).CompareTo (value2);
1673 string msg = Locale.GetText ("No IComparable or IComparable<T> interface found for type '{0}'.");
1674 throw new InvalidOperationException (String.Format (msg, typeof (T)));
1677 private static void qsort<T> (T [] array, int low0, int high0, Comparison<T> comparison)
1685 T keyPivot = array [(low + high) / 2];
1687 while (low <= high) {
1688 // Move the walls in
1689 while (low < high0 && comparison (array [low], keyPivot) < 0)
1691 while (high > low0 && comparison (keyPivot, array [high]) < 0)
1695 swap<T> (array, low, high);
1702 qsort<T> (array, low0, high, comparison);
1704 qsort<T> (array, low, high0, comparison);
1707 private static void swap<K, V> (K [] keys, V [] items, int i, int j)
1712 keys [i] = keys [j];
1715 if (items != null) {
1718 items [i] = items [j];
1723 private static void swap<T> (T [] array, int i, int j)
1726 array [i] = array [j];
1735 void CopyTo (Array array, int index)
1738 throw new ArgumentNullException ("array");
1740 // The order of these exception checks may look strange,
1741 // but that's how the microsoft runtime does it.
1743 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1744 if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
1745 throw new ArgumentException ();
1747 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1749 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
1750 "Value has to be >= 0."));
1752 Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
1756 [ComVisible (false)]
1761 void CopyTo (Array array, long index)
1763 if (index < 0 || index > Int32.MaxValue)
1764 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
1765 "Value must be >= 0 and <= Int32.MaxValue."));
1767 CopyTo (array, (int) index);
1771 internal class SimpleEnumerator : IEnumerator, ICloneable
1777 public SimpleEnumerator (Array arrayToEnumerate)
1779 this.enumeratee = arrayToEnumerate;
1780 this.currentpos = -1;
1781 this.length = arrayToEnumerate.Length;
1784 public object Current {
1786 // Exception messages based on MS implementation
1787 if (currentpos < 0 )
1788 throw new InvalidOperationException (Locale.GetText (
1789 "Enumeration has not started."));
1790 if (currentpos >= length)
1791 throw new InvalidOperationException (Locale.GetText (
1792 "Enumeration has already ended"));
1793 // Current should not increase the position. So no ++ over here.
1794 return enumeratee.GetValueImpl (currentpos);
1798 public bool MoveNext()
1800 //The docs say Current should throw an exception if last
1801 //call to MoveNext returned false. This means currentpos
1802 //should be set to length when returning false.
1803 if (currentpos < length)
1805 if(currentpos < length)
1816 public object Clone ()
1818 return MemberwiseClone ();
1823 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1824 public static void Resize<T> (ref T [] array, int newSize)
1826 Resize<T> (ref array, array == null ? 0 : array.Length, newSize);
1829 internal static void Resize<T> (ref T[] array, int length, int newSize)
1832 throw new ArgumentOutOfRangeException ();
1834 if (array == null) {
1835 array = new T [newSize];
1839 if (array.Length == newSize)
1842 T [] a = new T [newSize];
1843 Array.Copy (array, a, Math.Min (newSize, length));
1847 public static bool TrueForAll <T> (T [] array, Predicate <T> match)
1850 throw new ArgumentNullException ("array");
1852 throw new ArgumentNullException ("match");
1854 foreach (T t in array)
1861 public static void ForEach<T> (T [] array, Action <T> action)
1864 throw new ArgumentNullException ("array");
1866 throw new ArgumentNullException ("action");
1868 foreach (T t in array)
1872 public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
1875 throw new ArgumentNullException ("array");
1876 if (converter == null)
1877 throw new ArgumentNullException ("converter");
1879 TOutput [] output = new TOutput [array.Length];
1880 for (int i = 0; i < array.Length; i ++)
1881 output [i] = converter (array [i]);
1886 public static int FindLastIndex<T> (T [] array, Predicate <T> match)
1889 throw new ArgumentNullException ("array");
1891 return FindLastIndex<T> (array, 0, array.Length, match);
1894 public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
1897 throw new ArgumentNullException ();
1899 return FindLastIndex<T> (array, startIndex, array.Length - startIndex, match);
1902 public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
1905 throw new ArgumentNullException ("array");
1907 throw new ArgumentNullException ("match");
1909 if (startIndex > array.Length || startIndex + count > array.Length)
1910 throw new ArgumentOutOfRangeException ();
1912 for (int i = startIndex + count - 1; i >= startIndex; i--)
1913 if (match (array [i]))
1919 public static int FindIndex<T> (T [] array, Predicate<T> match)
1922 throw new ArgumentNullException ("array");
1924 return FindIndex<T> (array, 0, array.Length, match);
1927 public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
1930 throw new ArgumentNullException ("array");
1932 return FindIndex<T> (array, startIndex, array.Length - startIndex, match);
1935 public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
1938 throw new ArgumentNullException ("array");
1941 throw new ArgumentNullException ("match");
1943 if (startIndex > array.Length || startIndex + count > array.Length)
1944 throw new ArgumentOutOfRangeException ();
1946 for (int i = startIndex; i < startIndex + count; i ++)
1947 if (match (array [i]))
1953 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1954 public static int BinarySearch<T> (T [] array, T value)
1957 throw new ArgumentNullException ("array");
1959 return BinarySearch<T> (array, 0, array.Length, value, null);
1962 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1963 public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
1966 throw new ArgumentNullException ("array");
1968 return BinarySearch<T> (array, 0, array.Length, value, comparer);
1971 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1972 public static int BinarySearch<T> (T [] array, int offset, int length, T value)
1974 return BinarySearch<T> (array, offset, length, value, null);
1977 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1978 public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
1981 throw new ArgumentNullException ("array");
1983 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
1984 "index is less than the lower bound of array."));
1986 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1987 "Value has to be >= 0."));
1988 // re-ordered to avoid possible integer overflow
1989 if (index > array.Length - length)
1990 throw new ArgumentException (Locale.GetText (
1991 "index and length do not specify a valid range in array."));
1992 if (comparer == null)
1993 comparer = Comparer <T>.Default;
1996 int iMax = index + length - 1;
1999 while (iMin <= iMax) {
2000 int iMid = (iMin + iMax) / 2;
2001 iCmp = comparer.Compare (value, array [iMid]);
2008 iMin = iMid + 1; // compensate for the rounding down
2010 } catch (Exception e) {
2011 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
2017 public static int IndexOf<T> (T [] array, T value)
2020 throw new ArgumentNullException ("array");
2022 return IndexOf<T> (array, value, 0, array.Length);
2025 public static int IndexOf<T> (T [] array, T value, int startIndex)
2028 throw new ArgumentNullException ("array");
2030 return IndexOf<T> (array, value, startIndex, array.Length - startIndex);
2033 public static int IndexOf<T> (T [] array, T value, int startIndex, int count)
2036 throw new ArgumentNullException ("array");
2038 // re-ordered to avoid possible integer overflow
2039 if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
2040 throw new ArgumentOutOfRangeException ();
2042 int max = startIndex + count;
2043 EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
2044 for (int i = startIndex; i < max; i++) {
2045 if (equalityComparer.Equals (value, array [i]))
2052 public static int LastIndexOf<T> (T [] array, T value)
2055 throw new ArgumentNullException ("array");
2057 return LastIndexOf<T> (array, value, array.Length - 1);
2060 public static int LastIndexOf<T> (T [] array, T value, int startIndex)
2063 throw new ArgumentNullException ("array");
2065 return LastIndexOf<T> (array, value, startIndex, startIndex + 1);
2068 public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
2071 throw new ArgumentNullException ("array");
2073 if (count < 0 || startIndex > array.Length || startIndex - count + 1 < 0)
2074 throw new ArgumentOutOfRangeException ();
2076 EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
2077 for (int i = startIndex; i >= startIndex - count + 1; i--) {
2078 if (equalityComparer.Equals (value, array [i]))
2085 public static T [] FindAll<T> (T [] array, Predicate <T> match)
2088 throw new ArgumentNullException ("array");
2091 throw new ArgumentNullException ("match");
2094 T [] d = new T [array.Length];
2095 foreach (T t in array)
2099 Resize <T> (ref d, pos);
2103 public static bool Exists<T> (T [] array, Predicate <T> match)
2106 throw new ArgumentNullException ("array");
2109 throw new ArgumentNullException ("match");
2111 foreach (T t in array)
2117 public static ReadOnlyCollection<T> AsReadOnly<T> (T[] array)
2120 throw new ArgumentNullException ("array");
2121 return new ReadOnlyCollection<T> (new ArrayReadOnlyList<T> (array));
2124 public static T Find<T> (T [] array, Predicate<T> match)
2127 throw new ArgumentNullException ("array");
2130 throw new ArgumentNullException ("match");
2132 foreach (T t in array)
2139 public static T FindLast<T> (T [] array, Predicate <T> match)
2142 throw new ArgumentNullException ("array");
2145 throw new ArgumentNullException ("match");
2147 for (int i = array.Length - 1; i >= 0; i--)
2148 if (match (array [i]))
2154 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
2156 // The constrained copy should guarantee that if there is an exception thrown
2157 // during the copy, the destination array remains unchanged.
2158 // This is related to System.Runtime.Reliability.CER
2159 public static void ConstrainedCopy (Array s, int s_i, Array d, int d_i, int c)
2161 Copy (s, s_i, d, d_i, c);
2166 class ArrayReadOnlyList<T> : IList<T>
2171 public ArrayReadOnlyList (T [] array)
2174 is_value_type = typeof (T).IsValueType;
2177 public T this [int index] {
2179 if (unchecked ((uint) index) >= unchecked ((uint) array.Length))
2180 throw new ArgumentOutOfRangeException ("index");
2181 return array [index];
2183 set { throw ReadOnlyError (); }
2187 get { return array.Length; }
2190 public bool IsReadOnly {
2191 get { return true; }
2194 public void Add (T item)
2196 throw ReadOnlyError ();
2199 public void Clear ()
2201 throw ReadOnlyError ();
2204 public bool Contains (T item)
2206 return Array.IndexOf<T> (array, item) >= 0;
2209 public void CopyTo (T [] array, int index)
2211 array.CopyTo (array, index);
2214 IEnumerator IEnumerable.GetEnumerator ()
2216 return GetEnumerator ();
2219 public IEnumerator<T> GetEnumerator ()
2221 for (int i = 0; i < array.Length; i++)
2222 yield return array [i];
2225 public int IndexOf (T item)
2227 return Array.IndexOf<T> (array, item);
2230 public void Insert (int index, T item)
2232 throw ReadOnlyError ();
2235 public bool Remove (T item)
2237 throw ReadOnlyError ();
2240 public void RemoveAt (int index)
2242 throw ReadOnlyError ();
2245 Exception ReadOnlyError ()
2247 return new NotSupportedException ("This collection is read-only.");
2253 #if BOOTSTRAP_WITH_OLDLIB
2254 /* delegate used to swap array elements, keep defined outside Array */
2255 delegate void Swapper (int i, int j);