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 //   Jeffrey Stedfast (fejj@novell.com)
  10 //   Marek Safar (marek.safar@gmail.com)
  11 //
  12 // (C) 2001-2003 Ximian, Inc.  http://www.ximian.com
  13 // Copyright (C) 2004-2011 Novell, Inc (http://www.novell.com)
  14 // Copyright (C) 2011 Xamarin Inc (http://www.xamarin.com)
  15 //
  16 // Permission is hereby granted, free of charge, to any person obtaining
  17 // a copy of this software and associated documentation files (the
  18 // "Software"), to deal in the Software without restriction, including
  19 // without limitation the rights to use, copy, modify, merge, publish,
  20 // distribute, sublicense, and/or sell copies of the Software, and to
  21 // permit persons to whom the Software is furnished to do so, subject to
  22 // the following conditions:
  23 //
  24 // The above copyright notice and this permission notice shall be
  25 // included in all copies or substantial portions of the Software.
  26 //
  27 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  28 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  29 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  30 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  31 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  32 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  33 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  34 //
  35
  36 using System.Collections;
  37 using System.Runtime.CompilerServices;
  38 using System.Runtime.InteropServices;
  39
  40 using System.Collections.Generic;
  41 using System.Collections.ObjectModel;
  42 using System.Runtime.ConstrainedExecution;
  43 #if !FULL_AOT_RUNTIME
  44 using System.Reflection.Emit;
  45 #endif
  46
  47 namespace System
  48 {
  49         [Serializable]
  50         [ComVisible (true)]
  51         // FIXME: We are doing way to many double/triple exception checks for the overloaded functions"
  52         public abstract class Array : ICloneable, ICollection, IList, IEnumerable
  53 #if NET_4_0
  54                 , IStructuralComparable, IStructuralEquatable
  55 #endif
  56         {
  57                 // Constructor
  58                 private Array ()
  59                 {
  60                 }
  61
  62                 /*
  63                  * These methods are used to implement the implicit generic interfaces
  64                  * implemented by arrays in NET 2.0.
  65                  * Only make those methods generic which really need it, to avoid
  66                  * creating useless instantiations.
  67                  */
  68                 internal int InternalArray__ICollection_get_Count ()
  69                 {
  70                         return Length;
  71                 }
  72
  73                 internal bool InternalArray__ICollection_get_IsReadOnly ()
  74                 {
  75                         return true;
  76                 }
  77
  78                 internal IEnumerator<T> InternalArray__IEnumerable_GetEnumerator<T> ()
  79                 {
  80                         return new InternalEnumerator<T> (this);
  81                 }
  82
  83                 internal void InternalArray__ICollection_Clear ()
  84                 {
  85                         throw new NotSupportedException ("Collection is read-only");
  86                 }
  87
  88                 internal void InternalArray__ICollection_Add<T> (T item)
  89                 {
  90                         throw new NotSupportedException ("Collection is of a fixed size");
  91                 }
  92
  93                 internal bool InternalArray__ICollection_Remove<T> (T item)
  94                 {
  95                         throw new NotSupportedException ("Collection is of a fixed size");
  96                 }
  97
  98                 internal bool InternalArray__ICollection_Contains<T> (T item)
  99                 {
 100                         if (this.Rank > 1)
 101                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 102
 103                         int length = this.Length;
 104                         for (int i = 0; i < length; i++) {
 105                                 T value;
 106                                 GetGenericValueImpl (i, out value);
 107                                 if (item == null){
 108                                         if (value == null) {
 109                                                 return true;
 110                                         }
 111
 112                                         continue;
 113                                 }
 114
 115                                 if (item.Equals (value)) {
 116                                         return true;
 117                                 }
 118                         }
 119
 120                         return false;
 121                 }
 122
 123                 internal void InternalArray__ICollection_CopyTo<T> (T[] array, int index)
 124                 {
 125                         if (array == null)
 126                                 throw new ArgumentNullException ("array");
 127
 128                         // The order of these exception checks may look strange,
 129                         // but that's how the microsoft runtime does it.
 130                         if (this.Rank > 1)
 131                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 132                         if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
 133                                 throw new ArgumentException ("Destination array was not long " +
 134                                         "enough. Check destIndex and length, and the array's " +
 135                                         "lower bounds.");
 136                         if (array.Rank > 1)
 137                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 138                         if (index < 0)
 139                                 throw new ArgumentOutOfRangeException (
 140                                         "index", Locale.GetText ("Value has to be >= 0."));
 141
 142                         Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
 143                 }
 144
 145 #if NET_4_5
 146                 internal T InternalArray__IReadOnlyList_get_Item<T> (int index)
 147                 {
 148                         if (unchecked ((uint) index) >= unchecked ((uint) Length))
 149                                 throw new ArgumentOutOfRangeException ("index");
 150
 151                         T value;
 152                         GetGenericValueImpl (index, out value);
 153                         return value;
 154                 }
 155
 156                 internal int InternalArray__IReadOnlyCollection_get_Count ()
 157                 {
 158                         return Length;
 159                 }
 160 #endif
 161
 162                 internal void InternalArray__Insert<T> (int index, T item)
 163                 {
 164                         throw new NotSupportedException ("Collection is of a fixed size");
 165                 }
 166
 167                 internal void InternalArray__RemoveAt (int index)
 168                 {
 169                         throw new NotSupportedException ("Collection is of a fixed size");
 170                 }
 171
 172                 internal int InternalArray__IndexOf<T> (T item)
 173                 {
 174                         if (this.Rank > 1)
 175                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 176
 177                         int length = this.Length;
 178                         for (int i = 0; i < length; i++) {
 179                                 T value;
 180                                 GetGenericValueImpl (i, out value);
 181                                 if (item == null){
 182                                         if (value == null)
 183                                                 return i + this.GetLowerBound (0);
 184
 185                                         continue;
 186                                 }
 187                                 if (value.Equals (item))
 188                                         // array index may not be zero-based.
 189                                         // use lower bound
 190                                         return i + this.GetLowerBound (0);
 191                         }
 192
 193                         unchecked {
 194                                 // lower bound may be MinValue
 195                                 return this.GetLowerBound (0) - 1;
 196                         }
 197                 }
 198
 199                 internal T InternalArray__get_Item<T> (int index)
 200                 {
 201                         if (unchecked ((uint) index) >= unchecked ((uint) Length))
 202                                 throw new ArgumentOutOfRangeException ("index");
 203
 204                         T value;
 205                         GetGenericValueImpl (index, out value);
 206                         return value;
 207                 }
 208
 209                 internal void InternalArray__set_Item<T> (int index, T item)
 210                 {
 211                         if (unchecked ((uint) index) >= unchecked ((uint) Length))
 212                                 throw new ArgumentOutOfRangeException ("index");
 213
 214                         object[] oarray = this as object [];
 215                         if (oarray != null) {
 216                                 oarray [index] = (object)item;
 217                                 return;
 218                         }
 219                         SetGenericValueImpl (index, ref item);
 220                 }
 221
 222                 // CAUTION! No bounds checking!
 223                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 224                 internal extern void GetGenericValueImpl<T> (int pos, out T value);
 225
 226                 // CAUTION! No bounds checking!
 227                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 228                 internal extern void SetGenericValueImpl<T> (int pos, ref T value);
 229
 230                 internal struct InternalEnumerator<T> : IEnumerator<T>
 231                 {
 232                         const int NOT_STARTED = -2;
 233
 234                         // this MUST be -1, because we depend on it in move next.
 235                         // we just decr the size, so, 0 - 1 == FINISHED
 236                         const int FINISHED = -1;
 237
 238                         Array array;
 239                         int idx;
 240
 241                         internal InternalEnumerator (Array array)
 242                         {
 243                                 this.array = array;
 244                                 idx = NOT_STARTED;
 245                         }
 246
 247                         public void Dispose ()
 248                         {
 249                                 idx = NOT_STARTED;
 250                         }
 251
 252                         public bool MoveNext ()
 253                         {
 254                                 if (idx == NOT_STARTED)
 255                                         idx = array.Length;
 256
 257                                 return idx != FINISHED && -- idx != FINISHED;
 258                         }
 259
 260                         public T Current {
 261                                 get {
 262                                         if (idx == NOT_STARTED)
 263                                                 throw new InvalidOperationException ("Enumeration has not started. Call MoveNext");
 264                                         if (idx == FINISHED)
 265                                                 throw new InvalidOperationException ("Enumeration already finished");
 266
 267                                         return array.InternalArray__get_Item<T> (array.Length - 1 - idx);
 268                                 }
 269                         }
 270
 271                         void IEnumerator.Reset ()
 272                         {
 273                                 idx = NOT_STARTED;
 274                         }
 275
 276                         object IEnumerator.Current {
 277                                 get {
 278                                         return Current;
 279                                 }
 280                         }
 281                 }
 282
 283                 // Properties
 284                 public int Length {
 285                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 286                         get {
 287                                 int length = this.GetLength (0);
 288
 289                                 for (int i = 1; i < this.Rank; i++) {
 290                                         length *= this.GetLength (i);
 291                                 }
 292                                 return length;
 293                         }
 294                 }
 295
 296                 [ComVisible (false)]
 297                 public long LongLength {
 298                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 299                         get { return Length; }
 300                 }
 301
 302                 public int Rank {
 303                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 304                         get {
 305                                 return this.GetRank ();
 306                         }
 307                 }
 308
 309                 // IList interface
 310                 object IList.this [int index] {
 311                         get {
 312                                 if (unchecked ((uint) index) >= unchecked ((uint) Length))
 313                                         throw new IndexOutOfRangeException ("index");
 314                                 if (this.Rank > 1)
 315                                         throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported."));
 316                                 return GetValueImpl (index);
 317                         }
 318                         set {
 319                                 if (unchecked ((uint) index) >= unchecked ((uint) Length))
 320                                         throw new IndexOutOfRangeException ("index");
 321                                 if (this.Rank > 1)
 322                                         throw new ArgumentException (Locale.GetText ("Only single dimension arrays are supported."));
 323                                 SetValueImpl (value, index);
 324                         }
 325                 }
 326
 327                 int IList.Add (object value)
 328                 {
 329                         throw new NotSupportedException ();
 330                 }
 331
 332                 void IList.Clear ()
 333                 {
 334                         Array.Clear (this, this.GetLowerBound (0), this.Length);
 335                 }
 336
 337                 bool IList.Contains (object value)
 338                 {
 339                         if (this.Rank > 1)
 340                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 341
 342                         int length = this.Length;
 343                         for (int i = 0; i < length; i++) {
 344                                 if (Object.Equals (this.GetValueImpl (i), value))
 345                                         return true;
 346                         }
 347                         return false;
 348                 }
 349
 350                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 351                 int IList.IndexOf (object value)
 352                 {
 353                         if (this.Rank > 1)
 354                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 355
 356                         int length = this.Length;
 357                         for (int i = 0; i < length; i++) {
 358                                 if (Object.Equals (this.GetValueImpl (i), value))
 359                                         // array index may not be zero-based.
 360                                         // use lower bound
 361                                         return i + this.GetLowerBound (0);
 362                         }
 363
 364                         unchecked {
 365                                 // lower bound may be MinValue
 366                                 return this.GetLowerBound (0) - 1;
 367                         }
 368                 }
 369
 370                 void IList.Insert (int index, object value)
 371                 {
 372                         throw new NotSupportedException ();
 373                 }
 374
 375                 void IList.Remove (object value)
 376                 {
 377                         throw new NotSupportedException ();
 378                 }
 379
 380                 void IList.RemoveAt (int index)
 381                 {
 382                         throw new NotSupportedException ();
 383                 }
 384
 385                 // InternalCall Methods
 386                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 387                 extern int GetRank ();
 388
 389                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 390                 public extern int GetLength (int dimension);
 391
 392                 [ComVisible (false)]
 393                 public long GetLongLength (int dimension)
 394                 {
 395                         return GetLength (dimension);
 396                 }
 397
 398                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 399                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 400                 public extern int GetLowerBound (int dimension);
 401
 402                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 403                 public extern object GetValue (params int[] indices);
 404
 405                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 406                 public extern void SetValue (object value, params int[] indices);
 407
 408                 // CAUTION! No bounds checking!
 409                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 410                 internal extern object GetValueImpl (int pos);
 411
 412                 // CAUTION! No bounds checking!
 413                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 414                 internal extern void SetValueImpl (object value, int pos);
 415
 416                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 417                 internal extern static bool FastCopy (Array source, int source_idx, Array dest, int dest_idx, int length);
 418
 419                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 420                 internal extern static Array CreateInstanceImpl (Type elementType, int[] lengths, int[] bounds);
 421
 422                 // Properties
 423                 int ICollection.Count {
 424                         get {
 425                                 return Length;
 426                         }
 427                 }
 428
 429                 public bool IsSynchronized {
 430                         get {
 431                                 return false;
 432                         }
 433                 }
 434
 435                 public object SyncRoot {
 436                         get {
 437                                 return this;
 438                         }
 439                 }
 440
 441                 public bool IsFixedSize {
 442                         get {
 443                                 return true;
 444                         }
 445                 }
 446
 447                 public bool IsReadOnly {
 448                         get {
 449                                 return false;
 450                         }
 451                 }
 452
 453                 public IEnumerator GetEnumerator ()
 454                 {
 455                         return new SimpleEnumerator (this);
 456                 }
 457
 458 #if NET_4_0
 459                 int IStructuralComparable.CompareTo (object other, IComparer comparer)
 460                 {
 461                         if (other == null)
 462                                 return 1;
 463
 464                         Array arr = other as Array;
 465                         if (arr == null)
 466                                 throw new ArgumentException ("Not an array", "other");
 467
 468                         int len = GetLength (0);
 469                         if (len != arr.GetLength (0))
 470                                 throw new ArgumentException ("Not of the same length", "other");
 471
 472                         if (Rank > 1)
 473                                 throw new ArgumentException ("Array must be single dimensional");
 474
 475                         if (arr.Rank > 1)
 476                                 throw new ArgumentException ("Array must be single dimensional", "other");
 477
 478                         for (int i = 0; i < len; ++i) {
 479                                 object a = GetValue (i);
 480                                 object b = arr.GetValue (i);
 481                                 int r = comparer.Compare (a, b);
 482                                 if (r != 0)
 483                                         return r;
 484                         }
 485                         return 0;
 486                 }
 487
 488                 bool IStructuralEquatable.Equals (object other, IEqualityComparer comparer)
 489                 {
 490                         Array o = other as Array;
 491                         if (o == null || o.Length != Length)
 492                                 return false;
 493
 494                         if (Object.ReferenceEquals (other, this))
 495                                 return true;
 496
 497                         for (int i = 0; i < Length; i++) {
 498                                 object this_item = this.GetValue (i);
 499                                 object other_item = o.GetValue (i);
 500                                 if (!comparer.Equals (this_item, other_item))
 501                                         return false;
 502                         }
 503                         return true;
 504                 }
 505
 506
 507                 int IStructuralEquatable.GetHashCode (IEqualityComparer comparer)
 508                 {
 509                         if (comparer == null)
 510                                 throw new ArgumentNullException ("comparer");
 511
 512                         int hash = 0;
 513                         for (int i = 0; i < Length; i++)
 514                                 hash = ((hash << 7) + hash) ^ comparer.GetHashCode (GetValueImpl (i));
 515                         return hash;
 516                 }
 517 #endif
 518
 519                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 520                 public int GetUpperBound (int dimension)
 521                 {
 522                         return GetLowerBound (dimension) + GetLength (dimension) - 1;
 523                 }
 524
 525                 public object GetValue (int index)
 526                 {
 527                         if (Rank != 1)
 528                                 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
 529                         if (index < GetLowerBound (0) || index > GetUpperBound (0))
 530                                 throw new IndexOutOfRangeException (Locale.GetText (
 531                                         "Index has to be between upper and lower bound of the array."));
 532
 533                         return GetValueImpl (index - GetLowerBound (0));
 534                 }
 535
 536                 public object GetValue (int index1, int index2)
 537                 {
 538                         int[] ind = {index1, index2};
 539                         return GetValue (ind);
 540                 }
 541
 542                 public object GetValue (int index1, int index2, int index3)
 543                 {
 544                         int[] ind = {index1, index2, index3};
 545                         return GetValue (ind);
 546                 }
 547
 548                 [ComVisible (false)]
 549                 public object GetValue (long index)
 550                 {
 551                         if (index < 0 || index > Int32.MaxValue)
 552                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 553                                         "Value must be >= 0 and <= Int32.MaxValue."));
 554
 555                         return GetValue ((int) index);
 556                 }
 557
 558                 [ComVisible (false)]
 559                 public object GetValue (long index1, long index2)
 560                 {
 561                         if (index1 < 0 || index1 > Int32.MaxValue)
 562                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 563                                         "Value must be >= 0 and <= Int32.MaxValue."));
 564
 565                         if (index2 < 0 || index2 > Int32.MaxValue)
 566                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 567                                         "Value must be >= 0 and <= Int32.MaxValue."));
 568
 569                         return GetValue ((int) index1, (int) index2);
 570                 }
 571
 572                 [ComVisible (false)]
 573                 public object GetValue (long index1, long index2, long index3)
 574                 {
 575                         if (index1 < 0 || index1 > Int32.MaxValue)
 576                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 577                                         "Value must be >= 0 and <= Int32.MaxValue."));
 578
 579                         if (index2 < 0 || index2 > Int32.MaxValue)
 580                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 581                                         "Value must be >= 0 and <= Int32.MaxValue."));
 582
 583                         if (index3 < 0 || index3 > Int32.MaxValue)
 584                                 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
 585                                         "Value must be >= 0 and <= Int32.MaxValue."));
 586
 587                         return GetValue ((int) index1, (int) index2, (int) index3);
 588                 }
 589
 590                 [ComVisible (false)]
 591                 public void SetValue (object value, long index)
 592                 {
 593                         if (index < 0 || index > Int32.MaxValue)
 594                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 595                                         "Value must be >= 0 and <= Int32.MaxValue."));
 596
 597                         SetValue (value, (int) index);
 598                 }
 599
 600                 [ComVisible (false)]
 601                 public void SetValue (object value, long index1, long index2)
 602                 {
 603                         if (index1 < 0 || index1 > Int32.MaxValue)
 604                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 605                                         "Value must be >= 0 and <= Int32.MaxValue."));
 606
 607                         if (index2 < 0 || index2 > Int32.MaxValue)
 608                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 609                                         "Value must be >= 0 and <= Int32.MaxValue."));
 610
 611                         int[] ind = {(int) index1, (int) index2};
 612                         SetValue (value, ind);
 613                 }
 614
 615                 [ComVisible (false)]
 616                 public void SetValue (object value, long index1, long index2, long index3)
 617                 {
 618                         if (index1 < 0 || index1 > Int32.MaxValue)
 619                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 620                                         "Value must be >= 0 and <= Int32.MaxValue."));
 621
 622                         if (index2 < 0 || index2 > Int32.MaxValue)
 623                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 624                                         "Value must be >= 0 and <= Int32.MaxValue."));
 625
 626                         if (index3 < 0 || index3 > Int32.MaxValue)
 627                                 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
 628                                         "Value must be >= 0 and <= Int32.MaxValue."));
 629
 630                         int[] ind = {(int) index1, (int) index2, (int) index3};
 631                         SetValue (value, ind);
 632                 }
 633
 634                 public void SetValue (object value, int index)
 635                 {
 636                         if (Rank != 1)
 637                                 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
 638                         if (index < GetLowerBound (0) || index > GetUpperBound (0))
 639                                 throw new IndexOutOfRangeException (Locale.GetText (
 640                                         "Index has to be >= lower bound and <= upper bound of the array."));
 641
 642                         SetValueImpl (value, index - GetLowerBound (0));
 643                 }
 644
 645                 public void SetValue (object value, int index1, int index2)
 646                 {
 647                         int[] ind = {index1, index2};
 648                         SetValue (value, ind);
 649                 }
 650
 651                 public void SetValue (object value, int index1, int index2, int index3)
 652                 {
 653                         int[] ind = {index1, index2, index3};
 654                         SetValue (value, ind);
 655                 }
 656
 657                 public static Array CreateInstance (Type elementType, int length)
 658                 {
 659                         int[] lengths = {length};
 660
 661                         return CreateInstance (elementType, lengths);
 662                 }
 663
 664                 public static Array CreateInstance (Type elementType, int length1, int length2)
 665                 {
 666                         int[] lengths = {length1, length2};
 667
 668                         return CreateInstance (elementType, lengths);
 669                 }
 670
 671                 public static Array CreateInstance (Type elementType, int length1, int length2, int length3)
 672                 {
 673                         int[] lengths = {length1, length2, length3};
 674
 675                         return CreateInstance (elementType, lengths);
 676                 }
 677
 678                 public static Array CreateInstance (Type elementType, params int[] lengths)
 679                 {
 680                         if (elementType == null)
 681                                 throw new ArgumentNullException ("elementType");
 682                         if (lengths == null)
 683                                 throw new ArgumentNullException ("lengths");
 684
 685                         if (lengths.Length > 255)
 686                                 throw new TypeLoadException ();
 687
 688                         int[] bounds = null;
 689
 690                         elementType = elementType.UnderlyingSystemType;
 691                         if (!elementType.IsSystemType)
 692                                 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
 693                         if (elementType.Equals (typeof (void)))
 694                                 throw new NotSupportedException ("Array type can not be void");
 695                         if (elementType.ContainsGenericParameters)
 696                                 throw new NotSupportedException ("Array type can not be an open generic type");
 697 #if !FULL_AOT_RUNTIME
 698                         if ((elementType is TypeBuilder) && !(elementType as TypeBuilder).IsCreated ())
 699                                 throw new NotSupportedException ("Can't create an array of the unfinished type '" + elementType + "'.");
 700 #endif
 701
 702                         return CreateInstanceImpl (elementType, lengths, bounds);
 703                 }
 704
 705                 public static Array CreateInstance (Type elementType, int[] lengths, int [] lowerBounds)
 706                 {
 707                         if (elementType == null)
 708                                 throw new ArgumentNullException ("elementType");
 709                         if (lengths == null)
 710                                 throw new ArgumentNullException ("lengths");
 711                         if (lowerBounds == null)
 712                                 throw new ArgumentNullException ("lowerBounds");
 713
 714                         elementType = elementType.UnderlyingSystemType;
 715                         if (!elementType.IsSystemType)
 716                                 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
 717                         if (elementType.Equals (typeof (void)))
 718                                 throw new NotSupportedException ("Array type can not be void");
 719                         if (elementType.ContainsGenericParameters)
 720                                 throw new NotSupportedException ("Array type can not be an open generic type");
 721
 722                         if (lengths.Length < 1)
 723                                 throw new ArgumentException (Locale.GetText ("Arrays must contain >= 1 elements."));
 724
 725                         if (lengths.Length != lowerBounds.Length)
 726                                 throw new ArgumentException (Locale.GetText ("Arrays must be of same size."));
 727
 728                         for (int j = 0; j < lowerBounds.Length; j ++) {
 729                                 if (lengths [j] < 0)
 730                                         throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
 731                                                 "Each value has to be >= 0."));
 732                                 if ((long)lowerBounds [j] + (long)lengths [j] > (long)Int32.MaxValue)
 733                                         throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
 734                                                 "Length + bound must not exceed Int32.MaxValue."));
 735                         }
 736
 737                         if (lengths.Length > 255)
 738                                 throw new TypeLoadException ();
 739
 740                         return CreateInstanceImpl (elementType, lengths, lowerBounds);
 741                 }
 742
 743                 static int [] GetIntArray (long [] values)
 744                 {
 745                         int len = values.Length;
 746                         int [] ints = new int [len];
 747                         for (int i = 0; i < len; i++) {
 748                                 long current = values [i];
 749                                 if (current < 0 || current > (long) Int32.MaxValue)
 750                                         throw new ArgumentOutOfRangeException ("values", Locale.GetText (
 751                                                 "Each value has to be >= 0 and <= Int32.MaxValue."));
 752
 753                                 ints [i] = (int) current;
 754                         }
 755                         return ints;
 756                 }
 757
 758                 public static Array CreateInstance (Type elementType, params long [] lengths)
 759                 {
 760                         if (lengths == null)
 761                                 throw new ArgumentNullException ("lengths");
 762                         return CreateInstance (elementType, GetIntArray (lengths));
 763                 }
 764
 765                 [ComVisible (false)]
 766                 public object GetValue (params long [] indices)
 767                 {
 768                         if (indices == null)
 769                                 throw new ArgumentNullException ("indices");
 770                         return GetValue (GetIntArray (indices));
 771                 }
 772
 773                 [ComVisible (false)]
 774                 public void SetValue (object value, params long [] indices)
 775                 {
 776                         if (indices == null)
 777                                 throw new ArgumentNullException ("indices");
 778                         SetValue (value, GetIntArray (indices));
 779                 }
 780
 781                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 782                 public static int BinarySearch (Array array, object value)
 783                 {
 784                         return BinarySearch (array, value, null);
 785                 }
 786
 787                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 788                 public static int BinarySearch (Array array, object value, IComparer comparer)
 789                 {
 790                         if (array == null)
 791                                 throw new ArgumentNullException ("array");
 792
 793                         if (array.Rank > 1)
 794                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 795
 796                         if (array.Length == 0)
 797                                 return -1;
 798
 799                         return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer);
 800                 }
 801
 802                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 803                 public static int BinarySearch (Array array, int index, int length, object value)
 804                 {
 805                         return BinarySearch (array, index, length, value, null);
 806                 }
 807
 808                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 809                 public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
 810                 {
 811                         if (array == null)
 812                                 throw new ArgumentNullException ("array");
 813
 814                         if (array.Rank > 1)
 815                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 816
 817                         if (index < array.GetLowerBound (0))
 818                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 819                                         "index is less than the lower bound of array."));
 820                         if (length < 0)
 821                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 822                                         "Value has to be >= 0."));
 823                         // re-ordered to avoid possible integer overflow
 824                         if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
 825                                 throw new ArgumentException (Locale.GetText (
 826                                         "index and length do not specify a valid range in array."));
 827
 828                         if (array.Length == 0)
 829                                 return -1;
 830
 831                         return DoBinarySearch (array, index, length, value, comparer);
 832                 }
 833
 834                 static int DoBinarySearch (Array array, int index, int length, object value, IComparer comparer)
 835                 {
 836                         // cache this in case we need it
 837                         if (comparer == null)
 838                                 comparer = Comparer.Default;
 839
 840                         int iMin = index;
 841                         // Comment from Tum (tum@veridicus.com):
 842                         // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
 843                         int iMax = index + length - 1;
 844                         int iCmp = 0;
 845                         try {
 846                                 while (iMin <= iMax) {
 847                                         // Be careful with overflow
 848                                         // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
 849                                         int iMid = iMin + ((iMax - iMin) / 2);
 850                                         object elt = array.GetValueImpl (iMid);
 851
 852                                         iCmp = comparer.Compare (elt, value);
 853
 854                                         if (iCmp == 0)
 855                                                 return iMid;
 856                                         else if (iCmp > 0)
 857                                                 iMax = iMid - 1;
 858                                         else
 859                                                 iMin = iMid + 1; // compensate for the rounding down
 860                                 }
 861                         }
 862                         catch (Exception e) {
 863                                 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
 864                         }
 865
 866                         return ~iMin;
 867                 }
 868
 869                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 870                 public static void Clear (Array array, int index, int length)
 871                 {
 872                         if (array == null)
 873                                 throw new ArgumentNullException ("array");
 874                         if (length < 0)
 875                                 throw new IndexOutOfRangeException ("length < 0");
 876
 877                         int low = array.GetLowerBound (0);
 878                         if (index < low)
 879                                 throw new IndexOutOfRangeException ("index < lower bound");
 880                         index = index - low;
 881
 882                         // re-ordered to avoid possible integer overflow
 883                         if (index > array.Length - length)
 884                                 throw new IndexOutOfRangeException ("index + length > size");
 885
 886                         ClearInternal (array, index, length);
 887                 }
 888
 889                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 890                 static extern void ClearInternal (Array a, int index, int count);
 891
 892                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 893                 public extern object Clone ();
 894
 895                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 896                 public static void Copy (Array sourceArray, Array destinationArray, int length)
 897                 {
 898                         // need these checks here because we are going to use
 899                         // GetLowerBound() on source and dest.
 900                         if (sourceArray == null)
 901                                 throw new ArgumentNullException ("sourceArray");
 902
 903                         if (destinationArray == null)
 904                                 throw new ArgumentNullException ("destinationArray");
 905
 906                         Copy (sourceArray, sourceArray.GetLowerBound (0), destinationArray,
 907                                 destinationArray.GetLowerBound (0), length);
 908                 }
 909
 910                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 911                 public static void Copy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
 912                 {
 913                         if (sourceArray == null)
 914                                 throw new ArgumentNullException ("sourceArray");
 915
 916                         if (destinationArray == null)
 917                                 throw new ArgumentNullException ("destinationArray");
 918
 919                         if (length < 0)
 920                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 921                                         "Value has to be >= 0."));;
 922
 923                         if (sourceIndex < 0)
 924                                 throw new ArgumentOutOfRangeException ("sourceIndex", Locale.GetText (
 925                                         "Value has to be >= 0."));;
 926
 927                         if (destinationIndex < 0)
 928                                 throw new ArgumentOutOfRangeException ("destinationIndex", Locale.GetText (
 929                                         "Value has to be >= 0."));;
 930
 931                         if (FastCopy (sourceArray, sourceIndex, destinationArray, destinationIndex, length))
 932                                 return;
 933
 934                         int source_pos = sourceIndex - sourceArray.GetLowerBound (0);
 935                         int dest_pos = destinationIndex - destinationArray.GetLowerBound (0);
 936
 937                         // re-ordered to avoid possible integer overflow
 938                         if (source_pos > sourceArray.Length - length)
 939                                 throw new ArgumentException ("length");
 940
 941                         if (dest_pos > destinationArray.Length - length) {
 942                                 string msg = "Destination array was not long enough. Check " +
 943                                         "destIndex and length, and the array's lower bounds";
 944                                 throw new ArgumentException (msg, string.Empty);
 945                         }
 946
 947                         if (sourceArray.Rank != destinationArray.Rank)
 948                                 throw new RankException (Locale.GetText ("Arrays must be of same size."));
 949
 950                         Type src_type = sourceArray.GetType ().GetElementType ();
 951                         Type dst_type = destinationArray.GetType ().GetElementType ();
 952
 953                         if (!Object.ReferenceEquals (sourceArray, destinationArray) || source_pos > dest_pos) {
 954                                 for (int i = 0; i < length; i++) {
 955                                         Object srcval = sourceArray.GetValueImpl (source_pos + i);
 956
 957                                         try {
 958                                                 destinationArray.SetValueImpl (srcval, dest_pos + i);
 959                                         } catch (ArgumentException) {
 960                                                 throw CreateArrayTypeMismatchException ();
 961                                         } catch {
 962                                                 if (CanAssignArrayElement (src_type, dst_type))
 963                                                         throw;
 964
 965                                                 throw CreateArrayTypeMismatchException ();
 966                                         }
 967                                 }
 968                         }
 969                         else {
 970                                 for (int i = length - 1; i >= 0; i--) {
 971                                         Object srcval = sourceArray.GetValueImpl (source_pos + i);
 972
 973                                         try {
 974                                                 destinationArray.SetValueImpl (srcval, dest_pos + i);
 975                                         } catch (ArgumentException) {
 976                                                 throw CreateArrayTypeMismatchException ();
 977                                         } catch {
 978                                                 if (CanAssignArrayElement (src_type, dst_type))
 979                                                         throw;
 980
 981                                                 throw CreateArrayTypeMismatchException ();
 982                                         }
 983                                 }
 984                         }
 985                 }
 986
 987                 static Exception CreateArrayTypeMismatchException ()
 988                 {
 989                         return new ArrayTypeMismatchException ();
 990                 }
 991
 992                 static bool CanAssignArrayElement (Type source, Type target)
 993                 {
 994                         if (source.IsValueType)
 995                                 return source.IsAssignableFrom (target);
 996
 997                         if (source.IsInterface)
 998                                 return !target.IsValueType;
 999
1000                         if (target.IsInterface)
1001                                 return !source.IsValueType;
1002
1003                         return source.IsAssignableFrom (target) || target.IsAssignableFrom (source);
1004                 }
1005
1006                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1007                 public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray,
1008                                          long destinationIndex, long length)
1009                 {
1010                         if (sourceArray == null)
1011                                 throw new ArgumentNullException ("sourceArray");
1012
1013                         if (destinationArray == null)
1014                                 throw new ArgumentNullException ("destinationArray");
1015
1016                         if (sourceIndex < Int32.MinValue || sourceIndex > Int32.MaxValue)
1017                                 throw new ArgumentOutOfRangeException ("sourceIndex",
1018                                         Locale.GetText ("Must be in the Int32 range."));
1019
1020                         if (destinationIndex < Int32.MinValue || destinationIndex > Int32.MaxValue)
1021                                 throw new ArgumentOutOfRangeException ("destinationIndex",
1022                                         Locale.GetText ("Must be in the Int32 range."));
1023
1024                         if (length < 0 || length > Int32.MaxValue)
1025                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1026                                         "Value must be >= 0 and <= Int32.MaxValue."));
1027
1028                         Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
1029                 }
1030
1031                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1032                 public static void Copy (Array sourceArray, Array destinationArray, long length)
1033                 {
1034                         if (length < 0 || length > Int32.MaxValue)
1035                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1036                                         "Value must be >= 0 and <= Int32.MaxValue."));
1037
1038                         Copy (sourceArray, destinationArray, (int) length);
1039                 }
1040
1041                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1042                 public static int IndexOf (Array array, object value)
1043                 {
1044                         if (array == null)
1045                                 throw new ArgumentNullException ("array");
1046
1047                         return IndexOf (array, value, 0, array.Length);
1048                 }
1049
1050                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1051                 public static int IndexOf (Array array, object value, int startIndex)
1052                 {
1053                         if (array == null)
1054                                 throw new ArgumentNullException ("array");
1055
1056                         return IndexOf (array, value, startIndex, array.Length - startIndex);
1057                 }
1058
1059                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1060                 public static int IndexOf (Array array, object value, int startIndex, int count)
1061                 {
1062                         if (array == null)
1063                                 throw new ArgumentNullException ("array");
1064
1065                         if (array.Rank > 1)
1066                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1067
1068                         // re-ordered to avoid possible integer overflow
1069                         if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
1070                                 throw new ArgumentOutOfRangeException ();
1071
1072                         int max = startIndex + count;
1073                         for (int i = startIndex; i < max; i++) {
1074                                 if (Object.Equals (array.GetValueImpl (i), value))
1075                                         return i;
1076                         }
1077
1078                         return array.GetLowerBound (0) - 1;
1079                 }
1080
1081                 public void Initialize()
1082                 {
1083                         //FIXME: We would like to find a compiler that uses
1084                         // this method. It looks like this method do nothing
1085                         // in C# so no exception is trown by the moment.
1086                 }
1087
1088                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1089                 public static int LastIndexOf (Array array, object value)
1090                 {
1091                         if (array == null)
1092                                 throw new ArgumentNullException ("array");
1093
1094                         if (array.Length == 0)
1095                                 return array.GetLowerBound (0) - 1;
1096                         return LastIndexOf (array, value, array.Length - 1);
1097                 }
1098
1099                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1100                 public static int LastIndexOf (Array array, object value, int startIndex)
1101                 {
1102                         if (array == null)
1103                                 throw new ArgumentNullException ("array");
1104
1105                         return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1);
1106                 }
1107
1108                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1109                 public static int LastIndexOf (Array array, object value, int startIndex, int count)
1110                 {
1111                         if (array == null)
1112                                 throw new ArgumentNullException ("array");
1113
1114                         if (array.Rank > 1)
1115                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1116
1117                         int lb = array.GetLowerBound (0);
1118                         // Empty arrays do not throw ArgumentOutOfRangeException
1119                         if (array.Length == 0)
1120                                 return lb - 1;
1121
1122                         if (count < 0 || startIndex < lb ||
1123                                 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < lb)
1124                                 throw new ArgumentOutOfRangeException ();
1125
1126                         for (int i = startIndex; i >= startIndex - count + 1; i--) {
1127                                 if (Object.Equals (array.GetValueImpl (i), value))
1128                                         return i;
1129                         }
1130
1131                         return lb - 1;
1132                 }
1133
1134                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1135                 public static void Reverse (Array array)
1136                 {
1137                         if (array == null)
1138                                 throw new ArgumentNullException ("array");
1139
1140                         Reverse (array, array.GetLowerBound (0), array.Length);
1141                 }
1142
1143                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1144                 public static void Reverse (Array array, int index, int length)
1145                 {
1146                         if (array == null)
1147                                 throw new ArgumentNullException ("array");
1148
1149                         if (array.Rank > 1)
1150                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1151
1152                         if (index < array.GetLowerBound (0) || length < 0)
1153                                 throw new ArgumentOutOfRangeException ();
1154
1155                         // re-ordered to avoid possible integer overflow
1156                         if (index > array.GetUpperBound (0) + 1 - length)
1157                                 throw new ArgumentException ();
1158
1159                         int end = index + length - 1;
1160                         var et = array.GetType ().GetElementType ();
1161                         switch (Type.GetTypeCode (et)) {
1162                         case TypeCode.Boolean:
1163                                 while (index < end) {
1164                                         bool a, b;
1165
1166                                         array.GetGenericValueImpl (index, out a);
1167                                         array.GetGenericValueImpl (end, out b);
1168                                         array.SetGenericValueImpl (index, ref b);
1169                                         array.SetGenericValueImpl (end, ref a);
1170                                         ++index;
1171                                         --end;
1172                                 }
1173                                 return;
1174
1175                         case TypeCode.Byte:
1176                         case TypeCode.SByte:
1177                                 while (index < end) {
1178                                         byte a, b;
1179
1180                                         array.GetGenericValueImpl (index, out a);
1181                                         array.GetGenericValueImpl (end, out b);
1182                                         array.SetGenericValueImpl (index, ref b);
1183                                         array.SetGenericValueImpl (end, ref a);
1184                                         ++index;
1185                                         --end;
1186                                 }
1187                                 return;
1188
1189                         case TypeCode.Int16:
1190                         case TypeCode.UInt16:
1191                         case TypeCode.Char:
1192                                 while (index < end) {
1193                                         short a, b;
1194
1195                                         array.GetGenericValueImpl (index, out a);
1196                                         array.GetGenericValueImpl (end, out b);
1197                                         array.SetGenericValueImpl (index, ref b);
1198                                         array.SetGenericValueImpl (end, ref a);
1199                                         ++index;
1200                                         --end;
1201                                 }
1202                                 return;
1203
1204                         case TypeCode.Int32:
1205                         case TypeCode.UInt32:
1206                         case TypeCode.Single:
1207                                 while (index < end) {
1208                                         int a, b;
1209
1210                                         array.GetGenericValueImpl (index, out a);
1211                                         array.GetGenericValueImpl (end, out b);
1212                                         array.SetGenericValueImpl (index, ref b);
1213                                         array.SetGenericValueImpl (end, ref a);
1214                                         ++index;
1215                                         --end;
1216                                 }
1217                                 return;
1218
1219                         case TypeCode.Int64:
1220                         case TypeCode.UInt64:
1221                         case TypeCode.Double:
1222                                 while (index < end) {
1223                                         long a, b;
1224
1225                                         array.GetGenericValueImpl (index, out a);
1226                                         array.GetGenericValueImpl (end, out b);
1227                                         array.SetGenericValueImpl (index, ref b);
1228                                         array.SetGenericValueImpl (end, ref a);
1229                                         ++index;
1230                                         --end;
1231                                 }
1232                                 return;
1233
1234                         case TypeCode.Decimal:
1235                                 while (index < end) {
1236                                         decimal a, b;
1237
1238                                         array.GetGenericValueImpl (index, out a);
1239                                         array.GetGenericValueImpl (end, out b);
1240                                         array.SetGenericValueImpl (index, ref b);
1241                                         array.SetGenericValueImpl (end, ref a);
1242                                         ++index;
1243                                         --end;
1244                                 }
1245                                 return;
1246
1247                         case TypeCode.String:
1248                                 while (index < end) {
1249                                         object a, b;
1250
1251                                         array.GetGenericValueImpl (index, out a);
1252                                         array.GetGenericValueImpl (end, out b);
1253                                         array.SetGenericValueImpl (index, ref b);
1254                                         array.SetGenericValueImpl (end, ref a);
1255                                         ++index;
1256                                         --end;
1257                                 }
1258                                 return;
1259                         default:
1260                                 if (array is object[])
1261                                         goto case TypeCode.String;
1262
1263                                 // Very slow fallback
1264                                 while (index < end) {
1265                                         object val = array.GetValueImpl (index);
1266                                         array.SetValueImpl (array.GetValueImpl (end), index);
1267                                         array.SetValueImpl (val, end);
1268                                         ++index;
1269                                         --end;
1270                                 }
1271
1272                                 return;
1273                         }
1274                 }
1275
1276                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1277                 public static void Sort (Array array)
1278                 {
1279                         Sort (array, (IComparer)null);
1280                 }
1281
1282                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1283                 public static void Sort (Array keys, Array items)
1284                 {
1285                         Sort (keys, items, (IComparer)null);
1286                 }
1287
1288                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1289                 public static void Sort (Array array, IComparer comparer)
1290                 {
1291                         if (array == null)
1292                                 throw new ArgumentNullException ("array");
1293
1294                         if (array.Rank > 1)
1295                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1296
1297                         SortImpl (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
1298                 }
1299
1300                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1301                 public static void Sort (Array array, int index, int length)
1302                 {
1303                         Sort (array, index, length, (IComparer)null);
1304                 }
1305
1306                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1307                 public static void Sort (Array keys, Array items, IComparer comparer)
1308                 {
1309                         if (items == null) {
1310                                 Sort (keys, comparer);
1311                                 return;
1312                         }
1313
1314                         if (keys == null)
1315                                 throw new ArgumentNullException ("keys");
1316
1317                         if (keys.Rank > 1 || items.Rank > 1)
1318                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1319
1320                         SortImpl (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
1321                 }
1322
1323                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1324                 public static void Sort (Array keys, Array items, int index, int length)
1325                 {
1326                         Sort (keys, items, index, length, (IComparer)null);
1327                 }
1328
1329                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1330                 public static void Sort (Array array, int index, int length, IComparer comparer)
1331                 {
1332                         if (array == null)
1333                                 throw new ArgumentNullException ("array");
1334
1335                         if (array.Rank > 1)
1336                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1337
1338                         if (index < array.GetLowerBound (0))
1339                                 throw new ArgumentOutOfRangeException ("index");
1340
1341                         if (length < 0)
1342                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1343                                         "Value has to be >= 0."));
1344
1345                         if (array.Length - (array.GetLowerBound (0) + index) < length)
1346                                 throw new ArgumentException ();
1347
1348                         SortImpl (array, null, index, length, comparer);
1349                 }
1350
1351                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1352                 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
1353                 {
1354                         if (items == null) {
1355                                 Sort (keys, index, length, comparer);
1356                                 return;
1357                         }
1358
1359                         if (keys == null)
1360                                 throw new ArgumentNullException ("keys");
1361
1362                         if (keys.Rank > 1 || items.Rank > 1)
1363                                 throw new RankException ();
1364
1365                         if (keys.GetLowerBound (0) != items.GetLowerBound (0))
1366                                 throw new ArgumentException ();
1367
1368                         if (index < keys.GetLowerBound (0))
1369                                 throw new ArgumentOutOfRangeException ("index");
1370
1371                         if (length < 0)
1372                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1373                                         "Value has to be >= 0."));
1374
1375                         if (items.Length - (index + items.GetLowerBound (0)) < length || keys.Length - (index + keys.GetLowerBound (0)) < length)
1376                                 throw new ArgumentException ();
1377
1378                         SortImpl (keys, items, index, length, comparer);
1379                 }
1380
1381                 private static void SortImpl (Array keys, Array items, int index, int length, IComparer comparer)
1382                 {
1383                         if (length <= 1)
1384                                 return;
1385
1386                         int low = index;
1387                         int high = index + length - 1;
1388
1389 #if !BOOTSTRAP_BASIC
1390                         if (comparer == null && items is object[]) {
1391                                 /* Its better to compare typecodes as casts treat long/ulong/long based enums the same */
1392                                 switch (Type.GetTypeCode (keys.GetType ().GetElementType ())) {
1393                                 case TypeCode.Int32:
1394                                         qsort (keys as Int32[], items as object[], low, high);
1395                                         return;
1396                                 case TypeCode.Int64:
1397                                         qsort (keys as Int64[], items as object[], low, high);
1398                                         return;
1399                                 case TypeCode.Byte:
1400                                         qsort (keys as byte[], items as object[], low, high);
1401                                         return;
1402                                 case TypeCode.Char:
1403                                         qsort (keys as char[], items as object[], low, high);
1404                                         return;
1405                                 case TypeCode.DateTime:
1406                                         qsort (keys as DateTime[], items as object[], low, high);
1407                                         return;
1408                                 case TypeCode.Decimal:
1409                                         qsort (keys as decimal[], items as object[], low, high);
1410                                         return;
1411                                 case TypeCode.Double:
1412                                         qsort (keys as double[], items as object[], low, high);
1413                                         return;
1414                                 case TypeCode.Int16:
1415                                         qsort (keys as Int16[], items as object[], low, high);
1416                                         return;
1417                                 case TypeCode.SByte:
1418                                         qsort (keys as SByte[], items as object[], low, high);
1419                                         return;
1420                                 case TypeCode.Single:
1421                                         qsort (keys as Single[], items as object[], low, high);
1422                                         return;
1423                                 case TypeCode.UInt16:
1424                                         qsort (keys as UInt16[], items as object[], low, high);
1425                                         return;
1426                                 case TypeCode.UInt32:
1427                                         qsort (keys as UInt32[], items as object[], low, high);
1428                                         return;
1429                                 case TypeCode.UInt64:
1430                                         qsort (keys as UInt64[], items as object[], low, high);
1431                                         return;
1432                                 default:
1433                                         break;
1434                                 }
1435                         }
1436 #endif
1437
1438                         if (comparer == null)
1439                                 CheckComparerAvailable (keys, low, high);
1440
1441                         try {
1442                                 qsort (keys, items, low, high, comparer);
1443                         } catch (Exception e) {
1444                                 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1445                         }
1446                 }
1447
1448                 struct QSortStack {
1449                         public int high;
1450                         public int low;
1451                 }
1452
1453                 static bool QSortArrange (Array keys, Array items, int lo, ref object v0, int hi, ref object v1, IComparer comparer)
1454                 {
1455                         IComparable cmp;
1456                         object tmp;
1457
1458                         if (comparer != null) {
1459                                 if (comparer.Compare (v1, v0) < 0) {
1460                                         swap (keys, items, lo, hi);
1461                                         tmp = v0;
1462                                         v0 = v1;
1463                                         v1 = tmp;
1464
1465                                         return true;
1466                                 }
1467                         } else if (v0 != null) {
1468                                 cmp = v1 as IComparable;
1469
1470                                 if (v1 == null || cmp.CompareTo (v0) < 0) {
1471                                         swap (keys, items, lo, hi);
1472                                         tmp = v0;
1473                                         v0 = v1;
1474                                         v1 = tmp;
1475
1476                                         return true;
1477                                 }
1478                         }
1479
1480                         return false;
1481                 }
1482
1483                 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
1484                 {
1485                         QSortStack[] stack = new QSortStack[32];
1486                         const int QSORT_THRESHOLD = 7;
1487                         int high, low, mid, i, k;
1488                         object key, hi, lo;
1489                         IComparable cmp;
1490                         int sp = 1;
1491
1492                         // initialize our stack
1493                         stack[0].high = high0;
1494                         stack[0].low = low0;
1495
1496                         do {
1497                                 // pop the stack
1498                                 sp--;
1499                                 high = stack[sp].high;
1500                                 low = stack[sp].low;
1501
1502                                 if ((low + QSORT_THRESHOLD) > high) {
1503                                         // switch to insertion sort
1504                                         for (i = low + 1; i <= high; i++) {
1505                                                 for (k = i; k > low; k--) {
1506                                                         lo = keys.GetValueImpl (k - 1);
1507                                                         hi = keys.GetValueImpl (k);
1508                                                         if (comparer != null) {
1509                                                                 if (comparer.Compare (hi, lo) >= 0)
1510                                                                         break;
1511                                                         } else {
1512                                                                 if (lo == null)
1513                                                                         break;
1514
1515                                                                 if (hi != null) {
1516                                                                         cmp = hi as IComparable;
1517                                                                         if (cmp.CompareTo (lo) >= 0)
1518                                                                                 break;
1519                                                                 }
1520                                                         }
1521
1522                                                         swap (keys, items, k - 1, k);
1523                                                 }
1524                                         }
1525
1526                                         continue;
1527                                 }
1528
1529                                 // calculate the middle element
1530                                 mid = low + ((high - low) / 2);
1531
1532                                 // get the 3 keys
1533                                 key = keys.GetValueImpl (mid);
1534                                 hi = keys.GetValueImpl (high);
1535                                 lo = keys.GetValueImpl (low);
1536
1537                                 // once we re-order the low, mid, and high elements to be in
1538                                 // ascending order, we'll use mid as our pivot.
1539                                 QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1540                                 if (QSortArrange (keys, items, mid, ref key, high, ref hi, comparer))
1541                                         QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1542
1543                                 cmp = key as IComparable;
1544
1545                                 // since we've already guaranteed that lo <= mid and mid <= hi,
1546                                 // we can skip comparing them again.
1547                                 k = high - 1;
1548                                 i = low + 1;
1549
1550                                 do {
1551                                         // Move the walls in
1552                                         if (comparer != null) {
1553                                                 // find the first element with a value >= pivot value
1554                                                 while (i < k && comparer.Compare (key, keys.GetValueImpl (i)) > 0)
1555                                                         i++;
1556
1557                                                 // find the last element with a value <= pivot value
1558                                                 while (k > i && comparer.Compare (key, keys.GetValueImpl (k)) < 0)
1559                                                         k--;
1560                                         } else if (cmp != null) {
1561                                                 // find the first element with a value >= pivot value
1562                                                 while (i < k && cmp.CompareTo (keys.GetValueImpl (i)) > 0)
1563                                                         i++;
1564
1565                                                 // find the last element with a value <= pivot value
1566                                                 while (k > i && cmp.CompareTo (keys.GetValueImpl (k)) < 0)
1567                                                         k--;
1568                                         } else {
1569                                                 // This has the effect of moving the null values to the front if comparer is null
1570                                                 while (i < k && keys.GetValueImpl (i) == null)
1571                                                         i++;
1572
1573                                                 while (k > i && keys.GetValueImpl (k) != null)
1574                                                         k--;
1575                                         }
1576
1577                                         if (k <= i)
1578                                                 break;
1579
1580                                         swap (keys, items, i, k);
1581
1582                                         i++;
1583                                         k--;
1584                                 } while (true);
1585
1586                                 // push our partitions onto the stack, largest first
1587                                 // (to make sure we don't run out of stack space)
1588                                 if ((high - k) >= (k - low)) {
1589                                         if ((k + 1) < high) {
1590                                                 stack[sp].high = high;
1591                                                 stack[sp].low = k;
1592                                                 sp++;
1593                                         }
1594
1595                                         if ((k - 1) > low) {
1596                                                 stack[sp].high = k;
1597                                                 stack[sp].low = low;
1598                                                 sp++;
1599                                         }
1600                                 } else {
1601                                         if ((k - 1) > low) {
1602                                                 stack[sp].high = k;
1603                                                 stack[sp].low = low;
1604                                                 sp++;
1605                                         }
1606
1607                                         if ((k + 1) < high) {
1608                                                 stack[sp].high = high;
1609                                                 stack[sp].low = k;
1610                                                 sp++;
1611                                         }
1612                                 }
1613                         } while (sp > 0);
1614                 }
1615
1616                 private static void CheckComparerAvailable (Array keys, int low, int high)
1617                 {
1618                         // move null keys to beginning of array,
1619                         // ensure that non-null keys implement IComparable
1620                         for (int i = 0; i < high; i++) {
1621                                 object obj = keys.GetValueImpl (i);
1622                                 if (obj == null)
1623                                         continue;
1624                                 if (!(obj is IComparable)) {
1625                                         string msg = Locale.GetText ("No IComparable interface found for type '{0}'.");
1626                                         throw new InvalidOperationException (String.Format (msg, obj.GetType ()));
1627                                 }
1628                         }
1629                 }
1630
1631                 private static void swap (Array keys, Array items, int i, int j)
1632                 {
1633                         object tmp = keys.GetValueImpl (i);
1634                         keys.SetValueImpl (keys.GetValueImpl (j), i);
1635                         keys.SetValueImpl (tmp, j);
1636
1637                         if (items != null) {
1638                                 tmp = items.GetValueImpl (i);
1639                                 items.SetValueImpl (items.GetValueImpl (j), i);
1640                                 items.SetValueImpl (tmp, j);
1641                         }
1642                 }
1643
1644                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1645                 public static void Sort<T> (T [] array)
1646                 {
1647                         Sort<T> (array, (IComparer<T>)null);
1648                 }
1649
1650                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1651                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items)
1652                 {
1653                         Sort<TKey, TValue> (keys, items, (IComparer<TKey>)null);
1654                 }
1655
1656                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1657                 public static void Sort<T> (T [] array, IComparer<T> comparer)
1658                 {
1659                         if (array == null)
1660                                 throw new ArgumentNullException ("array");
1661
1662                         SortImpl<T> (array, 0, array.Length, comparer);
1663                 }
1664
1665                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1666                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, IComparer<TKey> comparer)
1667                 {
1668                         if (items == null) {
1669                                 Sort<TKey> (keys, comparer);
1670                                 return;
1671                         }
1672
1673                         if (keys == null)
1674                                 throw new ArgumentNullException ("keys");
1675
1676                         if (keys.Length != items.Length)
1677                                 throw new ArgumentException ("Length of keys and items does not match.");
1678
1679                         SortImpl<TKey, TValue> (keys, items, 0, keys.Length, comparer);
1680                 }
1681
1682                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1683                 public static void Sort<T> (T [] array, int index, int length)
1684                 {
1685                         Sort<T> (array, index, length, (IComparer<T>)null);
1686                 }
1687
1688                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1689                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length)
1690                 {
1691                         Sort<TKey, TValue> (keys, items, index, length, (IComparer<TKey>)null);
1692                 }
1693
1694                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1695                 public static void Sort<T> (T [] array, int index, int length, IComparer<T> comparer)
1696                 {
1697                         if (array == null)
1698                                 throw new ArgumentNullException ("array");
1699
1700                         if (index < 0)
1701                                 throw new ArgumentOutOfRangeException ("index");
1702
1703                         if (length < 0)
1704                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1705                                         "Value has to be >= 0."));
1706
1707                         if (index + length > array.Length)
1708                                 throw new ArgumentException ();
1709
1710                         SortImpl<T> (array, index, length, comparer);
1711                 }
1712
1713                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1714                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1715                 {
1716                         if (items == null) {
1717                                 Sort<TKey> (keys, index, length, comparer);
1718                                 return;
1719                         }
1720
1721                         if (keys == null)
1722                                 throw new ArgumentNullException ("keys");
1723
1724                         if (index < 0)
1725                                 throw new ArgumentOutOfRangeException ("index");
1726
1727                         if (length < 0)
1728                                 throw new ArgumentOutOfRangeException ("length");
1729
1730                         if (items.Length - index < length || keys.Length - index < length)
1731                                 throw new ArgumentException ();
1732
1733                         SortImpl<TKey, TValue> (keys, items, index, length, comparer);
1734                 }
1735
1736                 private static void SortImpl<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1737                 {
1738                         if (keys.Length <= 1)
1739                                 return;
1740
1741                         int low = index;
1742                         int high = index + length - 1;
1743
1744                         //
1745                         // Check for value types which can be sorted without Compare () method
1746                         //
1747                         if (comparer == null) {
1748                                 /* Avoid this when using full-aot to prevent the generation of many unused qsort<K,T> instantiations */
1749 #if FULL_AOT_RUNTIME
1750 #if !BOOTSTRAP_BASIC
1751                                 switch (Type.GetTypeCode (typeof (TKey))) {
1752                                 case TypeCode.Int32:
1753                                         qsort (keys as Int32[], items, low, high);
1754                                         return;
1755                                 case TypeCode.Int64:
1756                                         qsort (keys as Int64[], items, low, high);
1757                                         return;
1758                                 case TypeCode.Byte:
1759                                         qsort (keys as byte[], items, low, high);
1760                                         return;
1761                                 case TypeCode.Char:
1762                                         qsort (keys as char[], items, low, high);
1763                                         return;
1764                                 case TypeCode.DateTime:
1765                                         qsort (keys as DateTime[], items, low, high);
1766                                         return;
1767                                 case TypeCode.Decimal:
1768                                         qsort (keys as decimal[], items, low, high);
1769                                         return;
1770                                 case TypeCode.Double:
1771                                         qsort (keys as double[], items, low, high);
1772                                         return;
1773                                 case TypeCode.Int16:
1774                                         qsort (keys as Int16[], items, low, high);
1775                                         return;
1776                                 case TypeCode.SByte:
1777                                         qsort (keys as SByte[], items, low, high);
1778                                         return;
1779                                 case TypeCode.Single:
1780                                         qsort (keys as Single[], items, low, high);
1781                                         return;
1782                                 case TypeCode.UInt16:
1783                                         qsort (keys as UInt16[], items, low, high);
1784                                         return;
1785                                 case TypeCode.UInt32:
1786                                         qsort (keys as UInt32[], items, low, high);
1787                                         return;
1788                                 case TypeCode.UInt64:
1789                                         qsort (keys as UInt64[], items, low, high);
1790                                         return;
1791                                 }
1792 #endif
1793 #endif
1794                                 // Using Comparer<TKey> adds a small overload, but with value types it
1795                                 // helps us to not box them.
1796                                 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1797                                                 typeof (TKey).IsValueType)
1798                                         comparer = Comparer<TKey>.Default;
1799                         }
1800
1801                         if (comparer == null)
1802                                 CheckComparerAvailable<TKey> (keys, low, high);
1803
1804                         //try {
1805                                 qsort (keys, items, low, high, comparer);
1806                                 //} catch (Exception e) {
1807                                 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1808                                 //}
1809                 }
1810
1811                 // Specialized version for items==null
1812                 private static void SortImpl<TKey> (TKey [] keys, int index, int length, IComparer<TKey> comparer)
1813                 {
1814                         if (keys.Length <= 1)
1815                                 return;
1816
1817                         int low = index;
1818                         int high = index + length - 1;
1819
1820                         //
1821                         // Check for value types which can be sorted without Compare () method
1822                         //
1823                         if (comparer == null) {
1824 #if !BOOTSTRAP_BASIC
1825                                 switch (Type.GetTypeCode (typeof (TKey))) {
1826                                 case TypeCode.Int32:
1827                                         qsort (keys as Int32[], low, high);
1828                                         return;
1829                                 case TypeCode.Int64:
1830                                         qsort (keys as Int64[], low, high);
1831                                         return;
1832                                 case TypeCode.Byte:
1833                                         qsort (keys as byte[], low, high);
1834                                         return;
1835                                 case TypeCode.Char:
1836                                         qsort (keys as char[], low, high);
1837                                         return;
1838                                 case TypeCode.DateTime:
1839                                         qsort (keys as DateTime[], low, high);
1840                                         return;
1841                                 case TypeCode.Decimal:
1842                                         qsort (keys as decimal[], low, high);
1843                                         return;
1844                                 case TypeCode.Double:
1845                                         qsort (keys as double[], low, high);
1846                                         return;
1847                                 case TypeCode.Int16:
1848                                         qsort (keys as Int16[], low, high);
1849                                         return;
1850                                 case TypeCode.SByte:
1851                                         qsort (keys as SByte[], low, high);
1852                                         return;
1853                                 case TypeCode.Single:
1854                                         qsort (keys as Single[], low, high);
1855                                         return;
1856                                 case TypeCode.UInt16:
1857                                         qsort (keys as UInt16[], low, high);
1858                                         return;
1859                                 case TypeCode.UInt32:
1860                                         qsort (keys as UInt32[], low, high);
1861                                         return;
1862                                 case TypeCode.UInt64:
1863                                         qsort (keys as UInt64[], low, high);
1864                                         return;
1865                                 }
1866 #endif
1867                                 // Using Comparer<TKey> adds a small overload, but with value types it
1868                                 // helps us to not box them.
1869                                 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1870                                                 typeof (TKey).IsValueType)
1871                                         comparer = Comparer<TKey>.Default;
1872                         }
1873
1874                         if (comparer == null)
1875                                 CheckComparerAvailable<TKey> (keys, low, high);
1876
1877                         //try {
1878                                 qsort<TKey> (keys, low, high, comparer);
1879                                 //} catch (Exception e) {
1880                                 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1881                                 //}
1882                 }
1883
1884                 public static void Sort<T> (T [] array, Comparison<T> comparison)
1885                 {
1886                         if (array == null)
1887                                 throw new ArgumentNullException ("array");
1888
1889                         if (comparison == null)
1890                                 throw new ArgumentNullException ("comparison");
1891
1892                         SortImpl<T> (array, array.Length, comparison);
1893                 }
1894
1895                 // used by List<T>.Sort (Comparison <T>)
1896                 internal static void SortImpl<T> (T [] array, int length, Comparison<T> comparison)
1897                 {
1898                         if (length <= 1)
1899                                 return;
1900
1901                         try {
1902                                 int low0 = 0;
1903                                 int high0 = length - 1;
1904                                 qsort<T> (array, low0, high0, comparison);
1905                         } catch (InvalidOperationException) {
1906                                 throw;
1907                         } catch (Exception e) {
1908                                 throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e);
1909                         }
1910                 }
1911
1912                 static bool QSortArrange<T, U> (T [] keys, U [] items, int lo, int hi) where T : IComparable<T>
1913                 {
1914                         if (keys[lo] != null) {
1915                                 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1916                                         swap (keys, items, lo, hi);
1917                                         return true;
1918                                 }
1919                         }
1920
1921                         return false;
1922                 }
1923
1924                 // Specialized version for items==null
1925                 static bool QSortArrange<T> (T [] keys, int lo, int hi) where T : IComparable<T>
1926                 {
1927                         if (keys[lo] != null) {
1928                                 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1929                                         swap (keys, lo, hi);
1930                                         return true;
1931                                 }
1932                         }
1933
1934                         return false;
1935                 }
1936
1937                 private static void qsort<T, U> (T[] keys, U[] items, int low0, int high0) where T : IComparable<T>
1938                 {
1939                         QSortStack[] stack = new QSortStack[32];
1940                         const int QSORT_THRESHOLD = 7;
1941                         int high, low, mid, i, k;
1942                         int sp = 1;
1943                         T key;
1944
1945                         // initialize our stack
1946                         stack[0].high = high0;
1947                         stack[0].low = low0;
1948
1949                         do {
1950                                 // pop the stack
1951                                 sp--;
1952                                 high = stack[sp].high;
1953                                 low = stack[sp].low;
1954
1955                                 if ((low + QSORT_THRESHOLD) > high) {
1956                                         // switch to insertion sort
1957                                         for (i = low + 1; i <= high; i++) {
1958                                                 for (k = i; k > low; k--) {
1959                                                         // if keys[k] >= keys[k-1], break
1960                                                         if (keys[k-1] == null)
1961                                                                 break;
1962
1963                                                         if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
1964                                                                 break;
1965
1966                                                         swap (keys, items, k - 1, k);
1967                                                 }
1968                                         }
1969
1970                                         continue;
1971                                 }
1972
1973                                 // calculate the middle element
1974                                 mid = low + ((high - low) / 2);
1975
1976                                 // once we re-order the lo, mid, and hi elements to be in
1977                                 // ascending order, we'll use mid as our pivot.
1978                                 QSortArrange<T, U> (keys, items, low, mid);
1979                                 if (QSortArrange<T, U> (keys, items, mid, high))
1980                                         QSortArrange<T, U> (keys, items, low, mid);
1981
1982                                 key = keys[mid];
1983
1984                                 // since we've already guaranteed that lo <= mid and mid <= hi,
1985                                 // we can skip comparing them again
1986                                 k = high - 1;
1987                                 i = low + 1;
1988
1989                                 do {
1990                                         if (key != null) {
1991                                                 // find the first element with a value >= pivot value
1992                                                 while (i < k && key.CompareTo (keys[i]) > 0)
1993                                                         i++;
1994
1995                                                 // find the last element with a value <= pivot value
1996                                                 while (k > i && key.CompareTo (keys[k]) < 0)
1997                                                         k--;
1998                                         } else {
1999                                                 while (i < k && keys[i] == null)
2000                                                         i++;
2001
2002                                                 while (k > i && keys[k] != null)
2003                                                         k--;
2004                                         }
2005
2006                                         if (k <= i)
2007                                                 break;
2008
2009                                         swap (keys, items, i, k);
2010
2011                                         i++;
2012                                         k--;
2013                                 } while (true);
2014
2015                                 // push our partitions onto the stack, largest first
2016                                 // (to make sure we don't run out of stack space)
2017                                 if ((high - k) >= (k - low)) {
2018                                         if ((k + 1) < high) {
2019                                                 stack[sp].high = high;
2020                                                 stack[sp].low = k;
2021                                                 sp++;
2022                                         }
2023
2024                                         if ((k - 1) > low) {
2025                                                 stack[sp].high = k;
2026                                                 stack[sp].low = low;
2027                                                 sp++;
2028                                         }
2029                                 } else {
2030                                         if ((k - 1) > low) {
2031                                                 stack[sp].high = k;
2032                                                 stack[sp].low = low;
2033                                                 sp++;
2034                                         }
2035
2036                                         if ((k + 1) < high) {
2037                                                 stack[sp].high = high;
2038                                                 stack[sp].low = k;
2039                                                 sp++;
2040                                         }
2041                                 }
2042                         } while (sp > 0);
2043                 }
2044
2045                 // Specialized version for items==null
2046                 private static void qsort<T> (T[] keys, int low0, int high0) where T : IComparable<T>
2047                 {
2048                         QSortStack[] stack = new QSortStack[32];
2049                         const int QSORT_THRESHOLD = 7;
2050                         int high, low, mid, i, k;
2051                         int sp = 1;
2052                         T key;
2053
2054                         // initialize our stack
2055                         stack[0].high = high0;
2056                         stack[0].low = low0;
2057
2058                         do {
2059                                 // pop the stack
2060                                 sp--;
2061                                 high = stack[sp].high;
2062                                 low = stack[sp].low;
2063
2064                                 if ((low + QSORT_THRESHOLD) > high) {
2065                                         // switch to insertion sort
2066                                         for (i = low + 1; i <= high; i++) {
2067                                                 for (k = i; k > low; k--) {
2068                                                         // if keys[k] >= keys[k-1], break
2069                                                         if (keys[k-1] == null)
2070                                                                 break;
2071
2072                                                         if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
2073                                                                 break;
2074
2075                                                         swap (keys, k - 1, k);
2076                                                 }
2077                                         }
2078
2079                                         continue;
2080                                 }
2081
2082                                 // calculate the middle element
2083                                 mid = low + ((high - low) / 2);
2084
2085                                 // once we re-order the lo, mid, and hi elements to be in
2086                                 // ascending order, we'll use mid as our pivot.
2087                                 QSortArrange<T> (keys, low, mid);
2088                                 if (QSortArrange<T> (keys, mid, high))
2089                                         QSortArrange<T> (keys, low, mid);
2090
2091                                 key = keys[mid];
2092
2093                                 // since we've already guaranteed that lo <= mid and mid <= hi,
2094                                 // we can skip comparing them again
2095                                 k = high - 1;
2096                                 i = low + 1;
2097
2098                                 do {
2099                                         if (key != null) {
2100                                                 // find the first element with a value >= pivot value
2101                                                 while (i < k && key.CompareTo (keys[i]) > 0)
2102                                                         i++;
2103
2104                                                 // find the last element with a value <= pivot value
2105                                                 while (k >= i && key.CompareTo (keys[k]) < 0)
2106                                                         k--;
2107                                         } else {
2108                                                 while (i < k && keys[i] == null)
2109                                                         i++;
2110
2111                                                 while (k >= i && keys[k] != null)
2112                                                         k--;
2113                                         }
2114
2115                                         if (k <= i)
2116                                                 break;
2117
2118                                         swap (keys, i, k);
2119
2120                                         i++;
2121                                         k--;
2122                                 } while (true);
2123
2124                                 // push our partitions onto the stack, largest first
2125                                 // (to make sure we don't run out of stack space)
2126                                 if ((high - k) >= (k - low)) {
2127                                         if ((k + 1) < high) {
2128                                                 stack[sp].high = high;
2129                                                 stack[sp].low = k;
2130                                                 sp++;
2131                                         }
2132
2133                                         if ((k - 1) > low) {
2134                                                 stack[sp].high = k;
2135                                                 stack[sp].low = low;
2136                                                 sp++;
2137                                         }
2138                                 } else {
2139                                         if ((k - 1) > low) {
2140                                                 stack[sp].high = k;
2141                                                 stack[sp].low = low;
2142                                                 sp++;
2143                                         }
2144
2145                                         if ((k + 1) < high) {
2146                                                 stack[sp].high = high;
2147                                                 stack[sp].low = k;
2148                                                 sp++;
2149                                         }
2150                                 }
2151                         } while (sp > 0);
2152                 }
2153
2154                 static bool QSortArrange<K, V> (K [] keys, V [] items, int lo, int hi, IComparer<K> comparer)
2155                 {
2156                         IComparable<K> gcmp;
2157                         IComparable cmp;
2158
2159                         if (comparer != null) {
2160                                 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2161                                         swap<K, V> (keys, items, lo, hi);
2162                                         return true;
2163                                 }
2164                         } else if (keys[lo] != null) {
2165                                 if (keys[hi] == null) {
2166                                         swap<K, V> (keys, items, lo, hi);
2167                                         return true;
2168                                 }
2169
2170                                 gcmp = keys[hi] as IComparable<K>;
2171                                 if (gcmp != null) {
2172                                         if (gcmp.CompareTo (keys[lo]) < 0) {
2173                                                 swap<K, V> (keys, items, lo, hi);
2174                                                 return true;
2175                                         }
2176
2177                                         return false;
2178                                 }
2179
2180                                 cmp = keys[hi] as IComparable;
2181                                 if (cmp != null) {
2182                                         if (cmp.CompareTo (keys[lo]) < 0) {
2183                                                 swap<K, V> (keys, items, lo, hi);
2184                                                 return true;
2185                                         }
2186
2187                                         return false;
2188                                 }
2189                         }
2190
2191                         return false;
2192                 }
2193
2194                 // Specialized version for items==null
2195                 static bool QSortArrange<K> (K [] keys, int lo, int hi, IComparer<K> comparer)
2196                 {
2197                         IComparable<K> gcmp;
2198                         IComparable cmp;
2199
2200                         if (comparer != null) {
2201                                 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2202                                         swap<K> (keys, lo, hi);
2203                                         return true;
2204                                 }
2205                         } else if (keys[lo] != null) {
2206                                 if (keys[hi] == null) {
2207                                         swap<K> (keys, lo, hi);
2208                                         return true;
2209                                 }
2210
2211                                 gcmp = keys[hi] as IComparable<K>;
2212                                 if (gcmp != null) {
2213                                         if (gcmp.CompareTo (keys[lo]) < 0) {
2214                                                 swap<K> (keys, lo, hi);
2215                                                 return true;
2216                                         }
2217
2218                                         return false;
2219                                 }
2220
2221                                 cmp = keys[hi] as IComparable;
2222                                 if (cmp != null) {
2223                                         if (cmp.CompareTo (keys[lo]) < 0) {
2224                                                 swap<K> (keys, lo, hi);
2225                                                 return true;
2226                                         }
2227
2228                                         return false;
2229                                 }
2230                         }
2231
2232                         return false;
2233                 }
2234
2235                 private static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
2236                 {
2237                         QSortStack[] stack = new QSortStack[32];
2238                         const int QSORT_THRESHOLD = 7;
2239                         int high, low, mid, i, k;
2240                         IComparable<K> gcmp;
2241                         IComparable cmp;
2242                         int sp = 1;
2243                         K key;
2244
2245                         // initialize our stack
2246                         stack[0].high = high0;
2247                         stack[0].low = low0;
2248
2249                         do {
2250                                 // pop the stack
2251                                 sp--;
2252                                 high = stack[sp].high;
2253                                 low = stack[sp].low;
2254
2255                                 if ((low + QSORT_THRESHOLD) > high) {
2256                                         // switch to insertion sort
2257                                         for (i = low + 1; i <= high; i++) {
2258                                                 for (k = i; k > low; k--) {
2259                                                         // if keys[k] >= keys[k-1], break
2260                                                         if (comparer != null) {
2261                                                                 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2262                                                                         break;
2263                                                         } else {
2264                                                                 if (keys[k-1] == null)
2265                                                                         break;
2266
2267                                                                 if (keys[k] != null) {
2268                                                                         gcmp = keys[k] as IComparable<K>;
2269                                                                         cmp = keys[k] as IComparable;
2270                                                                         if (gcmp != null) {
2271                                                                                 if (gcmp.CompareTo (keys[k-1]) >= 0)
2272                                                                                         break;
2273                                                                         } else {
2274                                                                                 if (cmp.CompareTo (keys[k-1]) >= 0)
2275                                                                                         break;
2276                                                                         }
2277                                                                 }
2278                                                         }
2279
2280                                                         swap<K, V> (keys, items, k - 1, k);
2281                                                 }
2282                                         }
2283
2284                                         continue;
2285                                 }
2286
2287                                 // calculate the middle element
2288                                 mid = low + ((high - low) / 2);
2289
2290                                 // once we re-order the low, mid, and high elements to be in
2291                                 // ascending order, we'll use mid as our pivot.
2292                                 QSortArrange<K, V> (keys, items, low, mid, comparer);
2293                                 if (QSortArrange<K, V> (keys, items, mid, high, comparer))
2294                                         QSortArrange<K, V> (keys, items, low, mid, comparer);
2295
2296                                 key = keys[mid];
2297                                 gcmp = key as IComparable<K>;
2298                                 cmp = key as IComparable;
2299
2300                                 // since we've already guaranteed that lo <= mid and mid <= hi,
2301                                 // we can skip comparing them again.
2302                                 k = high - 1;
2303                                 i = low + 1;
2304
2305                                 do {
2306                                         // Move the walls in
2307                                         if (comparer != null) {
2308                                                 // find the first element with a value >= pivot value
2309                                                 while (i < k && comparer.Compare (key, keys[i]) > 0)
2310                                                         i++;
2311
2312                                                 // find the last element with a value <= pivot value
2313                                                 while (k > i && comparer.Compare (key, keys[k]) < 0)
2314                                                         k--;
2315                                         } else {
2316                                                 if (gcmp != null) {
2317                                                         // find the first element with a value >= pivot value
2318                                                         while (i < k && gcmp.CompareTo (keys[i]) > 0)
2319                                                                 i++;
2320
2321                                                         // find the last element with a value <= pivot value
2322                                                         while (k > i && gcmp.CompareTo (keys[k]) < 0)
2323                                                                 k--;
2324                                                 } else if (cmp != null) {
2325                                                         // find the first element with a value >= pivot value
2326                                                         while (i < k && cmp.CompareTo (keys[i]) > 0)
2327                                                                 i++;
2328
2329                                                         // find the last element with a value <= pivot value
2330                                                         while (k > i && cmp.CompareTo (keys[k]) < 0)
2331                                                                 k--;
2332                                                 } else {
2333                                                         while (i < k && keys[i] == null)
2334                                                                 i++;
2335
2336                                                         while (k > i && keys[k] != null)
2337                                                                 k--;
2338                                                 }
2339                                         }
2340
2341                                         if (k <= i)
2342                                                 break;
2343
2344                                         swap<K, V> (keys, items, i, k);
2345
2346                                         i++;
2347                                         k--;
2348                                 } while (true);
2349
2350                                 // push our partitions onto the stack, largest first
2351                                 // (to make sure we don't run out of stack space)
2352                                 if ((high - k) >= (k - low)) {
2353                                         if ((k + 1) < high) {
2354                                                 stack[sp].high = high;
2355                                                 stack[sp].low = k;
2356                                                 sp++;
2357                                         }
2358
2359                                         if ((k - 1) > low) {
2360                                                 stack[sp].high = k;
2361                                                 stack[sp].low = low;
2362                                                 sp++;
2363                                         }
2364                                 } else {
2365                                         if ((k - 1) > low) {
2366                                                 stack[sp].high = k;
2367                                                 stack[sp].low = low;
2368                                                 sp++;
2369                                         }
2370
2371                                         if ((k + 1) < high) {
2372                                                 stack[sp].high = high;
2373                                                 stack[sp].low = k;
2374                                                 sp++;
2375                                         }
2376                                 }
2377                         } while (sp > 0);
2378                 }
2379
2380                 // Specialized version for items==null
2381                 private static void qsort<K> (K [] keys, int low0, int high0, IComparer<K> comparer)
2382                 {
2383                         QSortStack[] stack = new QSortStack[32];
2384                         const int QSORT_THRESHOLD = 7;
2385                         int high, low, mid, i, k;
2386                         IComparable<K> gcmp;
2387                         IComparable cmp;
2388                         int sp = 1;
2389                         K key;
2390
2391                         // initialize our stack
2392                         stack[0].high = high0;
2393                         stack[0].low = low0;
2394
2395                         do {
2396                                 // pop the stack
2397                                 sp--;
2398                                 high = stack[sp].high;
2399                                 low = stack[sp].low;
2400
2401                                 if ((low + QSORT_THRESHOLD) > high) {
2402                                         // switch to insertion sort
2403                                         for (i = low + 1; i <= high; i++) {
2404                                                 for (k = i; k > low; k--) {
2405                                                         // if keys[k] >= keys[k-1], break
2406                                                         if (comparer != null) {
2407                                                                 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2408                                                                         break;
2409                                                         } else {
2410                                                                 if (keys[k-1] == null)
2411                                                                         break;
2412
2413                                                                 if (keys[k] != null) {
2414                                                                         gcmp = keys[k] as IComparable<K>;
2415                                                                         cmp = keys[k] as IComparable;
2416                                                                         if (gcmp != null) {
2417                                                                                 if (gcmp.CompareTo (keys[k-1]) >= 0)
2418                                                                                         break;
2419                                                                         } else {
2420                                                                                 if (cmp.CompareTo (keys[k-1]) >= 0)
2421                                                                                         break;
2422                                                                         }
2423                                                                 }
2424                                                         }
2425
2426                                                         swap<K> (keys, k - 1, k);
2427                                                 }
2428                                         }
2429
2430                                         continue;
2431                                 }
2432
2433                                 // calculate the middle element
2434                                 mid = low + ((high - low) / 2);
2435
2436                                 // once we re-order the low, mid, and high elements to be in
2437                                 // ascending order, we'll use mid as our pivot.
2438                                 QSortArrange<K> (keys, low, mid, comparer);
2439                                 if (QSortArrange<K> (keys, mid, high, comparer))
2440                                         QSortArrange<K> (keys, low, mid, comparer);
2441
2442                                 key = keys[mid];
2443                                 gcmp = key as IComparable<K>;
2444                                 cmp = key as IComparable;
2445
2446                                 // since we've already guaranteed that lo <= mid and mid <= hi,
2447                                 // we can skip comparing them again.
2448                                 k = high - 1;
2449                                 i = low + 1;
2450
2451                                 do {
2452                                         // Move the walls in
2453                                         if (comparer != null) {
2454                                                 // find the first element with a value >= pivot value
2455                                                 while (i < k && comparer.Compare (key, keys[i]) > 0)
2456                                                         i++;
2457
2458                                                 // find the last element with a value <= pivot value
2459                                                 while (k > i && comparer.Compare (key, keys[k]) < 0)
2460                                                         k--;
2461                                         } else {
2462                                                 if (gcmp != null) {
2463                                                         // find the first element with a value >= pivot value
2464                                                         while (i < k && gcmp.CompareTo (keys[i]) > 0)
2465                                                                 i++;
2466
2467                                                         // find the last element with a value <= pivot value
2468                                                         while (k > i && gcmp.CompareTo (keys[k]) < 0)
2469                                                                 k--;
2470                                                 } else if (cmp != null) {
2471                                                         // find the first element with a value >= pivot value
2472                                                         while (i < k && cmp.CompareTo (keys[i]) > 0)
2473                                                                 i++;
2474
2475                                                         // find the last element with a value <= pivot value
2476                                                         while (k > i && cmp.CompareTo (keys[k]) < 0)
2477                                                                 k--;
2478                                                 } else {
2479                                                         while (i < k && keys[i] == null)
2480                                                                 i++;
2481
2482                                                         while (k > i && keys[k] != null)
2483                                                                 k--;
2484                                                 }
2485                                         }
2486
2487                                         if (k <= i)
2488                                                 break;
2489
2490                                         swap<K> (keys, i, k);
2491
2492                                         i++;
2493                                         k--;
2494                                 } while (true);
2495
2496                                 // push our partitions onto the stack, largest first
2497                                 // (to make sure we don't run out of stack space)
2498                                 if ((high - k) >= (k - low)) {
2499                                         if ((k + 1) < high) {
2500                                                 stack[sp].high = high;
2501                                                 stack[sp].low = k;
2502                                                 sp++;
2503                                         }
2504
2505                                         if ((k - 1) > low) {
2506                                                 stack[sp].high = k;
2507                                                 stack[sp].low = low;
2508                                                 sp++;
2509                                         }
2510                                 } else {
2511                                         if ((k - 1) > low) {
2512                                                 stack[sp].high = k;
2513                                                 stack[sp].low = low;
2514                                                 sp++;
2515                                         }
2516
2517                                         if ((k + 1) < high) {
2518                                                 stack[sp].high = high;
2519                                                 stack[sp].low = k;
2520                                                 sp++;
2521                                         }
2522                                 }
2523                         } while (sp > 0);
2524                 }
2525
2526                 static bool QSortArrange<T> (T [] array, int lo, int hi, Comparison<T> compare)
2527                 {
2528                         if (array[lo] != null) {
2529                                 if (array[hi] == null || compare (array[hi], array[lo]) < 0) {
2530                                         swap<T> (array, lo, hi);
2531                                         return true;
2532                                 }
2533                         }
2534
2535                         return false;
2536                 }
2537
2538                 private static void qsort<T> (T [] array, int low0, int high0, Comparison<T> compare)
2539                 {
2540                         QSortStack[] stack = new QSortStack[32];
2541                         const int QSORT_THRESHOLD = 7;
2542                         int high, low, mid, i, k;
2543                         int sp = 1;
2544                         T key;
2545
2546                         // initialize our stack
2547                         stack[0].high = high0;
2548                         stack[0].low = low0;
2549
2550                         do {
2551                                 // pop the stack
2552                                 sp--;
2553                                 high = stack[sp].high;
2554                                 low = stack[sp].low;
2555
2556                                 if ((low + QSORT_THRESHOLD) > high) {
2557                                         // switch to insertion sort
2558                                         for (i = low + 1; i <= high; i++) {
2559                                                 for (k = i; k > low; k--) {
2560                                                         if (compare (array[k], array[k-1]) >= 0)
2561                                                                 break;
2562
2563                                                         swap<T> (array, k - 1, k);
2564                                                 }
2565                                         }
2566
2567                                         continue;
2568                                 }
2569
2570                                 // calculate the middle element
2571                                 mid = low + ((high - low) / 2);
2572
2573                                 // once we re-order the lo, mid, and hi elements to be in
2574                                 // ascending order, we'll use mid as our pivot.
2575                                 QSortArrange<T> (array, low, mid, compare);
2576                                 if (QSortArrange<T> (array, mid, high, compare))
2577                                         QSortArrange<T> (array, low, mid, compare);
2578
2579                                 key = array[mid];
2580
2581                                 // since we've already guaranteed that lo <= mid and mid <= hi,
2582                                 // we can skip comparing them again
2583                                 k = high - 1;
2584                                 i = low + 1;
2585
2586                                 do {
2587                                         // Move the walls in
2588                                         if (key != null) {
2589                                                 // find the first element with a value >= pivot value
2590                                                 while (i < k && compare (key, array[i]) > 0)
2591                                                         i++;
2592
2593                                                 // find the last element with a value <= pivot value
2594                                                 while (k > i && compare (key, array[k]) < 0)
2595                                                         k--;
2596                                         } else {
2597                                                 while (i < k && array[i] == null)
2598                                                         i++;
2599
2600                                                 while (k > i && array[k] != null)
2601                                                         k--;
2602                                         }
2603
2604                                         if (k <= i)
2605                                                 break;
2606
2607                                         swap<T> (array, i, k);
2608
2609                                         i++;
2610                                         k--;
2611                                 } while (true);
2612
2613                                 // push our partitions onto the stack, largest first
2614                                 // (to make sure we don't run out of stack space)
2615                                 if ((high - k) >= (k - low)) {
2616                                         if ((k + 1) < high) {
2617                                                 stack[sp].high = high;
2618                                                 stack[sp].low = k;
2619                                                 sp++;
2620                                         }
2621
2622                                         if ((k - 1) > low) {
2623                                                 stack[sp].high = k;
2624                                                 stack[sp].low = low;
2625                                                 sp++;
2626                                         }
2627                                 } else {
2628                                         if ((k - 1) > low) {
2629                                                 stack[sp].high = k;
2630                                                 stack[sp].low = low;
2631                                                 sp++;
2632                                         }
2633
2634                                         if ((k + 1) < high) {
2635                                                 stack[sp].high = high;
2636                                                 stack[sp].low = k;
2637                                                 sp++;
2638                                         }
2639                                 }
2640                         } while (sp > 0);
2641                 }
2642
2643                 private static void CheckComparerAvailable<K> (K [] keys, int low, int high)
2644                 {
2645                         // move null keys to beginning of array,
2646                         // ensure that non-null keys implement IComparable
2647                         for (int i = low; i < high; i++) {
2648                                 K key = keys [i];
2649                                 if (key != null) {
2650                                         if (!(key is IComparable<K>) && !(key is IComparable)) {
2651                                                 string msg = Locale.GetText ("No IComparable<T> or IComparable interface found for type '{0}'.");
2652                                                 throw new InvalidOperationException (String.Format (msg, key.GetType ()));
2653                                         }
2654                                 }
2655                         }
2656                 }
2657
2658                 [MethodImpl ((MethodImplOptions)256)]
2659                 private static void swap<K, V> (K [] keys, V [] items, int i, int j)
2660                 {
2661                         K tmp;
2662
2663                         tmp = keys [i];
2664                         keys [i] = keys [j];
2665                         keys [j] = tmp;
2666
2667                         if (items != null) {
2668                                 V itmp;
2669                                 itmp = items [i];
2670                                 items [i] = items [j];
2671                                 items [j] = itmp;
2672                         }
2673                 }
2674
2675                 [MethodImpl ((MethodImplOptions)256)]
2676                 private static void swap<T> (T [] array, int i, int j)
2677                 {
2678                         T tmp = array [i];
2679                         array [i] = array [j];
2680                         array [j] = tmp;
2681                 }
2682
2683                 public void CopyTo (Array array, int index)
2684                 {
2685                         if (array == null)
2686                                 throw new ArgumentNullException ("array");
2687
2688                         // The order of these exception checks may look strange,
2689                         // but that's how the microsoft runtime does it.
2690                         if (this.Rank > 1)
2691                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2692                         if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
2693                                 throw new ArgumentException ("Destination array was not long " +
2694                                         "enough. Check destIndex and length, and the array's " +
2695                                         "lower bounds.");
2696                         if (array.Rank > 1)
2697                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2698                         if (index < 0)
2699                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2700                                         "Value has to be >= 0."));
2701
2702                         Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
2703                 }
2704
2705                 [ComVisible (false)]
2706                 public void CopyTo (Array array, long index)
2707                 {
2708                         if (index < 0 || index > Int32.MaxValue)
2709                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2710                                         "Value must be >= 0 and <= Int32.MaxValue."));
2711
2712                         CopyTo (array, (int) index);
2713                 }
2714
2715                 internal class SimpleEnumerator : IEnumerator, ICloneable
2716                 {
2717                         Array enumeratee;
2718                         int currentpos;
2719                         int length;
2720
2721                         public SimpleEnumerator (Array arrayToEnumerate)
2722                         {
2723                                 this.enumeratee = arrayToEnumerate;
2724                                 this.currentpos = -1;
2725                                 this.length = arrayToEnumerate.Length;
2726                         }
2727
2728                         public object Current {
2729                                 get {
2730                                         // Exception messages based on MS implementation
2731                                         if (currentpos < 0 )
2732                                                 throw new InvalidOperationException (Locale.GetText (
2733                                                         "Enumeration has not started."));
2734                                         if  (currentpos >= length)
2735                                                 throw new InvalidOperationException (Locale.GetText (
2736                                                         "Enumeration has already ended"));
2737                                         // Current should not increase the position. So no ++ over here.
2738                                         return enumeratee.GetValueImpl (currentpos);
2739                                 }
2740                         }
2741
2742                         public bool MoveNext()
2743                         {
2744                                 //The docs say Current should throw an exception if last
2745                                 //call to MoveNext returned false. This means currentpos
2746                                 //should be set to length when returning false.
2747                                 if (currentpos < length)
2748                                         currentpos++;
2749                                 if(currentpos < length)
2750                                         return true;
2751                                 else
2752                                         return false;
2753                         }
2754
2755                         public void Reset()
2756                         {
2757                                 currentpos = -1;
2758                         }
2759
2760                         public object Clone ()
2761                         {
2762                                 return MemberwiseClone ();
2763                         }
2764                 }
2765
2766                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2767                 public static void Resize<T> (ref T [] array, int newSize)
2768                 {
2769                         if (newSize < 0)
2770                                 throw new ArgumentOutOfRangeException ("newSize");
2771
2772                         if (array == null) {
2773                                 array = new T [newSize];
2774                                 return;
2775                         }
2776
2777                         var arr = array;
2778                         int length = arr.Length;
2779                         if (length == newSize)
2780                                 return;
2781
2782                         T [] a = new T [newSize];
2783                         int tocopy = Math.Min (newSize, length);
2784
2785                         if (tocopy < 9) {
2786                                 for (int i = 0; i < tocopy; ++i)
2787                                         UnsafeStore (a, i, UnsafeLoad (arr, i));
2788                         } else {
2789                                 FastCopy (arr, 0, a, 0, tocopy);
2790                         }
2791                         array = a;
2792                 }
2793
2794                 public static bool TrueForAll <T> (T [] array, Predicate <T> match)
2795                 {
2796                         if (array == null)
2797                                 throw new ArgumentNullException ("array");
2798                         if (match == null)
2799                                 throw new ArgumentNullException ("match");
2800
2801                         foreach (T t in array)
2802                                 if (! match (t))
2803                                         return false;
2804
2805                         return true;
2806                 }
2807
2808                 public static void ForEach<T> (T [] array, Action <T> action)
2809                 {
2810                         if (array == null)
2811                                 throw new ArgumentNullException ("array");
2812                         if (action == null)
2813                                 throw new ArgumentNullException ("action");
2814
2815                         foreach (T t in array)
2816                                 action (t);
2817                 }
2818
2819                 public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
2820                 {
2821                         if (array == null)
2822                                 throw new ArgumentNullException ("array");
2823                         if (converter == null)
2824                                 throw new ArgumentNullException ("converter");
2825
2826                         TOutput [] output = new TOutput [array.Length];
2827                         for (int i = 0; i < array.Length; i ++)
2828                                 output [i] = converter (array [i]);
2829
2830                         return output;
2831                 }
2832
2833                 public static int FindLastIndex<T> (T [] array, Predicate <T> match)
2834                 {
2835                         if (array == null)
2836                                 throw new ArgumentNullException ("array");
2837
2838                         if (match == null)
2839                                 throw new ArgumentNullException ("match");
2840
2841                         return GetLastIndex (array, 0, array.Length, match);
2842                 }
2843
2844                 public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
2845                 {
2846                         if (array == null)
2847                                 throw new ArgumentNullException ();
2848
2849                         if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2850                                 throw new ArgumentOutOfRangeException ("startIndex");
2851
2852                         if (match == null)
2853                                 throw new ArgumentNullException ("match");
2854
2855                         return GetLastIndex (array, 0, startIndex + 1, match);
2856                 }
2857
2858                 public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2859                 {
2860                         if (array == null)
2861                                 throw new ArgumentNullException ("array");
2862
2863                         if (match == null)
2864                                 throw new ArgumentNullException ("match");
2865
2866                         if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2867                                 throw new ArgumentOutOfRangeException ("startIndex");
2868
2869                         if (count < 0)
2870                                 throw new ArgumentOutOfRangeException ("count");
2871
2872                         if (startIndex - count + 1 < 0)
2873                                 throw new ArgumentOutOfRangeException ("count must refer to a location within the array");
2874
2875                         return GetLastIndex (array, startIndex - count + 1, count, match);
2876                 }
2877
2878                 internal static int GetLastIndex<T> (T[] array, int startIndex, int count, Predicate<T> match)
2879                 {
2880                         // unlike FindLastIndex, takes regular params for search range
2881                         for (int i = startIndex + count; i != startIndex;)
2882                                 if (match (array [--i]))
2883                                         return i;
2884
2885                         return -1;
2886                 }
2887
2888                 public static int FindIndex<T> (T [] array, Predicate<T> match)
2889                 {
2890                         if (array == null)
2891                                 throw new ArgumentNullException ("array");
2892
2893                         if (match == null)
2894                                 throw new ArgumentNullException ("match");
2895
2896                         return GetIndex (array, 0, array.Length, match);
2897                 }
2898
2899                 public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
2900                 {
2901                         if (array == null)
2902                                 throw new ArgumentNullException ("array");
2903
2904                         if (startIndex < 0 || (uint) startIndex > (uint) array.Length)
2905                                 throw new ArgumentOutOfRangeException ("startIndex");
2906
2907                         if (match == null)
2908                                 throw new ArgumentNullException ("match");
2909
2910                         return GetIndex (array, startIndex, array.Length - startIndex, match);
2911                 }
2912
2913                 public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2914                 {
2915                         if (array == null)
2916                                 throw new ArgumentNullException ("array");
2917
2918                         if (startIndex < 0)
2919                                 throw new ArgumentOutOfRangeException ("startIndex");
2920
2921                         if (count < 0)
2922                                 throw new ArgumentOutOfRangeException ("count");
2923
2924                         if ((uint) startIndex + (uint) count > (uint) array.Length)
2925                                 throw new ArgumentOutOfRangeException ("index and count exceed length of list");
2926
2927                         return GetIndex (array, startIndex, count, match);
2928                 }
2929
2930                 internal static int GetIndex<T> (T[] array, int startIndex, int count, Predicate<T> match)
2931                 {
2932                         int end = startIndex + count;
2933                         for (int i = startIndex; i < end; i ++)
2934                                 if (match (array [i]))
2935                                         return i;
2936
2937                         return -1;
2938                 }
2939
2940                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2941                 public static int BinarySearch<T> (T [] array, T value)
2942                 {
2943                         if (array == null)
2944                                 throw new ArgumentNullException ("array");
2945
2946                         return BinarySearch<T> (array, 0, array.Length, value, null);
2947                 }
2948
2949                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2950                 public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
2951                 {
2952                         if (array == null)
2953                                 throw new ArgumentNullException ("array");
2954
2955                         return BinarySearch<T> (array, 0, array.Length, value, comparer);
2956                 }
2957
2958                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2959                 public static int BinarySearch<T> (T [] array, int index, int length, T value)
2960                 {
2961                         return BinarySearch<T> (array, index, length, value, null);
2962                 }
2963
2964                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2965                 public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
2966                 {
2967                         if (array == null)
2968                                 throw new ArgumentNullException ("array");
2969                         if (index < 0)
2970                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2971                                         "index is less than the lower bound of array."));
2972                         if (length < 0)
2973                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
2974                                         "Value has to be >= 0."));
2975                         // re-ordered to avoid possible integer overflow
2976                         if (index > array.Length - length)
2977                                 throw new ArgumentException (Locale.GetText (
2978                                         "index and length do not specify a valid range in array."));
2979                         if (comparer == null)
2980                                 comparer = Comparer <T>.Default;
2981
2982                         int iMin = index;
2983                         int iMax = index + length - 1;
2984                         int iCmp = 0;
2985                         try {
2986                                 while (iMin <= iMax) {
2987                                         // Be careful with overflows
2988                                         int iMid = iMin + ((iMax - iMin) / 2);
2989                                         iCmp = comparer.Compare (array [iMid], value);
2990
2991                                         if (iCmp == 0)
2992                                                 return iMid;
2993
2994                                         if (iCmp > 0)
2995                                                 iMax = iMid - 1;
2996                                         else
2997                                                 iMin = iMid + 1; // compensate for the rounding down
2998                                 }
2999                         } catch (Exception e) {
3000                                 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
3001                         }
3002
3003                         return ~iMin;
3004                 }
3005
3006                 public static int IndexOf<T> (T [] array, T value)
3007                 {
3008                         if (array == null)
3009                                 throw new ArgumentNullException ("array");
3010
3011                         return IndexOf<T> (array, value, 0, array.Length);
3012                 }
3013
3014                 public static int IndexOf<T> (T [] array, T value, int startIndex)
3015                 {
3016                         if (array == null)
3017                                 throw new ArgumentNullException ("array");
3018
3019                         return IndexOf<T> (array, value, startIndex, array.Length - startIndex);
3020                 }
3021
3022                 public static int IndexOf<T> (T [] array, T value, int startIndex, int count)
3023                 {
3024                         if (array == null)
3025                                 throw new ArgumentNullException ("array");
3026
3027                         // re-ordered to avoid possible integer overflow
3028                         if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
3029                                 throw new ArgumentOutOfRangeException ();
3030
3031                         int max = startIndex + count;
3032                         EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
3033                         for (int i = startIndex; i < max; i++) {
3034                                 if (equalityComparer.Equals (array [i], value))
3035                                         return i;
3036                         }
3037
3038                         return -1;
3039                 }
3040
3041                 public static int LastIndexOf<T> (T [] array, T value)
3042                 {
3043                         if (array == null)
3044                                 throw new ArgumentNullException ("array");
3045
3046                         if (array.Length == 0)
3047                                 return -1;
3048                         return LastIndexOf<T> (array, value, array.Length - 1);
3049                 }
3050
3051                 public static int LastIndexOf<T> (T [] array, T value, int startIndex)
3052                 {
3053                         if (array == null)
3054                                 throw new ArgumentNullException ("array");
3055
3056                         return LastIndexOf<T> (array, value, startIndex, startIndex + 1);
3057                 }
3058
3059                 public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
3060                 {
3061                         if (array == null)
3062                                 throw new ArgumentNullException ("array");
3063
3064                         if (count < 0 || startIndex < array.GetLowerBound (0) ||
3065                                 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
3066                                 throw new ArgumentOutOfRangeException ();
3067
3068                         EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
3069                         for (int i = startIndex; i >= startIndex - count + 1; i--) {
3070                                 if (equalityComparer.Equals (array [i], value))
3071                                         return i;
3072                         }
3073
3074                         return -1;
3075                 }
3076
3077                 public static T [] FindAll<T> (T [] array, Predicate <T> match)
3078                 {
3079                         if (array == null)
3080                                 throw new ArgumentNullException ("array");
3081
3082                         if (match == null)
3083                                 throw new ArgumentNullException ("match");
3084
3085                         int pos = 0;
3086                         T [] d = new T [array.Length];
3087                         foreach (T t in array)
3088                                 if (match (t))
3089                                         d [pos++] = t;
3090
3091                         Resize <T> (ref d, pos);
3092                         return d;
3093                 }
3094
3095                 public static bool Exists<T> (T [] array, Predicate <T> match)
3096                 {
3097                         if (array == null)
3098                                 throw new ArgumentNullException ("array");
3099
3100                         if (match == null)
3101                                 throw new ArgumentNullException ("match");
3102
3103                         foreach (T t in array)
3104                                 if (match (t))
3105                                         return true;
3106                         return false;
3107                 }
3108
3109                 public static ReadOnlyCollection<T> AsReadOnly<T> (T[] array)
3110                 {
3111                         if (array == null)
3112                                 throw new ArgumentNullException ("array");
3113
3114                         return new ReadOnlyCollection<T> (array);
3115                 }
3116
3117                 public static T Find<T> (T [] array, Predicate<T> match)
3118                 {
3119                         if (array == null)
3120                                 throw new ArgumentNullException ("array");
3121
3122                         if (match == null)
3123                                 throw new ArgumentNullException ("match");
3124
3125                         foreach (T t in array)
3126                                 if (match (t))
3127                                         return t;
3128
3129                         return default (T);
3130                 }
3131
3132                 public static T FindLast<T> (T [] array, Predicate <T> match)
3133                 {
3134                         if (array == null)
3135                                 throw new ArgumentNullException ("array");
3136
3137                         if (match == null)
3138                                 throw new ArgumentNullException ("match");
3139
3140                         for (int i = array.Length - 1; i >= 0; i--)
3141                                 if (match (array [i]))
3142                                         return array [i];
3143
3144                         return default (T);
3145                 }
3146
3147                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
3148                 //
3149                 // The constrained copy should guarantee that if there is an exception thrown
3150                 // during the copy, the destination array remains unchanged.
3151                 // This is related to System.Runtime.Reliability.CER
3152                 public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
3153                 {
3154                         Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length);
3155                 }
3156
3157                 internal static T UnsafeLoad<T> (T[] array, int index) {
3158                         return array [index];
3159                 }
3160
3161                 internal static void UnsafeStore<T> (T[] array, int index, T value) {
3162                         array [index] = value;
3163                 }
3164         }
3165 }