mcs/class/corlib/System/Array.cs

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