mcs/class/corlib/System/Array.cs

   1 //
   2 // System.Array.cs
   3 //
   4 // Authors:
   5 //   Joe Shaw (joe@ximian.com)
   6 //   Martin Baulig (martin@gnome.org)
   7 //   Dietmar Maurer (dietmar@ximian.com)
   8 //   Gonzalo Paniagua Javier (gonzalo@ximian.com)
   9 //
  10 // (C) 2001-2003 Ximian, Inc.  http://www.ximian.com
  11 //
  12
  13 //
  14 // Copyright (C) 2004 Novell, Inc (http://www.novell.com)
  15 //
  16 // Permission is hereby granted, free of charge, to any person obtaining
  17 // a copy of this software and associated documentation files (the
  18 // "Software"), to deal in the Software without restriction, including
  19 // without limitation the rights to use, copy, modify, merge, publish,
  20 // distribute, sublicense, and/or sell copies of the Software, and to
  21 // permit persons to whom the Software is furnished to do so, subject to
  22 // the following conditions:
  23 //
  24 // The above copyright notice and this permission notice shall be
  25 // included in all copies or substantial portions of the Software.
  26 //
  27 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  28 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  29 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  30 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  31 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  32 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  33 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  34 //
  35
  36 using System.Collections;
  37 using System.Runtime.CompilerServices;
  38 using System.Runtime.InteropServices;
  39
  40 #if NET_2_0
  41 using System.Collections.Generic;
  42 using System.Runtime.ConstrainedExecution;
  43 #endif
  44
  45 namespace System
  46 {
  47
  48         [Serializable]
  49         [MonoTODO ("We are doing way to many double/triple exception checks for the overloaded functions")]
  50         [MonoTODO ("Sort overloads parameter checks are VERY inconsistent")]
  51         public abstract class Array : ICloneable, ICollection, IList, IEnumerable
  52         {
  53                 // Constructor
  54                 private Array ()
  55                 {
  56                 }
  57
  58                 // Properties
  59                 public int Length {
  60 #if NET_2_0
  61                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
  62 #endif
  63                         get {
  64                                 int length = this.GetLength (0);
  65
  66                                 for (int i = 1; i < this.Rank; i++) {
  67                                         length *= this.GetLength (i);
  68                                 }
  69                                 return length;
  70                         }
  71                 }
  72
  73 #if NET_1_1
  74                 [ComVisible (false)]
  75                 public long LongLength {
  76 #if NET_2_0
  77                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
  78 #endif
  79                         get { return Length; }
  80                 }
  81 #endif
  82
  83                 public int Rank {
  84 #if NET_2_0
  85                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
  86 #endif
  87                         get {
  88                                 return this.GetRank ();
  89                         }
  90                 }
  91
  92                 // IList interface
  93                 object IList.this [int index] {
  94                         get {
  95                                 if (unchecked ((uint) index) >= unchecked ((uint) Length))
  96                                         throw new ArgumentOutOfRangeException ("index");
  97                                 return GetValueImpl (index);
  98                         }
  99                         set {
 100                                 if (unchecked ((uint) index) >= unchecked ((uint) Length))
 101                                         throw new ArgumentOutOfRangeException ("index");
 102                                 SetValueImpl (value, index);
 103                         }
 104                 }
 105
 106                 int IList.Add (object value)
 107                 {
 108                         throw new NotSupportedException ();
 109                 }
 110
 111                 void IList.Clear ()
 112                 {
 113                         Array.Clear (this, this.GetLowerBound (0), this.Length);
 114                 }
 115
 116                 bool IList.Contains (object value)
 117                 {
 118                         if (this.Rank > 1)
 119                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 120
 121                         int length = this.Length;
 122                         for (int i = 0; i < length; i++) {
 123                                 if (Object.Equals (value, this.GetValueImpl (i)))
 124                                         return true;
 125                         }
 126                         return false;
 127                 }
 128
 129 #if NET_2_0
 130                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 131 #endif
 132                 int IList.IndexOf (object value)
 133                 {
 134                         if (this.Rank > 1)
 135                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 136
 137                         int length = this.Length;
 138                         for (int i = 0; i < length; i++) {
 139                                 if (Object.Equals (value, this.GetValueImpl (i)))
 140                                         // array index may not be zero-based.
 141                                         // use lower bound
 142                                         return i + this.GetLowerBound (0);
 143                         }
 144
 145                         int retVal;
 146                         unchecked {
 147                                 // lower bound may be MinValue
 148                                 retVal = this.GetLowerBound (0) - 1;
 149                         }
 150
 151                         return retVal;
 152                 }
 153
 154                 void IList.Insert (int index, object value)
 155                 {
 156                         throw new NotSupportedException ();
 157                 }
 158
 159                 void IList.Remove (object value)
 160                 {
 161                         throw new NotSupportedException ();
 162                 }
 163
 164                 void IList.RemoveAt (int index)
 165                 {
 166                         throw new NotSupportedException ();
 167                 }
 168
 169                 // InternalCall Methods
 170                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 171                 private extern int GetRank ();
 172
 173                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 174                 public extern int GetLength (int dimension);
 175
 176 #if NET_1_1
 177                 [ComVisible (false)]
 178                 public long GetLongLength (int dimension)
 179                 {
 180                         return GetLength (dimension);
 181                 }
 182 #endif
 183
 184 #if NET_2_0
 185                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 186 #endif
 187                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 188                 public extern int GetLowerBound (int dimension);
 189
 190                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 191                 public extern object GetValue (params int[] indices);
 192
 193                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 194                 public extern void SetValue (object value, params int[] indices);
 195
 196                 // CAUTION! No bounds checking!
 197                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 198                 internal extern object GetValueImpl (int pos);
 199
 200                 // CAUTION! No bounds checking!
 201                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 202                 internal extern void SetValueImpl (object value, int pos);
 203
 204                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 205                 internal extern static bool FastCopy (Array source, int source_idx, Array dest, int dest_idx, int length);
 206
 207                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 208                 internal extern static Array CreateInstanceImpl (Type elementType, int[] lengths, int[] bounds);
 209
 210                 // Properties
 211                 int ICollection.Count {
 212                         get {
 213                                 return Length;
 214                         }
 215                 }
 216
 217                 public virtual bool IsSynchronized {
 218                         get {
 219                                 return false;
 220                         }
 221                 }
 222
 223                 public virtual object SyncRoot {
 224                         get {
 225                                 return this;
 226                         }
 227                 }
 228
 229                 public virtual bool IsFixedSize {
 230                         get {
 231                                 return true;
 232                         }
 233                 }
 234
 235                 public virtual bool IsReadOnly {
 236                         get {
 237                                 return false;
 238                         }
 239                 }
 240
 241                 public virtual IEnumerator GetEnumerator ()
 242                 {
 243                         return new SimpleEnumerator (this);
 244                 }
 245
 246 #if NET_2_0
 247                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 248 #endif
 249                 public int GetUpperBound (int dimension)
 250                 {
 251                         return GetLowerBound (dimension) + GetLength (dimension) - 1;
 252                 }
 253
 254                 public object GetValue (int index)
 255                 {
 256                         if (Rank != 1)
 257                                 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
 258                         if (index < GetLowerBound (0) || index > GetUpperBound (0))
 259                                 throw new IndexOutOfRangeException (Locale.GetText (
 260                                         "Index has to be between upper and lower bound of the array."));
 261
 262                         return GetValueImpl (index - GetLowerBound (0));
 263                 }
 264
 265                 public object GetValue (int index1, int index2)
 266                 {
 267                         int[] ind = {index1, index2};
 268                         return GetValue (ind);
 269                 }
 270
 271                 public object GetValue (int index1, int index2, int index3)
 272                 {
 273                         int[] ind = {index1, index2, index3};
 274                         return GetValue (ind);
 275                 }
 276
 277 #if NET_1_1
 278                 [ComVisible (false)]
 279                 public object GetValue (long index)
 280                 {
 281                         if (index < 0 || index > Int32.MaxValue)
 282                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 283                                         "Value must be >= 0 and <= Int32.MaxValue."));
 284
 285                         return GetValue ((int) index);
 286                 }
 287
 288                 [ComVisible (false)]
 289                 public object GetValue (long index1, long index2)
 290                 {
 291                         if (index1 < 0 || index1 > Int32.MaxValue)
 292                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 293                                         "Value must be >= 0 and <= Int32.MaxValue."));
 294
 295                         if (index2 < 0 || index2 > Int32.MaxValue)
 296                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 297                                         "Value must be >= 0 and <= Int32.MaxValue."));
 298
 299                         return GetValue ((int) index1, (int) index2);
 300                 }
 301
 302                 [ComVisible (false)]
 303                 public object GetValue (long index1, long index2, long index3)
 304                 {
 305                         if (index1 < 0 || index1 > Int32.MaxValue)
 306                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 307                                         "Value must be >= 0 and <= Int32.MaxValue."));
 308
 309                         if (index2 < 0 || index2 > Int32.MaxValue)
 310                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 311                                         "Value must be >= 0 and <= Int32.MaxValue."));
 312
 313                         if (index3 < 0 || index3 > Int32.MaxValue)
 314                                 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
 315                                         "Value must be >= 0 and <= Int32.MaxValue."));
 316
 317                         return GetValue ((int) index1, (int) index2, (int) index3);
 318                 }
 319
 320                 [ComVisible (false)]
 321                 public void SetValue (object value, long index)
 322                 {
 323                         if (index < 0 || index > Int32.MaxValue)
 324                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 325                                         "Value must be >= 0 and <= Int32.MaxValue."));
 326
 327                         SetValue (value, (int) index);
 328                 }
 329
 330                 [ComVisible (false)]
 331                 public void SetValue (object value, long index1, long index2)
 332                 {
 333                         if (index1 < 0 || index1 > Int32.MaxValue)
 334                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 335                                         "Value must be >= 0 and <= Int32.MaxValue."));
 336
 337                         if (index2 < 0 || index2 > Int32.MaxValue)
 338                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 339                                         "Value must be >= 0 and <= Int32.MaxValue."));
 340
 341                         int[] ind = {(int) index1, (int) index2};
 342                         SetValue (value, ind);
 343                 }
 344
 345                 [ComVisible (false)]
 346                 public void SetValue (object value, long index1, long index2, long index3)
 347                 {
 348                         if (index1 < 0 || index1 > Int32.MaxValue)
 349                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 350                                         "Value must be >= 0 and <= Int32.MaxValue."));
 351
 352                         if (index2 < 0 || index2 > Int32.MaxValue)
 353                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 354                                         "Value must be >= 0 and <= Int32.MaxValue."));
 355
 356                         if (index3 < 0 || index3 > Int32.MaxValue)
 357                                 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
 358                                         "Value must be >= 0 and <= Int32.MaxValue."));
 359
 360                         int[] ind = {(int) index1, (int) index2, (int) index3};
 361                         SetValue (value, ind);
 362                 }
 363 #endif
 364
 365                 public void SetValue (object value, int index)
 366                 {
 367                         if (Rank != 1)
 368                                 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
 369                         if (index < GetLowerBound (0) || index > GetUpperBound (0))
 370                                 throw new IndexOutOfRangeException (Locale.GetText (
 371                                         "Index has to be >= lower bound and <= upper bound of the array."));
 372
 373                         SetValueImpl (value, index - GetLowerBound (0));
 374                 }
 375
 376                 public void SetValue (object value, int index1, int index2)
 377                 {
 378                         int[] ind = {index1, index2};
 379                         SetValue (value, ind);
 380                 }
 381
 382                 public void SetValue (object value, int index1, int index2, int index3)
 383                 {
 384                         int[] ind = {index1, index2, index3};
 385                         SetValue (value, ind);
 386                 }
 387
 388                 public static Array CreateInstance (Type elementType, int length)
 389                 {
 390                         int[] lengths = {length};
 391
 392                         return CreateInstance (elementType, lengths);
 393                 }
 394
 395                 public static Array CreateInstance (Type elementType, int length1, int length2)
 396                 {
 397                         int[] lengths = {length1, length2};
 398
 399                         return CreateInstance (elementType, lengths);
 400                 }
 401
 402                 public static Array CreateInstance (Type elementType, int length1, int length2, int length3)
 403                 {
 404                         int[] lengths = {length1, length2, length3};
 405
 406                         return CreateInstance (elementType, lengths);
 407                 }
 408
 409                 public static Array CreateInstance (Type elementType, int[] lengths)
 410                 {
 411                         if (elementType == null)
 412                                 throw new ArgumentNullException ("elementType");
 413                         if (lengths == null)
 414                                 throw new ArgumentNullException ("lengths");
 415
 416                         if (lengths.Length > 255)
 417                                 throw new TypeLoadException ();
 418
 419                         int[] bounds = null;
 420
 421                         elementType = elementType.UnderlyingSystemType;
 422                         if (!elementType.IsSystemType)
 423                                 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
 424
 425                         return CreateInstanceImpl (elementType, lengths, bounds);
 426                 }
 427
 428                 public static Array CreateInstance (Type elementType, int[] lengths, int [] bounds)
 429                 {
 430                         if (elementType == null)
 431                                 throw new ArgumentNullException ("elementType");
 432                         if (lengths == null)
 433                                 throw new ArgumentNullException ("lengths");
 434                         if (bounds == null)
 435                                 throw new ArgumentNullException ("bounds");
 436
 437                         elementType = elementType.UnderlyingSystemType;
 438                         if (!elementType.IsSystemType)
 439                                 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
 440
 441                         if (lengths.Length < 1)
 442                                 throw new ArgumentException (Locale.GetText ("Arrays must contain >= 1 elements."));
 443
 444                         if (lengths.Length != bounds.Length)
 445                                 throw new ArgumentException (Locale.GetText ("Arrays must be of same size."));
 446
 447                         for (int j = 0; j < bounds.Length; j ++) {
 448                                 if (lengths [j] < 0)
 449                                         throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
 450                                                 "Each value has to be >= 0."));
 451                                 if ((long)bounds [j] + (long)lengths [j] > (long)Int32.MaxValue)
 452                                         throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
 453                                                 "Length + bound must not exceed Int32.MaxValue."));
 454                         }
 455
 456                         if (lengths.Length > 255)
 457                                 throw new TypeLoadException ();
 458
 459                         return CreateInstanceImpl (elementType, lengths, bounds);
 460                 }
 461
 462 #if NET_1_1
 463                 static int [] GetIntArray (long [] values)
 464                 {
 465                         int len = values.Length;
 466                         int [] ints = new int [len];
 467                         for (int i = 0; i < len; i++) {
 468                                 long current = values [i];
 469                                 if (current < 0 || current > (long) Int32.MaxValue)
 470                                         throw new ArgumentOutOfRangeException ("values", Locale.GetText (
 471                                                 "Each value has to be >= 0 and <= Int32.MaxValue."));
 472
 473                                 ints [i] = (int) current;
 474                         }
 475                         return ints;
 476                 }
 477
 478                 public static Array CreateInstance (Type elementType, params long [] lengths)
 479                 {
 480                         if (lengths == null) {
 481                                 // LAMESPEC: Docs say we should throw a ArgumentNull, but .NET
 482                                 // 1.1 actually throws a NullReference.
 483                                 throw new NullReferenceException (Locale.GetText ("'lengths' cannot be null."));
 484                         }
 485                         return CreateInstance (elementType, GetIntArray (lengths));
 486                 }
 487
 488                 [ComVisible (false)]
 489                 public object GetValue (params long [] indices)
 490                 {
 491                         if (indices == null) {
 492                                 // LAMESPEC: Docs say we should throw a ArgumentNull, but .NET
 493                                 // 1.1 actually throws a NullReference.
 494                                 throw new NullReferenceException (Locale.GetText ("'indices' cannot be null."));
 495                         }
 496                         return GetValue (GetIntArray (indices));
 497                 }
 498
 499                 [ComVisible (false)]
 500                 public void SetValue (object value, params long [] indices)
 501                 {
 502                         if (indices == null) {
 503                                 // LAMESPEC: Docs say we should throw a ArgumentNull, but .NET
 504                                 // 1.1 actually throws a NullReference.
 505                                 throw new NullReferenceException (Locale.GetText ("'indices' cannot be null."));
 506                         }
 507                         SetValue (value, GetIntArray (indices));
 508                 }
 509 #endif
 510
 511 #if NET_2_0
 512                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 513 #endif
 514                 public static int BinarySearch (Array array, object value)
 515                 {
 516                         if (array == null)
 517                                 throw new ArgumentNullException ("array");
 518
 519                         if (value == null)
 520                                 return -1;
 521
 522                         if (array.Rank > 1)
 523                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 524
 525                         if (!(value is IComparable))
 526                                 throw new ArgumentException (Locale.GetText ("value does not support IComparable."));
 527
 528                         return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, null);
 529                 }
 530
 531 #if NET_2_0
 532         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 533 #endif
 534                 public static int BinarySearch (Array array, object value, IComparer comparer)
 535                 {
 536                         if (array == null)
 537                                 throw new ArgumentNullException ("array");
 538
 539                         if (array.Rank > 1)
 540                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 541
 542                         if ((comparer == null) && (value != null) && !(value is IComparable))
 543                                 throw new ArgumentException (Locale.GetText (
 544                                         "comparer is null and value does not support IComparable."));
 545
 546                         return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer);
 547                 }
 548
 549 #if NET_2_0
 550                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 551 #endif
 552                 public static int BinarySearch (Array array, int index, int length, object value)
 553                 {
 554                         if (array == null)
 555                                 throw new ArgumentNullException ("array");
 556
 557                         if (array.Rank > 1)
 558                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 559
 560                         if (index < array.GetLowerBound (0))
 561                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 562                                         "index is less than the lower bound of array."));
 563                         if (length < 0)
 564                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 565                                         "Value has to be >= 0."));
 566                         // re-ordered to avoid possible integer overflow
 567                         if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
 568                                 throw new ArgumentException (Locale.GetText (
 569                                         "index and length do not specify a valid range in array."));
 570                         if ((value != null) && (!(value is IComparable)))
 571                                 throw new ArgumentException (Locale.GetText (
 572                                         "value does not support IComparable"));
 573
 574                         return DoBinarySearch (array, index, length, value, null);
 575                 }
 576
 577 #if NET_2_0
 578                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 579 #endif
 580                 public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
 581                 {
 582                         if (array == null)
 583                                 throw new ArgumentNullException ("array");
 584
 585                         if (array.Rank > 1)
 586                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 587
 588                         if (index < array.GetLowerBound (0))
 589                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 590                                         "index is less than the lower bound of array."));
 591                         if (length < 0)
 592                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 593                                         "Value has to be >= 0."));
 594                         // re-ordered to avoid possible integer overflow
 595                         if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
 596                                 throw new ArgumentException (Locale.GetText (
 597                                         "index and length do not specify a valid range in array."));
 598
 599                         if ((comparer == null) && (value != null) && !(value is IComparable))
 600                                 throw new ArgumentException (Locale.GetText (
 601                                         "comparer is null and value does not support IComparable."));
 602
 603                         return DoBinarySearch (array, index, length, value, comparer);
 604                 }
 605
 606                 static int DoBinarySearch (Array array, int index, int length, object value, IComparer comparer)
 607                 {
 608                         // cache this in case we need it
 609                         if (comparer == null)
 610                                 comparer = Comparer.Default;
 611
 612                         int iMin = index;
 613                         // Comment from Tum (tum@veridicus.com):
 614                         // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
 615                         int iMax = index + length - 1;
 616                         int iCmp = 0;
 617                         try {
 618                                 while (iMin <= iMax) {
 619                                         int iMid = (iMin + iMax) / 2;
 620                                         object elt = array.GetValueImpl (iMid);
 621
 622                                         iCmp = comparer.Compare (elt, value);
 623
 624                                         if (iCmp == 0)
 625                                                 return iMid;
 626                                         else if (iCmp > 0)
 627                                                 iMax = iMid - 1;
 628                                         else
 629                                                 iMin = iMid + 1; // compensate for the rounding down
 630                                 }
 631                         }
 632                         catch (Exception e) {
 633                                 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
 634                         }
 635
 636                         return ~iMin;
 637                 }
 638
 639 #if NET_2_0
 640                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 641 #endif
 642                 public static void Clear (Array array, int index, int length)
 643                 {
 644                         if (array == null)
 645                                 throw new ArgumentNullException ("array");
 646                         if (length < 0)
 647                                 throw new ArgumentOutOfRangeException ("length < 0");
 648
 649                         int low = array.GetLowerBound (0);
 650                         if (index < low)
 651                                 throw new IndexOutOfRangeException ("index < lower bound");
 652                         index = index - low;
 653
 654                         // re-ordered to avoid possible integer overflow
 655                         if (index > array.Length - length)
 656                                 throw new IndexOutOfRangeException ("index + length > size");
 657
 658                         ClearInternal (array, index, length);
 659                 }
 660
 661                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 662                 static extern void ClearInternal (Array a, int index, int count);
 663
 664                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 665                 public virtual extern object Clone ();
 666
 667 #if NET_2_0
 668                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 669 #endif
 670                 public static void Copy (Array sourceArray, Array destinationArray, int length)
 671                 {
 672                         // need these checks here because we are going to use
 673                         // GetLowerBound() on source and dest.
 674                         if (sourceArray == null)
 675                                 throw new ArgumentNullException ("sourceArray");
 676
 677                         if (destinationArray == null)
 678                                 throw new ArgumentNullException ("destinationArray");
 679
 680                         Copy (sourceArray, sourceArray.GetLowerBound (0), destinationArray,
 681                                 destinationArray.GetLowerBound (0), length);
 682                 }
 683
 684 #if NET_2_0
 685                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 686 #endif
 687                 public static void Copy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
 688                 {
 689                         if (sourceArray == null)
 690                                 throw new ArgumentNullException ("sourceArray");
 691
 692                         if (destinationArray == null)
 693                                 throw new ArgumentNullException ("destinationArray");
 694
 695                         if (length < 0)
 696                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 697                                         "Value has to be >= 0."));;
 698
 699                         if (sourceIndex < 0)
 700                                 throw new ArgumentOutOfRangeException ("sourceIndex", Locale.GetText (
 701                                         "Value has to be >= 0."));;
 702
 703                         if (destinationIndex < 0)
 704                                 throw new ArgumentOutOfRangeException ("destinationIndex", Locale.GetText (
 705                                         "Value has to be >= 0."));;
 706
 707                         if (FastCopy (sourceArray, sourceIndex, destinationArray, destinationIndex, length))
 708                                 return;
 709
 710                         int source_pos = sourceIndex - sourceArray.GetLowerBound (0);
 711                         int dest_pos = destinationIndex - destinationArray.GetLowerBound (0);
 712
 713                         // re-ordered to avoid possible integer overflow
 714                         if (source_pos > sourceArray.Length - length || dest_pos > destinationArray.Length - length)
 715                                 throw new ArgumentException ("length");
 716
 717                         if (sourceArray.Rank != destinationArray.Rank)
 718                                 throw new RankException (Locale.GetText ("Arrays must be of same size."));
 719
 720                         Type src_type = sourceArray.GetType ().GetElementType ();
 721                         Type dst_type = destinationArray.GetType ().GetElementType ();
 722
 723                         if (!Object.ReferenceEquals (sourceArray, destinationArray) || source_pos > dest_pos) {
 724                                 for (int i = 0; i < length; i++) {
 725                                         Object srcval = sourceArray.GetValueImpl (source_pos + i);
 726
 727                                         try {
 728                                                 destinationArray.SetValueImpl (srcval, dest_pos + i);
 729                                         } catch {
 730                                                 if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) &&
 731                                                         (src_type.Equals (typeof (Object))))
 732                                                         throw new InvalidCastException ();
 733                                                 else
 734                                                         throw new ArrayTypeMismatchException (String.Format (Locale.GetText (
 735                                                                 "(Types: source={0};  target={1})"), src_type.FullName, dst_type.FullName));
 736                                         }
 737                                 }
 738                         }
 739                         else {
 740                                 for (int i = length - 1; i >= 0; i--) {
 741                                         Object srcval = sourceArray.GetValueImpl (source_pos + i);
 742
 743                                         try {
 744                                                 destinationArray.SetValueImpl (srcval, dest_pos + i);
 745                                         } catch {
 746                                                 if ((dst_type.IsValueType || dst_type.Equals (typeof (String))) &&
 747                                                         (src_type.Equals (typeof (Object))))
 748                                                         throw new InvalidCastException ();
 749                                                 else
 750                                                         throw new ArrayTypeMismatchException (String.Format (Locale.GetText (
 751                                                                 "(Types: source={0};  target={1})"), src_type.FullName, dst_type.FullName));
 752                                         }
 753                                 }
 754                         }
 755                 }
 756
 757 #if NET_1_1
 758 #if NET_2_0
 759                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 760 #endif
 761                 public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray,
 762                                          long destinationIndex, long length)
 763                 {
 764                         if (sourceArray == null)
 765                                 throw new ArgumentNullException ("sourceArray");
 766
 767                         if (destinationArray == null)
 768                                 throw new ArgumentNullException ("destinationArray");
 769
 770                         if (sourceIndex < Int32.MinValue || sourceIndex > Int32.MaxValue)
 771                                 throw new ArgumentOutOfRangeException ("sourceIndex",
 772                                         Locale.GetText ("Must be in the Int32 range."));
 773
 774                         if (destinationIndex < Int32.MinValue || destinationIndex > Int32.MaxValue)
 775                                 throw new ArgumentOutOfRangeException ("destinationIndex",
 776                                         Locale.GetText ("Must be in the Int32 range."));
 777
 778                         if (length < 0 || length > Int32.MaxValue)
 779                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 780                                         "Value must be >= 0 and <= Int32.MaxValue."));
 781
 782                         Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
 783                 }
 784
 785 #if NET_2_0
 786                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 787 #endif
 788                 public static void Copy (Array sourceArray, Array destinationArray, long length)
 789                 {
 790                         if (length < 0 || length > Int32.MaxValue)
 791                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 792                                         "Value must be >= 0 and <= Int32.MaxValue."));
 793
 794                         Copy (sourceArray, destinationArray, (int) length);
 795                 }
 796 #endif
 797
 798 #if NET_2_0
 799                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 800 #endif
 801                 public static int IndexOf (Array array, object value)
 802                 {
 803                         if (array == null)
 804                                 throw new ArgumentNullException ("array");
 805
 806                         return IndexOf (array, value, 0, array.Length);
 807                 }
 808
 809 #if NET_2_0
 810                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 811 #endif
 812                 public static int IndexOf (Array array, object value, int startIndex)
 813                 {
 814                         if (array == null)
 815                                 throw new ArgumentNullException ("array");
 816
 817                         return IndexOf (array, value, startIndex, array.Length - startIndex);
 818                 }
 819
 820 #if NET_2_0
 821                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 822 #endif
 823                 public static int IndexOf (Array array, object value, int startIndex, int count)
 824                 {
 825                         if (array == null)
 826                                 throw new ArgumentNullException ("array");
 827
 828                         if (array.Rank > 1)
 829                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 830
 831                         // re-ordered to avoid possible integer overflow
 832                         if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
 833                                 throw new ArgumentOutOfRangeException ();
 834
 835                         int max = startIndex + count;
 836                         for (int i = startIndex; i < max; i++) {
 837                                 if (Object.Equals (value, array.GetValueImpl (i)))
 838                                         return i;
 839                         }
 840
 841                         return array.GetLowerBound (0) - 1;
 842                 }
 843
 844                 [MonoTODO]
 845                 public void Initialize()
 846                 {
 847                         //FIXME: We would like to find a compiler that uses
 848                         // this method. It looks like this method do nothing
 849                         // in C# so no exception is trown by the moment.
 850                 }
 851
 852 #if NET_2_0
 853                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 854 #endif
 855                 public static int LastIndexOf (Array array, object value)
 856                 {
 857                         if (array == null)
 858                                 throw new ArgumentNullException ("array");
 859
 860                         return LastIndexOf (array, value, array.Length - 1);
 861                 }
 862
 863 #if NET_2_0
 864                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 865 #endif
 866                 public static int LastIndexOf (Array array, object value, int startIndex)
 867                 {
 868                         if (array == null)
 869                                 throw new ArgumentNullException ("array");
 870
 871                         return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1);
 872                 }
 873
 874 #if NET_2_0
 875                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 876 #endif
 877                 public static int LastIndexOf (Array array, object value, int startIndex, int count)
 878                 {
 879                         if (array == null)
 880                                 throw new ArgumentNullException ("array");
 881
 882                         if (array.Rank > 1)
 883                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 884
 885                         if (count < 0 || startIndex < array.GetLowerBound (0) ||
 886                                 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
 887                                 throw new ArgumentOutOfRangeException ();
 888
 889                         for (int i = startIndex; i >= startIndex - count + 1; i--) {
 890                                 if (Object.Equals (value, array.GetValueImpl (i)))
 891                                         return i;
 892                         }
 893
 894                         return array.GetLowerBound (0) - 1;
 895                 }
 896
 897 #if !BOOTSTRAP_WITH_OLDLIB
 898                 /* delegate used to swap array elements */
 899                 delegate void Swapper (int i, int j);
 900 #endif
 901
 902                 static Swapper get_swapper (Array array)
 903                 {
 904                         if (array is int[])
 905                                 return new Swapper (array.int_swapper);
 906                         if (array is double[])
 907                                 return new Swapper (array.double_swapper);
 908                         if (array is object[]) {
 909                                 return new Swapper (array.obj_swapper);
 910                         }
 911                         return new Swapper (array.slow_swapper);
 912                 }
 913
 914 #if NET_2_0
 915                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 916 #endif
 917                 public static void Reverse (Array array)
 918                 {
 919                         if (array == null)
 920                                 throw new ArgumentNullException ("array");
 921
 922                         Reverse (array, array.GetLowerBound (0), array.GetLength (0));
 923                 }
 924
 925 #if NET_2_0
 926                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 927 #endif
 928                 public static void Reverse (Array array, int index, int length)
 929                 {
 930                         if (array == null)
 931                                 throw new ArgumentNullException ("array");
 932
 933                         if (array.Rank > 1)
 934                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 935
 936                         if (index < array.GetLowerBound (0) || length < 0)
 937                                 throw new ArgumentOutOfRangeException ();
 938
 939                         // re-ordered to avoid possible integer overflow
 940                         if (index > array.GetUpperBound (0) + 1 - length)
 941                                 throw new ArgumentException ();
 942
 943                         int end = index + length - 1;
 944                         object[] oarray = array as object[];
 945                         if (oarray != null) {
 946                                 while (index < end) {
 947                                         object tmp = oarray [index];
 948                                         oarray [index] = oarray [end];
 949                                         oarray [end] = tmp;
 950                                         ++index;
 951                                         --end;
 952                                 }
 953                                 return;
 954                         }
 955                         int[] iarray = array as int[];
 956                         if (iarray != null) {
 957                                 while (index < end) {
 958                                         int tmp = iarray [index];
 959                                         iarray [index] = iarray [end];
 960                                         iarray [end] = tmp;
 961                                         ++index;
 962                                         --end;
 963                                 }
 964                                 return;
 965                         }
 966                         double[] darray = array as double[];
 967                         if (darray != null) {
 968                                 while (index < end) {
 969                                         double tmp = darray [index];
 970                                         darray [index] = darray [end];
 971                                         darray [end] = tmp;
 972                                         ++index;
 973                                         --end;
 974                                 }
 975                                 return;
 976                         }
 977                         // fallback
 978                         Swapper swapper = get_swapper (array);
 979                         while (index < end) {
 980                                 swapper (index, end);
 981                                 ++index;
 982                                 --end;
 983                         }
 984                 }
 985
 986 #if NET_2_0
 987                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 988 #endif
 989                 public static void Sort (Array array)
 990                 {
 991                         if (array == null)
 992                                 throw new ArgumentNullException ("array");
 993
 994                         Sort (array, null, array.GetLowerBound (0), array.GetLength (0), null);
 995                 }
 996
 997 #if NET_2_0
 998                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 999 #endif
1000                 public static void Sort (Array keys, Array items)
1001                 {
1002                         if (keys == null)
1003                                 throw new ArgumentNullException ("keys");
1004
1005                         Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), null);
1006                 }
1007
1008 #if NET_2_0
1009                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1010 #endif
1011                 public static void Sort (Array array, IComparer comparer)
1012                 {
1013                         if (array == null)
1014                                 throw new ArgumentNullException ("array");
1015
1016                         Sort (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
1017                 }
1018
1019 #if NET_2_0
1020                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1021 #endif
1022                 public static void Sort (Array array, int index, int length)
1023                 {
1024                         Sort (array, null, index, length, null);
1025                 }
1026
1027 #if NET_2_0
1028                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1029 #endif
1030                 public static void Sort (Array keys, Array items, IComparer comparer)
1031                 {
1032                         if (keys == null)
1033                                 throw new ArgumentNullException ("keys");
1034
1035                         Sort (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
1036                 }
1037
1038 #if NET_2_0
1039                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1040 #endif
1041                 public static void Sort (Array keys, Array items, int index, int length)
1042                 {
1043                         Sort (keys, items, index, length, null);
1044                 }
1045
1046 #if NET_2_0
1047                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1048 #endif
1049                 public static void Sort (Array array, int index, int length, IComparer comparer)
1050                 {
1051                         Sort (array, null, index, length, comparer);
1052                 }
1053
1054 #if NET_2_0
1055                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1056 #endif
1057
1058                 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
1059                 {
1060                         if (keys == null)
1061                                 throw new ArgumentNullException ("keys");
1062
1063                         if (keys.Rank > 1 || (items != null && items.Rank > 1))
1064                                 throw new RankException ();
1065
1066                         if (items != null && keys.GetLowerBound (0) != items.GetLowerBound (0))
1067                                 throw new ArgumentException ();
1068
1069                         if (index < keys.GetLowerBound (0))
1070                                 throw new ArgumentOutOfRangeException ("index");
1071
1072                         if (length < 0)
1073                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1074                                         "Value has to be >= 0."));
1075
1076                         if (keys.Length - (index + keys.GetLowerBound (0)) < length || (items != null && index > items.Length - length))
1077                                 throw new ArgumentException ();
1078
1079                         if (length <= 1)
1080                                 return;
1081
1082                         if (comparer == null) {
1083                                 Swapper iswapper;
1084                                 if (items == null)
1085                                         iswapper = null;
1086                                 else
1087                                         iswapper = get_swapper (items);
1088                                 if (keys is double[]) {
1089                                         combsort (keys as double[], index, length, iswapper);
1090                                         return;
1091                                 }
1092                                 if (keys is int[]) {
1093                                         combsort (keys as int[], index, length, iswapper);
1094                                         return;
1095                                 }
1096                                 if (keys is char[]) {
1097                                         combsort (keys as char[], index, length, iswapper);
1098                                         return;
1099                                 }
1100                         }
1101                         try {
1102                                 int low0 = index;
1103                                 int high0 = index + length - 1;
1104                                 qsort (keys, items, low0, high0, comparer);
1105                         }
1106                         catch (Exception e) {
1107                                 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1108                         }
1109                 }
1110
1111                 /* note, these are instance methods */
1112                 void int_swapper (int i, int j) {
1113                         int[] array = this as int[];
1114                         int val = array [i];
1115                         array [i] = array [j];
1116                         array [j] = val;
1117                 }
1118
1119                 void obj_swapper (int i, int j) {
1120                         object[] array = this as object[];
1121                         object val = array [i];
1122                         array [i] = array [j];
1123                         array [j] = val;
1124                 }
1125
1126                 void slow_swapper (int i, int j) {
1127                         object val = GetValueImpl (i);
1128                         SetValueImpl (GetValue (j), i);
1129                         SetValueImpl (val, j);
1130                 }
1131
1132                 void double_swapper (int i, int j) {
1133                         double[] array = this as double[];
1134                         double val = array [i];
1135                         array [i] = array [j];
1136                         array [j] = val;
1137                 }
1138
1139                 static int new_gap (int gap)
1140                 {
1141                         gap = (gap * 10) / 13;
1142                         if (gap == 9 || gap == 10)
1143                                 return 11;
1144                         if (gap < 1)
1145                                 return 1;
1146                         return gap;
1147                 }
1148
1149                 /* we use combsort because it's fast enough and very small, since we have
1150                  * several specialized versions here.
1151                  */
1152                 static void combsort (double[] array, int start, int size, Swapper swap_items)
1153                 {
1154                         int gap = size;
1155                         while (true) {
1156                                 gap = new_gap (gap);
1157                                 bool swapped = false;
1158                                 int end = start + size - gap;
1159                                 for (int i = start; i < end; i++) {
1160                                         int j = i + gap;
1161                                         if (array [i] > array [j]) {
1162                                                 double val = array [i];
1163                                                 array [i] = array [j];
1164                                                 array [j] = val;
1165                                                 swapped = true;
1166                                                 if (swap_items != null)
1167                                                         swap_items (i, j);
1168                                         }
1169                                 }
1170                                 if (gap == 1 && !swapped)
1171                                         break;
1172                         }
1173                 }
1174
1175                 static void combsort (int[] array, int start, int size, Swapper swap_items)
1176                 {
1177                         int gap = size;
1178                         while (true) {
1179                                 gap = new_gap (gap);
1180                                 bool swapped = false;
1181                                 int end = start + size - gap;
1182                                 for (int i = start; i < end; i++) {
1183                                         int j = i + gap;
1184                                         if (array [i] > array [j]) {
1185                                                 int val = array [i];
1186                                                 array [i] = array [j];
1187                                                 array [j] = val;
1188                                                 swapped = true;
1189                                                 if (swap_items != null)
1190                                                         swap_items (i, j);
1191                                         }
1192                                 }
1193                                 if (gap == 1 && !swapped)
1194                                         break;
1195                         }
1196                 }
1197
1198                 static void combsort (char[] array, int start, int size, Swapper swap_items)
1199                 {
1200                         int gap = size;
1201                         while (true) {
1202                                 gap = new_gap (gap);
1203                                 bool swapped = false;
1204                                 int end = start + size - gap;
1205                                 for (int i = start; i < end; i++) {
1206                                         int j = i + gap;
1207                                         if (array [i] > array [j]) {
1208                                                 char val = array [i];
1209                                                 array [i] = array [j];
1210                                                 array [j] = val;
1211                                                 swapped = true;
1212                                                 if (swap_items != null)
1213                                                         swap_items (i, j);
1214                                         }
1215                                 }
1216                                 if (gap == 1 && !swapped)
1217                                         break;
1218                         }
1219                 }
1220
1221                 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
1222                 {
1223                         if (low0 >= high0)
1224                                 return;
1225
1226                         int low = low0;
1227                         int high = high0;
1228
1229                         object objPivot = keys.GetValueImpl ((low + high) / 2);
1230
1231                         while (low <= high) {
1232                                 // Move the walls in
1233                                 while (low < high0 && compare (keys.GetValueImpl (low), objPivot, comparer) < 0)
1234                                         ++low;
1235                                 while (high > low0 && compare (objPivot, keys.GetValueImpl (high), comparer) < 0)
1236                                         --high;
1237
1238                                 if (low <= high) {
1239                                         swap (keys, items, low, high);
1240                                         ++low;
1241                                         --high;
1242                                 }
1243                         }
1244
1245                         if (low0 < high)
1246                                 qsort (keys, items, low0, high, comparer);
1247                         if (low < high0)
1248                                 qsort (keys, items, low, high0, comparer);
1249                 }
1250
1251                 private static void swap (Array keys, Array items, int i, int j)
1252                 {
1253                         object tmp;
1254
1255                         tmp = keys.GetValueImpl (i);
1256                         keys.SetValueImpl (keys.GetValue (j), i);
1257                         keys.SetValueImpl (tmp, j);
1258
1259                         if (items != null) {
1260                                 tmp = items.GetValueImpl (i);
1261                                 items.SetValueImpl (items.GetValueImpl (j), i);
1262                                 items.SetValueImpl (tmp, j);
1263                         }
1264                 }
1265
1266                 private static int compare (object value1, object value2, IComparer comparer)
1267                 {
1268                         if (value1 == null)
1269                                 return value2 == null ? 0 : -1;
1270                         else if (value2 == null)
1271                                 return 1;
1272                         else if (comparer == null)
1273                                 return ((IComparable) value1).CompareTo (value2);
1274                         else
1275                                 return comparer.Compare (value1, value2);
1276                 }
1277
1278                 public virtual void CopyTo (Array array, int index)
1279                 {
1280                         if (array == null)
1281                                 throw new ArgumentNullException ("array");
1282
1283                         // The order of these exception checks may look strange,
1284                         // but that's how the microsoft runtime does it.
1285                         if (this.Rank > 1)
1286                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1287                         if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
1288                                 throw new ArgumentException ();
1289                         if (array.Rank > 1)
1290                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1291                         if (index < 0)
1292                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
1293                                         "Value has to be >= 0."));
1294
1295                         Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
1296                 }
1297
1298 #if NET_1_1
1299                 [ComVisible (false)]
1300                 public virtual void CopyTo (Array array, long index)
1301                 {
1302                         if (index < 0 || index > Int32.MaxValue)
1303                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
1304                                         "Value must be >= 0 and <= Int32.MaxValue."));
1305
1306                         CopyTo (array, (int) index);
1307                 }
1308 #endif
1309
1310                 internal class SimpleEnumerator : IEnumerator, ICloneable
1311                 {
1312                         Array enumeratee;
1313                         int currentpos;
1314                         int length;
1315
1316                         public SimpleEnumerator (Array arrayToEnumerate)
1317                         {
1318                                 this.enumeratee = arrayToEnumerate;
1319                                 this.currentpos = -1;
1320                                 this.length = arrayToEnumerate.Length;
1321                         }
1322
1323                         public object Current {
1324                                 get {
1325                                         // Exception messages based on MS implementation
1326                                         if (currentpos < 0 )
1327                                                 throw new InvalidOperationException (Locale.GetText (
1328                                                         "Enumeration has not started."));
1329                                         if  (currentpos >= length)
1330                                                 throw new InvalidOperationException (Locale.GetText (
1331                                                         "Enumeration has already ended"));
1332                                         // Current should not increase the position. So no ++ over here.
1333                                         return enumeratee.GetValueImpl (currentpos);
1334                                 }
1335                         }
1336
1337                         public bool MoveNext()
1338                         {
1339                                 //The docs say Current should throw an exception if last
1340                                 //call to MoveNext returned false. This means currentpos
1341                                 //should be set to length when returning false.
1342                                 if (currentpos < length)
1343                                         currentpos++;
1344                                 if(currentpos < length)
1345                                         return true;
1346                                 else
1347                                         return false;
1348                         }
1349
1350                         public void Reset()
1351                         {
1352                                 currentpos = -1;
1353                         }
1354
1355                         public object Clone ()
1356                         {
1357                                 return MemberwiseClone ();
1358                         }
1359                 }
1360
1361 #if NET_2_0
1362                 public static void Resize<T> (ref T [] array, int newSize)
1363                 {
1364                         Resize<T> (ref array, array == null ? 0 : array.Length, newSize);
1365                 }
1366
1367                 internal static void Resize<T> (ref T[] array, int length, int newSize)
1368                 {
1369                         if (newSize < 0)
1370                                 throw new ArgumentOutOfRangeException ();
1371
1372                         if (array == null) {
1373                                 array = new T [newSize];
1374                                 return;
1375                         }
1376
1377                         if (array.Length == newSize)
1378                                 return;
1379
1380                         T [] a = new T [newSize];
1381                         Array.Copy (array, a, Math.Min (newSize, length));
1382                         array = a;
1383                 }
1384
1385                 public static bool TrueForAll <T> (T [] array, Predicate <T> match)
1386                 {
1387                         if (array == null)
1388                                 throw new ArgumentNullException ("array");
1389                         if (match == null)
1390                                 throw new ArgumentNullException ("match");
1391
1392                         foreach (T t in array)
1393                                 if (! match (t))
1394                                         return false;
1395
1396                         return true;
1397                 }
1398
1399                 public static void ForEach<T> (T [] array, Action <T> action)
1400                 {
1401                         if (array == null)
1402                                 throw new ArgumentNullException ("array");
1403                         if (action == null)
1404                                 throw new ArgumentNullException ("action");
1405
1406                         foreach (T t in array)
1407                                 action (t);
1408                 }
1409
1410                 public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
1411                 {
1412                         if (array == null)
1413                                 throw new ArgumentNullException ("array");
1414                         if (converter == null)
1415                                 throw new ArgumentNullException ("converter");
1416
1417                         TOutput [] output = new TOutput [array.Length];
1418                         for (int i = 0; i < array.Length; i ++)
1419                                 output [i] = converter (array [i]);
1420
1421                         return output;
1422                 }
1423
1424                 public static int FindLastIndex<T> (T [] array, Predicate <T> match)
1425                 {
1426                         if (array == null)
1427                                 throw new ArgumentNullException ("array");
1428
1429                         return FindLastIndex<T> (array, 0, array.Length, match);
1430                 }
1431
1432                 public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
1433                 {
1434                         if (array == null)
1435                                 throw new ArgumentNullException ();
1436
1437                         return FindLastIndex<T> (array, startIndex, array.Length - startIndex, match);
1438                 }
1439
1440                 public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
1441                 {
1442                         if (array == null)
1443                                 throw new ArgumentNullException ("array");
1444                         if (match == null)
1445                                 throw new ArgumentNullException ("match");
1446
1447                         if (startIndex > array.Length || startIndex + count > array.Length)
1448                                 throw new ArgumentOutOfRangeException ();
1449
1450                         for (int i = startIndex + count - 1; i >= startIndex; i--)
1451                                 if (match (array [i]))
1452                                         return i;
1453
1454                         return -1;
1455                 }
1456
1457                 public static int FindIndex<T> (T [] array, Predicate<T> match)
1458                 {
1459                         if (array == null)
1460                                 throw new ArgumentNullException ("array");
1461
1462                         return FindIndex<T> (array, 0, array.Length, match);
1463                 }
1464
1465                 public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
1466                 {
1467                         if (array == null)
1468                                 throw new ArgumentNullException ("array");
1469
1470                         return FindIndex<T> (array, startIndex, array.Length - startIndex, match);
1471                 }
1472
1473                 public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
1474                 {
1475                         if (array == null)
1476                                 throw new ArgumentNullException ("array");
1477
1478                         if (match == null)
1479                                 throw new ArgumentNullException ("match");
1480
1481                         if (startIndex > array.Length || startIndex + count > array.Length)
1482                                 throw new ArgumentOutOfRangeException ();
1483
1484                         for (int i = startIndex; i < startIndex + count; i ++)
1485                                 if (match (array [i]))
1486                                         return i;
1487
1488                         return -1;
1489                 }
1490
1491                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1492                 public static int BinarySearch<T> (T [] array, T value)
1493                 {
1494                         if (array == null)
1495                                 throw new ArgumentNullException ("array");
1496
1497                         return BinarySearch<T> (array, 0, array.Length, value, null);
1498                 }
1499
1500                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1501                 public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
1502                 {
1503                         if (array == null)
1504                                 throw new ArgumentNullException ("array");
1505
1506                         return BinarySearch<T> (array, 0, array.Length, value, comparer);
1507                 }
1508
1509                 public static int BinarySearch<T> (T [] array, int offset, int length, T value)
1510                 {
1511                         return BinarySearch<T> (array, offset, length, value, null);
1512                 }
1513
1514                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1515                 public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
1516                 {
1517                         if (array == null)
1518                                 throw new ArgumentNullException ("array");
1519                         if (index < 0)
1520                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
1521                                         "index is less than the lower bound of array."));
1522                         if (length < 0)
1523                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1524                                         "Value has to be >= 0."));
1525                         // re-ordered to avoid possible integer overflow
1526                         if (index > array.Length - length)
1527                                 throw new ArgumentException (Locale.GetText (
1528                                         "index and length do not specify a valid range in array."));
1529                         if (comparer == null)
1530                                 comparer = Comparer <T>.Default;
1531
1532                         int iMin = index;
1533                         int iMax = index + length - 1;
1534                         int iCmp = 0;
1535                         try {
1536                                 while (iMin <= iMax) {
1537                                         int iMid = (iMin + iMax) / 2;
1538                                         iCmp = comparer.Compare (value, array [iMid]);
1539
1540                                         if (iCmp == 0)
1541                                                 return iMid;
1542                                         else if (iCmp < 0)
1543                                                 iMax = iMid - 1;
1544                                         else
1545                                                 iMin = iMid + 1; // compensate for the rounding down
1546                                 }
1547                         } catch (Exception e) {
1548                                 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
1549                         }
1550
1551                         return ~iMin;
1552                 }
1553
1554                 public static int IndexOf<T> (T [] array, T value)
1555                 {
1556                         if (array == null)
1557                                 throw new ArgumentNullException ("array");
1558
1559                         return IndexOf (array, value, 0, array.Length);
1560                 }
1561
1562                 public static int IndexOf<T> (T [] array, T value, int startIndex)
1563                 {
1564                         if (array == null)
1565                                 throw new ArgumentNullException ("array");
1566
1567                         return IndexOf (array, value, startIndex, array.Length - startIndex);
1568                 }
1569
1570                 public static int IndexOf<T> (T [] array, T value, int startIndex, int count)
1571                 {
1572                         if (array == null)
1573                                 throw new ArgumentNullException ("array");
1574
1575                         // re-ordered to avoid possible integer overflow
1576                         if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
1577                                 throw new ArgumentOutOfRangeException ();
1578
1579                         int max = startIndex + count;
1580                         for (int i = startIndex; i < max; i++) {
1581                                 if (Object.Equals (value, array [i]))
1582                                         return i;
1583                         }
1584
1585                         return -1;
1586                 }
1587
1588                 public static int LastIndexOf<T> (T [] array, T value)
1589                 {
1590                         if (array == null)
1591                                 throw new ArgumentNullException ("array");
1592
1593                         return LastIndexOf (array, value, array.Length - 1);
1594                 }
1595
1596                 public static int LastIndexOf<T> (T [] array, T value, int startIndex)
1597                 {
1598                         if (array == null)
1599                                 throw new ArgumentNullException ("array");
1600
1601                         return LastIndexOf (array, value, startIndex, startIndex + 1);
1602                 }
1603
1604                 public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
1605                 {
1606                         if (array == null)
1607                                 throw new ArgumentNullException ("array");
1608
1609                         if (count < 0 || startIndex > array.Length || startIndex - count + 1 < 0)
1610                                 throw new ArgumentOutOfRangeException ();
1611
1612                         for (int i = startIndex; i >= startIndex - count + 1; i--) {
1613                                 if (Object.Equals (value, array [i]))
1614                                         return i;
1615                         }
1616
1617                         return -1;
1618                 }
1619
1620                 public static T [] FindAll<T> (T [] array, Predicate <T> match)
1621                 {
1622                         if (array == null)
1623                                 throw new ArgumentNullException ("array");
1624
1625                         if (match == null)
1626                                 throw new ArgumentNullException ("match");
1627
1628                         int pos = 0;
1629                         T [] d = new T [array.Length];
1630                         foreach (T t in array)
1631                                 if (match (t))
1632                                         d [pos++] = t;
1633
1634                         Resize <T> (ref d, pos);
1635                         return d;
1636                 }
1637
1638                 public static bool Exists<T> (T [] array, Predicate <T> match)
1639                 {
1640                         if (array == null)
1641                                 throw new ArgumentNullException ("array");
1642
1643                         if (match == null)
1644                                 throw new ArgumentNullException ("match");
1645
1646                         foreach (T t in array)
1647                                 if (match (t))
1648                                         return true;
1649                         return false;
1650                 }
1651
1652                 public static IList<T> AsReadOnly<T> (T[] array)
1653                 {
1654                         if (array == null)
1655                                 throw new ArgumentNullException ("array");
1656                         return new ReadOnlyArray<T> (array);
1657                 }
1658
1659                 public static Nullable<T> Find<T> (T [] array, Predicate<T> match)
1660                 {
1661                         if (array == null)
1662                                 throw new ArgumentNullException ("array");
1663
1664                         if (match == null)
1665                                 throw new ArgumentNullException ("match");
1666
1667                         foreach (T t in array)
1668                                 if (match (t))
1669                                         return new Nullable <T> (t);
1670
1671                         return default (Nullable <T>);
1672                 }
1673
1674                 public static Nullable<T> FindLast<T> (T [] array, Predicate <T> match)
1675                 {
1676                         if (array == null)
1677                                 throw new ArgumentNullException ("array");
1678
1679                         if (match == null)
1680                                 throw new ArgumentNullException ("match");
1681
1682                         for (int i = array.Length - 1; i >= 0; i--)
1683                                 if (match (array [i]))
1684                                         return new Nullable <T> (array [i]);
1685
1686                         return default (Nullable <T>);
1687                 }
1688
1689                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
1690                 //
1691                 // The constrained copy should guarantee that if there is an exception thrown
1692                 // during the copy, the destination array remains unchanged.
1693                 // This is related to System.Runtime.Reliability.CER
1694                 public static void ConstrainedCopy (Array s, int s_i, Array d, int d_i, int c)
1695                 {
1696                         Copy (s, s_i, d, d_i, c);
1697                 }
1698 #endif
1699
1700 #if NET_2_0
1701                 //
1702                 // This is used internally by the runtime to represent arrays; see #74953.
1703                 //
1704                 // Note that you normally can't derive a class from System.Array (CS0644),
1705                 // but GMCS makes an exception here for all classes which are nested inside
1706                 // System.Array.
1707                 //
1708                 internal class InternalArray<T> : Array, IList<T>
1709                 {
1710                         new public IEnumerator<T> GetEnumerator ()
1711                         {
1712                                 return new InternalEnumerator (this);
1713                         }
1714
1715                         public int Count {
1716                                 get {
1717                                         return Length;
1718                                 }
1719                         }
1720
1721                         bool ICollection<T>.IsReadOnly {
1722                                 get {
1723                                         return true;
1724                                 }
1725                         }
1726
1727                         void ICollection<T>.Clear ()
1728                         {
1729                                 throw new NotSupportedException ("Collection is read-only");
1730                         }
1731
1732                         void ICollection<T>.Add (T item)
1733                         {
1734                                 throw new NotSupportedException ("Collection is read-only");
1735                         }
1736
1737                         bool ICollection<T>.Remove (T item)
1738                         {
1739                                 throw new NotSupportedException ("Collection is read-only");
1740                         }
1741
1742                         public bool Contains (T item)
1743                         {
1744                                 if (this.Rank > 1)
1745                                         throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1746
1747                                 int length = this.Length;
1748                                 for (int i = 0; i < length; i++) {
1749                                         T value;
1750                                         GetGenericValueImpl (i, out value);
1751                                         if (item.Equals (value))
1752                                                 return true;
1753                                 }
1754
1755                                 return false;
1756                         }
1757
1758                         public void CopyTo (T[] array, int index)
1759                         {
1760                                 if (array == null)
1761                                         throw new ArgumentNullException ("array");
1762
1763                                 // The order of these exception checks may look strange,
1764                                 // but that's how the microsoft runtime does it.
1765                                 if (this.Rank > 1)
1766                                         throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1767                                 if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
1768                                         throw new ArgumentException ();
1769                                 if (array.Rank > 1)
1770                                         throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1771                                 if (index < 0)
1772                                         throw new ArgumentOutOfRangeException (
1773                                                 "index", Locale.GetText ("Value has to be >= 0."));
1774
1775                                 Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
1776                         }
1777
1778                         new public T this [int index] {
1779                                 get {
1780                                         if (unchecked ((uint) index) >= unchecked ((uint) Length))
1781                                                 throw new ArgumentOutOfRangeException ("index");
1782
1783                                         T value;
1784                                         GetGenericValueImpl (index, out value);
1785                                         return value;
1786                                 }
1787
1788                                 set {
1789                                         throw new NotSupportedException ("Collection is read-only");
1790                                 }
1791                         }
1792
1793                         void IList<T>.Insert (int index, T item)
1794                         {
1795                                 throw new NotSupportedException ("Collection is read-only");
1796                         }
1797
1798                         void IList<T>.RemoveAt (int index)
1799                         {
1800                                 throw new NotSupportedException ("Collection is read-only");
1801                         }
1802
1803                         public int IndexOf (T item)
1804                         {
1805                                 if (this.Rank > 1)
1806                                         throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1807
1808                                 int length = this.Length;
1809                                 for (int i = 0; i < length; i++) {
1810                                         T value;
1811                                         GetGenericValueImpl (i, out value);
1812                                         if (item.Equals (value))
1813                                                 // array index may not be zero-based.
1814                                                 // use lower bound
1815                                                 return i + this.GetLowerBound (0);
1816                                 }
1817
1818                                 int retVal;
1819                                 unchecked {
1820                                         // lower bound may be MinValue
1821                                         retVal = this.GetLowerBound (0) - 1;
1822                                 }
1823
1824                                 return retVal;
1825                         }
1826
1827                         // CAUTION! No bounds checking!
1828                         [MethodImplAttribute (MethodImplOptions.InternalCall)]
1829                         protected extern void GetGenericValueImpl (int pos, out T value);
1830
1831                         internal struct InternalEnumerator : IEnumerator<T>
1832                         {
1833                                 const int NOT_STARTED = -2;
1834
1835                                 // this MUST be -1, because we depend on it in move next.
1836                                 // we just decr the size, so, 0 - 1 == FINISHED
1837                                 const int FINISHED = -1;
1838
1839                                 InternalArray<T> array;
1840                                 int idx;
1841
1842                                 internal InternalEnumerator (InternalArray<T> array)
1843                                 {
1844                                         this.array = array;
1845                                         idx = NOT_STARTED;
1846                                 }
1847
1848                                 public void Dispose ()
1849                                 {
1850                                         idx = NOT_STARTED;
1851                                 }
1852
1853                                 public bool MoveNext ()
1854                                 {
1855                                         if (idx == NOT_STARTED)
1856                                                 idx = array.Length;
1857
1858                                         return idx != FINISHED && -- idx != FINISHED;
1859                                 }
1860
1861                                 public T Current {
1862                                         get {
1863                                                 if (idx < 0)
1864                                                         throw new InvalidOperationException ();
1865
1866                                                 return array [array.Length - 1 - idx];
1867                                         }
1868                                 }
1869
1870                                 void IEnumerator.Reset ()
1871                                 {
1872                                         throw new NotImplementedException ();
1873                                 }
1874
1875                                 object IEnumerator.Current {
1876                                         get {
1877                                                 return Current;
1878                                         }
1879                                 }
1880                         }
1881                 }
1882 #endif
1883         }
1884
1885 #if NET_2_0
1886
1887         internal struct ReadOnlyArrayEnumerator <T> : IEnumerator <T> {
1888                 const int NOT_STARTED = -2;
1889
1890                 // this MUST be -1, because we depend on it in move next.
1891                 // we just decr the size, so, 0 - 1 == FINISHED
1892                 const int FINISHED = -1;
1893
1894                 ReadOnlyArray <T> array;
1895                 int idx;
1896
1897                 internal ReadOnlyArrayEnumerator (ReadOnlyArray<T> array)
1898                 {
1899                         this.array = array;
1900                         idx = NOT_STARTED;
1901                 }
1902
1903                 public void Dispose ()
1904                 {
1905                         idx = NOT_STARTED;
1906                 }
1907
1908                 public bool MoveNext ()
1909                 {
1910                         if (idx == NOT_STARTED)
1911                                 idx = array.Count;
1912
1913                         return idx != FINISHED && -- idx != FINISHED;
1914                 }
1915
1916                 public T Current {
1917                         get {
1918                                 if (idx < 0)
1919                                         throw new InvalidOperationException ();
1920
1921                                 return array [array.Count - 1 - idx];
1922                         }
1923                 }
1924
1925                 void IEnumerator.Reset ()
1926                 {
1927                         throw new NotImplementedException ();
1928                 }
1929
1930                 object IEnumerator.Current {
1931                         get {
1932                                 return Current;
1933                         }
1934                 }
1935         }
1936
1937         internal class ReadOnlyArray <T> : ICollection <T>, IList <T>, IEnumerable <T>
1938         {
1939                 T[] arr;
1940
1941                 internal ReadOnlyArray (T[] array) {
1942                         arr = array;
1943                 }
1944
1945                 // ICollection<T> interface
1946                 public int Count {
1947                         get {
1948                                 return arr.Length;
1949                         }
1950                 }
1951
1952                 public bool IsReadOnly {
1953                         get {
1954                                 return true;
1955                         }
1956                 }
1957
1958                 public void Add (T item) {
1959                         throw new NotSupportedException ("Collection is read-only");
1960                 }
1961
1962                 public bool Remove (T item) {
1963                         throw new NotSupportedException ("Collection is read-only");
1964                 }
1965
1966                 public void Clear () {
1967                         throw new NotSupportedException ("Collection is read-only");
1968                 }
1969
1970                 public void CopyTo (T[] array, int index) {
1971                         arr.CopyTo (array, index);
1972                 }
1973
1974                 public bool Contains (T item) {
1975                         return Array.IndexOf <T> (arr, item) != -1;
1976                 }
1977
1978                 // IList<T> interface
1979                 public T this [int index] {
1980                         get {
1981                                 if (unchecked ((uint) index) >= unchecked ((uint) arr.Length))
1982                                         throw new ArgumentOutOfRangeException ("index");
1983                                 return arr [index];
1984                         }
1985                         set {
1986                                 if (unchecked ((uint) index) >= unchecked ((uint) arr.Length))
1987                                         throw new ArgumentOutOfRangeException ("index");
1988                                 arr [index] = value;
1989                         }
1990                 }
1991
1992                 public void Insert (int index, T item) {
1993                         throw new NotSupportedException ("Collection is read-only");
1994                 }
1995
1996                 public void RemoveAt (int index) {
1997                         throw new NotSupportedException ("Collection is read-only");
1998                 }
1999
2000                 public int IndexOf (T item) {
2001                         return Array.IndexOf <T> (arr, item);
2002                 }
2003
2004                 // IEnumerable<T> interface
2005                 public IEnumerator<T> GetEnumerator () {
2006                         return new ReadOnlyArrayEnumerator <T> (this);
2007                 }
2008
2009                 IEnumerator IEnumerable.GetEnumerator () {
2010                         return new ReadOnlyArrayEnumerator <T> (this);
2011                 }
2012         }
2013 #endif
2014
2015 #if BOOTSTRAP_WITH_OLDLIB
2016         /* delegate used to swap array elements, keep defined outside Array */
2017         delegate void Swapper (int i, int j);
2018 #endif
2019 }