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