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