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