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