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