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