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 //
  10 // (C) 2001-2003 Ximian, Inc.  http://www.ximian.com
  11 // Copyright (C) 2004-2005 Novell, Inc (http://www.novell.com)
  12 //
  13 // Permission is hereby granted, free of charge, to any person obtaining
  14 // a copy of this software and associated documentation files (the
  15 // "Software"), to deal in the Software without restriction, including
  16 // without limitation the rights to use, copy, modify, merge, publish,
  17 // distribute, sublicense, and/or sell copies of the Software, and to
  18 // permit persons to whom the Software is furnished to do so, subject to
  19 // the following conditions:
  20 //
  21 // The above copyright notice and this permission notice shall be
  22 // included in all copies or substantial portions of the Software.
  23 //
  24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  25 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  26 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  27 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  28 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  29 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  30 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  31 //
  32
  33 using System.Collections;
  34 using System.Runtime.CompilerServices;
  35 using System.Runtime.InteropServices;
  36
  37 using System.Collections.Generic;
  38 using System.Collections.ObjectModel;
  39 using System.Runtime.ConstrainedExecution;
  40
  41 namespace System
  42 {
  43         [Serializable]
  44         [ComVisible (true)]
  45         // FIXME: We are doing way to many double/triple exception checks for the overloaded functions"
  46         public abstract class Array : ICloneable, ICollection, IList, IEnumerable
  47         {
  48                 // Constructor
  49                 private Array ()
  50                 {
  51                 }
  52
  53                 /*
  54                  * These methods are used to implement the implicit generic interfaces
  55                  * implemented by arrays in NET 2.0.
  56                  * Only make those methods generic which really need it, to avoid
  57                  * creating useless instantiations.
  58                  */
  59                 internal int InternalArray__ICollection_get_Count ()
  60                 {
  61                         return Length;
  62                 }
  63
  64                 internal bool InternalArray__ICollection_get_IsReadOnly ()
  65                 {
  66                         return true;
  67                 }
  68
  69                 internal IEnumerator<T> InternalArray__IEnumerable_GetEnumerator<T> ()
  70                 {
  71                         return new InternalEnumerator<T> (this);
  72                 }
  73
  74                 internal void InternalArray__ICollection_Clear ()
  75                 {
  76                         throw new NotSupportedException ("Collection is read-only");
  77                 }
  78
  79                 internal void InternalArray__ICollection_Add<T> (T item)
  80                 {
  81                         throw new NotSupportedException ("Collection is read-only");
  82                 }
  83
  84                 internal bool InternalArray__ICollection_Remove<T> (T item)
  85                 {
  86                         throw new NotSupportedException ("Collection is read-only");
  87                 }
  88
  89                 internal bool InternalArray__ICollection_Contains<T> (T item)
  90                 {
  91                         if (this.Rank > 1)
  92                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
  93
  94                         int length = this.Length;
  95                         for (int i = 0; i < length; i++) {
  96                                 T value;
  97                                 GetGenericValueImpl (i, out value);
  98                                 if (item == null){
  99                                         if (value == null)
 100                                                 return true;
 101                                         else
 102                                                 return false;
 103                                 }
 104
 105                                 if (item.Equals (value))
 106                                         return true;
 107                         }
 108
 109                         return false;
 110                 }
 111
 112                 internal void InternalArray__ICollection_CopyTo<T> (T[] array, int index)
 113                 {
 114                         if (array == null)
 115                                 throw new ArgumentNullException ("array");
 116
 117                         // The order of these exception checks may look strange,
 118                         // but that's how the microsoft runtime does it.
 119                         if (this.Rank > 1)
 120                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 121                         if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
 122                                 throw new ArgumentException ("Destination array was not long " +
 123                                         "enough. Check destIndex and length, and the array's " +
 124                                         "lower bounds.");
 125                         if (array.Rank > 1)
 126                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 127                         if (index < 0)
 128                                 throw new ArgumentOutOfRangeException (
 129                                         "index", Locale.GetText ("Value has to be >= 0."));
 130
 131                         Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
 132                 }
 133
 134                 internal void InternalArray__Insert<T> (int index, T item)
 135                 {
 136                         throw new NotSupportedException ("Collection is read-only");
 137                 }
 138
 139                 internal void InternalArray__RemoveAt (int index)
 140                 {
 141                         throw new NotSupportedException ("Collection is read-only");
 142                 }
 143
 144                 internal int InternalArray__IndexOf<T> (T item)
 145                 {
 146                         if (this.Rank > 1)
 147                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 148
 149                         int length = this.Length;
 150                         for (int i = 0; i < length; i++) {
 151                                 T value;
 152                                 GetGenericValueImpl (i, out value);
 153                                 if (item == null){
 154                                         if (value == null)
 155                                                 return i + this.GetLowerBound (0);
 156                                         else {
 157                                                 unchecked {
 158                                                         return this.GetLowerBound (0) - 1;
 159                                                 }
 160                                         }
 161                                 }
 162                                 if (value.Equals (item))
 163                                         // array index may not be zero-based.
 164                                         // use lower bound
 165                                         return i + this.GetLowerBound (0);
 166                         }
 167
 168                         unchecked {
 169                                 // lower bound may be MinValue
 170                                 return this.GetLowerBound (0) - 1;
 171                         }
 172                 }
 173
 174                 internal T InternalArray__get_Item<T> (int index)
 175                 {
 176                         if (unchecked ((uint) index) >= unchecked ((uint) Length))
 177                                 throw new ArgumentOutOfRangeException ("index");
 178
 179                         T value;
 180                         GetGenericValueImpl (index, out value);
 181                         return value;
 182                 }
 183
 184                 internal void InternalArray__set_Item<T> (int index, T item)
 185                 {
 186                         if (unchecked ((uint) index) >= unchecked ((uint) Length))
 187                                 throw new ArgumentOutOfRangeException ("index");
 188
 189                         object[] oarray = this as object [];
 190                         if (oarray != null) {
 191                                 oarray [index] = (object)item;
 192                                 return;
 193                         }
 194                         SetGenericValueImpl (index, ref item);
 195                 }
 196
 197                 // CAUTION! No bounds checking!
 198                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 199                 internal extern void GetGenericValueImpl<T> (int pos, out T value);
 200
 201                 // CAUTION! No bounds checking!
 202                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 203                 internal extern void SetGenericValueImpl<T> (int pos, ref T value);
 204
 205                 internal struct InternalEnumerator<T> : IEnumerator<T>
 206                 {
 207                         const int NOT_STARTED = -2;
 208
 209                         // this MUST be -1, because we depend on it in move next.
 210                         // we just decr the size, so, 0 - 1 == FINISHED
 211                         const int FINISHED = -1;
 212
 213                         Array array;
 214                         int idx;
 215
 216                         internal InternalEnumerator (Array array)
 217                         {
 218                                 this.array = array;
 219                                 idx = NOT_STARTED;
 220                         }
 221
 222                         public void Dispose ()
 223                         {
 224                                 idx = NOT_STARTED;
 225                         }
 226
 227                         public bool MoveNext ()
 228                         {
 229                                 if (idx == NOT_STARTED)
 230                                         idx = array.Length;
 231
 232                                 return idx != FINISHED && -- idx != FINISHED;
 233                         }
 234
 235                         public T Current {
 236                                 get {
 237                                         if (idx == NOT_STARTED)
 238                                                 throw new InvalidOperationException ("Enumeration has not started. Call MoveNext");
 239                                         if (idx == FINISHED)
 240                                                 throw new InvalidOperationException ("Enumeration already finished");
 241
 242                                         return array.InternalArray__get_Item<T> (array.Length - 1 - idx);
 243                                 }
 244                         }
 245
 246                         void IEnumerator.Reset ()
 247                         {
 248                                 idx = NOT_STARTED;
 249                         }
 250
 251                         object IEnumerator.Current {
 252                                 get {
 253                                         return Current;
 254                                 }
 255                         }
 256                 }
 257
 258                 // Properties
 259                 public int Length {
 260                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 261                         get {
 262                                 int length = this.GetLength (0);
 263
 264                                 for (int i = 1; i < this.Rank; i++) {
 265                                         length *= this.GetLength (i);
 266                                 }
 267                                 return length;
 268                         }
 269                 }
 270
 271                 [ComVisible (false)]
 272                 public long LongLength {
 273                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 274                         get { return Length; }
 275                 }
 276
 277                 public int Rank {
 278                         [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 279                         get {
 280                                 return this.GetRank ();
 281                         }
 282                 }
 283
 284                 // IList interface
 285                 object IList.this [int index] {
 286                         get {
 287                                 if (unchecked ((uint) index) >= unchecked ((uint) Length))
 288                                         throw new IndexOutOfRangeException ("index");
 289                                 return GetValueImpl (index);
 290                         }
 291                         set {
 292                                 if (unchecked ((uint) index) >= unchecked ((uint) Length))
 293                                         throw new IndexOutOfRangeException ("index");
 294                                 SetValueImpl (value, index);
 295                         }
 296                 }
 297
 298                 int IList.Add (object value)
 299                 {
 300                         throw new NotSupportedException ();
 301                 }
 302
 303                 void IList.Clear ()
 304                 {
 305                         Array.Clear (this, this.GetLowerBound (0), this.Length);
 306                 }
 307
 308                 bool IList.Contains (object value)
 309                 {
 310                         if (this.Rank > 1)
 311                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 312
 313                         int length = this.Length;
 314                         for (int i = 0; i < length; i++) {
 315                                 if (Object.Equals (this.GetValueImpl (i), value))
 316                                         return true;
 317                         }
 318                         return false;
 319                 }
 320
 321                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 322                 int IList.IndexOf (object value)
 323                 {
 324                         if (this.Rank > 1)
 325                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 326
 327                         int length = this.Length;
 328                         for (int i = 0; i < length; i++) {
 329                                 if (Object.Equals (this.GetValueImpl (i), value))
 330                                         // array index may not be zero-based.
 331                                         // use lower bound
 332                                         return i + this.GetLowerBound (0);
 333                         }
 334
 335                         unchecked {
 336                                 // lower bound may be MinValue
 337                                 return this.GetLowerBound (0) - 1;
 338                         }
 339                 }
 340
 341                 void IList.Insert (int index, object value)
 342                 {
 343                         throw new NotSupportedException ();
 344                 }
 345
 346                 void IList.Remove (object value)
 347                 {
 348                         throw new NotSupportedException ();
 349                 }
 350
 351                 void IList.RemoveAt (int index)
 352                 {
 353                         throw new NotSupportedException ();
 354                 }
 355
 356                 // InternalCall Methods
 357                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 358                 extern int GetRank ();
 359
 360                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 361                 public extern int GetLength (int dimension);
 362
 363                 [ComVisible (false)]
 364                 public long GetLongLength (int dimension)
 365                 {
 366                         return GetLength (dimension);
 367                 }
 368
 369                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 370                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 371                 public extern int GetLowerBound (int dimension);
 372
 373                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 374                 public extern object GetValue (params int[] indices);
 375
 376                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 377                 public extern void SetValue (object value, params int[] indices);
 378
 379                 // CAUTION! No bounds checking!
 380                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 381                 internal extern object GetValueImpl (int pos);
 382
 383                 // CAUTION! No bounds checking!
 384                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 385                 internal extern void SetValueImpl (object value, int pos);
 386
 387                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 388                 internal extern static bool FastCopy (Array source, int source_idx, Array dest, int dest_idx, int length);
 389
 390                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 391                 internal extern static Array CreateInstanceImpl (Type elementType, int[] lengths, int[] bounds);
 392
 393                 // Properties
 394                 int ICollection.Count {
 395                         get {
 396                                 return Length;
 397                         }
 398                 }
 399
 400                 public bool IsSynchronized {
 401                         get {
 402                                 return false;
 403                         }
 404                 }
 405
 406                 public object SyncRoot {
 407                         get {
 408                                 return this;
 409                         }
 410                 }
 411
 412                 public bool IsFixedSize {
 413                         get {
 414                                 return true;
 415                         }
 416                 }
 417
 418                 public bool IsReadOnly {
 419                         get {
 420                                 return false;
 421                         }
 422                 }
 423
 424                 public IEnumerator GetEnumerator ()
 425                 {
 426                         return new SimpleEnumerator (this);
 427                 }
 428
 429                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 430                 public int GetUpperBound (int dimension)
 431                 {
 432                         return GetLowerBound (dimension) + GetLength (dimension) - 1;
 433                 }
 434
 435                 public object GetValue (int index)
 436                 {
 437                         if (Rank != 1)
 438                                 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
 439                         if (index < GetLowerBound (0) || index > GetUpperBound (0))
 440                                 throw new IndexOutOfRangeException (Locale.GetText (
 441                                         "Index has to be between upper and lower bound of the array."));
 442
 443                         return GetValueImpl (index - GetLowerBound (0));
 444                 }
 445
 446                 public object GetValue (int index1, int index2)
 447                 {
 448                         int[] ind = {index1, index2};
 449                         return GetValue (ind);
 450                 }
 451
 452                 public object GetValue (int index1, int index2, int index3)
 453                 {
 454                         int[] ind = {index1, index2, index3};
 455                         return GetValue (ind);
 456                 }
 457
 458                 [ComVisible (false)]
 459                 public object GetValue (long index)
 460                 {
 461                         if (index < 0 || index > Int32.MaxValue)
 462                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 463                                         "Value must be >= 0 and <= Int32.MaxValue."));
 464
 465                         return GetValue ((int) index);
 466                 }
 467
 468                 [ComVisible (false)]
 469                 public object GetValue (long index1, long index2)
 470                 {
 471                         if (index1 < 0 || index1 > Int32.MaxValue)
 472                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 473                                         "Value must be >= 0 and <= Int32.MaxValue."));
 474
 475                         if (index2 < 0 || index2 > Int32.MaxValue)
 476                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 477                                         "Value must be >= 0 and <= Int32.MaxValue."));
 478
 479                         return GetValue ((int) index1, (int) index2);
 480                 }
 481
 482                 [ComVisible (false)]
 483                 public object GetValue (long index1, long index2, long index3)
 484                 {
 485                         if (index1 < 0 || index1 > Int32.MaxValue)
 486                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 487                                         "Value must be >= 0 and <= Int32.MaxValue."));
 488
 489                         if (index2 < 0 || index2 > Int32.MaxValue)
 490                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 491                                         "Value must be >= 0 and <= Int32.MaxValue."));
 492
 493                         if (index3 < 0 || index3 > Int32.MaxValue)
 494                                 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
 495                                         "Value must be >= 0 and <= Int32.MaxValue."));
 496
 497                         return GetValue ((int) index1, (int) index2, (int) index3);
 498                 }
 499
 500                 [ComVisible (false)]
 501                 public void SetValue (object value, long index)
 502                 {
 503                         if (index < 0 || index > Int32.MaxValue)
 504                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 505                                         "Value must be >= 0 and <= Int32.MaxValue."));
 506
 507                         SetValue (value, (int) index);
 508                 }
 509
 510                 [ComVisible (false)]
 511                 public void SetValue (object value, long index1, long index2)
 512                 {
 513                         if (index1 < 0 || index1 > Int32.MaxValue)
 514                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 515                                         "Value must be >= 0 and <= Int32.MaxValue."));
 516
 517                         if (index2 < 0 || index2 > Int32.MaxValue)
 518                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 519                                         "Value must be >= 0 and <= Int32.MaxValue."));
 520
 521                         int[] ind = {(int) index1, (int) index2};
 522                         SetValue (value, ind);
 523                 }
 524
 525                 [ComVisible (false)]
 526                 public void SetValue (object value, long index1, long index2, long index3)
 527                 {
 528                         if (index1 < 0 || index1 > Int32.MaxValue)
 529                                 throw new ArgumentOutOfRangeException ("index1", Locale.GetText (
 530                                         "Value must be >= 0 and <= Int32.MaxValue."));
 531
 532                         if (index2 < 0 || index2 > Int32.MaxValue)
 533                                 throw new ArgumentOutOfRangeException ("index2", Locale.GetText (
 534                                         "Value must be >= 0 and <= Int32.MaxValue."));
 535
 536                         if (index3 < 0 || index3 > Int32.MaxValue)
 537                                 throw new ArgumentOutOfRangeException ("index3", Locale.GetText (
 538                                         "Value must be >= 0 and <= Int32.MaxValue."));
 539
 540                         int[] ind = {(int) index1, (int) index2, (int) index3};
 541                         SetValue (value, ind);
 542                 }
 543
 544                 public void SetValue (object value, int index)
 545                 {
 546                         if (Rank != 1)
 547                                 throw new ArgumentException (Locale.GetText ("Array was not a one-dimensional array."));
 548                         if (index < GetLowerBound (0) || index > GetUpperBound (0))
 549                                 throw new IndexOutOfRangeException (Locale.GetText (
 550                                         "Index has to be >= lower bound and <= upper bound of the array."));
 551
 552                         SetValueImpl (value, index - GetLowerBound (0));
 553                 }
 554
 555                 public void SetValue (object value, int index1, int index2)
 556                 {
 557                         int[] ind = {index1, index2};
 558                         SetValue (value, ind);
 559                 }
 560
 561                 public void SetValue (object value, int index1, int index2, int index3)
 562                 {
 563                         int[] ind = {index1, index2, index3};
 564                         SetValue (value, ind);
 565                 }
 566
 567                 public static Array CreateInstance (Type elementType, int length)
 568                 {
 569                         int[] lengths = {length};
 570
 571                         return CreateInstance (elementType, lengths);
 572                 }
 573
 574                 public static Array CreateInstance (Type elementType, int length1, int length2)
 575                 {
 576                         int[] lengths = {length1, length2};
 577
 578                         return CreateInstance (elementType, lengths);
 579                 }
 580
 581                 public static Array CreateInstance (Type elementType, int length1, int length2, int length3)
 582                 {
 583                         int[] lengths = {length1, length2, length3};
 584
 585                         return CreateInstance (elementType, lengths);
 586                 }
 587
 588                 public static Array CreateInstance (Type elementType, params int[] lengths)
 589                 {
 590                         if (elementType == null)
 591                                 throw new ArgumentNullException ("elementType");
 592                         if (lengths == null)
 593                                 throw new ArgumentNullException ("lengths");
 594
 595                         if (lengths.Length > 255)
 596                                 throw new TypeLoadException ();
 597
 598                         int[] bounds = null;
 599
 600                         elementType = elementType.UnderlyingSystemType;
 601                         if (!elementType.IsSystemType)
 602                                 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
 603
 604                         return CreateInstanceImpl (elementType, lengths, bounds);
 605                 }
 606
 607                 public static Array CreateInstance (Type elementType, int[] lengths, int [] lowerBounds)
 608                 {
 609                         if (elementType == null)
 610                                 throw new ArgumentNullException ("elementType");
 611                         if (lengths == null)
 612                                 throw new ArgumentNullException ("lengths");
 613                         if (lowerBounds == null)
 614                                 throw new ArgumentNullException ("lowerBounds");
 615
 616                         elementType = elementType.UnderlyingSystemType;
 617                         if (!elementType.IsSystemType)
 618                                 throw new ArgumentException ("Type must be a type provided by the runtime.", "elementType");
 619
 620                         if (lengths.Length < 1)
 621                                 throw new ArgumentException (Locale.GetText ("Arrays must contain >= 1 elements."));
 622
 623                         if (lengths.Length != lowerBounds.Length)
 624                                 throw new ArgumentException (Locale.GetText ("Arrays must be of same size."));
 625
 626                         for (int j = 0; j < lowerBounds.Length; j ++) {
 627                                 if (lengths [j] < 0)
 628                                         throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
 629                                                 "Each value has to be >= 0."));
 630                                 if ((long)lowerBounds [j] + (long)lengths [j] > (long)Int32.MaxValue)
 631                                         throw new ArgumentOutOfRangeException ("lengths", Locale.GetText (
 632                                                 "Length + bound must not exceed Int32.MaxValue."));
 633                         }
 634
 635                         if (lengths.Length > 255)
 636                                 throw new TypeLoadException ();
 637
 638                         return CreateInstanceImpl (elementType, lengths, lowerBounds);
 639                 }
 640
 641                 static int [] GetIntArray (long [] values)
 642                 {
 643                         int len = values.Length;
 644                         int [] ints = new int [len];
 645                         for (int i = 0; i < len; i++) {
 646                                 long current = values [i];
 647                                 if (current < 0 || current > (long) Int32.MaxValue)
 648                                         throw new ArgumentOutOfRangeException ("values", Locale.GetText (
 649                                                 "Each value has to be >= 0 and <= Int32.MaxValue."));
 650
 651                                 ints [i] = (int) current;
 652                         }
 653                         return ints;
 654                 }
 655
 656                 public static Array CreateInstance (Type elementType, params long [] lengths)
 657                 {
 658                         if (lengths == null)
 659                                 throw new ArgumentNullException ("lengths");
 660                         return CreateInstance (elementType, GetIntArray (lengths));
 661                 }
 662
 663                 [ComVisible (false)]
 664                 public object GetValue (params long [] indices)
 665                 {
 666                         if (indices == null)
 667                                 throw new ArgumentNullException ("indices");
 668                         return GetValue (GetIntArray (indices));
 669                 }
 670
 671                 [ComVisible (false)]
 672                 public void SetValue (object value, params long [] indices)
 673                 {
 674                         if (indices == null)
 675                                 throw new ArgumentNullException ("indices");
 676                         SetValue (value, GetIntArray (indices));
 677                 }
 678
 679                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 680                 public static int BinarySearch (Array array, object value)
 681                 {
 682                         if (array == null)
 683                                 throw new ArgumentNullException ("array");
 684
 685                         if (value == null)
 686                                 return -1;
 687
 688                         if (array.Rank > 1)
 689                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 690
 691                         if (array.Length == 0)
 692                                 return -1;
 693
 694                         if (!(value is IComparable))
 695                                 throw new ArgumentException (Locale.GetText ("value does not support IComparable."));
 696
 697                         return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, null);
 698                 }
 699
 700                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 701                 public static int BinarySearch (Array array, object value, IComparer comparer)
 702                 {
 703                         if (array == null)
 704                                 throw new ArgumentNullException ("array");
 705
 706                         if (array.Rank > 1)
 707                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 708
 709                         if (array.Length == 0)
 710                                 return -1;
 711
 712                         if ((comparer == null) && (value != null) && !(value is IComparable))
 713                                 throw new ArgumentException (Locale.GetText (
 714                                         "comparer is null and value does not support IComparable."));
 715
 716                         return DoBinarySearch (array, array.GetLowerBound (0), array.GetLength (0), value, comparer);
 717                 }
 718
 719                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 720                 public static int BinarySearch (Array array, int index, int length, object value)
 721                 {
 722                         if (array == null)
 723                                 throw new ArgumentNullException ("array");
 724
 725                         if (array.Rank > 1)
 726                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 727
 728                         if (index < array.GetLowerBound (0))
 729                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 730                                         "index is less than the lower bound of array."));
 731                         if (length < 0)
 732                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 733                                         "Value has to be >= 0."));
 734                         // re-ordered to avoid possible integer overflow
 735                         if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
 736                                 throw new ArgumentException (Locale.GetText (
 737                                         "index and length do not specify a valid range in array."));
 738
 739                         if (array.Length == 0)
 740                                 return -1;
 741
 742                         if ((value != null) && (!(value is IComparable)))
 743                                 throw new ArgumentException (Locale.GetText (
 744                                         "value does not support IComparable"));
 745
 746                         return DoBinarySearch (array, index, length, value, null);
 747                 }
 748
 749                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 750                 public static int BinarySearch (Array array, int index, int length, object value, IComparer comparer)
 751                 {
 752                         if (array == null)
 753                                 throw new ArgumentNullException ("array");
 754
 755                         if (array.Rank > 1)
 756                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 757
 758                         if (index < array.GetLowerBound (0))
 759                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
 760                                         "index is less than the lower bound of array."));
 761                         if (length < 0)
 762                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 763                                         "Value has to be >= 0."));
 764                         // re-ordered to avoid possible integer overflow
 765                         if (index > array.GetLowerBound (0) + array.GetLength (0) - length)
 766                                 throw new ArgumentException (Locale.GetText (
 767                                         "index and length do not specify a valid range in array."));
 768
 769                         if (array.Length == 0)
 770                                 return -1;
 771
 772                         if ((comparer == null) && (value != null) && !(value is IComparable))
 773                                 throw new ArgumentException (Locale.GetText (
 774                                         "comparer is null and value does not support IComparable."));
 775
 776                         return DoBinarySearch (array, index, length, value, comparer);
 777                 }
 778
 779                 static int DoBinarySearch (Array array, int index, int length, object value, IComparer comparer)
 780                 {
 781                         // cache this in case we need it
 782                         if (comparer == null)
 783                                 comparer = Comparer.Default;
 784
 785                         int iMin = index;
 786                         // Comment from Tum (tum@veridicus.com):
 787                         // *Must* start at index + length - 1 to pass rotor test co2460binarysearch_iioi
 788                         int iMax = index + length - 1;
 789                         int iCmp = 0;
 790                         try {
 791                                 while (iMin <= iMax) {
 792                                         // Be careful with overflow
 793                                         // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
 794                                         int iMid = iMin + ((iMax - iMin) / 2);
 795                                         object elt = array.GetValueImpl (iMid);
 796
 797                                         iCmp = comparer.Compare (elt, value);
 798
 799                                         if (iCmp == 0)
 800                                                 return iMid;
 801                                         else if (iCmp > 0)
 802                                                 iMax = iMid - 1;
 803                                         else
 804                                                 iMin = iMid + 1; // compensate for the rounding down
 805                                 }
 806                         }
 807                         catch (Exception e) {
 808                                 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
 809                         }
 810
 811                         return ~iMin;
 812                 }
 813
 814                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
 815                 public static void Clear (Array array, int index, int length)
 816                 {
 817                         if (array == null)
 818                                 throw new ArgumentNullException ("array");
 819                         if (length < 0)
 820                                 throw new ArgumentOutOfRangeException ("length < 0");
 821
 822                         int low = array.GetLowerBound (0);
 823                         if (index < low)
 824                                 throw new IndexOutOfRangeException ("index < lower bound");
 825                         index = index - low;
 826
 827                         // re-ordered to avoid possible integer overflow
 828                         if (index > array.Length - length)
 829                                 throw new IndexOutOfRangeException ("index + length > size");
 830
 831                         ClearInternal (array, index, length);
 832                 }
 833
 834                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 835                 static extern void ClearInternal (Array a, int index, int count);
 836
 837                 [MethodImplAttribute (MethodImplOptions.InternalCall)]
 838                 public extern object Clone ();
 839
 840                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 841                 public static void Copy (Array sourceArray, Array destinationArray, int length)
 842                 {
 843                         // need these checks here because we are going to use
 844                         // GetLowerBound() on source and dest.
 845                         if (sourceArray == null)
 846                                 throw new ArgumentNullException ("sourceArray");
 847
 848                         if (destinationArray == null)
 849                                 throw new ArgumentNullException ("destinationArray");
 850
 851                         Copy (sourceArray, sourceArray.GetLowerBound (0), destinationArray,
 852                                 destinationArray.GetLowerBound (0), length);
 853                 }
 854
 855                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 856                 public static void Copy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
 857                 {
 858                         if (sourceArray == null)
 859                                 throw new ArgumentNullException ("sourceArray");
 860
 861                         if (destinationArray == null)
 862                                 throw new ArgumentNullException ("destinationArray");
 863
 864                         if (length < 0)
 865                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 866                                         "Value has to be >= 0."));;
 867
 868                         if (sourceIndex < 0)
 869                                 throw new ArgumentOutOfRangeException ("sourceIndex", Locale.GetText (
 870                                         "Value has to be >= 0."));;
 871
 872                         if (destinationIndex < 0)
 873                                 throw new ArgumentOutOfRangeException ("destinationIndex", Locale.GetText (
 874                                         "Value has to be >= 0."));;
 875
 876                         if (FastCopy (sourceArray, sourceIndex, destinationArray, destinationIndex, length))
 877                                 return;
 878
 879                         int source_pos = sourceIndex - sourceArray.GetLowerBound (0);
 880                         int dest_pos = destinationIndex - destinationArray.GetLowerBound (0);
 881
 882                         // re-ordered to avoid possible integer overflow
 883                         if (source_pos > sourceArray.Length - length)
 884                                 throw new ArgumentException ("length");
 885
 886                         if (dest_pos > destinationArray.Length - length) {
 887                                 string msg = "Destination array was not long enough. Check " +
 888                                         "destIndex and length, and the array's lower bounds";
 889                                 throw new ArgumentException (msg, string.Empty);
 890                         }
 891
 892                         if (sourceArray.Rank != destinationArray.Rank)
 893                                 throw new RankException (Locale.GetText ("Arrays must be of same size."));
 894
 895                         Type src_type = sourceArray.GetType ().GetElementType ();
 896                         Type dst_type = destinationArray.GetType ().GetElementType ();
 897
 898                         if (!Object.ReferenceEquals (sourceArray, destinationArray) || source_pos > dest_pos) {
 899                                 for (int i = 0; i < length; i++) {
 900                                         Object srcval = sourceArray.GetValueImpl (source_pos + i);
 901
 902                                         try {
 903                                                 destinationArray.SetValueImpl (srcval, dest_pos + i);
 904                                         } catch {
 905                                                 if (src_type.Equals (typeof (Object)))
 906                                                         throw new InvalidCastException ();
 907                                                 else
 908                                                         throw new ArrayTypeMismatchException (String.Format (Locale.GetText (
 909                                                                 "(Types: source={0};  target={1})"), src_type.FullName, dst_type.FullName));
 910                                         }
 911                                 }
 912                         }
 913                         else {
 914                                 for (int i = length - 1; i >= 0; i--) {
 915                                         Object srcval = sourceArray.GetValueImpl (source_pos + i);
 916
 917                                         try {
 918                                                 destinationArray.SetValueImpl (srcval, dest_pos + i);
 919                                         } catch {
 920                                                 if (src_type.Equals (typeof (Object)))
 921                                                         throw new InvalidCastException ();
 922                                                 else
 923                                                         throw new ArrayTypeMismatchException (String.Format (Locale.GetText (
 924                                                                 "(Types: source={0};  target={1})"), src_type.FullName, dst_type.FullName));
 925                                         }
 926                                 }
 927                         }
 928                 }
 929
 930                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 931                 public static void Copy (Array sourceArray, long sourceIndex, Array destinationArray,
 932                                          long destinationIndex, long length)
 933                 {
 934                         if (sourceArray == null)
 935                                 throw new ArgumentNullException ("sourceArray");
 936
 937                         if (destinationArray == null)
 938                                 throw new ArgumentNullException ("destinationArray");
 939
 940                         if (sourceIndex < Int32.MinValue || sourceIndex > Int32.MaxValue)
 941                                 throw new ArgumentOutOfRangeException ("sourceIndex",
 942                                         Locale.GetText ("Must be in the Int32 range."));
 943
 944                         if (destinationIndex < Int32.MinValue || destinationIndex > Int32.MaxValue)
 945                                 throw new ArgumentOutOfRangeException ("destinationIndex",
 946                                         Locale.GetText ("Must be in the Int32 range."));
 947
 948                         if (length < 0 || length > Int32.MaxValue)
 949                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 950                                         "Value must be >= 0 and <= Int32.MaxValue."));
 951
 952                         Copy (sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
 953                 }
 954
 955                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
 956                 public static void Copy (Array sourceArray, Array destinationArray, long length)
 957                 {
 958                         if (length < 0 || length > Int32.MaxValue)
 959                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
 960                                         "Value must be >= 0 and <= Int32.MaxValue."));
 961
 962                         Copy (sourceArray, destinationArray, (int) length);
 963                 }
 964
 965                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 966                 public static int IndexOf (Array array, object value)
 967                 {
 968                         if (array == null)
 969                                 throw new ArgumentNullException ("array");
 970
 971                         return IndexOf (array, value, 0, array.Length);
 972                 }
 973
 974                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 975                 public static int IndexOf (Array array, object value, int startIndex)
 976                 {
 977                         if (array == null)
 978                                 throw new ArgumentNullException ("array");
 979
 980                         return IndexOf (array, value, startIndex, array.Length - startIndex);
 981                 }
 982
 983                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
 984                 public static int IndexOf (Array array, object value, int startIndex, int count)
 985                 {
 986                         if (array == null)
 987                                 throw new ArgumentNullException ("array");
 988
 989                         if (array.Rank > 1)
 990                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
 991
 992                         // re-ordered to avoid possible integer overflow
 993                         if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
 994                                 throw new ArgumentOutOfRangeException ();
 995
 996                         int max = startIndex + count;
 997                         for (int i = startIndex; i < max; i++) {
 998                                 if (Object.Equals (array.GetValueImpl (i), value))
 999                                         return i;
1000                         }
1001
1002                         return array.GetLowerBound (0) - 1;
1003                 }
1004
1005                 public void Initialize()
1006                 {
1007                         //FIXME: We would like to find a compiler that uses
1008                         // this method. It looks like this method do nothing
1009                         // in C# so no exception is trown by the moment.
1010                 }
1011
1012                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1013                 public static int LastIndexOf (Array array, object value)
1014                 {
1015                         if (array == null)
1016                                 throw new ArgumentNullException ("array");
1017
1018                         if (array.Length == 0)
1019                                 return array.GetLowerBound (0) - 1;
1020                         return LastIndexOf (array, value, array.Length - 1);
1021                 }
1022
1023                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1024                 public static int LastIndexOf (Array array, object value, int startIndex)
1025                 {
1026                         if (array == null)
1027                                 throw new ArgumentNullException ("array");
1028
1029                         return LastIndexOf (array, value, startIndex, startIndex - array.GetLowerBound (0) + 1);
1030                 }
1031
1032                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1033                 public static int LastIndexOf (Array array, object value, int startIndex, int count)
1034                 {
1035                         if (array == null)
1036                                 throw new ArgumentNullException ("array");
1037
1038                         if (array.Rank > 1)
1039                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1040
1041                         int lb = array.GetLowerBound (0);
1042                         // Empty arrays do not throw ArgumentOutOfRangeException
1043                         if (array.Length == 0)
1044                                 return lb - 1;
1045
1046                         if (count < 0 || startIndex < lb ||
1047                                 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < lb)
1048                                 throw new ArgumentOutOfRangeException ();
1049
1050                         for (int i = startIndex; i >= startIndex - count + 1; i--) {
1051                                 if (Object.Equals (array.GetValueImpl (i), value))
1052                                         return i;
1053                         }
1054
1055                         return lb - 1;
1056                 }
1057
1058                 /* delegate used to swap array elements */
1059                 delegate void Swapper (int i, int j);
1060
1061                 static Swapper get_swapper (Array array)
1062                 {
1063                         if (array is int[])
1064                                 return new Swapper (array.int_swapper);
1065                         if (array is double[])
1066                                 return new Swapper (array.double_swapper);
1067                         if (array is object[]) {
1068                                 return new Swapper (array.obj_swapper);
1069                         }
1070                         return new Swapper (array.slow_swapper);
1071                 }
1072
1073                 static Swapper get_swapper<T> (T [] array)
1074                 {
1075                         if (array is int[])
1076                                 return new Swapper (array.int_swapper);
1077                         if (array is double[])
1078                                 return new Swapper (array.double_swapper);
1079
1080                         // gmcs refuses to compile this
1081                         //return new Swapper (array.generic_swapper<T>);
1082                         return new Swapper (array.slow_swapper);
1083                 }
1084
1085                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1086                 public static void Reverse (Array array)
1087                 {
1088                         if (array == null)
1089                                 throw new ArgumentNullException ("array");
1090
1091                         Reverse (array, array.GetLowerBound (0), array.GetLength (0));
1092                 }
1093
1094                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1095                 public static void Reverse (Array array, int index, int length)
1096                 {
1097                         if (array == null)
1098                                 throw new ArgumentNullException ("array");
1099
1100                         if (array.Rank > 1)
1101                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1102
1103                         if (index < array.GetLowerBound (0) || length < 0)
1104                                 throw new ArgumentOutOfRangeException ();
1105
1106                         // re-ordered to avoid possible integer overflow
1107                         if (index > array.GetUpperBound (0) + 1 - length)
1108                                 throw new ArgumentException ();
1109
1110                         int end = index + length - 1;
1111                         object[] oarray = array as object[];
1112                         if (oarray != null) {
1113                                 while (index < end) {
1114                                         object tmp = oarray [index];
1115                                         oarray [index] = oarray [end];
1116                                         oarray [end] = tmp;
1117                                         ++index;
1118                                         --end;
1119                                 }
1120                                 return;
1121                         }
1122                         int[] iarray = array as int[];
1123                         if (iarray != null) {
1124                                 while (index < end) {
1125                                         int tmp = iarray [index];
1126                                         iarray [index] = iarray [end];
1127                                         iarray [end] = tmp;
1128                                         ++index;
1129                                         --end;
1130                                 }
1131                                 return;
1132                         }
1133                         double[] darray = array as double[];
1134                         if (darray != null) {
1135                                 while (index < end) {
1136                                         double tmp = darray [index];
1137                                         darray [index] = darray [end];
1138                                         darray [end] = tmp;
1139                                         ++index;
1140                                         --end;
1141                                 }
1142                                 return;
1143                         }
1144                         // fallback
1145                         Swapper swapper = get_swapper (array);
1146                         while (index < end) {
1147                                 swapper (index, end);
1148                                 ++index;
1149                                 --end;
1150                         }
1151                 }
1152
1153                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1154                 public static void Sort (Array array)
1155                 {
1156                         Sort (array, (IComparer)null);
1157                 }
1158
1159                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1160                 public static void Sort (Array keys, Array items)
1161                 {
1162                         Sort (keys, items, (IComparer)null);
1163                 }
1164
1165                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1166                 public static void Sort (Array array, IComparer comparer)
1167                 {
1168                         if (array == null)
1169                                 throw new ArgumentNullException ("array");
1170
1171                         if (array.Rank > 1)
1172                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1173
1174                         SortImpl (array, null, array.GetLowerBound (0), array.GetLength (0), comparer);
1175                 }
1176
1177                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1178                 public static void Sort (Array array, int index, int length)
1179                 {
1180                         Sort (array, index, length, (IComparer)null);
1181                 }
1182
1183                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1184                 public static void Sort (Array keys, Array items, IComparer comparer)
1185                 {
1186                         if (items == null) {
1187                                 Sort (keys, comparer);
1188                                 return;
1189                         }
1190
1191                         if (keys == null)
1192                                 throw new ArgumentNullException ("keys");
1193
1194                         if (keys.Rank > 1 || items.Rank > 1)
1195                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1196
1197                         SortImpl (keys, items, keys.GetLowerBound (0), keys.GetLength (0), comparer);
1198                 }
1199
1200                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1201                 public static void Sort (Array keys, Array items, int index, int length)
1202                 {
1203                         Sort (keys, items, index, length, (IComparer)null);
1204                 }
1205
1206                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1207                 public static void Sort (Array array, int index, int length, IComparer comparer)
1208                 {
1209                         if (array == null)
1210                                 throw new ArgumentNullException ("array");
1211
1212                         if (array.Rank > 1)
1213                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1214
1215                         if (index < array.GetLowerBound (0))
1216                                 throw new ArgumentOutOfRangeException ("index");
1217
1218                         if (length < 0)
1219                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1220                                         "Value has to be >= 0."));
1221
1222                         if (array.Length - (array.GetLowerBound (0) + index) < length)
1223                                 throw new ArgumentException ();
1224
1225                         SortImpl (array, null, index, length, comparer);
1226                 }
1227
1228                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1229                 public static void Sort (Array keys, Array items, int index, int length, IComparer comparer)
1230                 {
1231                         if (items == null) {
1232                                 Sort (keys, index, length, comparer);
1233                                 return;
1234                         }
1235
1236                         if (keys == null)
1237                                 throw new ArgumentNullException ("keys");
1238
1239                         if (keys.Rank > 1 || items.Rank > 1)
1240                                 throw new RankException ();
1241
1242                         if (keys.GetLowerBound (0) != items.GetLowerBound (0))
1243                                 throw new ArgumentException ();
1244
1245                         if (index < keys.GetLowerBound (0))
1246                                 throw new ArgumentOutOfRangeException ("index");
1247
1248                         if (length < 0)
1249                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1250                                         "Value has to be >= 0."));
1251
1252                         if (keys.Length != items.Length || keys.Length - (index + keys.GetLowerBound (0)) < length)
1253                                 throw new ArgumentException ();
1254
1255                         SortImpl (keys, items, index, length, comparer);
1256                 }
1257
1258                 private static void SortImpl (Array keys, Array items, int index, int length, IComparer comparer)
1259                 {
1260                         if (length <= 1)
1261                                 return;
1262
1263                         if (comparer == null) {
1264                                 Swapper iswapper = (items != null ? get_swapper (items) : null);
1265                                 if (keys is double[]) {
1266                                         combsort (keys as double[], index, length, iswapper);
1267                                         return;
1268                                 }
1269                                 if (keys is int[]) {
1270                                         combsort (keys as int[], index, length, iswapper);
1271                                         return;
1272                                 }
1273                                 if (keys is char[]) {
1274                                         combsort (keys as char[], index, length, iswapper);
1275                                         return;
1276                                 }
1277                         }
1278
1279                         int low = index;
1280                         int high = index + length - 1;
1281                         low = MoveNullKeysToFront (keys, items, low, high, comparer == null);
1282                         if (low == high)
1283                                 return;
1284
1285                         try {
1286                                 qsort (keys, items, low, high, comparer);
1287                         } catch (Exception e) {
1288                                 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1289                         }
1290                 }
1291
1292                 /* note, these are instance methods */
1293                 void int_swapper (int i, int j) {
1294                         int[] array = this as int[];
1295                         int val = array [i];
1296                         array [i] = array [j];
1297                         array [j] = val;
1298                 }
1299
1300                 void obj_swapper (int i, int j) {
1301                         object[] array = this as object[];
1302                         object val = array [i];
1303                         array [i] = array [j];
1304                         array [j] = val;
1305                 }
1306
1307                 void slow_swapper (int i, int j) {
1308                         object val = GetValueImpl (i);
1309                         SetValueImpl (GetValue (j), i);
1310                         SetValueImpl (val, j);
1311                 }
1312
1313                 void double_swapper (int i, int j) {
1314                         double[] array = this as double[];
1315                         double val = array [i];
1316                         array [i] = array [j];
1317                         array [j] = val;
1318                 }
1319
1320                 static int new_gap (int gap)
1321                 {
1322                         gap = (gap * 10) / 13;
1323                         if (gap == 9 || gap == 10)
1324                                 return 11;
1325                         if (gap < 1)
1326                                 return 1;
1327                         return gap;
1328                 }
1329
1330                 /* we use combsort because it's fast enough and very small, since we have
1331                  * several specialized versions here.
1332                  */
1333                 static void combsort (double[] array, int start, int size, Swapper swap_items)
1334                 {
1335                         int gap = size;
1336                         while (true) {
1337                                 gap = new_gap (gap);
1338                                 bool swapped = false;
1339                                 int end = start + size - gap;
1340                                 for (int i = start; i < end; i++) {
1341                                         int j = i + gap;
1342                                         if (array [i] > array [j]) {
1343                                                 double val = array [i];
1344                                                 array [i] = array [j];
1345                                                 array [j] = val;
1346                                                 swapped = true;
1347                                                 if (swap_items != null)
1348                                                         swap_items (i, j);
1349                                         }
1350                                 }
1351                                 if (gap == 1 && !swapped)
1352                                         break;
1353                         }
1354                 }
1355
1356                 static void combsort (int[] array, int start, int size, Swapper swap_items)
1357                 {
1358                         int gap = size;
1359                         while (true) {
1360                                 gap = new_gap (gap);
1361                                 bool swapped = false;
1362                                 int end = start + size - gap;
1363                                 for (int i = start; i < end; i++) {
1364                                         int j = i + gap;
1365                                         if (array [i] > array [j]) {
1366                                                 int val = array [i];
1367                                                 array [i] = array [j];
1368                                                 array [j] = val;
1369                                                 swapped = true;
1370                                                 if (swap_items != null)
1371                                                         swap_items (i, j);
1372                                         }
1373                                 }
1374                                 if (gap == 1 && !swapped)
1375                                         break;
1376                         }
1377                 }
1378
1379                 static void combsort (char[] array, int start, int size, Swapper swap_items)
1380                 {
1381                         int gap = size;
1382                         while (true) {
1383                                 gap = new_gap (gap);
1384                                 bool swapped = false;
1385                                 int end = start + size - gap;
1386                                 for (int i = start; i < end; i++) {
1387                                         int j = i + gap;
1388                                         if (array [i] > array [j]) {
1389                                                 char val = array [i];
1390                                                 array [i] = array [j];
1391                                                 array [j] = val;
1392                                                 swapped = true;
1393                                                 if (swap_items != null)
1394                                                         swap_items (i, j);
1395                                         }
1396                                 }
1397                                 if (gap == 1 && !swapped)
1398                                         break;
1399                         }
1400                 }
1401
1402                 private static void qsort (Array keys, Array items, int low0, int high0, IComparer comparer)
1403                 {
1404                         int low = low0;
1405                         int high = high0;
1406
1407                         // Be careful with overflows
1408                         int mid = low + ((high - low) / 2);
1409                         object keyPivot = keys.GetValueImpl (mid);
1410                         IComparable cmpPivot = keyPivot as IComparable;
1411
1412                         while (true) {
1413                                 // Move the walls in
1414                                 if (comparer != null) {
1415                                         while (low < high0 && comparer.Compare (keyPivot, keys.GetValueImpl (low)) > 0)
1416                                                 ++low;
1417                                         while (high > low0 && comparer.Compare (keyPivot, keys.GetValueImpl (high)) < 0)
1418                                                 --high;
1419                                 } else {
1420                                         while (low < high0 && cmpPivot.CompareTo (keys.GetValueImpl (low)) > 0)
1421                                                 ++low;
1422                                         while (high > low0 && cmpPivot.CompareTo (keys.GetValueImpl (high)) < 0)
1423                                                 --high;
1424                                 }
1425
1426                                 if (low <= high) {
1427                                         swap (keys, items, low, high);
1428                                         ++low;
1429                                         --high;
1430                                 } else
1431                                         break;
1432                         }
1433
1434                         if (low0 < high)
1435                                 qsort (keys, items, low0, high, comparer);
1436                         if (low < high0)
1437                                 qsort (keys, items, low, high0, comparer);
1438                 }
1439
1440                 private static int MoveNullKeysToFront (Array keys, Array items, int low, int high, bool ensureComparable)
1441                 {
1442                         // find first nun-null key
1443                         while (low < high && keys.GetValueImpl (low) == null)
1444                                 low++;
1445
1446                         // move null keys to beginning of array,
1447                         // ensure that non-null keys implement IComparable
1448                         for (int i = low + 1; i <= high; i++) {
1449                                 object obj = keys.GetValueImpl (i);
1450                                 if (obj == null) {
1451                                         swap (keys, items, low, i);
1452                                         low++;
1453                                 } else {
1454                                         if (ensureComparable && !(obj is IComparable)) {
1455                                                 string msg = Locale.GetText ("No IComparable interface found for type '{0}'.");
1456                                                 throw new InvalidOperationException (String.Format (msg, obj.GetType ()));
1457                                         }
1458                                 }
1459                         }
1460                         return low;
1461                 }
1462
1463                 private static void swap (Array keys, Array items, int i, int j)
1464                 {
1465                         object tmp = keys.GetValueImpl (i);
1466                         keys.SetValueImpl (keys.GetValueImpl (j), i);
1467                         keys.SetValueImpl (tmp, j);
1468
1469                         if (items != null) {
1470                                 tmp = items.GetValueImpl (i);
1471                                 items.SetValueImpl (items.GetValueImpl (j), i);
1472                                 items.SetValueImpl (tmp, j);
1473                         }
1474                 }
1475
1476                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1477                 public static void Sort<T> (T [] array)
1478                 {
1479                         Sort<T> (array, (IComparer<T>)null);
1480                 }
1481
1482                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1483                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items)
1484                 {
1485                         Sort<TKey, TValue> (keys, items, (IComparer<TKey>)null);
1486                 }
1487
1488                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1489                 public static void Sort<T> (T [] array, IComparer<T> comparer)
1490                 {
1491                         if (array == null)
1492                                 throw new ArgumentNullException ("array");
1493
1494                         SortImpl<T, T> (array, null, 0, array.Length, comparer);
1495                 }
1496
1497                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1498                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, IComparer<TKey> comparer)
1499                 {
1500                         if (items == null) {
1501                                 Sort<TKey> (keys, comparer);
1502                                 return;
1503                         }
1504
1505                         if (keys == null)
1506                                 throw new ArgumentNullException ("keys");
1507
1508                         if (keys.Length != items.Length)
1509                                 throw new ArgumentException ("Length of keys and items does not match.");
1510
1511                         SortImpl<TKey, TValue> (keys, items, 0, keys.Length, comparer);
1512                 }
1513
1514                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1515                 public static void Sort<T> (T [] array, int index, int length)
1516                 {
1517                         Sort<T> (array, index, length, (IComparer<T>)null);
1518                 }
1519
1520                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1521                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length)
1522                 {
1523                         Sort<TKey, TValue> (keys, items, index, length, (IComparer<TKey>)null);
1524                 }
1525
1526                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1527                 public static void Sort<T> (T [] array, int index, int length, IComparer<T> comparer)
1528                 {
1529                         if (array == null)
1530                                 throw new ArgumentNullException ("array");
1531
1532                         if (index < 0)
1533                                 throw new ArgumentOutOfRangeException ("index");
1534
1535                         if (length < 0)
1536                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
1537                                         "Value has to be >= 0."));
1538
1539                         if (index + length > array.Length)
1540                                 throw new ArgumentException ();
1541
1542                         SortImpl<T, T> (array, null, index, length, comparer);
1543                 }
1544
1545                 [ReliabilityContractAttribute (Consistency.MayCorruptInstance, Cer.MayFail)]
1546                 public static void Sort<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1547                 {
1548                         if (items == null) {
1549                                 Sort<TKey> (keys, index, length, comparer);
1550                                 return;
1551                         }
1552
1553                         if (keys == null)
1554                                 throw new ArgumentNullException ("keys");
1555
1556                         if (index < 0)
1557                                 throw new ArgumentOutOfRangeException ("index");
1558
1559                         if (length < 0)
1560                                 throw new ArgumentOutOfRangeException ("length");
1561
1562                         if (keys.Length != items.Length || keys.Length - index < length)
1563                                 throw new ArgumentException ();
1564
1565                         SortImpl<TKey, TValue> (keys, items, index, length, comparer);
1566                 }
1567
1568                 private static void SortImpl<TKey, TValue> (TKey [] keys, TValue [] items, int index, int length, IComparer<TKey> comparer)
1569                 {
1570                         if (keys.Length <= 1)
1571                                 return;
1572
1573                         //
1574                         // Check for value types which can be sorted without Compare () method
1575                         //
1576                         if (comparer == null) {
1577                                 Swapper iswapper = (items != null ? get_swapper<TValue> (items) : null);
1578                                 if (keys is double[]) {
1579                                         combsort (keys as double[], index, length, iswapper);
1580                                         return;
1581                                 }
1582                                 if (keys is int[]) {
1583                                         combsort (keys as int[], index, length, iswapper);
1584                                         return;
1585                                 }
1586                                 if (keys is char[]) {
1587                                         combsort (keys as char[], index, length, iswapper);
1588                                         return;
1589                                 }
1590
1591                                 // Use Comparer<T>.Default instead
1592                                 // comparer = Comparer<K>.Default;
1593                         }
1594
1595                         int low = index;
1596                         int high = index + length - 1;
1597                         low = MoveNullKeysToFront<TKey, TValue> (keys, items, low, high, comparer == null);
1598                         if (low == high)
1599                                 return;
1600
1601                         try {
1602                                 qsort<TKey, TValue> (keys, items, low, high, comparer);
1603                         } catch (Exception e) {
1604                                 throw new InvalidOperationException (Locale.GetText ("The comparer threw an exception."), e);
1605                         }
1606                 }
1607
1608                 public static void Sort<T> (T [] array, Comparison<T> comparison)
1609                 {
1610                         if (array == null)
1611                                 throw new ArgumentNullException ("array");
1612
1613                         if (comparison == null)
1614                                 throw new ArgumentNullException ("comparison");
1615
1616                         SortImpl<T> (array, array.Length, comparison);
1617                 }
1618
1619                 // used by List<T>.Sort (Comparison <T>)
1620                 internal static void SortImpl<T> (T [] array, int length, Comparison<T> comparison)
1621                 {
1622                         if (length <= 1)
1623                                 return;
1624
1625                         try {
1626                                 int low0 = 0;
1627                                 int high0 = length - 1;
1628                                 qsort<T> (array, low0, high0, comparison);
1629                         } catch (InvalidOperationException) {
1630                                 throw;
1631                         } catch (Exception e) {
1632                                 throw new InvalidOperationException (Locale.GetText ("Comparison threw an exception."), e);
1633                         }
1634                 }
1635
1636                 private static void qsort<K, V> (K [] keys, V [] items, int low0, int high0, IComparer<K> comparer)
1637                 {
1638                         int low = low0;
1639                         int high = high0;
1640
1641                         // Be careful with overflows
1642                         int mid = low + ((high - low) / 2);
1643                         K keyPivot = keys [mid];
1644                         IComparable<K> genCmpPivot = keyPivot as IComparable<K>;
1645                         IComparable cmpPivot = keyPivot as IComparable;
1646
1647                         while (true) {
1648                                 // Move the walls in
1649                                 if (comparer != null) {
1650                                         while (low < high0 && comparer.Compare (keyPivot, keys [low]) > 0)
1651                                                 ++low;
1652                                         while (high > low0 && comparer.Compare (keyPivot, keys [high]) < 0)
1653                                                 --high;
1654                                 } else {
1655                                         if (genCmpPivot != null) {
1656                                                 while (low < high0 && genCmpPivot.CompareTo (keys [low]) > 0)
1657                                                         ++low;
1658                                                 while (high > low0 && genCmpPivot.CompareTo (keys [high]) < 0)
1659                                                         --high;
1660                                         } else {
1661                                                 while (low < high0 && cmpPivot.CompareTo (keys [low]) > 0)
1662                                                         ++low;
1663                                                 while (high > low0 && cmpPivot.CompareTo (keys [high]) < 0)
1664                                                         --high;
1665                                         }
1666                                 }
1667
1668                                 if (low <= high) {
1669                                         swap<K, V> (keys, items, low, high);
1670                                         ++low;
1671                                         --high;
1672                                 } else
1673                                         break;
1674                         }
1675
1676                         if (low0 < high)
1677                                 qsort<K, V> (keys, items, low0, high, comparer);
1678                         if (low < high0)
1679                                 qsort<K, V> (keys, items, low, high0, comparer);
1680                 }
1681
1682                 private static void qsort<T> (T [] array, int low0, int high0, Comparison<T> comparison)
1683                 {
1684                         int low = low0;
1685                         int high = high0;
1686
1687                         // Be careful with overflows
1688                         int mid = low + ((high - low) / 2);
1689                         T keyPivot = array [mid];
1690
1691                         while (true) {
1692                                 // Move the walls in
1693                                 while (low < high0 && comparison (array [low], keyPivot) < 0)
1694                                         ++low;
1695                                 while (high > low0 && comparison (keyPivot, array [high]) < 0)
1696                                         --high;
1697
1698                                 if (low <= high) {
1699                                         swap<T> (array, low, high);
1700                                         ++low;
1701                                         --high;
1702                                 } else
1703                                         break;
1704                         }
1705
1706                         if (low0 < high)
1707                                 qsort<T> (array, low0, high, comparison);
1708                         if (low < high0)
1709                                 qsort<T> (array, low, high0, comparison);
1710                 }
1711
1712                 private static int MoveNullKeysToFront<K, V> (K [] keys, V [] items, int low, int high, bool ensureComparable)
1713                 {
1714                         // find first nun-null key
1715                         while (low < high && keys [low] == null)
1716                                 low++;
1717
1718                         // move null keys to beginning of array,
1719                         // ensure that non-null keys implement IComparable
1720                         for (int i = low + 1; i <= high; i++) {
1721                                 K key = keys [i];
1722                                 if (key == null) {
1723                                         swap<K, V> (keys, items, low, i);
1724                                         low++;
1725                                 } else {
1726                                         if (ensureComparable && !(key is IComparable<K>) && !(key is IComparable)) {
1727                                                 string msg = Locale.GetText ("No IComparable<T> or IComparable interface found for type '{0}'.");
1728                                                 throw new InvalidOperationException (String.Format (msg, key.GetType ()));
1729                                         }
1730                                 }
1731                         }
1732                         return low;
1733                 }
1734
1735                 private static void swap<K, V> (K [] keys, V [] items, int i, int j)
1736                 {
1737                         K tmp;
1738
1739                         tmp = keys [i];
1740                         keys [i] = keys [j];
1741                         keys [j] = tmp;
1742
1743                         if (items != null) {
1744                                 V itmp;
1745                                 itmp = items [i];
1746                                 items [i] = items [j];
1747                                 items [j] = itmp;
1748                         }
1749                 }
1750
1751                 private static void swap<T> (T [] array, int i, int j)
1752                 {
1753                         T tmp = array [i];
1754                         array [i] = array [j];
1755                         array [j] = tmp;
1756                 }
1757
1758                 public void CopyTo (Array array, int index)
1759                 {
1760                         if (array == null)
1761                                 throw new ArgumentNullException ("array");
1762
1763                         // The order of these exception checks may look strange,
1764                         // but that's how the microsoft runtime does it.
1765                         if (this.Rank > 1)
1766                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1767                         if (index + this.GetLength (0) > array.GetLowerBound (0) + array.GetLength (0))
1768                                 throw new ArgumentException ("Destination array was not long " +
1769                                         "enough. Check destIndex and length, and the array's " +
1770                                         "lower bounds.");
1771                         if (array.Rank > 1)
1772                                 throw new RankException (Locale.GetText ("Only single dimension arrays are supported."));
1773                         if (index < 0)
1774                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
1775                                         "Value has to be >= 0."));
1776
1777                         Copy (this, this.GetLowerBound (0), array, index, this.GetLength (0));
1778                 }
1779
1780                 [ComVisible (false)]
1781                 public void CopyTo (Array array, long index)
1782                 {
1783                         if (index < 0 || index > Int32.MaxValue)
1784                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
1785                                         "Value must be >= 0 and <= Int32.MaxValue."));
1786
1787                         CopyTo (array, (int) index);
1788                 }
1789
1790                 internal class SimpleEnumerator : IEnumerator, ICloneable
1791                 {
1792                         Array enumeratee;
1793                         int currentpos;
1794                         int length;
1795
1796                         public SimpleEnumerator (Array arrayToEnumerate)
1797                         {
1798                                 this.enumeratee = arrayToEnumerate;
1799                                 this.currentpos = -1;
1800                                 this.length = arrayToEnumerate.Length;
1801                         }
1802
1803                         public object Current {
1804                                 get {
1805                                         // Exception messages based on MS implementation
1806                                         if (currentpos < 0 )
1807                                                 throw new InvalidOperationException (Locale.GetText (
1808                                                         "Enumeration has not started."));
1809                                         if  (currentpos >= length)
1810                                                 throw new InvalidOperationException (Locale.GetText (
1811                                                         "Enumeration has already ended"));
1812                                         // Current should not increase the position. So no ++ over here.
1813                                         return enumeratee.GetValueImpl (currentpos);
1814                                 }
1815                         }
1816
1817                         public bool MoveNext()
1818                         {
1819                                 //The docs say Current should throw an exception if last
1820                                 //call to MoveNext returned false. This means currentpos
1821                                 //should be set to length when returning false.
1822                                 if (currentpos < length)
1823                                         currentpos++;
1824                                 if(currentpos < length)
1825                                         return true;
1826                                 else
1827                                         return false;
1828                         }
1829
1830                         public void Reset()
1831                         {
1832                                 currentpos = -1;
1833                         }
1834
1835                         public object Clone ()
1836                         {
1837                                 return MemberwiseClone ();
1838                         }
1839                 }
1840
1841                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1842                 public static void Resize<T> (ref T [] array, int newSize)
1843                 {
1844                         Resize<T> (ref array, array == null ? 0 : array.Length, newSize);
1845                 }
1846
1847                 internal static void Resize<T> (ref T[] array, int length, int newSize)
1848                 {
1849                         if (newSize < 0)
1850                                 throw new ArgumentOutOfRangeException ();
1851
1852                         if (array == null) {
1853                                 array = new T [newSize];
1854                                 return;
1855                         }
1856
1857                         if (array.Length == newSize)
1858                                 return;
1859
1860                         T [] a = new T [newSize];
1861                         Array.Copy (array, a, Math.Min (newSize, length));
1862                         array = a;
1863                 }
1864
1865                 public static bool TrueForAll <T> (T [] array, Predicate <T> match)
1866                 {
1867                         if (array == null)
1868                                 throw new ArgumentNullException ("array");
1869                         if (match == null)
1870                                 throw new ArgumentNullException ("match");
1871
1872                         foreach (T t in array)
1873                                 if (! match (t))
1874                                         return false;
1875
1876                         return true;
1877                 }
1878
1879                 public static void ForEach<T> (T [] array, Action <T> action)
1880                 {
1881                         if (array == null)
1882                                 throw new ArgumentNullException ("array");
1883                         if (action == null)
1884                                 throw new ArgumentNullException ("action");
1885
1886                         foreach (T t in array)
1887                                 action (t);
1888                 }
1889
1890                 public static TOutput[] ConvertAll<TInput, TOutput> (TInput [] array, Converter<TInput, TOutput> converter)
1891                 {
1892                         if (array == null)
1893                                 throw new ArgumentNullException ("array");
1894                         if (converter == null)
1895                                 throw new ArgumentNullException ("converter");
1896
1897                         TOutput [] output = new TOutput [array.Length];
1898                         for (int i = 0; i < array.Length; i ++)
1899                                 output [i] = converter (array [i]);
1900
1901                         return output;
1902                 }
1903
1904                 public static int FindLastIndex<T> (T [] array, Predicate <T> match)
1905                 {
1906                         if (array == null)
1907                                 throw new ArgumentNullException ("array");
1908
1909                         return FindLastIndex<T> (array, 0, array.Length, match);
1910                 }
1911
1912                 public static int FindLastIndex<T> (T [] array, int startIndex, Predicate<T> match)
1913                 {
1914                         if (array == null)
1915                                 throw new ArgumentNullException ();
1916
1917                         return FindLastIndex<T> (array, startIndex, array.Length - startIndex, match);
1918                 }
1919
1920                 public static int FindLastIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
1921                 {
1922                         if (array == null)
1923                                 throw new ArgumentNullException ("array");
1924                         if (match == null)
1925                                 throw new ArgumentNullException ("match");
1926
1927                         if (startIndex > array.Length || startIndex + count > array.Length)
1928                                 throw new ArgumentOutOfRangeException ();
1929
1930                         for (int i = startIndex + count - 1; i >= startIndex; i--)
1931                                 if (match (array [i]))
1932                                         return i;
1933
1934                         return -1;
1935                 }
1936
1937                 public static int FindIndex<T> (T [] array, Predicate<T> match)
1938                 {
1939                         if (array == null)
1940                                 throw new ArgumentNullException ("array");
1941
1942                         return FindIndex<T> (array, 0, array.Length, match);
1943                 }
1944
1945                 public static int FindIndex<T> (T [] array, int startIndex, Predicate<T> match)
1946                 {
1947                         if (array == null)
1948                                 throw new ArgumentNullException ("array");
1949
1950                         return FindIndex<T> (array, startIndex, array.Length - startIndex, match);
1951                 }
1952
1953                 public static int FindIndex<T> (T [] array, int startIndex, int count, Predicate<T> match)
1954                 {
1955                         if (array == null)
1956                                 throw new ArgumentNullException ("array");
1957
1958                         if (match == null)
1959                                 throw new ArgumentNullException ("match");
1960
1961                         if (startIndex > array.Length || startIndex + count > array.Length)
1962                                 throw new ArgumentOutOfRangeException ();
1963
1964                         for (int i = startIndex; i < startIndex + count; i ++)
1965                                 if (match (array [i]))
1966                                         return i;
1967
1968                         return -1;
1969                 }
1970
1971                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1972                 public static int BinarySearch<T> (T [] array, T value)
1973                 {
1974                         if (array == null)
1975                                 throw new ArgumentNullException ("array");
1976
1977                         return BinarySearch<T> (array, 0, array.Length, value, null);
1978                 }
1979
1980                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1981                 public static int BinarySearch<T> (T [] array, T value, IComparer<T> comparer)
1982                 {
1983                         if (array == null)
1984                                 throw new ArgumentNullException ("array");
1985
1986                         return BinarySearch<T> (array, 0, array.Length, value, comparer);
1987                 }
1988
1989                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1990                 public static int BinarySearch<T> (T [] array, int index, int length, T value)
1991                 {
1992                         return BinarySearch<T> (array, index, length, value, null);
1993                 }
1994
1995                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.MayFail)]
1996                 public static int BinarySearch<T> (T [] array, int index, int length, T value, IComparer<T> comparer)
1997                 {
1998                         if (array == null)
1999                                 throw new ArgumentNullException ("array");
2000                         if (index < 0)
2001                                 throw new ArgumentOutOfRangeException ("index", Locale.GetText (
2002                                         "index is less than the lower bound of array."));
2003                         if (length < 0)
2004                                 throw new ArgumentOutOfRangeException ("length", Locale.GetText (
2005                                         "Value has to be >= 0."));
2006                         // re-ordered to avoid possible integer overflow
2007                         if (index > array.Length - length)
2008                                 throw new ArgumentException (Locale.GetText (
2009                                         "index and length do not specify a valid range in array."));
2010                         if (comparer == null)
2011                                 comparer = Comparer <T>.Default;
2012
2013                         int iMin = index;
2014                         int iMax = index + length - 1;
2015                         int iCmp = 0;
2016                         try {
2017                                 while (iMin <= iMax) {
2018                                         // Be careful with overflows
2019                                         int iMid = iMin + ((iMax - iMin) / 2);
2020                                         iCmp = comparer.Compare (value, array [iMid]);
2021
2022                                         if (iCmp == 0)
2023                                                 return iMid;
2024                                         else if (iCmp < 0)
2025                                                 iMax = iMid - 1;
2026                                         else
2027                                                 iMin = iMid + 1; // compensate for the rounding down
2028                                 }
2029                         } catch (Exception e) {
2030                                 throw new InvalidOperationException (Locale.GetText ("Comparer threw an exception."), e);
2031                         }
2032
2033                         return ~iMin;
2034                 }
2035
2036                 public static int IndexOf<T> (T [] array, T value)
2037                 {
2038                         if (array == null)
2039                                 throw new ArgumentNullException ("array");
2040
2041                         return IndexOf<T> (array, value, 0, array.Length);
2042                 }
2043
2044                 public static int IndexOf<T> (T [] array, T value, int startIndex)
2045                 {
2046                         if (array == null)
2047                                 throw new ArgumentNullException ("array");
2048
2049                         return IndexOf<T> (array, value, startIndex, array.Length - startIndex);
2050                 }
2051
2052                 public static int IndexOf<T> (T [] array, T value, int startIndex, int count)
2053                 {
2054                         if (array == null)
2055                                 throw new ArgumentNullException ("array");
2056
2057                         // re-ordered to avoid possible integer overflow
2058                         if (count < 0 || startIndex < array.GetLowerBound (0) || startIndex - 1 > array.GetUpperBound (0) - count)
2059                                 throw new ArgumentOutOfRangeException ();
2060
2061                         int max = startIndex + count;
2062                         EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
2063                         for (int i = startIndex; i < max; i++) {
2064                                 if (equalityComparer.Equals (array [i], value))
2065                                         return i;
2066                         }
2067
2068                         return -1;
2069                 }
2070
2071                 public static int LastIndexOf<T> (T [] array, T value)
2072                 {
2073                         if (array == null)
2074                                 throw new ArgumentNullException ("array");
2075
2076                         if (array.Length == 0)
2077                                 return -1;
2078                         return LastIndexOf<T> (array, value, array.Length - 1);
2079                 }
2080
2081                 public static int LastIndexOf<T> (T [] array, T value, int startIndex)
2082                 {
2083                         if (array == null)
2084                                 throw new ArgumentNullException ("array");
2085
2086                         return LastIndexOf<T> (array, value, startIndex, startIndex + 1);
2087                 }
2088
2089                 public static int LastIndexOf<T> (T [] array, T value, int startIndex, int count)
2090                 {
2091                         if (array == null)
2092                                 throw new ArgumentNullException ("array");
2093
2094                         if (count < 0 || startIndex < array.GetLowerBound (0) ||
2095                                 startIndex > array.GetUpperBound (0) || startIndex - count + 1 < array.GetLowerBound (0))
2096                                 throw new ArgumentOutOfRangeException ();
2097
2098                         EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
2099                         for (int i = startIndex; i >= startIndex - count + 1; i--) {
2100                                 if (equalityComparer.Equals (array [i], value))
2101                                         return i;
2102                         }
2103
2104                         return -1;
2105                 }
2106
2107                 public static T [] FindAll<T> (T [] array, Predicate <T> match)
2108                 {
2109                         if (array == null)
2110                                 throw new ArgumentNullException ("array");
2111
2112                         if (match == null)
2113                                 throw new ArgumentNullException ("match");
2114
2115                         int pos = 0;
2116                         T [] d = new T [array.Length];
2117                         foreach (T t in array)
2118                                 if (match (t))
2119                                         d [pos++] = t;
2120
2121                         Resize <T> (ref d, pos);
2122                         return d;
2123                 }
2124
2125                 public static bool Exists<T> (T [] array, Predicate <T> match)
2126                 {
2127                         if (array == null)
2128                                 throw new ArgumentNullException ("array");
2129
2130                         if (match == null)
2131                                 throw new ArgumentNullException ("match");
2132
2133                         foreach (T t in array)
2134                                 if (match (t))
2135                                         return true;
2136                         return false;
2137                 }
2138
2139                 public static ReadOnlyCollection<T> AsReadOnly<T> (T[] array)
2140                 {
2141                         if (array == null)
2142                                 throw new ArgumentNullException ("array");
2143                         return new ReadOnlyCollection<T> (new ArrayReadOnlyList<T> (array));
2144                 }
2145
2146                 public static T Find<T> (T [] array, Predicate<T> match)
2147                 {
2148                         if (array == null)
2149                                 throw new ArgumentNullException ("array");
2150
2151                         if (match == null)
2152                                 throw new ArgumentNullException ("match");
2153
2154                         foreach (T t in array)
2155                                 if (match (t))
2156                                         return t;
2157
2158                         return default (T);
2159                 }
2160
2161                 public static T FindLast<T> (T [] array, Predicate <T> match)
2162                 {
2163                         if (array == null)
2164                                 throw new ArgumentNullException ("array");
2165
2166                         if (match == null)
2167                                 throw new ArgumentNullException ("match");
2168
2169                         for (int i = array.Length - 1; i >= 0; i--)
2170                                 if (match (array [i]))
2171                                         return array [i];
2172
2173                         return default (T);
2174                 }
2175
2176                 [ReliabilityContractAttribute (Consistency.WillNotCorruptState, Cer.Success)]
2177                 //
2178                 // The constrained copy should guarantee that if there is an exception thrown
2179                 // during the copy, the destination array remains unchanged.
2180                 // This is related to System.Runtime.Reliability.CER
2181                 public static void ConstrainedCopy (Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
2182                 {
2183                         Copy (sourceArray, sourceIndex, destinationArray, destinationIndex, length);
2184                 }
2185
2186                 class ArrayReadOnlyList<T> : IList<T>
2187                 {
2188                         T [] array;
2189
2190                         public ArrayReadOnlyList (T [] array)
2191                         {
2192                                 this.array = array;
2193                         }
2194
2195                         public T this [int index] {
2196                                 get {
2197                                         if (unchecked ((uint) index) >= unchecked ((uint) array.Length))
2198                                                 throw new ArgumentOutOfRangeException ("index");
2199                                         return array [index];
2200                                 }
2201                                 set { throw ReadOnlyError (); }
2202                         }
2203
2204                         public int Count {
2205                                 get { return array.Length; }
2206                         }
2207
2208                         public bool IsReadOnly {
2209                                 get { return true; }
2210                         }
2211
2212                         public void Add (T item)
2213                         {
2214                                 throw ReadOnlyError ();
2215                         }
2216
2217                         public void Clear ()
2218                         {
2219                                 throw ReadOnlyError ();
2220                         }
2221
2222                         public bool Contains (T item)
2223                         {
2224                                 return Array.IndexOf<T> (array, item) >= 0;
2225                         }
2226
2227                         public void CopyTo (T [] array, int index)
2228                         {
2229                                 array.CopyTo (array, index);
2230                         }
2231
2232                         IEnumerator IEnumerable.GetEnumerator ()
2233                         {
2234                                 return GetEnumerator ();
2235                         }
2236
2237                         public IEnumerator<T> GetEnumerator ()
2238                         {
2239                                 for (int i = 0; i < array.Length; i++)
2240                                         yield return array [i];
2241                         }
2242
2243                         public int IndexOf (T item)
2244                         {
2245                                 return Array.IndexOf<T> (array, item);
2246                         }
2247
2248                         public void Insert (int index, T item)
2249                         {
2250                                 throw ReadOnlyError ();
2251                         }
2252
2253                         public bool Remove (T item)
2254                         {
2255                                 throw ReadOnlyError ();
2256                         }
2257
2258                         public void RemoveAt (int index)
2259                         {
2260                                 throw ReadOnlyError ();
2261                         }
2262
2263                         static Exception ReadOnlyError ()
2264                         {
2265                                 return new NotSupportedException ("This collection is read-only.");
2266                         }
2267                 }
2268         }
2269 }