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