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