mcs/class/corlib/System/Array.cs

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