mcs/class/corlib/System/Array.cs

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