mcs/class/corlib/System/Array.cs

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