-//
+
// System.Array.cs
//
-// Author:
+// Authors:
// Joe Shaw (joe@ximian.com)
+// Martin Baulig (martin@gnome.org)
+// Dietmar Maurer (dietmar@ximian.com)
//
// (C) 2001 Ximian, Inc. http://www.ximian.com
//
namespace System
{
- [MonoTODO("This should implement IList and IEnumerable too")]
- public abstract class Array : ICloneable, ICollection
+ [Serializable]
+ public abstract class Array : ICloneable, ICollection, IList, IEnumerable
{
// Constructor
- protected Array ()
+ private Array ()
{
/* empty */
}
}
}
+ // IList interface
+ object IList.this [int index] {
+ get {
+ return GetValueImpl (index);
+ }
+ set {
+ SetValueImpl (value, index);
+ }
+ }
+
+ int IList.Add (object value) {
+ throw new NotSupportedException ();
+ }
+
+ void IList.Clear () {
+ Array.Clear (this, this.GetLowerBound(0), this.Length);
+ }
+
+ 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)))
+ return true;
+ }
+ return false;
+ }
+
+ int IList.IndexOf (object value) {
+ if (this.Rank > 1)
+ throw new RankException ();
+
+ int length = this.Length;
+ for (int i = 0; i < length; i++) {
+ if (value.Equals (this.GetValueImpl (i)))
+ // 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 retVal;
+ }
+
+ void IList.Insert (int index, object value) {
+ throw new NotSupportedException ();
+ }
+
+ void IList.Remove (object value) {
+ throw new NotSupportedException ();
+ }
+
+ void IList.RemoveAt (int index) {
+ throw new NotSupportedException ();
+ }
+
// InternalCall Methods
[MethodImplAttribute(MethodImplOptions.InternalCall)]
- public extern int GetRank ();
+ private extern int GetRank ();
[MethodImplAttribute(MethodImplOptions.InternalCall)]
public extern int GetLength (int dimension);
[MethodImplAttribute(MethodImplOptions.InternalCall)]
public extern void SetValue (object value, int[] idxs);
-
+
+ [MethodImplAttribute(MethodImplOptions.InternalCall)]
+ internal extern object GetValueImpl (int pos);
+
[MethodImplAttribute(MethodImplOptions.InternalCall)]
+ internal extern void SetValueImpl (object value, int pos);
+
+ [MethodImplAttribute(MethodImplOptions.InternalCall)]
+ internal extern static void FastCopy (Array source, int source_idx, Array dest, int dest_idx, int length);\r
+\r
+ [MethodImplAttribute(MethodImplOptions.InternalCall)]\r
internal extern static Array CreateInstanceImpl(Type elementType, int[] lengths, int [] bounds);
// Properties
- public virtual int Count {
+ int ICollection.Count {
get {
return Length;
}
}
}
- [MonoTODO]
public virtual IEnumerator GetEnumerator ()
{
- // FIXME
- return null;
+ return new SimpleEnumerator(this);
}
public int GetUpperBound (int dimension)
return GetValue (ind);
}
+ // This function is currently unused, but just in case we need it later on ... */
+ internal int IndexToPos (int[] idxs)
+ {
+ if (idxs == null)
+ throw new ArgumentNullException ();
+
+ if ((idxs.Rank != 1) || (idxs.Length != Rank))
+ throw new ArgumentException ();
+
+ if ((idxs [0] < GetLowerBound (0)) || (idxs [0] > GetUpperBound (0)))
+ throw new IndexOutOfRangeException();
+
+ int pos = idxs [0] - GetLowerBound (0);
+ for (int i = 1; i < Rank; i++) {
+ if ((idxs [i] < GetLowerBound (i)) || (idxs [i] > GetUpperBound (i)))
+ throw new IndexOutOfRangeException();
+
+ pos *= GetLength (i);
+ pos += idxs [i] - GetLowerBound (i);
+ }
+
+ return pos;
+ }
+
public void SetValue (object value, int idx)
{
int[] ind = new int [1];
public static Array CreateInstance(Type elementType, int[] lengths, int [] bounds)
{
- if(bounds == null)
+ if (bounds == null)
throw new ArgumentNullException("bounds");
return CreateInstanceImpl (elementType, lengths, bounds);
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));
-
- if (result == 0)
- return index + i;
- else if (result < 0)
- return ~(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 (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");
- // I don't know how to handle this ?
- if (source.Rank > 1 || dest.Rank > 1)
- throw new RankException ();
+ 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 == null || dest == null)
- throw new ArgumentNullException ();
+ if (source_idx < 0)
+ throw new ArgumentException ("source_idx");
- if (source_idx < source.GetLowerBound (0) ||
- source_idx + length > source.GetUpperBound (0) + 1||
- dest_idx < dest.GetLowerBound (0) || dest_idx + length > dest.GetUpperBound (0) + 1)
- throw new ArgumentException ();
+ if (dest_idx < 0)
+ throw new ArgumentException ("dest_idx");
- if (source.Rank != dest.Rank)
- throw new RankException ();
+ int source_pos = source_idx - source.GetLowerBound (0);
+ int dest_pos = dest_idx - dest.GetLowerBound (0);
+
+
+ if (source_pos + length > source.Length || dest_pos + length > dest.Length)
+ throw new ArgumentException ("length");
- // I don't know how to handle this ?
- if (source.Rank > 1 || dest.Rank > 1)
+ if (source.Rank != dest.Rank)
throw new RankException ();
- for (int i = 0; i < length; i++)
- {
- int srcindex = source.GetLowerBound (0) + i + source_idx;
- int dstindex = dest.GetLowerBound (0) + i + dest_idx;
+ Type src_type = source.GetType ().GetElementType ();
+ Type dst_type = dest.GetType ().GetElementType ();
- Object newval = source.GetValue(srcindex);
+ if (src_type == dst_type) {
+ FastCopy (source, source_pos, dest, dest_pos, length);
+ return;
+ }
- dest.SetValue(newval, dstindex);
+ if (!Object.ReferenceEquals (source, dest) || source_pos > dest_pos)
+ {
+ 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));
+ }
+ }
}
-
}
public static int IndexOf (Array array, object value)
if (array == null)
throw new ArgumentNullException ();
+ if (array.Rank > 1)
+ throw new RankException ();
+
if (length < 0 || index < array.GetLowerBound (0) ||
- index > array.GetUpperBound (0))
+ index+length-1 > array.GetUpperBound (0))
throw new ArgumentOutOfRangeException ();
for (int i = 0; i < length; i++)
{
- if (array.GetValue(index + i).Equals(value))
+ if (array.GetValueImpl(index + i).Equals(value))
return index + i;
}
if (array == null)
throw new ArgumentNullException ();
- return LastIndexOf (array, value, 0, array.Length);
+ return LastIndexOf (array, value, array.Length-1);
}
public static int LastIndexOf (Array array, object value, int index)
if (array == null)
throw new ArgumentNullException ();
- return LastIndexOf (array, value, index, array.Length - index);
+ return LastIndexOf (array, value, index, index-array.GetLowerBound(0)+1);
}
public static int LastIndexOf (Array array, object value, int index, int length)
if (array == null)
throw new ArgumentNullException ();
- if (length < 0 || index < array.GetLowerBound (0) ||
+ if (array.Rank > 1)
+ throw new RankException ();
+
+ if (length < 0 || index-length+1 < array.GetLowerBound (0) ||
index > array.GetUpperBound (0))
throw new ArgumentOutOfRangeException ();
- for (int i = length - 1; i >= 0; i--)
+ for (int i = index; i >= index-length+1; i--)
{
- if (array.GetValue(index + i).Equals(value))
- return index + i;
+ if (array.GetValueImpl(i).Equals(value))
+ return i;
}
return array.GetLowerBound (0) - 1;
{
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);
}
}
// but that's how the microsoft runtime does it.
if (this.Rank > 1)
throw new RankException ();
- if (index >= this.GetLength(0))
+ if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
throw new ArgumentException ();
if (array.Rank > 1)
throw new RankException ();
Copy (this, this.GetLowerBound(0), array, index, this.GetLength (0));
}
+
+ internal class SimpleEnumerator : IEnumerator {
+ Array enumeratee;
+ int currentpos;
+ int length;
+
+ public SimpleEnumerator (Array arrayToEnumerate) {
+ this.enumeratee = arrayToEnumerate;
+ this.currentpos = -1;
+ this.length = arrayToEnumerate.Length;
+ }
+
+ public object Current {
+ get {
+ // Exception messages based on MS implementation
+ if (currentpos < 0 ) {
+ throw new InvalidOperationException
+ ("Enumeration has not started");
+ }
+ if (currentpos >= length) {
+ throw new InvalidOperationException
+ ("Enumeration has already ended");
+ }
+ // Current should not increase the position. So no ++ over here.
+ return enumeratee.GetValueImpl(currentpos);
+ }
+ }
+
+ public bool MoveNext() {
+ //The docs say Current should throw an exception if last
+ //call to MoveNext returned false. This means currentpos
+ //should be set to length when returning false.
+ if (currentpos < length) {
+ currentpos++;
+ }
+ if(currentpos < length)
+ return true;
+ else
+ return false;
+ }
+
+ public void Reset() {
+ currentpos= -1;
+ }
+ }
}
}