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