mcs/class/corlib/System/Array.cs

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