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