-//
+
// System.Array.cs
//
// Authors:
namespace System
{
+ [Serializable]
public abstract class Array : ICloneable, ICollection, IList, IEnumerable
{
// Constructor
- protected Array ()
+ private Array ()
{
/* empty */
}
}
// IList interface
- public object this [int index] {
+ object IList.this [int index] {
get {
return GetValueImpl (index);
}
}
bool IList.Contains (object value) {
+ if (this.Rank > 1)
+ throw new RankException ("Only single dimension arrays are supported.");
+
int length = this.Length;
for (int i = 0; i < length; i++) {
if (value.Equals (this.GetValueImpl (i)))
// InternalCall Methods
[MethodImplAttribute(MethodImplOptions.InternalCall)]
- public extern int GetRank ();
+ private extern int GetRank ();
[MethodImplAttribute(MethodImplOptions.InternalCall)]
public extern int GetLength (int dimension);
internal extern static Array CreateInstanceImpl(Type elementType, int[] lengths, int [] bounds);
// Properties
- public virtual int Count {
+ int ICollection.Count {
get {
return Length;
}
public static int BinarySearch (Array array, object value)
{
if (array == null)
- throw new ArgumentNullException ();
+ throw new ArgumentNullException("array");
+
+ if (array.Rank > 1)
+ throw new RankException();
+
+ if (!(value is IComparable))
+ throw new ArgumentException("value does not support IComparable");
return BinarySearch (array, array.GetLowerBound (0), array.GetLength (0),
value, null);
public static int BinarySearch (Array array, object value, IComparer comparer)
{
if (array == null)
- throw new ArgumentNullException ();
+ throw new ArgumentNullException("array");
+
+ if (array.Rank > 1)
+ throw new RankException();
+
+ if ((comparer == null) && !(value is IComparable))
+ throw new ArgumentException("comparer is null and value does not support IComparable");
return BinarySearch (array, array.GetLowerBound (0), array.GetLength (0),
value, comparer);
public static int BinarySearch (Array array, int index, int length, object value)
{
if (array == null)
- throw new ArgumentNullException ();
+ throw new ArgumentNullException("array");
+
+ if (array.Rank > 1)
+ throw new RankException();
+
+ if (index < array.GetLowerBound (0))
+ throw new ArgumentOutOfRangeException("index is less than the lower bound of array.");
+ if (length < 0)
+ throw new ArgumentOutOfRangeException("length is less than zero.");
+
+ if (index + length > array.GetLowerBound (0) + array.GetLength (0))
+ throw new ArgumentException("index and length do not specify a valid range in array.");
+ if (!(value is IComparable))
+ throw new ArgumentException("value does not support IComparable");
return BinarySearch (array, index, length, value, null);
}
IComparer comparer)
{
if (array == null)
- throw new ArgumentNullException ();
+ throw new ArgumentNullException ("array");
if (array.Rank > 1)
throw new RankException ();
- if (index < array.GetLowerBound (0) || length < 0)
- throw new ArgumentOutOfRangeException ();
-
- if (index + length > array.GetUpperBound (0) + 1)
- throw new ArgumentException ();
+ if (index < array.GetLowerBound (0))
+ throw new ArgumentOutOfRangeException("index is less than the lower bound of array.");
+ if (length < 0)
+ throw new ArgumentOutOfRangeException("length is less than zero.");
- if (comparer == null && !(value is IComparable))
- throw new ArgumentException ();
+ if (index + length > array.GetLowerBound (0) + array.GetLength (0))
+ throw new ArgumentException("index and length do not specify a valid range in array.");
- // FIXME: Throw an ArgumentException if comparer
- // is null and value is not of the same type as the
- // elements of array.
+ if ((comparer == null) && !(value is IComparable))
+ throw new ArgumentException("comparer is null and value does not support IComparable");
- // FIXME: This is implementing linear search. While it should do a binary one
- // FIXME: Should not throw exception when values are null
+ // cache this in case we need it
+ IComparable valueCompare = value as IComparable;
- for (int i = 0; i < length; i++)
+ int iMin = index;
+ int iMax = index + length;
+ int iCmp = 0;
+ try
{
- int result;
-
- if (comparer == null && !(array.GetValue(index + i) is IComparable))
- throw new ArgumentException ();
-
- if (comparer == null)
- result = (value as IComparable).CompareTo(array.GetValue(index + i));
- else
- result = comparer.Compare(value, array.GetValue(index + i));
+ // there's a subtle balance here between
+ // 1) the while condition
+ // 2) the rounding down of the '/ 2'
+ // 3) the asymetrical recursion
+ // 4) the fact that iMax starts beyond the end of the array
+ while (iMin < iMax)
+ {
+ int iMid = (iMin + iMax) / 2;
+ object elt = array.GetValueImpl (iMid);
+
+ // this order is from MSDN
+ if (comparer != null)
+ iCmp = comparer.Compare (value, elt);
+ else
+ {
+ IComparable eltCompare = elt as IComparable;
+ if (eltCompare != null)
+ iCmp = -eltCompare.CompareTo (value);
+ else
+ iCmp = valueCompare.CompareTo (elt);
+ }
- if (result == 0)
- return index + i;
- else if (result < 0)
- return ~(index + i);
+ if (iCmp == 0)
+ return iMid;
+ else if (iCmp < 0)
+ iMax = iMid;
+ else
+ iMin = iMid + 1; // compensate for the rounding down
+ }
+ }
+ catch (InvalidCastException e)
+ {
+ throw new ArgumentException ("array", e);
}
- return ~(index + length);
+ if (iCmp > 0)
+ return ~iMax;
+ else
+ return ~iMin;
}
public static void Clear (Array array, int index, int length)
for (int i = 0; i < length; i++)
{
- array.SetValue(null, index + i);
+ array.SetValueImpl(null, index + i);
}
}
public static void Copy (Array source, Array dest, int length)
{
- if (source == null || dest == null)
- throw new ArgumentNullException ();
+ // need these checks here because we are going to use
+ // GetLowerBound() on source and dest.
+ if (source == null)
+ throw new ArgumentNullException ("null");
+
+ if (dest == null)
+ throw new ArgumentNullException ("dest");
Copy (source, source.GetLowerBound (0), dest, dest.GetLowerBound (0), length);
}
public static void Copy (Array source, int source_idx, Array dest, int dest_idx, int length)
{
- if (source == null || dest == null)
- throw new ArgumentNullException ();
+ if (source == null)
+ throw new ArgumentNullException ("null");
+
+ if (dest == null)
+ throw new ArgumentNullException ("dest");
if (length < 0)
- throw new ArgumentOutOfRangeException ();
+ throw new ArgumentOutOfRangeException ("length");
+
+ if (source_idx < 0)
+ throw new ArgumentException ("source_idx");
+
+ if (dest_idx < 0)
+ throw new ArgumentException ("dest_idx");
int source_pos = source_idx - source.GetLowerBound (0);
int dest_pos = dest_idx - dest.GetLowerBound (0);
- if (source_idx < 0 || dest_idx < 0)
- throw new ArgumentException ();
if (source_pos + length > source.Length || dest_pos + length > dest.Length)
- throw new ArgumentException ();
+ throw new ArgumentException ("length");
if (source.Rank != dest.Rank)
throw new RankException ();
Type src_type = source.GetType ().GetElementType ();
Type dst_type = dest.GetType ().GetElementType ();
- if (src_type.IsValueType && (src_type == dst_type)) {
+ if (src_type == dst_type) {
FastCopy (source, source_pos, dest, dest_pos, length);
return;
}
- for (int i = 0; i < length; i++)
+ if (!Object.ReferenceEquals (source, dest) || source_pos > dest_pos)
{
- Object srcval = source.GetValueImpl (source_pos + i);
-
- bool errorThrown = false;
-
- try {
- dest.SetValueImpl (srcval, dest_pos + i);
- } catch {
- errorThrown = true;
+ for (int i = 0; i < length; i++)
+ {
+ Object srcval = source.GetValueImpl (source_pos + i);
+
+ try {
+ dest.SetValueImpl (srcval, dest_pos + i);
+ } catch {
+ if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) &&
+ (src_type.Equals (typeof (Object))))
+ throw new InvalidCastException ();
+ else
+ throw new ArrayTypeMismatchException (
+ String.Format ("(Types: source={0}; target={1})", src_type.FullName, dst_type.FullName));
+ }
+ }
+ }
+ else
+ {
+ for (int i = length - 1; i >= 0; i--)
+ {
+ Object srcval = source.GetValueImpl (source_pos + i);
+
+ try {
+ dest.SetValueImpl (srcval, dest_pos + i);
+ } catch {
+ if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) &&
+ (src_type.Equals (typeof (Object))))
+ throw new InvalidCastException ();
+ else
+ throw new ArrayTypeMismatchException (
+ String.Format ("(Types: source={0}; target={1})", src_type.FullName, dst_type.FullName));
+ }
}
-
- if (!errorThrown)
- continue;
-
- if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) &&
- (src_type.Equals (typeof (Object))))
- throw new InvalidCastException ();
- else
- throw new ArrayTypeMismatchException ();
}
}
for (int i = 0; i < length; i++)
{
- if (array.GetValue(index + i).Equals(value))
+ if (array.GetValueImpl(index + i).Equals(value))
return index + i;
}
for (int i = index; i >= index-length+1; i--)
{
- if (array.GetValue(i).Equals(value))
+ if (array.GetValueImpl(i).Equals(value))
return i;
}
{
object tmp;
- tmp = array.GetValue (index + i);
- array.SetValue(array.GetValue (index + length - i - 1), index + i);
- array.SetValue(tmp, index + length - i - 1);
+ tmp = array.GetValueImpl (index + i);
+ array.SetValueImpl(array.GetValueImpl (index + length - i - 1), index + i);
+ array.SetValueImpl(tmp, index + length - i - 1);
}
}
private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
{
- int pivot;
- int low = low0;
- int high = high0;
-
if (keys == null)
throw new ArgumentNullException ();
if (keys.Rank > 1 || (items != null && items.Rank > 1))
throw new RankException ();
- if (low >= high)
+ if (low0 >= high0)
return;
- pivot = (low + high) / 2;
+ int low = low0;
+ int high = high0;
- if (compare (keys.GetValue (low), keys.GetValue (pivot), comparer) > 0)
- swap (keys, items, low, pivot);
-
- if (compare (keys.GetValue (pivot), keys.GetValue (high), comparer) > 0)
- swap (keys, items, pivot, high);
+ object objPivot = keys.GetValueImpl ((low + high) / 2);
- while (low < high)
+ while (low <= high)
{
// Move the walls in
- while (low < high && compare (keys.GetValue (low), keys.GetValue (pivot), comparer) < 0)
- low++;
- while (low < high && compare (keys.GetValue (pivot), keys.GetValue (high), comparer) < 0)
- high--;
+ while (low < high0 && compare (keys.GetValueImpl (low), objPivot, comparer) < 0)
+ ++low;
+ while (high > low0 && compare (objPivot, keys.GetValueImpl (high), comparer) < 0)
+ --high;
- if (low < high)
+ if (low <= high)
{
swap (keys, items, low, high);
- low++;
- high--;
+ ++low;
+ --high;
}
}
- qsort (keys, items, low0, low - 1, comparer);
- qsort (keys, items, high + 1, high0, comparer);
+ if (low0 < high)
+ qsort (keys, items, low0, high, comparer);
+ if (low < high0)
+ qsort (keys, items, low, high0, comparer);
}
private static void swap (Array keys, Array items, int i, int j)
{
object tmp;
- tmp = keys.GetValue (i);
- keys.SetValue (keys.GetValue (j), i);
- keys.SetValue (tmp, j);
+ tmp = keys.GetValueImpl (i);
+ keys.SetValueImpl (keys.GetValue (j), i);
+ keys.SetValueImpl (tmp, j);
if (items != null)
{
- tmp = items.GetValue (i);
- items.SetValue (items.GetValue (j), i);
- items.SetValue (tmp, j);
+ tmp = items.GetValueImpl (i);
+ items.SetValueImpl (items.GetValueImpl (j), i);
+ items.SetValueImpl (tmp, j);
}
}