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