X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;ds=sidebyside;f=mcs%2Fclass%2Fcorlib%2FSystem%2FArray.cs;h=095d70027cdbc36181697cee33633b25345478cd;hb=1fda301a35846c9582cf757f6f2bd84e0a142805;hp=0364c42abeca31e2ffdcde7dc4477e94b8231ecb;hpb=5e5816fb5992c0e795057f537ed265b3b1b4a1e6;p=mono.git diff --git a/mcs/class/corlib/System/Array.cs b/mcs/class/corlib/System/Array.cs index 0364c42abec..095d70027cd 100644 --- a/mcs/class/corlib/System/Array.cs +++ b/mcs/class/corlib/System/Array.cs @@ -34,17 +34,15 @@ using System.Collections; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; -#if NET_2_0 using System.Collections.Generic; using System.Collections.ObjectModel; using System.Runtime.ConstrainedExecution; -#endif namespace System { [Serializable] + [ComVisible (true)] // FIXME: We are doing way to many double/triple exception checks for the overloaded functions" - // FIXME: Sort overloads parameter checks are VERY inconsistent" public abstract class Array : ICloneable, ICollection, IList, IEnumerable { // Constructor @@ -52,33 +50,43 @@ namespace System { } -#if NET_2_0 - protected int InternalArray__ICollection_get_Count () + /* + * These methods are used to implement the implicit generic interfaces + * implemented by arrays in NET 2.0. + * Only make those methods generic which really need it, to avoid + * creating useless instantiations. + */ + internal int InternalArray__ICollection_get_Count () { return Length; } - protected IEnumerator InternalArray__IEnumerable_GetEnumerator () + internal bool InternalArray__ICollection_get_IsReadOnly () + { + return true; + } + + internal IEnumerator InternalArray__IEnumerable_GetEnumerator () { return new InternalEnumerator (this); } - protected void InternalArray__ICollection_Clear () + internal void InternalArray__ICollection_Clear () { throw new NotSupportedException ("Collection is read-only"); } - protected void InternalArray__ICollection_Add (T item) + internal void InternalArray__ICollection_Add (T item) { throw new NotSupportedException ("Collection is read-only"); } - protected bool InternalArray__ICollection_Remove (T item) + internal bool InternalArray__ICollection_Remove (T item) { throw new NotSupportedException ("Collection is read-only"); } - protected bool InternalArray__ICollection_Contains (T item) + internal bool InternalArray__ICollection_Contains (T item) { if (this.Rank > 1) throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); @@ -101,7 +109,7 @@ namespace System return false; } - protected void InternalArray__ICollection_CopyTo (T[] array, int index) + internal void InternalArray__ICollection_CopyTo (T[] array, int index) { if (array == null) throw new ArgumentNullException ("array"); @@ -111,7 +119,9 @@ namespace System if (this.Rank > 1) throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0)) - throw new ArgumentException (); + throw new ArgumentException ("Destination array was not long " + + "enough. Check destIndex and length, and the array's " + + "lower bounds."); if (array.Rank > 1) throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); if (index < 0) @@ -121,17 +131,17 @@ namespace System Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0)); } - protected void InternalArray__Insert (int index, T item) + internal void InternalArray__Insert (int index, T item) { throw new NotSupportedException ("Collection is read-only"); } - protected void InternalArray__RemoveAt (int index) + internal void InternalArray__RemoveAt (int index) { throw new NotSupportedException ("Collection is read-only"); } - protected int InternalArray__IndexOf (T item) + internal int InternalArray__IndexOf (T item) { if (this.Rank > 1) throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); @@ -149,22 +159,19 @@ namespace System } } } - if (item.Equals (value)) + if (value.Equals (item)) // array index may not be zero-based. // use lower bound return i + this.GetLowerBound (0); } - int retVal; unchecked { // lower bound may be MinValue - retVal = this.GetLowerBound (0) - 1; + return this.GetLowerBound (0) - 1; } - - return retVal; } - protected T InternalArray__get_Item (int index) + internal T InternalArray__get_Item (int index) { if (unchecked ((uint) index) >= unchecked ((uint) Length)) throw new ArgumentOutOfRangeException ("index"); @@ -174,15 +181,27 @@ namespace System return value; } - protected void InternalArray__set_Item (int index, T item) + internal void InternalArray__set_Item (int index, T item) { - throw new NotSupportedException ("Collection is read-only"); + if (unchecked ((uint) index) >= unchecked ((uint) Length)) + throw new ArgumentOutOfRangeException ("index"); + + object[] oarray = this as object []; + if (oarray != null) { + oarray [index] = (object)item; + return; + } + SetGenericValueImpl (index, ref item); } // CAUTION! No bounds checking! [MethodImplAttribute (MethodImplOptions.InternalCall)] internal extern void GetGenericValueImpl (int pos, out T value); + // CAUTION! No bounds checking! + [MethodImplAttribute (MethodImplOptions.InternalCall)] + internal extern void SetGenericValueImpl (int pos, ref T value); + internal struct InternalEnumerator : IEnumerator { const int NOT_STARTED = -2; @@ -215,8 +234,10 @@ namespace System public T Current { get { - if (idx < 0) - throw new InvalidOperationException (); + if (idx == NOT_STARTED) + throw new InvalidOperationException ("Enumeration has not started. Call MoveNext"); + if (idx == FINISHED) + throw new InvalidOperationException ("Enumeration already finished"); return array.InternalArray__get_Item (array.Length - 1 - idx); } @@ -224,7 +245,7 @@ namespace System void IEnumerator.Reset () { - throw new NotImplementedException (); + idx = NOT_STARTED; } object IEnumerator.Current { @@ -233,13 +254,10 @@ namespace System } } } -#endif // Properties public int Length { -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)] -#endif get { int length = this.GetLength (0); @@ -250,20 +268,14 @@ namespace System } } -#if NET_1_1 [ComVisible (false)] public long LongLength { -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)] -#endif get { return Length; } } -#endif public int Rank { -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)] -#endif get { return this.GetRank (); } @@ -273,12 +285,16 @@ namespace System object IList.this [int index] { get { if (unchecked ((uint) index) >= unchecked ((uint) Length)) - throw new ArgumentOutOfRangeException ("index"); + throw new IndexOutOfRangeException ("index"); + if (this.Rank > 1) + throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported.")); return GetValueImpl (index); } set { if (unchecked ((uint) index) >= unchecked ((uint) Length)) - throw new ArgumentOutOfRangeException ("index"); + throw new IndexOutOfRangeException ("index"); + if (this.Rank > 1) + throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported.")); SetValueImpl (value, index); } } @@ -300,15 +316,13 @@ namespace System int length = this.Length; for (int i = 0; i < length; i++) { - if (Object.Equals (value, this.GetValueImpl (i))) + if (Object.Equals (this.GetValueImpl (i), value)) return true; } return false; } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif int IList.IndexOf (object value) { if (this.Rank > 1) @@ -316,19 +330,16 @@ namespace System int length = this.Length; for (int i = 0; i < length; i++) { - if (Object.Equals (value, this.GetValueImpl (i))) + if (Object.Equals (this.GetValueImpl (i), value)) // array index may not be zero-based. // use lower bound return i + this.GetLowerBound (0); } - int retVal; unchecked { // lower bound may be MinValue - retVal = this.GetLowerBound (0) - 1; + return this.GetLowerBound (0) - 1; } - - return retVal; } void IList.Insert (int index, object value) @@ -353,17 +364,13 @@ namespace System [MethodImplAttribute (MethodImplOptions.InternalCall)] public extern int GetLength (int dimension); -#if NET_1_1 [ComVisible (false)] public long GetLongLength (int dimension) { return GetLength (dimension); } -#endif -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)] -#endif [MethodImplAttribute (MethodImplOptions.InternalCall)] public extern int GetLowerBound (int dimension); @@ -394,58 +401,36 @@ namespace System } } - public -#if !NET_2_0 - virtual -#endif - bool IsSynchronized { + public bool IsSynchronized { get { return false; } } - public -#if !NET_2_0 - virtual -#endif - object SyncRoot { + public object SyncRoot { get { return this; } } - public -#if !NET_2_0 - virtual -#endif - bool IsFixedSize { + public bool IsFixedSize { get { return true; } } - public -#if !NET_2_0 - virtual -#endif - bool IsReadOnly { + public bool IsReadOnly { get { return false; } } - public -#if !NET_2_0 - virtual -#endif - IEnumerator GetEnumerator () + public IEnumerator GetEnumerator () { return new SimpleEnumerator (this); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)] -#endif public int GetUpperBound (int dimension) { return GetLowerBound (dimension) + GetLength (dimension) - 1; @@ -474,7 +459,6 @@ namespace System return GetValue (ind); } -#if NET_1_1 [ComVisible (false)] public object GetValue (long index) { @@ -560,7 +544,6 @@ namespace System int[] ind = {(int) index1, (int) index2, (int) index3}; SetValue (value, ind); } -#endif public void SetValue (object value, int index) { @@ -621,34 +604,42 @@ namespace System elementType = elementType.UnderlyingSystemType; if (!elementType.IsSystemType) throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType"); + if (elementType.Equals (typeof (void))) + throw new NotSupportedException ("Array type can not be void"); + if (elementType.ContainsGenericParameters) + throw new NotSupportedException ("Array type can not be an open generic type"); return CreateInstanceImpl (elementType, lengths, bounds); } - public static Array CreateInstance (Type elementType, int[] lengths, int [] bounds) + public static Array CreateInstance (Type elementType, int[] lengths, int [] lowerBounds) { if (elementType == null) throw new ArgumentNullException ("elementType"); if (lengths == null) throw new ArgumentNullException ("lengths"); - if (bounds == null) - throw new ArgumentNullException ("bounds"); + if (lowerBounds == null) + throw new ArgumentNullException ("lowerBounds"); elementType = elementType.UnderlyingSystemType; if (!elementType.IsSystemType) throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType"); + if (elementType.Equals (typeof (void))) + throw new NotSupportedException ("Array type can not be void"); + if (elementType.ContainsGenericParameters) + throw new NotSupportedException ("Array type can not be an open generic type"); if (lengths.Length < 1) throw new ArgumentException (Locale.GetText ("Arrays must contain >= 1 elements.")); - if (lengths.Length != bounds.Length) + if (lengths.Length != lowerBounds.Length) throw new ArgumentException (Locale.GetText ("Arrays must be of same size.")); - for (int j = 0; j < bounds.Length; j ++) { + for (int j = 0; j < lowerBounds.Length; j ++) { if (lengths [j] < 0) throw new ArgumentOutOfRangeException ("lengths", Locale.GetText ( "Each value has to be >= 0.")); - if ((long)bounds [j] + (long)lengths [j] > (long)Int32.MaxValue) + if ((long)lowerBounds [j] + (long)lengths [j] > (long)Int32.MaxValue) throw new ArgumentOutOfRangeException ("lengths", Locale.GetText ( "Length + bound must not exceed Int32.MaxValue.")); } @@ -656,10 +647,9 @@ namespace System if (lengths.Length > 255) throw new TypeLoadException (); - return CreateInstanceImpl (elementType, lengths, bounds); + return CreateInstanceImpl (elementType, lengths, lowerBounds); } -#if NET_1_1 static int [] GetIntArray (long [] values) { int len = values.Length; @@ -677,37 +667,28 @@ namespace System public static Array CreateInstance (Type elementType, params long [] lengths) { -#if NET_2_0 if (lengths == null) throw new ArgumentNullException ("lengths"); -#endif return CreateInstance (elementType, GetIntArray (lengths)); } [ComVisible (false)] public object GetValue (params long [] indices) { -#if NET_2_0 if (indices == null) throw new ArgumentNullException ("indices"); -#endif return GetValue (GetIntArray (indices)); } [ComVisible (false)] public void SetValue (object value, params long [] indices) { -#if NET_2_0 if (indices == null) throw new ArgumentNullException ("indices"); -#endif SetValue (value, GetIntArray (indices)); } -#endif -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int BinarySearch (Array array, object value) { if (array == null) @@ -728,9 +709,7 @@ namespace System return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, null); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int BinarySearch (Array array, object value, IComparer comparer) { if (array == null) @@ -749,9 +728,7 @@ namespace System return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int BinarySearch (Array array, int index, int length, object value) { if (array == null) @@ -781,9 +758,7 @@ namespace System return DoBinarySearch (array, index, length, value, null); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer) { if (array == null) @@ -826,7 +801,9 @@ namespace System int iCmp = 0; try { while (iMin <= iMax) { - int iMid = (iMin + iMax) / 2; + // Be careful with overflow + // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html + int iMid = iMin + ((iMax - iMin) / 2); object elt = array.GetValueImpl (iMid); iCmp = comparer.Compare (elt, value); @@ -846,15 +823,13 @@ namespace System return ~iMin; } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)] -#endif public static void Clear (Array array, int index, int length) { if (array == null) throw new ArgumentNullException ("array"); if (length < 0) - throw new ArgumentOutOfRangeException ("length < 0"); + throw new IndexOutOfRangeException ("length < 0"); int low = array.GetLowerBound (0); if (index < low) @@ -872,15 +847,9 @@ namespace System static extern void ClearInternal (Array a, int index, int count); [MethodImplAttribute (MethodImplOptions.InternalCall)] - public -#if !NET_2_0 - virtual -#endif - extern object Clone (); + public extern object Clone (); -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Copy (Array sourceArray, Array destinationArray, int length) { // need these checks here because we are going to use @@ -895,9 +864,7 @@ namespace System destinationArray.GetLowerBound (0), length); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Copy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) { if (sourceArray == null) @@ -925,9 +892,15 @@ namespace System int dest_pos = destinationIndex - destinationArray.GetLowerBound (0); // re-ordered to avoid possible integer overflow - if (source_pos > sourceArray.Length - length || dest_pos > destinationArray.Length - length) + if (source_pos > sourceArray.Length - length) throw new ArgumentException ("length"); + if (dest_pos > destinationArray.Length - length) { + string msg = "Destination array was not long enough. Check " + + "destIndex and length, and the array's lower bounds"; + throw new ArgumentException (msg, string.Empty); + } + if (sourceArray.Rank != destinationArray.Rank) throw new RankException (Locale.GetText ("Arrays must be of same size.")); @@ -941,8 +914,7 @@ namespace System try { destinationArray.SetValueImpl (srcval, dest_pos + i); } catch { - if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) && - (src_type.Equals (typeof (Object)))) + if (src_type.Equals (typeof (Object))) throw new InvalidCastException (); else throw new ArrayTypeMismatchException (String.Format (Locale.GetText ( @@ -957,8 +929,7 @@ namespace System try { destinationArray.SetValueImpl (srcval, dest_pos + i); } catch { - if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) && - (src_type.Equals (typeof (Object)))) + if (src_type.Equals (typeof (Object))) throw new InvalidCastException (); else throw new ArrayTypeMismatchException (String.Format (Locale.GetText ( @@ -968,10 +939,7 @@ namespace System } } -#if NET_1_1 -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray, long destinationIndex, long length) { @@ -996,9 +964,7 @@ namespace System Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Copy (Array sourceArray, Array destinationArray, long length) { if (length < 0 || length > Int32.MaxValue) @@ -1007,11 +973,8 @@ namespace System Copy (sourceArray, destinationArray, (int) length); } -#endif -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int IndexOf (Array array, object value) { if (array == null) @@ -1020,9 +983,7 @@ namespace System return IndexOf (array, value, 0, array.Length); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int IndexOf (Array array, object value, int startIndex) { if (array == null) @@ -1031,9 +992,7 @@ namespace System return IndexOf (array, value, startIndex, array.Length - startIndex); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int IndexOf (Array array, object value, int startIndex, int count) { if (array == null) @@ -1048,7 +1007,7 @@ namespace System int max = startIndex + count; for (int i = startIndex; i < max; i++) { - if (Object.Equals (value, array.GetValueImpl (i))) + if (Object.Equals (array.GetValueImpl (i), value)) return i; } @@ -1062,20 +1021,18 @@ namespace System // in C# so no exception is trown by the moment. } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int LastIndexOf (Array array, object value) { if (array == null) throw new ArgumentNullException ("array"); + if (array.Length == 0) + return array.GetLowerBound (0) - 1; return LastIndexOf (array, value, array.Length - 1); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int LastIndexOf (Array array, object value, int startIndex) { if (array == null) @@ -1084,9 +1041,7 @@ namespace System return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] -#endif public static int LastIndexOf (Array array, object value, int startIndex, int count) { if (array == null) @@ -1095,22 +1050,25 @@ namespace System if (array.Rank > 1) throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); - if (count < 0 || startIndex < array.GetLowerBound (0) || - startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0)) + int lb = array.GetLowerBound (0); + // Empty arrays do not throw ArgumentOutOfRangeException + if (array.Length == 0) + return lb - 1; + + if (count < 0 || startIndex < lb || + startIndex > array.GetUpperBound (0) || startIndex - count + 1 < lb) throw new ArgumentOutOfRangeException (); for (int i = startIndex; i >= startIndex - count + 1; i--) { - if (Object.Equals (value, array.GetValueImpl (i))) + if (Object.Equals (array.GetValueImpl (i), value)) return i; } - return array.GetLowerBound (0) - 1; + return lb - 1; } -#if !BOOTSTRAP_WITH_OLDLIB /* delegate used to swap array elements */ delegate void Swapper (int i, int j); -#endif static Swapper get_swapper (Array array) { @@ -1124,21 +1082,7 @@ namespace System return new Swapper (array.slow_swapper); } -#if NET_2_0 - static Swapper get_swapper (T [] array) - { - if (array is int[]) - return new Swapper (array.int_swapper); - if (array is double[]) - return new Swapper (array.double_swapper); - - return new Swapper (array.obj_swapper); - } -#endif - -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Reverse (Array array) { if (array == null) @@ -1147,9 +1091,7 @@ namespace System Reverse (array, array.GetLowerBound (0), array.GetLength (0)); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Reverse (Array array, int index, int length) { if (array == null) @@ -1208,87 +1150,96 @@ namespace System } } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Sort (Array array) { - if (array == null) - throw new ArgumentNullException ("array"); - - Sort (array, null, array.GetLowerBound (0), array.GetLength (0), null); + Sort (array, (IComparer)null); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Sort (Array keys, Array items) { - if (keys == null) - throw new ArgumentNullException ("keys"); - - Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), null); + Sort (keys, items, (IComparer)null); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Sort (Array array, IComparer comparer) { if (array == null) throw new ArgumentNullException ("array"); - Sort (array, null, array.GetLowerBound (0), array.GetLength (0), comparer); + if (array.Rank > 1) + throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); + + SortImpl (array, null, array.GetLowerBound (0), array.GetLength (0), comparer); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Sort (Array array, int index, int length) { - Sort (array, null, index, length, null); + Sort (array, index, length, (IComparer)null); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Sort (Array keys, Array items, IComparer comparer) { + if (items == null) { + Sort (keys, comparer); + return; + } + if (keys == null) throw new ArgumentNullException ("keys"); - Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer); + if (keys.Rank > 1 || items.Rank > 1) + throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); + + SortImpl (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Sort (Array keys, Array items, int index, int length) { - Sort (keys, items, index, length, null); + Sort (keys, items, index, length, (IComparer)null); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif public static void Sort (Array array, int index, int length, IComparer comparer) { - Sort (array, null, index, length, comparer); + if (array == null) + throw new ArgumentNullException ("array"); + + if (array.Rank > 1) + throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); + + if (index < array.GetLowerBound (0)) + throw new ArgumentOutOfRangeException ("index"); + + if (length < 0) + throw new ArgumentOutOfRangeException ("length", Locale.GetText ( + "Value has to be >= 0.")); + + if (array.Length - (array.GetLowerBound (0) + index) < length) + throw new ArgumentException (); + + SortImpl (array, null, index, length, comparer); } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] -#endif - public static void Sort (Array keys, Array items, int index, int length, IComparer comparer) { + if (items == null) { + Sort (keys, index, length, comparer); + return; + } + if (keys == null) throw new ArgumentNullException ("keys"); - if (keys.Rank > 1 || (items != null && items.Rank > 1)) + if (keys.Rank > 1 || items.Rank > 1) throw new RankException (); - if (items != null && keys.GetLowerBound (0) != items.GetLowerBound (0)) + if (keys.GetLowerBound (0) != items.GetLowerBound (0)) throw new ArgumentException (); if (index < keys.GetLowerBound (0)) @@ -1298,37 +1249,64 @@ namespace System throw new ArgumentOutOfRangeException ("length", Locale.GetText ( "Value has to be >= 0.")); - if (keys.Length - (index + keys.GetLowerBound (0)) < length || (items != null && index > items.Length - length)) + if (keys.Length != items.Length || keys.Length - (index + keys.GetLowerBound (0)) < length) throw new ArgumentException (); + SortImpl (keys, items, index, length, comparer); + } + + private static void SortImpl (Array keys, Array items, int index, int length, IComparer comparer) + { if (length <= 1) return; + int low = index; + int high = index + length - 1; + +#if !BOOTSTRAP_BASIC if (comparer == null) { - Swapper iswapper; - if (items == null) - iswapper = null; - else - iswapper = get_swapper (items); - if (keys is double[]) { - combsort (keys as double[], index, length, iswapper); + if (keys is int[]) { + qsort (keys as int[], items as object[], low, high); return; } - if (keys is int[]) { - combsort (keys as int[], index, length, iswapper); + if (keys is long[]) { + qsort (keys as long[], items as object[], low, high); return; } if (keys is char[]) { - combsort (keys as char[], index, length, iswapper); + qsort (keys as char[], items as object[], low, high); + return; + } + if (keys is double[]) { + qsort (keys as double[], items as object[], low, high); + return; + } + if (keys is uint[]) { + qsort (keys as uint[], items as object[], low, high); + return; + } + if (keys is ulong[]) { + qsort (keys as ulong[], items as object[], low, high); + return; + } + if (keys is byte[]) { + qsort (keys as byte[], items as object[], low, high); return; } + if (keys is ushort[]) { + qsort (keys as ushort[], items as object[], low, high); + return; + } } +#endif + + low = MoveNullKeysToFront (keys, items, low, high, comparer == null); + if (low == high) + return; + try { - int low0 = index; - int high0 = index + length - 1; - qsort (keys, items, low0, high0, comparer); - } - catch (Exception e) { + qsort (keys, items, low, high, comparer); + } catch (Exception e) { throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e); } } @@ -1361,110 +1339,36 @@ namespace System array [j] = val; } - static int new_gap (int gap) - { - gap = (gap * 10) / 13; - if (gap == 9 || gap == 10) - return 11; - if (gap < 1) - return 1; - return gap; - } - - /* we use combsort because it's fast enough and very small, since we have - * several specialized versions here. - */ - static void combsort (double[] array, int start, int size, Swapper swap_items) - { - int gap = size; - while (true) { - gap = new_gap (gap); - bool swapped = false; - int end = start + size - gap; - for (int i = start; i < end; i++) { - int j = i + gap; - if (array [i] > array [j]) { - double val = array [i]; - array [i] = array [j]; - array [j] = val; - swapped = true; - if (swap_items != null) - swap_items (i, j); - } - } - if (gap == 1 && !swapped) - break; - } - } - - static void combsort (int[] array, int start, int size, Swapper swap_items) - { - int gap = size; - while (true) { - gap = new_gap (gap); - bool swapped = false; - int end = start + size - gap; - for (int i = start; i < end; i++) { - int j = i + gap; - if (array [i] > array [j]) { - int val = array [i]; - array [i] = array [j]; - array [j] = val; - swapped = true; - if (swap_items != null) - swap_items (i, j); - } - } - if (gap == 1 && !swapped) - break; - } - } - - static void combsort (char[] array, int start, int size, Swapper swap_items) - { - int gap = size; - while (true) { - gap = new_gap (gap); - bool swapped = false; - int end = start + size - gap; - for (int i = start; i < end; i++) { - int j = i + gap; - if (array [i] > array [j]) { - char val = array [i]; - array [i] = array [j]; - array [j] = val; - swapped = true; - if (swap_items != null) - swap_items (i, j); - } - } - if (gap == 1 && !swapped) - break; - } - } - private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer) { - if (low0 >= high0) - return; - int low = low0; int high = high0; - object objPivot = keys.GetValueImpl ((low + high) / 2); + // Be careful with overflows + int mid = low + ((high - low) / 2); + object keyPivot = keys.GetValueImpl (mid); + IComparable cmpPivot = keyPivot as IComparable; - while (low <= high) { + while (true) { // Move the walls in - while (low < high0 && compare (keys.GetValueImpl (low), objPivot, comparer) < 0) - ++low; - while (high > low0 && compare (objPivot, keys.GetValueImpl (high), comparer) < 0) - --high; + if (comparer != null) { + while (low < high0 && comparer.Compare (keyPivot, keys.GetValueImpl (low)) > 0) + ++low; + while (high > low0 && comparer.Compare (keyPivot, keys.GetValueImpl (high)) < 0) + --high; + } else { + while (low < high0 && cmpPivot.CompareTo (keys.GetValueImpl (low)) > 0) + ++low; + while (high > low0 && cmpPivot.CompareTo (keys.GetValueImpl (high)) < 0) + --high; + } if (low <= high) { swap (keys, items, low, high); ++low; --high; - } + } else + break; } if (low0 < high) @@ -1473,12 +1377,33 @@ namespace System qsort (keys, items, low, high0, comparer); } + private static int MoveNullKeysToFront (Array keys, Array items, int low, int high, bool ensureComparable) + { + // find first nun-null key + while (low < high && keys.GetValueImpl (low) == null) + low++; + + // move null keys to beginning of array, + // ensure that non-null keys implement IComparable + for (int i = low + 1; i <= high; i++) { + object obj = keys.GetValueImpl (i); + if (obj == null) { + swap (keys, items, low, i); + low++; + } else { + if (ensureComparable && !(obj is IComparable)) { + string msg = Locale.GetText ("No IComparable interface found for type '{0}'."); + throw new InvalidOperationException (String.Format (msg, obj.GetType ())); + } + } + } + return low; + } + private static void swap (Array keys, Array items, int i, int j) { - object tmp; - - tmp = keys.GetValueImpl (i); - keys.SetValueImpl (keys.GetValue (j), i); + object tmp = keys.GetValueImpl (i); + keys.SetValueImpl (keys.GetValueImpl (j), i); keys.SetValueImpl (tmp, j); if (items != null) { @@ -1488,82 +1413,83 @@ namespace System } } - private static int compare (object value1, object value2, IComparer comparer) - { - if (value1 == null) - return value2 == null ? 0 : -1; - else if (value2 == null) - return 1; - else if (comparer == null) - return ((IComparable) value1).CompareTo (value2); - else - return comparer.Compare (value1, value2); - } - -#if NET_2_0 - [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] + [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] public static void Sort (T [] array) { - if (array == null) - throw new ArgumentNullException ("array"); - - Sort (array, null, 0, array.Length, null); + Sort (array, (IComparer)null); } - [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] + [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] public static void Sort (TKey [] keys, TValue [] items) { - if (keys == null) - throw new ArgumentNullException ("keys"); - - Sort (keys, items, 0, keys.Length, null); + Sort (keys, items, (IComparer)null); } - [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] + [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] public static void Sort (T [] array, IComparer comparer) { if (array == null) throw new ArgumentNullException ("array"); - Sort (array, null, 0, array.Length, comparer); + SortImpl (array, null, 0, array.Length, comparer); } - [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] + [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] public static void Sort (TKey [] keys, TValue [] items, IComparer comparer) { + if (items == null) { + Sort (keys, comparer); + return; + } + if (keys == null) throw new ArgumentNullException ("keys"); + + if (keys.Length != items.Length) + throw new ArgumentException ("Length of keys and items does not match."); - Sort (keys, items, 0, keys.Length, comparer); + SortImpl (keys, items, 0, keys.Length, comparer); } - [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] + [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] public static void Sort (T [] array, int index, int length) { - if (array == null) - throw new ArgumentNullException ("array"); - - Sort (array, null, index, length, null); + Sort (array, index, length, (IComparer)null); } - [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] + [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] public static void Sort (TKey [] keys, TValue [] items, int index, int length) { - Sort (keys, items, index, length, null); + Sort (keys, items, index, length, (IComparer)null); } - [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] + [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] public static void Sort (T [] array, int index, int length, IComparer comparer) { if (array == null) throw new ArgumentNullException ("array"); - Sort (array, null, index, length, comparer); + if (index < 0) + throw new ArgumentOutOfRangeException ("index"); + + if (length < 0) + throw new ArgumentOutOfRangeException ("length", Locale.GetText ( + "Value has to be >= 0.")); + + if (index + length > array.Length) + throw new ArgumentException (); + + SortImpl (array, null, index, length, comparer); } - [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] + [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)] public static void Sort (TKey [] keys, TValue [] items, int index, int length, IComparer comparer) { + if (items == null) { + Sort (keys, index, length, comparer); + return; + } + if (keys == null) throw new ArgumentNullException ("keys"); @@ -1573,134 +1499,200 @@ namespace System if (length < 0) throw new ArgumentOutOfRangeException ("length"); - if (keys.Length - index < length - || (items != null && index > items.Length - length)) + if (keys.Length != items.Length || keys.Length - index < length) throw new ArgumentException (); - if (length <= 1) + SortImpl (keys, items, index, length, comparer); + } + + private static void SortImpl (TKey [] keys, TValue [] items, int index, int length, IComparer comparer) + { + if (keys.Length <= 1) return; + + int low = index; + int high = index + length - 1; // // Check for value types which can be sorted without Compare () method // if (comparer == null) { - Swapper iswapper; - if (items == null) - iswapper = null; - else - iswapper = get_swapper (items); - if (keys is double[]) { - combsort (keys as double[], index, length, iswapper); +#if !BOOTSTRAP_BASIC + switch (Type.GetTypeCode (typeof (TKey))) { + case TypeCode.Int32: + qsort (keys as Int32[], items, low, high); return; - } - if (keys is int[]) { - combsort (keys as int[], index, length, iswapper); + case TypeCode.Int64: + qsort (keys as Int64[], items, low, high); return; - } - if (keys is char[]) { - combsort (keys as char[], index, length, iswapper); + case TypeCode.Byte: + qsort (keys as byte[], items, low, high); + return; + case TypeCode.Char: + qsort (keys as char[], items, low, high); + return; + case TypeCode.DateTime: + qsort (keys as DateTime[], items, low, high); + return; + case TypeCode.Decimal: + qsort (keys as decimal[], items, low, high); + return; + case TypeCode.Double: + qsort (keys as double[], items, low, high); + return; + case TypeCode.Int16: + qsort (keys as Int16[], items, low, high); + return; + case TypeCode.SByte: + qsort (keys as SByte[], items, low, high); + return; + case TypeCode.Single: + qsort (keys as Single[], items, low, high); + return; + case TypeCode.UInt16: + qsort (keys as UInt16[], items, low, high); + return; + case TypeCode.UInt32: + qsort (keys as UInt32[], items, low, high); + return; + case TypeCode.UInt64: + qsort (keys as UInt64[], items, low, high); return; } - - // Use Comparer.Default instead - // comparer = Comparer.Default; +#endif + // Using Comparer adds a small overload, but with value types it + // helps us to not box them. + if (typeof (IComparable).IsAssignableFrom (typeof (TKey)) && + typeof (TKey).IsValueType) + comparer = Comparer.Default; } - + + low = MoveNullKeysToFront (keys, items, low, high, comparer == null); + + if (low == high) + return; + try { - int low0 = index; - int high0 = index + length - 1; - qsort (keys, items, low0, high0, comparer); - } - catch (Exception e) { + qsort (keys, items, low, high, comparer); + } catch (Exception e) { throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e); } } - + public static void Sort (T [] array, Comparison comparison) { if (array == null) throw new ArgumentNullException ("array"); - Sort (array, array.Length, comparison); - } - internal static void Sort (T [] array, int length, Comparison comparison) - { if (comparison == null) throw new ArgumentNullException ("comparison"); - if (length <= 1 || array.Length <= 1) + SortImpl (array, array.Length, comparison); + } + + // used by List.Sort (Comparison ) + internal static void SortImpl (T [] array, int length, Comparison comparison) + { + if (length <= 1) return; try { int low0 = 0; int high0 = length - 1; qsort (array, low0, high0, comparison); - } - catch (Exception e) { + } catch (InvalidOperationException) { + throw; + } catch (Exception e) { throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e); } } - - private static void qsort (K [] keys, V [] items, int low0, int high0, IComparer comparer) + + public static void qsort (T[] array, U[] items, int low0, int high0) where T : IComparable { - if (low0 >= high0) - return; - int low = low0; int high = high0; - K keyPivot = keys [(low + high) / 2]; + // Be careful with overflows + int mid = low + ((high - low) / 2); + var keyPivot = array [mid]; - while (low <= high) { + while (true) { // Move the walls in - //while (low < high0 && comparer.Compare (keys [low], keyPivot) < 0) - while (low < high0 && compare (keys [low], keyPivot, comparer) < 0) + while (low < high0 && keyPivot.CompareTo (array [low]) > 0) ++low; - //while (high > low0 && comparer.Compare (keyPivot, keys [high]) < 0) - while (high > low0 && compare (keyPivot, keys [high], comparer) < 0) + while (high > low0 && keyPivot.CompareTo (array [high]) < 0) --high; if (low <= high) { - swap (keys, items, low, high); + swap (array, items, low, high); ++low; --high; - } + } else + break; } if (low0 < high) - qsort (keys, items, low0, high, comparer); + qsort (array, items, low0, high); if (low < high0) - qsort (keys, items, low, high0, comparer); - } + qsort (array, items, low, high0); + } - private static int compare (T value1, T value2, IComparer comparer) + private static void qsort (K [] keys, V [] items, int low0, int high0, IComparer comparer) { - if (comparer != null) - return comparer.Compare (value1, value2); - else if (value1 == null) - return value2 == null ? 0 : -1; - else if (value2 == null) - return 1; - else if (value1 is IComparable) - return ((IComparable) value1).CompareTo (value2); - else if (value1 is IComparable) - return ((IComparable) value1).CompareTo (value2); + int low = low0; + int high = high0; + + // Be careful with overflows + int mid = low + ((high - low) / 2); + K keyPivot = keys [mid]; + IComparable genCmpPivot = keyPivot as IComparable; + IComparable cmpPivot = keyPivot as IComparable; - string msg = Locale.GetText ("No IComparable or IComparable interface found for type '{0}'."); - throw new InvalidOperationException (String.Format (msg, typeof (T))); + while (true) { + // Move the walls in + if (comparer != null) { + while (low < high0 && comparer.Compare (keyPivot, keys [low]) > 0) + ++low; + while (high > low0 && comparer.Compare (keyPivot, keys [high]) < 0) + --high; + } else { + if (genCmpPivot != null) { + while (low < high0 && genCmpPivot.CompareTo (keys [low]) > 0) + ++low; + while (high > low0 && genCmpPivot.CompareTo (keys [high]) < 0) + --high; + } else { + while (low < high0 && cmpPivot.CompareTo (keys [low]) > 0) + ++low; + while (high > low0 && cmpPivot.CompareTo (keys [high]) < 0) + --high; + } + } + + if (low <= high) { + swap (keys, items, low, high); + ++low; + --high; + } else + break; + } + + if (low0 < high) + qsort (keys, items, low0, high, comparer); + if (low < high0) + qsort (keys, items, low, high0, comparer); } private static void qsort (T [] array, int low0, int high0, Comparison comparison) { - if (low0 >= high0) - return; - int low = low0; int high = high0; - T keyPivot = array [(low + high) / 2]; + // Be careful with overflows + int mid = low + ((high - low) / 2); + T keyPivot = array [mid]; - while (low <= high) { + while (true) { // Move the walls in while (low < high0 && comparison (array [low], keyPivot) < 0) ++low; @@ -1711,7 +1703,8 @@ namespace System swap (array, low, high); ++low; --high; - } + } else + break; } if (low0 < high) @@ -1720,6 +1713,29 @@ namespace System qsort (array, low, high0, comparison); } + private static int MoveNullKeysToFront (K [] keys, V [] items, int low, int high, bool ensureComparable) + { + // find first nun-null key + while (low < high && keys [low] == null) + low++; + + // move null keys to beginning of array, + // ensure that non-null keys implement IComparable + for (int i = low + 1; i <= high; i++) { + K key = keys [i]; + if (key == null) { + swap (keys, items, low, i); + low++; + } else { + if (ensureComparable && !(key is IComparable) && !(key is IComparable)) { + string msg = Locale.GetText ("No IComparable or IComparable interface found for type '{0}'."); + throw new InvalidOperationException (String.Format (msg, key.GetType ())); + } + } + } + return low; + } + private static void swap (K [] keys, V [] items, int i, int j) { K tmp; @@ -1742,13 +1758,8 @@ namespace System array [i] = array [j]; array [j] = tmp; } -#endif - public -#if !NET_2_0 - virtual -#endif - void CopyTo (Array array, int index) + public void CopyTo (Array array, int index) { if (array == null) throw new ArgumentNullException ("array"); @@ -1758,7 +1769,9 @@ namespace System if (this.Rank > 1) throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0)) - throw new ArgumentException (); + throw new ArgumentException ("Destination array was not long " + + "enough. Check destIndex and length, and the array's " + + "lower bounds."); if (array.Rank > 1) throw new RankException (Locale.GetText ("Only single dimension arrays are supported.")); if (index < 0) @@ -1768,13 +1781,8 @@ namespace System Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0)); } -#if NET_1_1 [ComVisible (false)] - public -#if !NET_2_0 - virtual -#endif - void CopyTo (Array array, long index) + public void CopyTo (Array array, long index) { if (index < 0 || index > Int32.MaxValue) throw new ArgumentOutOfRangeException ("index", Locale.GetText ( @@ -1782,7 +1790,6 @@ namespace System CopyTo (array, (int) index); } -#endif internal class SimpleEnumerator : IEnumerator, ICloneable { @@ -1835,7 +1842,6 @@ namespace System } } -#if NET_2_0 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] public static void Resize (ref T [] array, int newSize) { @@ -1985,9 +1991,9 @@ namespace System } [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] - public static int BinarySearch (T [] array, int offset, int length, T value) + public static int BinarySearch (T [] array, int index, int length, T value) { - return BinarySearch (array, offset, length, value, null); + return BinarySearch (array, index, length, value, null); } [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)] @@ -2013,7 +2019,8 @@ namespace System int iCmp = 0; try { while (iMin <= iMax) { - int iMid = (iMin + iMax) / 2; + // Be careful with overflows + int iMid = iMin + ((iMax - iMin) / 2); iCmp = comparer.Compare (value, array [iMid]); if (iCmp == 0) @@ -2058,7 +2065,7 @@ namespace System int max = startIndex + count; EqualityComparer equalityComparer = EqualityComparer.Default; for (int i = startIndex; i < max; i++) { - if (equalityComparer.Equals (value, array [i])) + if (equalityComparer.Equals (array [i], value)) return i; } @@ -2070,6 +2077,8 @@ namespace System if (array == null) throw new ArgumentNullException ("array"); + if (array.Length == 0) + return -1; return LastIndexOf (array, value, array.Length - 1); } @@ -2086,12 +2095,13 @@ namespace System if (array == null) throw new ArgumentNullException ("array"); - if (count < 0 || startIndex > array.Length || startIndex - count + 1 < 0) + if (count < 0 || startIndex < array.GetLowerBound (0) || + startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0)) throw new ArgumentOutOfRangeException (); - + EqualityComparer equalityComparer = EqualityComparer.Default; for (int i = startIndex; i >= startIndex - count + 1; i--) { - if (equalityComparer.Equals (value, array [i])) + if (equalityComparer.Equals (array [i], value)) return i; } @@ -2172,22 +2182,18 @@ namespace System // The constrained copy should guarantee that if there is an exception thrown // during the copy, the destination array remains unchanged. // This is related to System.Runtime.Reliability.CER - public static void ConstrainedCopy (Array s, int s_i, Array d, int d_i, int c) + public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) { - Copy (s, s_i, d, d_i, c); + Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length); } -#endif -#if NET_2_0 class ArrayReadOnlyList : IList { T [] array; - bool is_value_type; public ArrayReadOnlyList (T [] array) { this.array = array; - is_value_type = typeof (T).IsValueType; } public T this [int index] { @@ -2258,16 +2264,10 @@ namespace System throw ReadOnlyError (); } - Exception ReadOnlyError () + static Exception ReadOnlyError () { return new NotSupportedException ("This collection is read-only."); } } -#endif } - -#if BOOTSTRAP_WITH_OLDLIB - /* delegate used to swap array elements, keep defined outside Array */ - delegate void Swapper (int i, int j); -#endif }