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) ^ comparer.GetHashCode (GetValueImpl (i));
 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                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1138                 public static void Reverse (Array array)
1139                 {
1140                         if (array == null)
1141                                 throw new ArgumentNullException ("array");
1142
1143                         Reverse (array, array.GetLowerBound (0), array.Length);
1144                 }
1145
1146                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1147                 public static void Reverse (Array array, int index, int length)
1148                 {
1149                         if (array == null)
1150                                 throw new ArgumentNullException ("array");
1151
1152                         if (array.Rank > 1)
1153                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1154
1155                         if (index < array.GetLowerBound (0) || length < 0)
1156                                 throw new ArgumentOutOfRangeException ();
1157
1158                         // re-ordered to avoid possible integer overflow
1159                         if (index > array.GetUpperBound (0) + 1 - length)
1160                                 throw new ArgumentException ();
1161
1162                         int end = index + length - 1;
1163                         var et = array.GetType ().GetElementType ();
1164                         switch (Type.GetTypeCode (et)) {
1165                         case TypeCode.Boolean:
1166                                 while (index < end) {
1167                                         bool a, b;
1168
1169                                         array.GetGenericValueImpl (index, out a);
1170                                         array.GetGenericValueImpl (end, out b);
1171                                         array.SetGenericValueImpl (index, ref b);
1172                                         array.SetGenericValueImpl (end, ref a);
1173                                         ++index;
1174                                         --end;
1175                                 }
1176                                 return;
1177
1178                         case TypeCode.Byte:
1179                         case TypeCode.SByte:
1180                                 while (index < end) {
1181                                         byte a, b;
1182
1183                                         array.GetGenericValueImpl (index, out a);
1184                                         array.GetGenericValueImpl (end, out b);
1185                                         array.SetGenericValueImpl (index, ref b);
1186                                         array.SetGenericValueImpl (end, ref a);
1187                                         ++index;
1188                                         --end;
1189                                 }
1190                                 return;
1191
1192                         case TypeCode.Int16:
1193                         case TypeCode.UInt16:
1194                         case TypeCode.Char:
1195                                 while (index < end) {
1196                                         short a, b;
1197
1198                                         array.GetGenericValueImpl (index, out a);
1199                                         array.GetGenericValueImpl (end, out b);
1200                                         array.SetGenericValueImpl (index, ref b);
1201                                         array.SetGenericValueImpl (end, ref a);
1202                                         ++index;
1203                                         --end;
1204                                 }
1205                                 return;
1206
1207                         case TypeCode.Int32:
1208                         case TypeCode.UInt32:
1209                         case TypeCode.Single:
1210                                 while (index < end) {
1211                                         int a, b;
1212
1213                                         array.GetGenericValueImpl (index, out a);
1214                                         array.GetGenericValueImpl (end, out b);
1215                                         array.SetGenericValueImpl (index, ref b);
1216                                         array.SetGenericValueImpl (end, ref a);
1217                                         ++index;
1218                                         --end;
1219                                 }
1220                                 return;
1221
1222                         case TypeCode.Int64:
1223                         case TypeCode.UInt64:
1224                         case TypeCode.Double:
1225                                 while (index < end) {
1226                                         long a, b;
1227
1228                                         array.GetGenericValueImpl (index, out a);
1229                                         array.GetGenericValueImpl (end, out b);
1230                                         array.SetGenericValueImpl (index, ref b);
1231                                         array.SetGenericValueImpl (end, ref a);
1232                                         ++index;
1233                                         --end;
1234                                 }
1235                                 return;
1236
1237                         case TypeCode.Decimal:
1238                                 while (index < end) {
1239                                         decimal a, b;
1240
1241                                         array.GetGenericValueImpl (index, out a);
1242                                         array.GetGenericValueImpl (end, out b);
1243                                         array.SetGenericValueImpl (index, ref b);
1244                                         array.SetGenericValueImpl (end, ref a);
1245                                         ++index;
1246                                         --end;
1247                                 }
1248                                 return;
1249
1250                         case TypeCode.String:
1251                         case TypeCode.Object:
1252                                 while (index < end) {
1253                                         object a, b;
1254
1255                                         array.GetGenericValueImpl (index, out a);
1256                                         array.GetGenericValueImpl (end, out b);
1257                                         array.SetGenericValueImpl (index, ref b);
1258                                         array.SetGenericValueImpl (end, ref a);
1259                                         ++index;
1260                                         --end;
1261                                 }
1262                                 return;
1263                         default:
1264                                 if (array is object[])
1265                                         goto case TypeCode.Object;
1266
1267                                 // Very slow fallback
1268                                 while (index < end) {
1269                                         object val = array.GetValueImpl (index);
1270                                         array.SetValueImpl (array.GetValueImpl (end), index);
1271                                         array.SetValueImpl (val, end);
1272                                         ++index;
1273                                         --end;
1274                                 }
1275
1276                                 return;
1277                         }
1278                 }
1279
1280                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1281                 public static void Sort (Array array)
1282                 {
1283                         Sort (array, (IComparer)null);
1284                 }
1285
1286                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1287                 public static void Sort (Array keys, Array items)
1288                 {
1289                         Sort (keys, items, (IComparer)null);
1290                 }
1291
1292                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1293                 public static void Sort (Array array, IComparer comparer)
1294                 {
1295                         if (array == null)
1296                                 throw new ArgumentNullException ("array");
1297
1298                         if (array.Rank > 1)
1299                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1300
1301                         SortImpl (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
1302                 }
1303
1304                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1305                 public static void Sort (Array array, int index, int length)
1306                 {
1307                         Sort (array, index, length, (IComparer)null);
1308                 }
1309
1310                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1311                 public static void Sort (Array keys, Array items, IComparer comparer)
1312                 {
1313                         if (items == null) {
1314                                 Sort (keys, comparer);
1315                                 return;
1316                         }
1317
1318                         if (keys == null)
1319                                 throw new ArgumentNullException ("keys");
1320
1321                         if (keys.Rank > 1 || items.Rank > 1)
1322                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1323
1324                         SortImpl (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
1325                 }
1326
1327                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1328                 public static void Sort (Array keys, Array items, int index, int length)
1329                 {
1330                         Sort (keys, items, index, length, (IComparer)null);
1331                 }
1332
1333                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1334                 public static void Sort (Array array, int index, int length, IComparer comparer)
1335                 {
1336                         if (array == null)
1337                                 throw new ArgumentNullException ("array");
1338
1339                         if (array.Rank > 1)
1340                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1341
1342                         if (index < array.GetLowerBound (0))
1343                                 throw new ArgumentOutOfRangeException ("index");
1344
1345                         if (length < 0)
1346                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1347                                         "Value has to be >= 0."));
1348
1349                         if (array.Length - (array.GetLowerBound (0) + index) < length)
1350                                 throw new ArgumentException ();
1351
1352                         SortImpl (array, null, index, length, comparer);
1353                 }
1354
1355                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1356                 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
1357                 {
1358                         if (items == null) {
1359                                 Sort (keys, index, length, comparer);
1360                                 return;
1361                         }
1362
1363                         if (keys == null)
1364                                 throw new ArgumentNullException ("keys");
1365
1366                         if (keys.Rank > 1 || items.Rank > 1)
1367                                 throw new RankException ();
1368
1369                         if (keys.GetLowerBound (0) != items.GetLowerBound (0))
1370                                 throw new ArgumentException ();
1371
1372                         if (index < keys.GetLowerBound (0))
1373                                 throw new ArgumentOutOfRangeException ("index");
1374
1375                         if (length < 0)
1376                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1377                                         "Value has to be >= 0."));
1378
1379                         if (items.Length - (index + items.GetLowerBound (0)) < length || keys.Length - (index + keys.GetLowerBound (0)) < length)
1380                                 throw new ArgumentException ();
1381
1382                         SortImpl (keys, items, index, length, comparer);
1383                 }
1384
1385                 private static void SortImpl (Array keys, Array items, int index, int length, IComparer comparer)
1386                 {
1387                         if (length <= 1)
1388                                 return;
1389
1390                         int low = index;
1391                         int high = index + length - 1;
1392
1393 #if !BOOTSTRAP_BASIC
1394                         if (comparer == null && items is object[]) {
1395                                 /* Its better to compare typecodes as casts treat long/ulong/long based enums the same */
1396                                 switch (Type.GetTypeCode (keys.GetType ().GetElementType ())) {
1397                                 case TypeCode.Int32:
1398                                         qsort (keys as Int32[], items as object[], low, high);
1399                                         return;
1400                                 case TypeCode.Int64:
1401                                         qsort (keys as Int64[], items as object[], low, high);
1402                                         return;
1403                                 case TypeCode.Byte:
1404                                         qsort (keys as byte[], items as object[], low, high);
1405                                         return;
1406                                 case TypeCode.Char:
1407                                         qsort (keys as char[], items as object[], low, high);
1408                                         return;
1409                                 case TypeCode.DateTime:
1410                                         qsort (keys as DateTime[], items as object[], low, high);
1411                                         return;
1412                                 case TypeCode.Decimal:
1413                                         qsort (keys as decimal[], items as object[], low, high);
1414                                         return;
1415                                 case TypeCode.Double:
1416                                         qsort (keys as double[], items as object[], low, high);
1417                                         return;
1418                                 case TypeCode.Int16:
1419                                         qsort (keys as Int16[], items as object[], low, high);
1420                                         return;
1421                                 case TypeCode.SByte:
1422                                         qsort (keys as SByte[], items as object[], low, high);
1423                                         return;
1424                                 case TypeCode.Single:
1425                                         qsort (keys as Single[], items as object[], low, high);
1426                                         return;
1427                                 case TypeCode.UInt16:
1428                                         qsort (keys as UInt16[], items as object[], low, high);
1429                                         return;
1430                                 case TypeCode.UInt32:
1431                                         qsort (keys as UInt32[], items as object[], low, high);
1432                                         return;
1433                                 case TypeCode.UInt64:
1434                                         qsort (keys as UInt64[], items as object[], low, high);
1435                                         return;
1436                                 default:
1437                                         break;
1438                                 }
1439                         }
1440 #endif
1441
1442                         if (comparer == null)
1443                                 CheckComparerAvailable (keys, low, high);
1444
1445                         try {
1446                                 qsort (keys, items, low, high, comparer);
1447                         } catch (Exception e) {
1448                                 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1449                         }
1450                 }
1451
1452                 struct QSortStack {
1453                         public int high;
1454                         public int low;
1455                 }
1456
1457                 static bool QSortArrange (Array keys, Array items, int lo, ref object v0, int hi, ref object v1, IComparer comparer)
1458                 {
1459                         IComparable cmp;
1460                         object tmp;
1461
1462                         if (comparer != null) {
1463                                 if (comparer.Compare (v1, v0) < 0) {
1464                                         swap (keys, items, lo, hi);
1465                                         tmp = v0;
1466                                         v0 = v1;
1467                                         v1 = tmp;
1468
1469                                         return true;
1470                                 }
1471                         } else if (v0 != null) {
1472                                 cmp = v1 as IComparable;
1473
1474                                 if (v1 == null || cmp.CompareTo (v0) < 0) {
1475                                         swap (keys, items, lo, hi);
1476                                         tmp = v0;
1477                                         v0 = v1;
1478                                         v1 = tmp;
1479
1480                                         return true;
1481                                 }
1482                         }
1483
1484                         return false;
1485                 }
1486
1487                 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
1488                 {
1489                         QSortStack[] stack = new QSortStack[32];
1490                         const int QSORT_THRESHOLD = 7;
1491                         int high, low, mid, i, k;
1492                         object key, hi, lo;
1493                         IComparable cmp;
1494                         int sp = 1;
1495
1496                         // initialize our stack
1497                         stack[0].high = high0;
1498                         stack[0].low = low0;
1499
1500                         do {
1501                                 // pop the stack
1502                                 sp--;
1503                                 high = stack[sp].high;
1504                                 low = stack[sp].low;
1505
1506                                 if ((low + QSORT_THRESHOLD) > high) {
1507                                         // switch to insertion sort
1508                                         for (i = low + 1; i <= high; i++) {
1509                                                 for (k = i; k > low; k--) {
1510                                                         lo = keys.GetValueImpl (k - 1);
1511                                                         hi = keys.GetValueImpl (k);
1512                                                         if (comparer != null) {
1513                                                                 if (comparer.Compare (hi, lo) >= 0)
1514                                                                         break;
1515                                                         } else {
1516                                                                 if (lo == null)
1517                                                                         break;
1518
1519                                                                 if (hi != null) {
1520                                                                         cmp = hi as IComparable;
1521                                                                         if (cmp.CompareTo (lo) >= 0)
1522                                                                                 break;
1523                                                                 }
1524                                                         }
1525
1526                                                         swap (keys, items, k - 1, k);
1527                                                 }
1528                                         }
1529
1530                                         continue;
1531                                 }
1532
1533                                 // calculate the middle element
1534                                 mid = low + ((high - low) / 2);
1535
1536                                 // get the 3 keys
1537                                 key = keys.GetValueImpl (mid);
1538                                 hi = keys.GetValueImpl (high);
1539                                 lo = keys.GetValueImpl (low);
1540
1541                                 // once we re-order the low, mid, and high elements to be in
1542                                 // ascending order, we'll use mid as our pivot.
1543                                 QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1544                                 if (QSortArrange (keys, items, mid, ref key, high, ref hi, comparer))
1545                                         QSortArrange (keys, items, low, ref lo, mid, ref key, comparer);
1546
1547                                 cmp = key as IComparable;
1548
1549                                 // since we've already guaranteed that lo <= mid and mid <= hi,
1550                                 // we can skip comparing them again.
1551                                 k = high - 1;
1552                                 i = low + 1;
1553
1554                                 do {
1555                                         // Move the walls in
1556                                         if (comparer != null) {
1557                                                 // find the first element with a value >= pivot value
1558                                                 while (i < k && comparer.Compare (key, keys.GetValueImpl (i)) > 0)
1559                                                         i++;
1560
1561                                                 // find the last element with a value <= pivot value
1562                                                 while (k > i && comparer.Compare (key, keys.GetValueImpl (k)) < 0)
1563                                                         k--;
1564                                         } else if (cmp != null) {
1565                                                 // find the first element with a value >= pivot value
1566                                                 while (i < k && cmp.CompareTo (keys.GetValueImpl (i)) > 0)
1567                                                         i++;
1568
1569                                                 // find the last element with a value <= pivot value
1570                                                 while (k > i && cmp.CompareTo (keys.GetValueImpl (k)) < 0)
1571                                                         k--;
1572                                         } else {
1573                                                 // This has the effect of moving the null values to the front if comparer is null
1574                                                 while (i < k && keys.GetValueImpl (i) == null)
1575                                                         i++;
1576
1577                                                 while (k > i && keys.GetValueImpl (k) != null)
1578                                                         k--;
1579                                         }
1580
1581                                         if (k <= i)
1582                                                 break;
1583
1584                                         swap (keys, items, i, k);
1585
1586                                         i++;
1587                                         k--;
1588                                 } while (true);
1589
1590                                 // push our partitions onto the stack, largest first
1591                                 // (to make sure we don't run out of stack space)
1592                                 if ((high - k) >= (k - low)) {
1593                                         if ((k + 1) < high) {
1594                                                 stack[sp].high = high;
1595                                                 stack[sp].low = k;
1596                                                 sp++;
1597                                         }
1598
1599                                         if ((k - 1) > low) {
1600                                                 stack[sp].high = k;
1601                                                 stack[sp].low = low;
1602                                                 sp++;
1603                                         }
1604                                 } else {
1605                                         if ((k - 1) > low) {
1606                                                 stack[sp].high = k;
1607                                                 stack[sp].low = low;
1608                                                 sp++;
1609                                         }
1610
1611                                         if ((k + 1) < high) {
1612                                                 stack[sp].high = high;
1613                                                 stack[sp].low = k;
1614                                                 sp++;
1615                                         }
1616                                 }
1617                         } while (sp > 0);
1618                 }
1619
1620                 private static void CheckComparerAvailable (Array keys, int low, int high)
1621                 {
1622                         // move null keys to beginning of array,
1623                         // ensure that non-null keys implement IComparable
1624                         for (int i = 0; i < high; i++) {
1625                                 object obj = keys.GetValueImpl (i);
1626                                 if (obj == null)
1627                                         continue;
1628                                 if (!(obj is IComparable)) {
1629                                         string msg = Locale.GetText ("No IComparable interface found for type '{0}'.");
1630                                         throw new InvalidOperationException (String.Format (msg, obj.GetType ()));
1631                                 }
1632                         }
1633                 }
1634
1635                 private static void swap (Array keys, Array items, int i, int j)
1636                 {
1637                         object tmp = keys.GetValueImpl (i);
1638                         keys.SetValueImpl (keys.GetValueImpl (j), i);
1639                         keys.SetValueImpl (tmp, j);
1640
1641                         if (items != null) {
1642                                 tmp = items.GetValueImpl (i);
1643                                 items.SetValueImpl (items.GetValueImpl (j), i);
1644                                 items.SetValueImpl (tmp, j);
1645                         }
1646                 }
1647
1648                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1649                 public static void Sort<T> (T [] array)
1650                 {
1651                         Sort<T> (array, (IComparer<T>)null);
1652                 }
1653
1654                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1655                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items)
1656                 {
1657                         Sort<TKey, TValue> (keys, items, (IComparer<TKey>)null);
1658                 }
1659
1660                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1661                 public static void Sort<T> (T [] array, IComparer<T> comparer)
1662                 {
1663                         if (array == null)
1664                                 throw new ArgumentNullException ("array");
1665
1666                         SortImpl<T> (array, 0, array.Length, comparer);
1667                 }
1668
1669                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1670                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, IComparer<TKey> comparer)
1671                 {
1672                         if (items == null) {
1673                                 Sort<TKey> (keys, comparer);
1674                                 return;
1675                         }
1676
1677                         if (keys == null)
1678                                 throw new ArgumentNullException ("keys");
1679
1680                         if (keys.Length != items.Length)
1681                                 throw new ArgumentException ("Length of keys and items does not match.");
1682
1683                         SortImpl<TKey, TValue> (keys, items, 0, keys.Length, comparer);
1684                 }
1685
1686                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1687                 public static void Sort<T> (T [] array, int index, int length)
1688                 {
1689                         Sort<T> (array, index, length, (IComparer<T>)null);
1690                 }
1691
1692                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1693                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length)
1694                 {
1695                         Sort<TKey, TValue> (keys, items, index, length, (IComparer<TKey>)null);
1696                 }
1697
1698                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1699                 public static void Sort<T> (T [] array, int index, int length, IComparer<T> comparer)
1700                 {
1701                         if (array == null)
1702                                 throw new ArgumentNullException ("array");
1703
1704                         if (index < 0)
1705                                 throw new ArgumentOutOfRangeException ("index");
1706
1707                         if (length < 0)
1708                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1709                                         "Value has to be >= 0."));
1710
1711                         if (index + length > array.Length)
1712                                 throw new ArgumentException ();
1713
1714                         SortImpl<T, T> (array, null, index, length, comparer);
1715                 }
1716
1717                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1718                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1719                 {
1720                         if (items == null) {
1721                                 Sort<TKey> (keys, index, length, comparer);
1722                                 return;
1723                         }
1724
1725                         if (keys == null)
1726                                 throw new ArgumentNullException ("keys");
1727
1728                         if (index < 0)
1729                                 throw new ArgumentOutOfRangeException ("index");
1730
1731                         if (length < 0)
1732                                 throw new ArgumentOutOfRangeException ("length");
1733
1734                         if (items.Length - index < length || keys.Length - index < length)
1735                                 throw new ArgumentException ();
1736
1737                         SortImpl<TKey, TValue> (keys, items, index, length, comparer);
1738                 }
1739
1740                 private static void SortImpl<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1741                 {
1742                         if (keys.Length <= 1)
1743                                 return;
1744
1745                         int low = index;
1746                         int high = index + length - 1;
1747
1748                         //
1749                         // Check for value types which can be sorted without Compare () method
1750                         //
1751                         if (comparer == null) {
1752 #if !BOOTSTRAP_BASIC
1753                                 switch (Type.GetTypeCode (typeof (TKey))) {
1754                                 case TypeCode.Int32:
1755                                         qsort (keys as Int32[], items, low, high);
1756                                         return;
1757                                 case TypeCode.Int64:
1758                                         qsort (keys as Int64[], items, low, high);
1759                                         return;
1760                                 case TypeCode.Byte:
1761                                         qsort (keys as byte[], items, low, high);
1762                                         return;
1763                                 case TypeCode.Char:
1764                                         qsort (keys as char[], items, low, high);
1765                                         return;
1766                                 case TypeCode.DateTime:
1767                                         qsort (keys as DateTime[], items, low, high);
1768                                         return;
1769                                 case TypeCode.Decimal:
1770                                         qsort (keys as decimal[], items, low, high);
1771                                         return;
1772                                 case TypeCode.Double:
1773                                         qsort (keys as double[], items, low, high);
1774                                         return;
1775                                 case TypeCode.Int16:
1776                                         qsort (keys as Int16[], items, low, high);
1777                                         return;
1778                                 case TypeCode.SByte:
1779                                         qsort (keys as SByte[], items, low, high);
1780                                         return;
1781                                 case TypeCode.Single:
1782                                         qsort (keys as Single[], items, low, high);
1783                                         return;
1784                                 case TypeCode.UInt16:
1785                                         qsort (keys as UInt16[], items, low, high);
1786                                         return;
1787                                 case TypeCode.UInt32:
1788                                         qsort (keys as UInt32[], items, low, high);
1789                                         return;
1790                                 case TypeCode.UInt64:
1791                                         qsort (keys as UInt64[], items, low, high);
1792                                         return;
1793                                 }
1794 #endif
1795                                 // Using Comparer<TKey> adds a small overload, but with value types it
1796                                 // helps us to not box them.
1797                                 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1798                                                 typeof (TKey).IsValueType)
1799                                         comparer = Comparer<TKey>.Default;
1800                         }
1801
1802                         if (comparer == null)
1803                                 CheckComparerAvailable<TKey> (keys, low, high);
1804
1805                         //try {
1806                                 qsort (keys, items, low, high, comparer);
1807                                 //} catch (Exception e) {
1808                                 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1809                                 //}
1810                 }
1811
1812                 // Specialized version for items==null
1813                 private static void SortImpl<TKey> (TKey [] keys, int index, int length, IComparer<TKey> comparer)
1814                 {
1815                         if (keys.Length <= 1)
1816                                 return;
1817
1818                         int low = index;
1819                         int high = index + length - 1;
1820
1821                         //
1822                         // Check for value types which can be sorted without Compare () method
1823                         //
1824                         if (comparer == null) {
1825 #if !BOOTSTRAP_BASIC
1826                                 switch (Type.GetTypeCode (typeof (TKey))) {
1827                                 case TypeCode.Int32:
1828                                         qsort (keys as Int32[], low, high);
1829                                         return;
1830                                 case TypeCode.Int64:
1831                                         qsort (keys as Int64[], low, high);
1832                                         return;
1833                                 case TypeCode.Byte:
1834                                         qsort (keys as byte[], low, high);
1835                                         return;
1836                                 case TypeCode.Char:
1837                                         qsort (keys as char[], low, high);
1838                                         return;
1839                                 case TypeCode.DateTime:
1840                                         qsort (keys as DateTime[], low, high);
1841                                         return;
1842                                 case TypeCode.Decimal:
1843                                         qsort (keys as decimal[], low, high);
1844                                         return;
1845                                 case TypeCode.Double:
1846                                         qsort (keys as double[], low, high);
1847                                         return;
1848                                 case TypeCode.Int16:
1849                                         qsort (keys as Int16[], low, high);
1850                                         return;
1851                                 case TypeCode.SByte:
1852                                         qsort (keys as SByte[], low, high);
1853                                         return;
1854                                 case TypeCode.Single:
1855                                         qsort (keys as Single[], low, high);
1856                                         return;
1857                                 case TypeCode.UInt16:
1858                                         qsort (keys as UInt16[], low, high);
1859                                         return;
1860                                 case TypeCode.UInt32:
1861                                         qsort (keys as UInt32[], low, high);
1862                                         return;
1863                                 case TypeCode.UInt64:
1864                                         qsort (keys as UInt64[], low, high);
1865                                         return;
1866                                 }
1867 #endif
1868                                 // Using Comparer<TKey> adds a small overload, but with value types it
1869                                 // helps us to not box them.
1870                                 if (typeof (IComparable<TKey>).IsAssignableFrom (typeof (TKey)) &&
1871                                                 typeof (TKey).IsValueType)
1872                                         comparer = Comparer<TKey>.Default;
1873                         }
1874
1875                         if (comparer == null)
1876                                 CheckComparerAvailable<TKey> (keys, low, high);
1877
1878                         //try {
1879                                 qsort<TKey> (keys, low, high, comparer);
1880                                 //} catch (Exception e) {
1881                                 //throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1882                                 //}
1883                 }
1884
1885                 public static void Sort<T> (T [] array, Comparison<T> comparison)
1886                 {
1887                         if (array == null)
1888                                 throw new ArgumentNullException ("array");
1889
1890                         if (comparison == null)
1891                                 throw new ArgumentNullException ("comparison");
1892
1893                         SortImpl<T> (array, array.Length, comparison);
1894                 }
1895
1896                 // used by List<T>.Sort (Comparison <T>)
1897                 internal static void SortImpl<T> (T [] array, int length, Comparison<T> comparison)
1898                 {
1899                         if (length <= 1)
1900                                 return;
1901
1902                         try {
1903                                 int low0 = 0;
1904                                 int high0 = length - 1;
1905                                 qsort<T> (array, low0, high0, comparison);
1906                         } catch (InvalidOperationException) {
1907                                 throw;
1908                         } catch (Exception e) {
1909                                 throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e);
1910                         }
1911                 }
1912
1913                 static bool QSortArrange<T, U> (T [] keys, U [] items, int lo, int hi) where T : IComparable<T>
1914                 {
1915                         if (keys[lo] != null) {
1916                                 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1917                                         swap (keys, items, lo, hi);
1918                                         return true;
1919                                 }
1920                         }
1921
1922                         return false;
1923                 }
1924
1925                 // Specialized version for items==null
1926                 static bool QSortArrange<T> (T [] keys, int lo, int hi) where T : IComparable<T>
1927                 {
1928                         if (keys[lo] != null) {
1929                                 if (keys[hi] == null || keys[hi].CompareTo (keys[lo]) < 0) {
1930                                         swap (keys, lo, hi);
1931                                         return true;
1932                                 }
1933                         }
1934
1935                         return false;
1936                 }
1937
1938                 private static void qsort<T, U> (T[] keys, U[] items, int low0, int high0) where T : IComparable<T>
1939                 {
1940                         QSortStack[] stack = new QSortStack[32];
1941                         const int QSORT_THRESHOLD = 7;
1942                         int high, low, mid, i, k;
1943                         int sp = 1;
1944                         T key;
1945
1946                         // initialize our stack
1947                         stack[0].high = high0;
1948                         stack[0].low = low0;
1949
1950                         do {
1951                                 // pop the stack
1952                                 sp--;
1953                                 high = stack[sp].high;
1954                                 low = stack[sp].low;
1955
1956                                 if ((low + QSORT_THRESHOLD) > high) {
1957                                         // switch to insertion sort
1958                                         for (i = low + 1; i <= high; i++) {
1959                                                 for (k = i; k > low; k--) {
1960                                                         // if keys[k] >= keys[k-1], break
1961                                                         if (keys[k-1] == null)
1962                                                                 break;
1963
1964                                                         if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
1965                                                                 break;
1966
1967                                                         swap (keys, items, k - 1, k);
1968                                                 }
1969                                         }
1970
1971                                         continue;
1972                                 }
1973
1974                                 // calculate the middle element
1975                                 mid = low + ((high - low) / 2);
1976
1977                                 // once we re-order the lo, mid, and hi elements to be in
1978                                 // ascending order, we'll use mid as our pivot.
1979                                 QSortArrange<T, U> (keys, items, low, mid);
1980                                 if (QSortArrange<T, U> (keys, items, mid, high))
1981                                         QSortArrange<T, U> (keys, items, low, mid);
1982
1983                                 key = keys[mid];
1984
1985                                 // since we've already guaranteed that lo <= mid and mid <= hi,
1986                                 // we can skip comparing them again
1987                                 k = high - 1;
1988                                 i = low + 1;
1989
1990                                 do {
1991                                         if (key != null) {
1992                                                 // find the first element with a value >= pivot value
1993                                                 while (i < k && key.CompareTo (keys[i]) > 0)
1994                                                         i++;
1995
1996                                                 // find the last element with a value <= pivot value
1997                                                 while (k > i && key.CompareTo (keys[k]) < 0)
1998                                                         k--;
1999                                         } else {
2000                                                 while (i < k && keys[i] == null)
2001                                                         i++;
2002
2003                                                 while (k > i && keys[k] != null)
2004                                                         k--;
2005                                         }
2006
2007                                         if (k <= i)
2008                                                 break;
2009
2010                                         swap (keys, items, i, k);
2011
2012                                         i++;
2013                                         k--;
2014                                 } while (true);
2015
2016                                 // push our partitions onto the stack, largest first
2017                                 // (to make sure we don't run out of stack space)
2018                                 if ((high - k) >= (k - low)) {
2019                                         if ((k + 1) < high) {
2020                                                 stack[sp].high = high;
2021                                                 stack[sp].low = k;
2022                                                 sp++;
2023                                         }
2024
2025                                         if ((k - 1) > low) {
2026                                                 stack[sp].high = k;
2027                                                 stack[sp].low = low;
2028                                                 sp++;
2029                                         }
2030                                 } else {
2031                                         if ((k - 1) > low) {
2032                                                 stack[sp].high = k;
2033                                                 stack[sp].low = low;
2034                                                 sp++;
2035                                         }
2036
2037                                         if ((k + 1) < high) {
2038                                                 stack[sp].high = high;
2039                                                 stack[sp].low = k;
2040                                                 sp++;
2041                                         }
2042                                 }
2043                         } while (sp > 0);
2044                 }
2045
2046                 // Specialized version for items==null
2047                 private static void qsort<T> (T[] keys, int low0, int high0) where T : IComparable<T>
2048                 {
2049                         QSortStack[] stack = new QSortStack[32];
2050                         const int QSORT_THRESHOLD = 7;
2051                         int high, low, mid, i, k;
2052                         int sp = 1;
2053                         T key;
2054
2055                         // initialize our stack
2056                         stack[0].high = high0;
2057                         stack[0].low = low0;
2058
2059                         do {
2060                                 // pop the stack
2061                                 sp--;
2062                                 high = stack[sp].high;
2063                                 low = stack[sp].low;
2064
2065                                 if ((low + QSORT_THRESHOLD) > high) {
2066                                         // switch to insertion sort
2067                                         for (i = low + 1; i <= high; i++) {
2068                                                 for (k = i; k > low; k--) {
2069                                                         // if keys[k] >= keys[k-1], break
2070                                                         if (keys[k-1] == null)
2071                                                                 break;
2072
2073                                                         if (keys[k] != null && keys[k].CompareTo (keys[k-1]) >= 0)
2074                                                                 break;
2075
2076                                                         swap (keys, k - 1, k);
2077                                                 }
2078                                         }
2079
2080                                         continue;
2081                                 }
2082
2083                                 // calculate the middle element
2084                                 mid = low + ((high - low) / 2);
2085
2086                                 // once we re-order the lo, mid, and hi elements to be in
2087                                 // ascending order, we'll use mid as our pivot.
2088                                 QSortArrange<T> (keys, low, mid);
2089                                 if (QSortArrange<T> (keys, mid, high))
2090                                         QSortArrange<T> (keys, low, mid);
2091
2092                                 key = keys[mid];
2093
2094                                 // since we've already guaranteed that lo <= mid and mid <= hi,
2095                                 // we can skip comparing them again
2096                                 k = high - 1;
2097                                 i = low + 1;
2098
2099                                 do {
2100                                         if (key != null) {
2101                                                 // find the first element with a value >= pivot value
2102                                                 while (i < k && key.CompareTo (keys[i]) > 0)
2103                                                         i++;
2104
2105                                                 // find the last element with a value <= pivot value
2106                                                 while (k >= i && key.CompareTo (keys[k]) < 0)
2107                                                         k--;
2108                                         } else {
2109                                                 while (i < k && keys[i] == null)
2110                                                         i++;
2111
2112                                                 while (k >= i && keys[k] != null)
2113                                                         k--;
2114                                         }
2115
2116                                         if (k <= i)
2117                                                 break;
2118
2119                                         swap (keys, i, k);
2120
2121                                         i++;
2122                                         k--;
2123                                 } while (true);
2124
2125                                 // push our partitions onto the stack, largest first
2126                                 // (to make sure we don't run out of stack space)
2127                                 if ((high - k) >= (k - low)) {
2128                                         if ((k + 1) < high) {
2129                                                 stack[sp].high = high;
2130                                                 stack[sp].low = k;
2131                                                 sp++;
2132                                         }
2133
2134                                         if ((k - 1) > low) {
2135                                                 stack[sp].high = k;
2136                                                 stack[sp].low = low;
2137                                                 sp++;
2138                                         }
2139                                 } else {
2140                                         if ((k - 1) > low) {
2141                                                 stack[sp].high = k;
2142                                                 stack[sp].low = low;
2143                                                 sp++;
2144                                         }
2145
2146                                         if ((k + 1) < high) {
2147                                                 stack[sp].high = high;
2148                                                 stack[sp].low = k;
2149                                                 sp++;
2150                                         }
2151                                 }
2152                         } while (sp > 0);
2153                 }
2154
2155                 static bool QSortArrange<K, V> (K [] keys, V [] items, int lo, int hi, IComparer<K> comparer)
2156                 {
2157                         IComparable<K> gcmp;
2158                         IComparable cmp;
2159
2160                         if (comparer != null) {
2161                                 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2162                                         swap<K, V> (keys, items, lo, hi);
2163                                         return true;
2164                                 }
2165                         } else if (keys[lo] != null) {
2166                                 if (keys[hi] == null) {
2167                                         swap<K, V> (keys, items, lo, hi);
2168                                         return true;
2169                                 }
2170
2171                                 gcmp = keys[hi] as IComparable<K>;
2172                                 if (gcmp != null) {
2173                                         if (gcmp.CompareTo (keys[lo]) < 0) {
2174                                                 swap<K, V> (keys, items, lo, hi);
2175                                                 return true;
2176                                         }
2177
2178                                         return false;
2179                                 }
2180
2181                                 cmp = keys[hi] as IComparable;
2182                                 if (cmp != null) {
2183                                         if (cmp.CompareTo (keys[lo]) < 0) {
2184                                                 swap<K, V> (keys, items, lo, hi);
2185                                                 return true;
2186                                         }
2187
2188                                         return false;
2189                                 }
2190                         }
2191
2192                         return false;
2193                 }
2194
2195                 // Specialized version for items==null
2196                 static bool QSortArrange<K> (K [] keys, int lo, int hi, IComparer<K> comparer)
2197                 {
2198                         IComparable<K> gcmp;
2199                         IComparable cmp;
2200
2201                         if (comparer != null) {
2202                                 if (comparer.Compare (keys[hi], keys[lo]) < 0) {
2203                                         swap<K> (keys, lo, hi);
2204                                         return true;
2205                                 }
2206                         } else if (keys[lo] != null) {
2207                                 if (keys[hi] == null) {
2208                                         swap<K> (keys, lo, hi);
2209                                         return true;
2210                                 }
2211
2212                                 gcmp = keys[hi] as IComparable<K>;
2213                                 if (gcmp != null) {
2214                                         if (gcmp.CompareTo (keys[lo]) < 0) {
2215                                                 swap<K> (keys, lo, hi);
2216                                                 return true;
2217                                         }
2218
2219                                         return false;
2220                                 }
2221
2222                                 cmp = keys[hi] as IComparable;
2223                                 if (cmp != null) {
2224                                         if (cmp.CompareTo (keys[lo]) < 0) {
2225                                                 swap<K> (keys, lo, hi);
2226                                                 return true;
2227                                         }
2228
2229                                         return false;
2230                                 }
2231                         }
2232
2233                         return false;
2234                 }
2235
2236                 private static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
2237                 {
2238                         QSortStack[] stack = new QSortStack[32];
2239                         const int QSORT_THRESHOLD = 7;
2240                         int high, low, mid, i, k;
2241                         IComparable<K> gcmp;
2242                         IComparable cmp;
2243                         int sp = 1;
2244                         K key;
2245
2246                         // initialize our stack
2247                         stack[0].high = high0;
2248                         stack[0].low = low0;
2249
2250                         do {
2251                                 // pop the stack
2252                                 sp--;
2253                                 high = stack[sp].high;
2254                                 low = stack[sp].low;
2255
2256                                 if ((low + QSORT_THRESHOLD) > high) {
2257                                         // switch to insertion sort
2258                                         for (i = low + 1; i <= high; i++) {
2259                                                 for (k = i; k > low; k--) {
2260                                                         // if keys[k] >= keys[k-1], break
2261                                                         if (comparer != null) {
2262                                                                 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2263                                                                         break;
2264                                                         } else {
2265                                                                 if (keys[k-1] == null)
2266                                                                         break;
2267
2268                                                                 if (keys[k] != null) {
2269                                                                         gcmp = keys[k] as IComparable<K>;
2270                                                                         cmp = keys[k] as IComparable;
2271                                                                         if (gcmp != null) {
2272                                                                                 if (gcmp.CompareTo (keys[k-1]) >= 0)
2273                                                                                         break;
2274                                                                         } else {
2275                                                                                 if (cmp.CompareTo (keys[k-1]) >= 0)
2276                                                                                         break;
2277                                                                         }
2278                                                                 }
2279                                                         }
2280
2281                                                         swap<K, V> (keys, items, k - 1, k);
2282                                                 }
2283                                         }
2284
2285                                         continue;
2286                                 }
2287
2288                                 // calculate the middle element
2289                                 mid = low + ((high - low) / 2);
2290
2291                                 // once we re-order the low, mid, and high elements to be in
2292                                 // ascending order, we'll use mid as our pivot.
2293                                 QSortArrange<K, V> (keys, items, low, mid, comparer);
2294                                 if (QSortArrange<K, V> (keys, items, mid, high, comparer))
2295                                         QSortArrange<K, V> (keys, items, low, mid, comparer);
2296
2297                                 key = keys[mid];
2298                                 gcmp = key as IComparable<K>;
2299                                 cmp = key as IComparable;
2300
2301                                 // since we've already guaranteed that lo <= mid and mid <= hi,
2302                                 // we can skip comparing them again.
2303                                 k = high - 1;
2304                                 i = low + 1;
2305
2306                                 do {
2307                                         // Move the walls in
2308                                         if (comparer != null) {
2309                                                 // find the first element with a value >= pivot value
2310                                                 while (i < k && comparer.Compare (key, keys[i]) > 0)
2311                                                         i++;
2312
2313                                                 // find the last element with a value <= pivot value
2314                                                 while (k > i && comparer.Compare (key, keys[k]) < 0)
2315                                                         k--;
2316                                         } else {
2317                                                 if (gcmp != null) {
2318                                                         // find the first element with a value >= pivot value
2319                                                         while (i < k && gcmp.CompareTo (keys[i]) > 0)
2320                                                                 i++;
2321
2322                                                         // find the last element with a value <= pivot value
2323                                                         while (k > i && gcmp.CompareTo (keys[k]) < 0)
2324                                                                 k--;
2325                                                 } else if (cmp != null) {
2326                                                         // find the first element with a value >= pivot value
2327                                                         while (i < k && cmp.CompareTo (keys[i]) > 0)
2328                                                                 i++;
2329
2330                                                         // find the last element with a value <= pivot value
2331                                                         while (k > i && cmp.CompareTo (keys[k]) < 0)
2332                                                                 k--;
2333                                                 } else {
2334                                                         while (i < k && keys[i] == null)
2335                                                                 i++;
2336
2337                                                         while (k > i && keys[k] != null)
2338                                                                 k--;
2339                                                 }
2340                                         }
2341
2342                                         if (k <= i)
2343                                                 break;
2344
2345                                         swap<K, V> (keys, items, i, k);
2346
2347                                         i++;
2348                                         k--;
2349                                 } while (true);
2350
2351                                 // push our partitions onto the stack, largest first
2352                                 // (to make sure we don't run out of stack space)
2353                                 if ((high - k) >= (k - low)) {
2354                                         if ((k + 1) < high) {
2355                                                 stack[sp].high = high;
2356                                                 stack[sp].low = k;
2357                                                 sp++;
2358                                         }
2359
2360                                         if ((k - 1) > low) {
2361                                                 stack[sp].high = k;
2362                                                 stack[sp].low = low;
2363                                                 sp++;
2364                                         }
2365                                 } else {
2366                                         if ((k - 1) > low) {
2367                                                 stack[sp].high = k;
2368                                                 stack[sp].low = low;
2369                                                 sp++;
2370                                         }
2371
2372                                         if ((k + 1) < high) {
2373                                                 stack[sp].high = high;
2374                                                 stack[sp].low = k;
2375                                                 sp++;
2376                                         }
2377                                 }
2378                         } while (sp > 0);
2379                 }
2380
2381                 // Specialized version for items==null
2382                 private static void qsort<K> (K [] keys, int low0, int high0, IComparer<K> comparer)
2383                 {
2384                         QSortStack[] stack = new QSortStack[32];
2385                         const int QSORT_THRESHOLD = 7;
2386                         int high, low, mid, i, k;
2387                         IComparable<K> gcmp;
2388                         IComparable cmp;
2389                         int sp = 1;
2390                         K key;
2391
2392                         // initialize our stack
2393                         stack[0].high = high0;
2394                         stack[0].low = low0;
2395
2396                         do {
2397                                 // pop the stack
2398                                 sp--;
2399                                 high = stack[sp].high;
2400                                 low = stack[sp].low;
2401
2402                                 if ((low + QSORT_THRESHOLD) > high) {
2403                                         // switch to insertion sort
2404                                         for (i = low + 1; i <= high; i++) {
2405                                                 for (k = i; k > low; k--) {
2406                                                         // if keys[k] >= keys[k-1], break
2407                                                         if (comparer != null) {
2408                                                                 if (comparer.Compare (keys[k], keys[k-1]) >= 0)
2409                                                                         break;
2410                                                         } else {
2411                                                                 if (keys[k-1] == null)
2412                                                                         break;
2413
2414                                                                 if (keys[k] != null) {
2415                                                                         gcmp = keys[k] as IComparable<K>;
2416                                                                         cmp = keys[k] as IComparable;
2417                                                                         if (gcmp != null) {
2418                                                                                 if (gcmp.CompareTo (keys[k-1]) >= 0)
2419                                                                                         break;
2420                                                                         } else {
2421                                                                                 if (cmp.CompareTo (keys[k-1]) >= 0)
2422                                                                                         break;
2423                                                                         }
2424                                                                 }
2425                                                         }
2426
2427                                                         swap<K> (keys, k - 1, k);
2428                                                 }
2429                                         }
2430
2431                                         continue;
2432                                 }
2433
2434                                 // calculate the middle element
2435                                 mid = low + ((high - low) / 2);
2436
2437                                 // once we re-order the low, mid, and high elements to be in
2438                                 // ascending order, we'll use mid as our pivot.
2439                                 QSortArrange<K> (keys, low, mid, comparer);
2440                                 if (QSortArrange<K> (keys, mid, high, comparer))
2441                                         QSortArrange<K> (keys, low, mid, comparer);
2442
2443                                 key = keys[mid];
2444                                 gcmp = key as IComparable<K>;
2445                                 cmp = key as IComparable;
2446
2447                                 // since we've already guaranteed that lo <= mid and mid <= hi,
2448                                 // we can skip comparing them again.
2449                                 k = high - 1;
2450                                 i = low + 1;
2451
2452                                 do {
2453                                         // Move the walls in
2454                                         if (comparer != null) {
2455                                                 // find the first element with a value >= pivot value
2456                                                 while (i < k && comparer.Compare (key, keys[i]) > 0)
2457                                                         i++;
2458
2459                                                 // find the last element with a value <= pivot value
2460                                                 while (k > i && comparer.Compare (key, keys[k]) < 0)
2461                                                         k--;
2462                                         } else {
2463                                                 if (gcmp != null) {
2464                                                         // find the first element with a value >= pivot value
2465                                                         while (i < k && gcmp.CompareTo (keys[i]) > 0)
2466                                                                 i++;
2467
2468                                                         // find the last element with a value <= pivot value
2469                                                         while (k > i && gcmp.CompareTo (keys[k]) < 0)
2470                                                                 k--;
2471                                                 } else if (cmp != null) {
2472                                                         // find the first element with a value >= pivot value
2473                                                         while (i < k && cmp.CompareTo (keys[i]) > 0)
2474                                                                 i++;
2475
2476                                                         // find the last element with a value <= pivot value
2477                                                         while (k > i && cmp.CompareTo (keys[k]) < 0)
2478                                                                 k--;
2479                                                 } else {
2480                                                         while (i < k && keys[i] == null)
2481                                                                 i++;
2482
2483                                                         while (k > i && keys[k] != null)
2484                                                                 k--;
2485                                                 }
2486                                         }
2487
2488                                         if (k <= i)
2489                                                 break;
2490
2491                                         swap<K> (keys, i, k);
2492
2493                                         i++;
2494                                         k--;
2495                                 } while (true);
2496
2497                                 // push our partitions onto the stack, largest first
2498                                 // (to make sure we don't run out of stack space)
2499                                 if ((high - k) >= (k - low)) {
2500                                         if ((k + 1) < high) {
2501                                                 stack[sp].high = high;
2502                                                 stack[sp].low = k;
2503                                                 sp++;
2504                                         }
2505
2506                                         if ((k - 1) > low) {
2507                                                 stack[sp].high = k;
2508                                                 stack[sp].low = low;
2509                                                 sp++;
2510                                         }
2511                                 } else {
2512                                         if ((k - 1) > low) {
2513                                                 stack[sp].high = k;
2514                                                 stack[sp].low = low;
2515                                                 sp++;
2516                                         }
2517
2518                                         if ((k + 1) < high) {
2519                                                 stack[sp].high = high;
2520                                                 stack[sp].low = k;
2521                                                 sp++;
2522                                         }
2523                                 }
2524                         } while (sp > 0);
2525                 }
2526
2527                 static bool QSortArrange<T> (T [] array, int lo, int hi, Comparison<T> compare)
2528                 {
2529                         if (array[lo] != null) {
2530                                 if (array[hi] == null || compare (array[hi], array[lo]) < 0) {
2531                                         swap<T> (array, lo, hi);
2532                                         return true;
2533                                 }
2534                         }
2535
2536                         return false;
2537                 }
2538
2539                 private static void qsort<T> (T [] array, int low0, int high0, Comparison<T> compare)
2540                 {
2541                         QSortStack[] stack = new QSortStack[32];
2542                         const int QSORT_THRESHOLD = 7;
2543                         int high, low, mid, i, k;
2544                         int sp = 1;
2545                         T key;
2546
2547                         // initialize our stack
2548                         stack[0].high = high0;
2549                         stack[0].low = low0;
2550
2551                         do {
2552                                 // pop the stack
2553                                 sp--;
2554                                 high = stack[sp].high;
2555                                 low = stack[sp].low;
2556
2557                                 if ((low + QSORT_THRESHOLD) > high) {
2558                                         // switch to insertion sort
2559                                         for (i = low + 1; i <= high; i++) {
2560                                                 for (k = i; k > low; k--) {
2561                                                         // if keys[k] >= keys[k-1], break
2562                                                         if (array[k-1] == null)
2563                                                                 break;
2564
2565                                                         if (array[k] != null && compare (array[k], array[k-1]) >= 0)
2566                                                                 break;
2567
2568                                                         swap<T> (array, k - 1, k);
2569                                                 }
2570                                         }
2571
2572                                         continue;
2573                                 }
2574
2575                                 // calculate the middle element
2576                                 mid = low + ((high - low) / 2);
2577
2578                                 // once we re-order the lo, mid, and hi elements to be in
2579                                 // ascending order, we'll use mid as our pivot.
2580                                 QSortArrange<T> (array, low, mid, compare);
2581                                 if (QSortArrange<T> (array, mid, high, compare))
2582                                         QSortArrange<T> (array, low, mid, compare);
2583
2584                                 key = array[mid];
2585
2586                                 // since we've already guaranteed that lo <= mid and mid <= hi,
2587                                 // we can skip comparing them again
2588                                 k = high - 1;
2589                                 i = low + 1;
2590
2591                                 do {
2592                                         // Move the walls in
2593                                         if (key != null) {
2594                                                 // find the first element with a value >= pivot value
2595                                                 while (i < k && compare (key, array[i]) > 0)
2596                                                         i++;
2597
2598                                                 // find the last element with a value <= pivot value
2599                                                 while (k > i && compare (key, array[k]) < 0)
2600                                                         k--;
2601                                         } else {
2602                                                 while (i < k && array[i] == null)
2603                                                         i++;
2604
2605                                                 while (k > i && array[k] != null)
2606                                                         k--;
2607                                         }
2608
2609                                         if (k <= i)
2610                                                 break;
2611
2612                                         swap<T> (array, i, k);
2613
2614                                         i++;
2615                                         k--;
2616                                 } while (true);
2617
2618                                 // push our partitions onto the stack, largest first
2619                                 // (to make sure we don't run out of stack space)
2620                                 if ((high - k) >= (k - low)) {
2621                                         if ((k + 1) < high) {
2622                                                 stack[sp].high = high;
2623                                                 stack[sp].low = k;
2624                                                 sp++;
2625                                         }
2626
2627                                         if ((k - 1) > low) {
2628                                                 stack[sp].high = k;
2629                                                 stack[sp].low = low;
2630                                                 sp++;
2631                                         }
2632                                 } else {
2633                                         if ((k - 1) > low) {
2634                                                 stack[sp].high = k;
2635                                                 stack[sp].low = low;
2636                                                 sp++;
2637                                         }
2638
2639                                         if ((k + 1) < high) {
2640                                                 stack[sp].high = high;
2641                                                 stack[sp].low = k;
2642                                                 sp++;
2643                                         }
2644                                 }
2645                         } while (sp > 0);
2646                 }
2647
2648                 private static void CheckComparerAvailable<K> (K [] keys, int low, int high)
2649                 {
2650                         // move null keys to beginning of array,
2651                         // ensure that non-null keys implement IComparable
2652                         for (int i = low; i < high; i++) {
2653                                 K key = keys [i];
2654                                 if (key != null) {
2655                                         if (!(key is IComparable<K>) && !(key is IComparable)) {
2656                                                 string msg = Locale.GetText ("No IComparable<T> or IComparable interface found for type '{0}'.");
2657                                                 throw new InvalidOperationException (String.Format (msg, key.GetType ()));
2658                                         }
2659                                 }
2660                         }
2661                 }
2662
2663                 private static void swap<K, V> (K [] keys, V [] items, int i, int j)
2664                 {
2665                         K tmp;
2666
2667                         tmp = keys [i];
2668                         keys [i] = keys [j];
2669                         keys [j] = tmp;
2670
2671                         if (items != null) {
2672                                 V itmp;
2673                                 itmp = items [i];
2674                                 items [i] = items [j];
2675                                 items [j] = itmp;
2676                         }
2677                 }
2678
2679                 private static void swap<T> (T [] array, int i, int j)
2680                 {
2681                         T tmp = array [i];
2682                         array [i] = array [j];
2683                         array [j] = tmp;
2684                 }
2685
2686                 public void CopyTo (Array array, int index)
2687                 {
2688                         if (array == null)
2689                                 throw new ArgumentNullException ("array");
2690
2691                         // The order of these exception checks may look strange,
2692                         // but that's how the microsoft runtime does it.
2693                         if (this.Rank > 1)
2694                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2695                         if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
2696                                 throw new ArgumentException ("Destination array was not long " +
2697                                         "enough. Check destIndex and length, and the array's " +
2698                                         "lower bounds.");
2699                         if (array.Rank > 1)
2700                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
2701                         if (index < 0)
2702                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2703                                         "Value has to be >= 0."));
2704
2705                         Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
2706                 }
2707
2708                 [ComVisible (false)]
2709                 public void CopyTo (Array array, long index)
2710                 {
2711                         if (index < 0 || index > Int32.MaxValue)
2712                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2713                                         "Value must be >= 0 and <= Int32.MaxValue."));
2714
2715                         CopyTo (array, (int) index);
2716                 }
2717
2718                 internal class SimpleEnumerator : IEnumerator, ICloneable
2719                 {
2720                         Array enumeratee;
2721                         int currentpos;
2722                         int length;
2723
2724                         public SimpleEnumerator (Array arrayToEnumerate)
2725                         {
2726                                 this.enumeratee = arrayToEnumerate;
2727                                 this.currentpos = -1;
2728                                 this.length = arrayToEnumerate.Length;
2729                         }
2730
2731                         public object Current {
2732                                 get {
2733                                         // Exception messages based on MS implementation
2734                                         if (currentpos < 0 )
2735                                                 throw new InvalidOperationException (Locale.GetText (
2736                                                         "Enumeration has not started."));
2737                                         if  (currentpos >= length)
2738                                                 throw new InvalidOperationException (Locale.GetText (
2739                                                         "Enumeration has already ended"));
2740                                         // Current should not increase the position. So no ++ over here.
2741                                         return enumeratee.GetValueImpl (currentpos);
2742                                 }
2743                         }
2744
2745                         public bool MoveNext()
2746                         {
2747                                 //The docs say Current should throw an exception if last
2748                                 //call to MoveNext returned false. This means currentpos
2749                                 //should be set to length when returning false.
2750                                 if (currentpos < length)
2751                                         currentpos++;
2752                                 if(currentpos < length)
2753                                         return true;
2754                                 else
2755                                         return false;
2756                         }
2757
2758                         public void Reset()
2759                         {
2760                                 currentpos = -1;
2761                         }
2762
2763                         public object Clone ()
2764                         {
2765                                 return MemberwiseClone ();
2766                         }
2767                 }
2768
2769                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2770                 public static void Resize<T> (ref T [] array, int newSize)
2771                 {
2772                         if (newSize < 0)
2773                                 throw new ArgumentOutOfRangeException ();
2774
2775                         if (array == null) {
2776                                 array = new T [newSize];
2777                                 return;
2778                         }
2779
2780                         int length = array.Length;
2781                         if (length == newSize)
2782                                 return;
2783
2784                         T [] a = new T [newSize];
2785                         if (length != 0)
2786                                 FastCopy (array, 0, a, 0, Math.Min (newSize, length));
2787                         array = a;
2788                 }
2789
2790                 public static bool TrueForAll <T> (T [] array, Predicate <T> match)
2791                 {
2792                         if (array == null)
2793                                 throw new ArgumentNullException ("array");
2794                         if (match == null)
2795                                 throw new ArgumentNullException ("match");
2796
2797                         foreach (T t in array)
2798                                 if (! match (t))
2799                                         return false;
2800
2801                         return true;
2802                 }
2803
2804                 public static void ForEach<T> (T [] array, Action <T> action)
2805                 {
2806                         if (array == null)
2807                                 throw new ArgumentNullException ("array");
2808                         if (action == null)
2809                                 throw new ArgumentNullException ("action");
2810
2811                         foreach (T t in array)
2812                                 action (t);
2813                 }
2814
2815                 public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
2816                 {
2817                         if (array == null)
2818                                 throw new ArgumentNullException ("array");
2819                         if (converter == null)
2820                                 throw new ArgumentNullException ("converter");
2821
2822                         TOutput [] output = new TOutput [array.Length];
2823                         for (int i = 0; i < array.Length; i ++)
2824                                 output [i] = converter (array [i]);
2825
2826                         return output;
2827                 }
2828
2829                 public static int FindLastIndex<T> (T [] array, Predicate <T> match)
2830                 {
2831                         if (array == null)
2832                                 throw new ArgumentNullException ("array");
2833
2834                         return FindLastIndex<T> (array, 0, array.Length, match);
2835                 }
2836
2837                 public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
2838                 {
2839                         if (array == null)
2840                                 throw new ArgumentNullException ();
2841
2842                         return FindLastIndex<T> (array, startIndex, array.Length - startIndex, match);
2843                 }
2844
2845                 public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2846                 {
2847                         if (array == null)
2848                                 throw new ArgumentNullException ("array");
2849                         if (match == null)
2850                                 throw new ArgumentNullException ("match");
2851
2852                         if (startIndex > array.Length || startIndex + count > array.Length)
2853                                 throw new ArgumentOutOfRangeException ();
2854
2855                         for (int i = startIndex + count - 1; i >= startIndex; i--)
2856                                 if (match (array [i]))
2857                                         return i;
2858
2859                         return -1;
2860                 }
2861
2862                 public static int FindIndex<T> (T [] array, Predicate<T> match)
2863                 {
2864                         if (array == null)
2865                                 throw new ArgumentNullException ("array");
2866
2867                         return FindIndex<T> (array, 0, array.Length, match);
2868                 }
2869
2870                 public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
2871                 {
2872                         if (array == null)
2873                                 throw new ArgumentNullException ("array");
2874
2875                         return FindIndex<T> (array, startIndex, array.Length - startIndex, match);
2876                 }
2877
2878                 public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
2879                 {
2880                         if (array == null)
2881                                 throw new ArgumentNullException ("array");
2882
2883                         if (match == null)
2884                                 throw new ArgumentNullException ("match");
2885
2886                         if (startIndex > array.Length || startIndex + count > array.Length)
2887                                 throw new ArgumentOutOfRangeException ();
2888
2889                         for (int i = startIndex; i < startIndex + count; i ++)
2890                                 if (match (array [i]))
2891                                         return i;
2892
2893                         return -1;
2894                 }
2895
2896                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2897                 public static int BinarySearch<T> (T [] array, T value)
2898                 {
2899                         if (array == null)
2900                                 throw new ArgumentNullException ("array");
2901
2902                         return BinarySearch<T> (array, 0, array.Length, value, null);
2903                 }
2904
2905                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2906                 public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
2907                 {
2908                         if (array == null)
2909                                 throw new ArgumentNullException ("array");
2910
2911                         return BinarySearch<T> (array, 0, array.Length, value, comparer);
2912                 }
2913
2914                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2915                 public static int BinarySearch<T> (T [] array, int index, int length, T value)
2916                 {
2917                         return BinarySearch<T> (array, index, length, value, null);
2918                 }
2919
2920                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
2921                 public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
2922                 {
2923                         if (array == null)
2924                                 throw new ArgumentNullException ("array");
2925                         if (index < 0)
2926                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2927                                         "index is less than the lower bound of array."));
2928                         if (length < 0)
2929                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
2930                                         "Value has to be >= 0."));
2931                         // re-ordered to avoid possible integer overflow
2932                         if (index > array.Length - length)
2933                                 throw new ArgumentException (Locale.GetText (
2934                                         "index and length do not specify a valid range in array."));
2935                         if (comparer == null)
2936                                 comparer = Comparer <T>.Default;
2937
2938                         int iMin = index;
2939                         int iMax = index + length - 1;
2940                         int iCmp = 0;
2941                         try {
2942                                 while (iMin <= iMax) {
2943                                         // Be careful with overflows
2944                                         int iMid = iMin + ((iMax - iMin) / 2);
2945                                         iCmp = comparer.Compare (array [iMid], value);
2946
2947                                         if (iCmp == 0)
2948                                                 return iMid;
2949
2950                                         if (iCmp > 0)
2951                                                 iMax = iMid - 1;
2952                                         else
2953                                                 iMin = iMid + 1; // compensate for the rounding down
2954                                 }
2955                         } catch (Exception e) {
2956                                 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
2957                         }
2958
2959                         return ~iMin;
2960                 }
2961
2962                 public static int IndexOf<T> (T [] array, T value)
2963                 {
2964                         if (array == null)
2965                                 throw new ArgumentNullException ("array");
2966
2967                         return IndexOf<T> (array, value, 0, array.Length);
2968                 }
2969
2970                 public static int IndexOf<T> (T [] array, T value, int startIndex)
2971                 {
2972                         if (array == null)
2973                                 throw new ArgumentNullException ("array");
2974
2975                         return IndexOf<T> (array, value, startIndex, array.Length - startIndex);
2976                 }
2977
2978                 public static int IndexOf<T> (T [] array, T value, int startIndex, int count)
2979                 {
2980                         if (array == null)
2981                                 throw new ArgumentNullException ("array");
2982
2983                         // re-ordered to avoid possible integer overflow
2984                         if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
2985                                 throw new ArgumentOutOfRangeException ();
2986
2987                         int max = startIndex + count;
2988                         EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
2989                         for (int i = startIndex; i < max; i++) {
2990                                 if (equalityComparer.Equals (array [i], value))
2991                                         return i;
2992                         }
2993
2994                         return -1;
2995                 }
2996
2997                 public static int LastIndexOf<T> (T [] array, T value)
2998                 {
2999                         if (array == null)
3000                                 throw new ArgumentNullException ("array");
3001
3002                         if (array.Length == 0)
3003                                 return -1;
3004                         return LastIndexOf<T> (array, value, array.Length - 1);
3005                 }
3006
3007                 public static int LastIndexOf<T> (T [] array, T value, int startIndex)
3008                 {
3009                         if (array == null)
3010                                 throw new ArgumentNullException ("array");
3011
3012                         return LastIndexOf<T> (array, value, startIndex, startIndex + 1);
3013                 }
3014
3015                 public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
3016                 {
3017                         if (array == null)
3018                                 throw new ArgumentNullException ("array");
3019
3020                         if (count < 0 || startIndex < array.GetLowerBound (0) ||
3021                                 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
3022                                 throw new ArgumentOutOfRangeException ();
3023
3024                         EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
3025                         for (int i = startIndex; i >= startIndex - count + 1; i--) {
3026                                 if (equalityComparer.Equals (array [i], value))
3027                                         return i;
3028                         }
3029
3030                         return -1;
3031                 }
3032
3033                 public static T [] FindAll<T> (T [] array, Predicate <T> match)
3034                 {
3035                         if (array == null)
3036                                 throw new ArgumentNullException ("array");
3037
3038                         if (match == null)
3039                                 throw new ArgumentNullException ("match");
3040
3041                         int pos = 0;
3042                         T [] d = new T [array.Length];
3043                         foreach (T t in array)
3044                                 if (match (t))
3045                                         d [pos++] = t;
3046
3047                         Resize <T> (ref d, pos);
3048                         return d;
3049                 }
3050
3051                 public static bool Exists<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                         foreach (T t in array)
3060                                 if (match (t))
3061                                         return true;
3062                         return false;
3063                 }
3064
3065                 public static ReadOnlyCollection<T> AsReadOnly<T> (T[] array)
3066                 {
3067                         if (array == null)
3068                                 throw new ArgumentNullException ("array");
3069
3070                         return new ReadOnlyCollection<T> (array);
3071                 }
3072
3073                 public static T Find<T> (T [] array, Predicate<T> match)
3074                 {
3075                         if (array == null)
3076                                 throw new ArgumentNullException ("array");
3077
3078                         if (match == null)
3079                                 throw new ArgumentNullException ("match");
3080
3081                         foreach (T t in array)
3082                                 if (match (t))
3083                                         return t;
3084
3085                         return default (T);
3086                 }
3087
3088                 public static T FindLast<T> (T [] array, Predicate <T> match)
3089                 {
3090                         if (array == null)
3091                                 throw new ArgumentNullException ("array");
3092
3093                         if (match == null)
3094                                 throw new ArgumentNullException ("match");
3095
3096                         for (int i = array.Length - 1; i >= 0; i--)
3097                                 if (match (array [i]))
3098                                         return array [i];
3099
3100                         return default (T);
3101                 }
3102
3103                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
3104                 //
3105                 // The constrained copy should guarantee that if there is an exception thrown
3106                 // during the copy, the destination array remains unchanged.
3107                 // This is related to System.Runtime.Reliability.CER
3108                 public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
3109                 {
3110                         Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length);
3111                 }
3112
3113                 internal static T UnsafeLoad<T> (T[] array, int index) {
3114                         return array [index];
3115                 }
3116
3117                 internal static void UnsafeStore<T> (T[] array, int index, T value) {
3118                         array [index] = value;
3119                 }
3120         }
3121 }