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