src/mscorlib/src/System/Array.cs

   1 // Licensed to the .NET Foundation under one or more agreements.
   2 // The .NET Foundation licenses this file to you under the MIT license.
   3 // See the LICENSE file in the project root for more information.
   4
   5 /*============================================================
   6 **
   7 **
   8 ** Purpose: Base class which can be used to access any array
   9 **
  10 ===========================================================*/
  11 namespace System {
  12
  13     using System;
  14     using System.Collections;
  15     using System.Collections.Generic;
  16     using System.Collections.ObjectModel;
  17     using System.Runtime.InteropServices;
  18     using System.Runtime.CompilerServices;
  19     using System.Runtime.ConstrainedExecution;
  20     using System.Runtime.Versioning;
  21     using System.Security;
  22     using System.Security.Permissions;
  23     using System.Diagnostics.Contracts;
  24
  25     // Note that we make a T[] (single-dimensional w/ zero as the lower bound) implement both
  26     // IList<U> and IReadOnlyList<U>, where T : U dynamically.  See the SZArrayHelper class for details.
  27     [Serializable]
  28     [ComVisible(true)]
  29     public abstract class Array : ICloneable, IList, IStructuralComparable, IStructuralEquatable
  30     {
  31         // This ctor exists solely to prevent C# from generating a protected .ctor that violates the surface area. I really want this to be a
  32         // "protected-and-internal" rather than "internal" but C# has no keyword for the former.
  33         internal Array() {}
  34
  35         public static ReadOnlyCollection<T> AsReadOnly<T>(T[] array) {
  36             if (array == null) {
  37                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
  38             }
  39             Contract.Ensures(Contract.Result<ReadOnlyCollection<T>>() != null);
  40
  41             // T[] implements IList<T>.
  42             return new ReadOnlyCollection<T>(array);
  43         }
  44
  45         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  46         public static void Resize<T>(ref T[] array, int newSize) {
  47             if (newSize < 0)
  48                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.newSize, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  49             Contract.Ensures(Contract.ValueAtReturn(out array) != null);
  50             Contract.Ensures(Contract.ValueAtReturn(out array).Length == newSize);
  51             Contract.EndContractBlock();
  52
  53             T[] larray = array;
  54             if (larray == null) {
  55                 array = new T[newSize];
  56                 return;
  57             }
  58
  59             if (larray.Length != newSize) {
  60                 T[] newArray = new T[newSize];
  61                 Array.Copy(larray, 0, newArray, 0,  larray.Length > newSize? newSize : larray.Length);
  62                 array = newArray;
  63             }
  64         }
  65
  66         // Create instance will create an array
  67         [System.Security.SecuritySafeCritical]  // auto-generated
  68         public unsafe static Array CreateInstance(Type elementType, int length)
  69         {
  70             if ((object)elementType == null)
  71                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.elementType);
  72             if (length < 0)
  73                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  74             Contract.Ensures(Contract.Result<Array>() != null);
  75             Contract.Ensures(Contract.Result<Array>().Length == length);
  76             Contract.Ensures(Contract.Result<Array>().Rank == 1);
  77             Contract.EndContractBlock();
  78
  79             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
  80             if (t == null)
  81                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType);
  82             return InternalCreate((void*)t.TypeHandle.Value,1,&length,null);
  83         }
  84
  85         [System.Security.SecuritySafeCritical]  // auto-generated
  86         public unsafe static Array CreateInstance(Type elementType, int length1, int length2)
  87         {
  88             if ((object)elementType == null)
  89                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.elementType);
  90             if (length1 < 0)
  91                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length1, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  92             if (length2 < 0)
  93                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length2, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
  94             Contract.Ensures(Contract.Result<Array>() != null);
  95             Contract.Ensures(Contract.Result<Array>().Rank == 2);
  96             Contract.Ensures(Contract.Result<Array>().GetLength(0) == length1);
  97             Contract.Ensures(Contract.Result<Array>().GetLength(1) == length2);
  98
  99             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
 100             if (t == null)
 101                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType);
 102             int* pLengths = stackalloc int[2];
 103             pLengths[0] = length1;
 104             pLengths[1] = length2;
 105             return InternalCreate((void*)t.TypeHandle.Value,2,pLengths,null);
 106         }
 107
 108         [System.Security.SecuritySafeCritical]  // auto-generated
 109         public unsafe static Array CreateInstance(Type elementType, int length1, int length2, int length3)
 110         {
 111             if ((object)elementType == null)
 112                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.elementType);
 113             if (length1 < 0)
 114                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length1, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
 115             if (length2 < 0)
 116                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length2, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
 117             if (length3 < 0)
 118                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length3, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
 119             Contract.Ensures(Contract.Result<Array>() != null);
 120             Contract.Ensures(Contract.Result<Array>().Rank == 3);
 121             Contract.Ensures(Contract.Result<Array>().GetLength(0) == length1);
 122             Contract.Ensures(Contract.Result<Array>().GetLength(1) == length2);
 123             Contract.Ensures(Contract.Result<Array>().GetLength(2) == length3);
 124
 125             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
 126             if (t == null)
 127                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType);
 128             int* pLengths = stackalloc int[3];
 129             pLengths[0] = length1;
 130             pLengths[1] = length2;
 131             pLengths[2] = length3;
 132             return InternalCreate((void*)t.TypeHandle.Value,3,pLengths,null);
 133         }
 134
 135         [System.Security.SecuritySafeCritical]  // auto-generated
 136         public unsafe static Array CreateInstance(Type elementType, params int[] lengths)
 137         {
 138             if ((object)elementType == null)
 139                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.elementType);
 140             if (lengths == null)
 141                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.lengths);
 142             if (lengths.Length == 0)
 143                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NeedAtLeast1Rank);
 144             Contract.Ensures(Contract.Result<Array>() != null);
 145             Contract.Ensures(Contract.Result<Array>().Rank == lengths.Length);
 146             Contract.EndContractBlock();
 147
 148             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
 149             if (t == null)
 150                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType);
 151
 152             // Check to make sure the lenghts are all positive. Note that we check this here to give
 153             // a good exception message if they are not; however we check this again inside the execution
 154             // engine's low level allocation function after having made a copy of the array to prevent a
 155             // malicious caller from mutating the array after this check.
 156             for (int i = 0; i < lengths.Length; i++)
 157                 if (lengths[i] < 0)
 158                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.lengths, i, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
 159
 160             fixed (int* pLengths = lengths)
 161                 return InternalCreate((void*)t.TypeHandle.Value,lengths.Length,pLengths,null);
 162         }
 163
 164         public static Array CreateInstance(Type elementType, params long[] lengths)
 165         {
 166             if( lengths == null) {
 167                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.lengths);
 168             }
 169             if (lengths.Length == 0)
 170                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NeedAtLeast1Rank);
 171             Contract.Ensures(Contract.Result<Array>() != null);
 172             Contract.Ensures(Contract.Result<Array>().Rank == lengths.Length);
 173             Contract.EndContractBlock();
 174
 175             int[] intLengths = new int[lengths.Length];
 176
 177             for (int i = 0; i < lengths.Length; ++i)
 178             {
 179                 long len = lengths[i];
 180                 if (len > Int32.MaxValue || len < Int32.MinValue)
 181                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.len, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 182                 intLengths[i] = (int) len;
 183             }
 184
 185             return Array.CreateInstance(elementType, intLengths);
 186         }
 187
 188
 189         [System.Security.SecuritySafeCritical]  // auto-generated
 190         public unsafe static Array CreateInstance(Type elementType, int[] lengths,int[] lowerBounds)
 191         {
 192             if (elementType == null)
 193                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.elementType);
 194             if (lengths == null)
 195                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.lengths);
 196             if (lowerBounds == null)
 197                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.lowerBounds);
 198             if (lengths.Length != lowerBounds.Length)
 199                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RanksAndBounds);
 200             if (lengths.Length == 0)
 201                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NeedAtLeast1Rank);
 202             Contract.Ensures(Contract.Result<Array>() != null);
 203             Contract.Ensures(Contract.Result<Array>().Rank == lengths.Length);
 204             Contract.EndContractBlock();
 205
 206             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
 207             if (t == null)
 208                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType);
 209
 210             // Check to make sure the lenghts are all positive. Note that we check this here to give
 211             // a good exception message if they are not; however we check this again inside the execution
 212             // engine's low level allocation function after having made a copy of the array to prevent a
 213             // malicious caller from mutating the array after this check.
 214             for (int i=0;i<lengths.Length;i++)
 215                 if (lengths[i] < 0)
 216                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.lengths, i, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
 217
 218             fixed (int* pLengths = lengths)
 219                 fixed(int* pLowerBounds = lowerBounds)
 220                     return InternalCreate((void*)t.TypeHandle.Value,lengths.Length,pLengths,pLowerBounds);
 221         }
 222         [System.Security.SecurityCritical]  // auto-generated
 223         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 224         private unsafe static extern Array InternalCreate(void* elementType,int rank,int *pLengths,int *pLowerBounds);
 225
 226         [SecurityCritical]
 227 #if !FEATURE_CORECLR
 228         [PermissionSet(SecurityAction.Assert, Unrestricted = true)]
 229 #endif
 230         internal static Array UnsafeCreateInstance(Type elementType, int length)
 231         {
 232             return CreateInstance(elementType, length);
 233         }
 234
 235         [SecurityCritical]
 236 #if !FEATURE_CORECLR
 237         [PermissionSet(SecurityAction.Assert, Unrestricted = true)]
 238 #endif
 239         internal static Array UnsafeCreateInstance(Type elementType, int length1, int length2)
 240         {
 241             return CreateInstance(elementType, length1, length2);
 242         }
 243
 244         [SecurityCritical]
 245 #if !FEATURE_CORECLR
 246         [PermissionSet(SecurityAction.Assert, Unrestricted = true)]
 247 #endif
 248         internal static Array UnsafeCreateInstance(Type elementType, params int[] lengths)
 249         {
 250             return CreateInstance(elementType, lengths);
 251         }
 252
 253         [SecurityCritical]
 254 #if !FEATURE_CORECLR
 255         [PermissionSet(SecurityAction.Assert, Unrestricted = true)]
 256 #endif
 257         internal static Array UnsafeCreateInstance(Type elementType, int[] lengths, int[] lowerBounds)
 258         {
 259             return CreateInstance(elementType, lengths, lowerBounds);
 260         }
 261
 262         // Copies length elements from sourceArray, starting at index 0, to
 263         // destinationArray, starting at index 0.
 264         //
 265         [System.Security.SecuritySafeCritical]  // auto-generated
 266         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
 267         public static void Copy(Array sourceArray, Array destinationArray, int length)
 268         {
 269             if (sourceArray == null)
 270                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.sourceArray);
 271             if (destinationArray == null)
 272                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.destinationArray);
 273             /*
 274             Contract.Requires(sourceArray.Rank == destinationArray.Rank);
 275             Contract.Requires(length >= 0);
 276             Contract.Requires(length <= sourceArray.GetLowerBound(0) + sourceArray.Length);
 277             Contract.Requires(length <= destinationArray.GetLowerBound(0) + destinationArray.Length);
 278              */
 279             Contract.EndContractBlock();
 280
 281             Copy(sourceArray, sourceArray.GetLowerBound(0), destinationArray, destinationArray.GetLowerBound(0), length, false);
 282         }
 283
 284         // Copies length elements from sourceArray, starting at sourceIndex, to
 285         // destinationArray, starting at destinationIndex.
 286         //
 287         [System.Security.SecuritySafeCritical]  // auto-generated
 288         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
 289         public static void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
 290         {
 291             Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, false);
 292         }
 293
 294         // Reliability-wise, this method will either possibly corrupt your
 295         // instance & might fail when called from within a CER, or if the
 296         // reliable flag is true, it will either always succeed or always
 297         // throw an exception with no side effects.
 298         [System.Security.SecurityCritical]  // auto-generated
 299         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
 300         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 301         internal static extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);
 302
 303         // Provides a strong exception guarantee - either it succeeds, or
 304         // it throws an exception with no side effects.  The arrays must be
 305         // compatible array types based on the array element type - this
 306         // method does not support casting, boxing, or primitive widening.
 307         // It will up-cast, assuming the array types are correct.
 308         [System.Security.SecuritySafeCritical]  // auto-generated
 309         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 310         public static void ConstrainedCopy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
 311         {
 312             Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, true);
 313         }
 314
 315         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
 316         public static void Copy(Array sourceArray, Array destinationArray, long length)
 317         {
 318             if (length > Int32.MaxValue || length < Int32.MinValue)
 319                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 320
 321             Array.Copy(sourceArray, destinationArray, (int) length);
 322         }
 323
 324         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
 325         public static void Copy(Array sourceArray, long sourceIndex, Array destinationArray, long destinationIndex, long length)
 326         {
 327             if (sourceIndex > Int32.MaxValue || sourceIndex < Int32.MinValue)
 328                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.sourceIndex, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 329             if (destinationIndex > Int32.MaxValue || destinationIndex < Int32.MinValue)
 330                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.destinationIndex, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 331             if (length > Int32.MaxValue || length < Int32.MinValue)
 332                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 333
 334             Array.Copy(sourceArray, (int) sourceIndex, destinationArray, (int) destinationIndex, (int) length);
 335         }
 336
 337
 338         // Sets length elements in array to 0 (or null for Object arrays), starting
 339         // at index.
 340         //
 341         [System.Security.SecuritySafeCritical]  // auto-generated
 342         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 343         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 344         public static extern void Clear(Array array, int index, int length);
 345
 346         // The various Get values...
 347         [System.Security.SecuritySafeCritical]  // auto-generated
 348         public unsafe Object GetValue(params int[] indices)
 349         {
 350             if (indices == null)
 351                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.indices);
 352             if (Rank != indices.Length)
 353                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices);
 354             Contract.EndContractBlock();
 355
 356             TypedReference elemref = new TypedReference();
 357             fixed(int* pIndices = indices)
 358                 InternalGetReference(&elemref, indices.Length, pIndices);
 359             return TypedReference.InternalToObject(&elemref);
 360         }
 361
 362         [System.Security.SecuritySafeCritical]  // auto-generated
 363         public unsafe Object GetValue(int index)
 364         {
 365             if (Rank != 1)
 366                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need1DArray);
 367             Contract.EndContractBlock();
 368
 369             TypedReference elemref = new TypedReference();
 370             InternalGetReference(&elemref, 1, &index);
 371             return TypedReference.InternalToObject(&elemref);
 372         }
 373
 374         [System.Security.SecuritySafeCritical]  // auto-generated
 375         public unsafe Object GetValue(int index1, int index2)
 376         {
 377             if (Rank != 2)
 378                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need2DArray);
 379             Contract.EndContractBlock();
 380
 381             int* pIndices = stackalloc int[2];
 382             pIndices[0] = index1;
 383             pIndices[1] = index2;
 384
 385             TypedReference elemref = new TypedReference();
 386             InternalGetReference(&elemref, 2, pIndices);
 387             return TypedReference.InternalToObject(&elemref);
 388         }
 389
 390         [System.Security.SecuritySafeCritical]  // auto-generated
 391         public unsafe Object GetValue(int index1, int index2, int index3)
 392         {
 393             if (Rank != 3)
 394                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need3DArray);
 395             Contract.EndContractBlock();
 396
 397             int* pIndices = stackalloc int[3];
 398             pIndices[0] = index1;
 399             pIndices[1] = index2;
 400             pIndices[2] = index3;
 401
 402             TypedReference elemref = new TypedReference();
 403             InternalGetReference(&elemref, 3, pIndices);
 404             return TypedReference.InternalToObject(&elemref);
 405         }
 406
 407         [ComVisible(false)]
 408         public Object GetValue(long index)
 409         {
 410             if (index > Int32.MaxValue || index < Int32.MinValue)
 411                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 412             Contract.EndContractBlock();
 413
 414             return this.GetValue((int) index);
 415         }
 416
 417         [ComVisible(false)]
 418         public Object GetValue(long index1, long index2)
 419         {
 420             if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
 421                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index1, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 422             if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
 423                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index2, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 424             Contract.EndContractBlock();
 425
 426             return this.GetValue((int) index1, (int) index2);
 427         }
 428
 429         [ComVisible(false)]
 430         public Object GetValue(long index1, long index2, long index3)
 431         {
 432             if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
 433                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index1, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 434             if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
 435                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index2, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 436             if (index3 > Int32.MaxValue || index3 < Int32.MinValue)
 437                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index3, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 438             Contract.EndContractBlock();
 439
 440             return this.GetValue((int) index1, (int) index2, (int) index3);
 441         }
 442
 443         [ComVisible(false)]
 444         public Object GetValue(params long[] indices)
 445         {
 446             if (indices == null)
 447                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.indices);
 448             if (Rank != indices.Length)
 449                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices);
 450             Contract.EndContractBlock();
 451
 452             int[] intIndices = new int[indices.Length];
 453
 454             for (int i = 0; i < indices.Length; ++i)
 455             {
 456                 long index = indices[i];
 457                 if (index > Int32.MaxValue || index < Int32.MinValue)
 458                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 459                 intIndices[i] = (int) index;
 460             }
 461
 462             return this.GetValue(intIndices);
 463         }
 464
 465
 466         [System.Security.SecuritySafeCritical]  // auto-generated
 467         public unsafe void SetValue(Object value,int index)
 468         {
 469             if (Rank != 1)
 470                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need1DArray);
 471             Contract.EndContractBlock();
 472
 473             TypedReference elemref = new TypedReference();
 474             InternalGetReference(&elemref, 1, &index);
 475             InternalSetValue(&elemref,value);
 476         }
 477
 478         [System.Security.SecuritySafeCritical]  // auto-generated
 479         public unsafe void SetValue(Object value,int index1, int index2)
 480         {
 481             if (Rank != 2)
 482                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need2DArray);
 483             Contract.EndContractBlock();
 484
 485             int* pIndices = stackalloc int[2];
 486             pIndices[0] = index1;
 487             pIndices[1] = index2;
 488
 489             TypedReference elemref = new TypedReference();
 490             InternalGetReference(&elemref, 2, pIndices);
 491             InternalSetValue(&elemref,value);
 492         }
 493
 494         [System.Security.SecuritySafeCritical]  // auto-generated
 495         public unsafe void SetValue(Object value,int index1, int index2, int index3)
 496         {
 497             if (Rank != 3)
 498                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need3DArray);
 499             Contract.EndContractBlock();
 500
 501             int* pIndices = stackalloc int[3];
 502             pIndices[0] = index1;
 503             pIndices[1] = index2;
 504             pIndices[2] = index3;
 505
 506             TypedReference elemref = new TypedReference();
 507             InternalGetReference(&elemref, 3, pIndices);
 508             InternalSetValue(&elemref,value);
 509         }
 510
 511         [System.Security.SecuritySafeCritical]  // auto-generated
 512         public unsafe void SetValue(Object value,params int[] indices)
 513         {
 514             if (indices == null)
 515                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.indices);
 516             if (Rank != indices.Length)
 517                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices);
 518             Contract.EndContractBlock();
 519
 520             TypedReference elemref = new TypedReference();
 521             fixed(int* pIndices = indices)
 522                 InternalGetReference(&elemref, indices.Length, pIndices);
 523             InternalSetValue(&elemref,value);
 524         }
 525
 526         [ComVisible(false)]
 527         public void SetValue(Object value, long index)
 528         {
 529             if (index > Int32.MaxValue || index < Int32.MinValue)
 530                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 531             Contract.EndContractBlock();
 532
 533             this.SetValue(value, (int) index);
 534         }
 535
 536         [ComVisible(false)]
 537         public void SetValue(Object value, long index1, long index2)
 538         {
 539             if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
 540                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index1, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 541             if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
 542                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index2, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 543             Contract.EndContractBlock();
 544
 545             this.SetValue(value, (int) index1, (int) index2);
 546         }
 547
 548         [ComVisible(false)]
 549         public void SetValue(Object value, long index1, long index2, long index3)
 550         {
 551             if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
 552                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index1, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 553             if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
 554                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index2, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 555             if (index3 > Int32.MaxValue || index3 < Int32.MinValue)
 556                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index3, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 557             Contract.EndContractBlock();
 558
 559             this.SetValue(value, (int) index1, (int) index2, (int) index3);
 560         }
 561
 562         [ComVisible(false)]
 563         public void SetValue(Object value, params long[] indices)
 564         {
 565             if (indices == null)
 566                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.indices);
 567             if (Rank != indices.Length)
 568                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices);
 569             Contract.EndContractBlock();
 570
 571             int[] intIndices = new int[indices.Length];
 572
 573             for (int i = 0; i < indices.Length; ++i)
 574             {
 575                 long index = indices[i];
 576                 if (index > Int32.MaxValue || index < Int32.MinValue)
 577                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
 578                 intIndices[i] = (int) index;
 579             }
 580
 581             this.SetValue(value, intIndices);
 582         }
 583
 584         [System.Security.SecurityCritical]  // auto-generated
 585         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 586         // reference to TypedReference is banned, so have to pass result as pointer
 587         private unsafe extern void InternalGetReference(void * elemRef, int rank, int * pIndices);
 588
 589         // Ideally, we would like to use TypedReference.SetValue instead. Unfortunately, TypedReference.SetValue
 590         // always throws not-supported exception
 591         [System.Security.SecurityCritical]  // auto-generated
 592         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 593         private unsafe extern static void InternalSetValue(void * target, Object value);
 594
 595         public extern int Length {
 596             [Pure]
 597             [System.Security.SecuritySafeCritical]  // auto-generated
 598             [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 599             [MethodImpl(MethodImplOptions.InternalCall)]
 600             get;
 601         }
 602
 603         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 604         private static int GetMedian(int low, int hi) {
 605             // Note both may be negative, if we are dealing with arrays w/ negative lower bounds.
 606             Contract.Requires(low <= hi);
 607             Contract.Assert( hi - low >= 0, "Length overflow!");
 608             return low + ((hi - low) >> 1);
 609         }
 610
 611         // We impose limits on maximum array lenght in each dimension to allow efficient
 612         // implementation of advanced range check elimination in future.
 613         // Keep in sync with vm\gcscan.cpp and HashHelpers.MaxPrimeArrayLength.
 614         // The constants are defined in this method: inline SIZE_T MaxArrayLength(SIZE_T componentSize) from gcscan
 615         // We have different max sizes for arrays with elements of size 1 for backwards compatibility
 616         internal const int MaxArrayLength = 0X7FEFFFFF;
 617         internal const int MaxByteArrayLength = 0x7FFFFFC7;
 618
 619         [ComVisible(false)]
 620         public extern long LongLength {
 621             [Pure]
 622             [System.Security.SecuritySafeCritical]  // auto-generated
 623             [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 624             [MethodImpl(MethodImplOptions.InternalCall)]
 625             get;
 626         }
 627
 628         [Pure]
 629         [System.Security.SecuritySafeCritical]  // auto-generated
 630         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 631         public extern int GetLength(int dimension);
 632
 633         [Pure]
 634         [ComVisible(false)]
 635         public long GetLongLength(int dimension) {
 636             //This method should throw an IndexOufOfRangeException for compat if dimension < 0 or >= Rank
 637             return GetLength(dimension);
 638         }
 639
 640         public extern int Rank {
 641             [Pure]
 642             [System.Security.SecuritySafeCritical]  // auto-generated
 643             [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 644             [MethodImplAttribute(MethodImplOptions.InternalCall)]
 645             get;
 646         }
 647
 648         [System.Security.SecuritySafeCritical]  // auto-generated
 649         [Pure]
 650         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 651         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 652         public extern int GetUpperBound(int dimension);
 653
 654         [System.Security.SecuritySafeCritical]  // auto-generated
 655         [Pure]
 656         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 657         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 658         public extern int GetLowerBound(int dimension);
 659
 660         [System.Security.SecurityCritical]  // auto-generated
 661         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
 662         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 663         internal extern int GetDataPtrOffsetInternal();
 664
 665         // Number of elements in the Array.
 666         int ICollection.Count
 667         { get { return Length; } }
 668
 669
 670         // Returns an object appropriate for synchronizing access to this
 671         // Array.
 672         public Object SyncRoot
 673         { get { return this; } }
 674
 675         // Is this Array read-only?
 676         public bool IsReadOnly
 677         { get { return false; } }
 678
 679         public bool IsFixedSize {
 680             get { return true; }
 681         }
 682
 683         // Is this Array synchronized (i.e., thread-safe)?  If you want a synchronized
 684         // collection, you can use SyncRoot as an object to synchronize your
 685         // collection with.  You could also call GetSynchronized()
 686         // to get a synchronized wrapper around the Array.
 687         public bool IsSynchronized
 688         { get { return false; } }
 689
 690
 691         Object IList.this[int index] {
 692             get { return GetValue(index); }
 693             set { SetValue(value, index); }
 694         }
 695
 696         int IList.Add(Object value)
 697         {
 698             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
 699             return default(int);
 700         }
 701
 702         bool IList.Contains(Object value)
 703         {
 704             return Array.IndexOf(this, value) >= this.GetLowerBound(0);
 705         }
 706
 707         void IList.Clear()
 708         {
 709             Array.Clear(this, this.GetLowerBound(0), this.Length);
 710         }
 711
 712         int IList.IndexOf(Object value)
 713         {
 714             return Array.IndexOf(this, value);
 715         }
 716
 717         void IList.Insert(int index, Object value)
 718         {
 719             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
 720         }
 721
 722         void IList.Remove(Object value)
 723         {
 724             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
 725         }
 726
 727         void IList.RemoveAt(int index)
 728         {
 729             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
 730         }
 731
 732         // Make a new array which is a shallow copy of the original array.
 733         //
 734         public Object Clone()
 735         {
 736             return MemberwiseClone();
 737         }
 738
 739         Int32 IStructuralComparable.CompareTo(Object other, IComparer comparer) {
 740             if (other == null) {
 741                 return 1;
 742             }
 743
 744             Array o = other as Array;
 745
 746             if (o == null || this.Length != o.Length)
 747             {
 748                 ThrowHelper.ThrowArgumentException(ExceptionResource.ArgumentException_OtherNotArrayOfCorrectLength, ExceptionArgument.other);
 749             }
 750
 751             int i = 0;
 752             int c = 0;
 753
 754             while (i < o.Length && c == 0) {
 755                 object left = GetValue(i);
 756                 object right = o.GetValue(i);
 757
 758                 c = comparer.Compare(left, right);
 759                 i++;
 760             }
 761
 762             return c;
 763         }
 764
 765         Boolean IStructuralEquatable.Equals(Object other, IEqualityComparer comparer) {
 766
 767             if (other == null) {
 768                 return false;
 769             }
 770
 771             if (Object.ReferenceEquals(this, other)) {
 772                 return true;
 773             }
 774
 775             Array o = other as Array;
 776
 777             if (o == null || o.Length != this.Length) {
 778                 return false;
 779             }
 780
 781             int i = 0;
 782             while (i < o.Length) {
 783                 object left = GetValue(i);
 784                 object right = o.GetValue(i);
 785
 786                 if (!comparer.Equals(left, right)) {
 787                     return false;
 788                 }
 789                 i++;
 790             }
 791
 792             return true;
 793         }
 794
 795         // From System.Web.Util.HashCodeCombiner
 796         internal static int CombineHashCodes(int h1, int h2) {
 797             return (((h1 << 5) + h1) ^ h2);
 798         }
 799
 800         int IStructuralEquatable.GetHashCode(IEqualityComparer comparer) {
 801             if (comparer == null)
 802                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparer);
 803             Contract.EndContractBlock();
 804
 805             int ret = 0;
 806
 807             for (int i = (this.Length >= 8 ? this.Length - 8 : 0); i < this.Length; i++) {
 808                 ret = CombineHashCodes(ret, comparer.GetHashCode(GetValue(i)));
 809             }
 810
 811             return ret;
 812         }
 813
 814         // Searches an array for a given element using a binary search algorithm.
 815         // Elements of the array are compared to the search value using the
 816         // IComparable interface, which must be implemented by all elements
 817         // of the array and the given search value. This method assumes that the
 818         // array is already sorted according to the IComparable interface;
 819         // if this is not the case, the result will be incorrect.
 820         //
 821         // The method returns the index of the given value in the array. If the
 822         // array does not contain the given value, the method returns a negative
 823         // integer. The bitwise complement operator (~) can be applied to a
 824         // negative result to produce the index of the first element (if any) that
 825         // is larger than the given search value.
 826         //
 827         [Pure]
 828         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 829         public static int BinarySearch(Array array, Object value) {
 830             if (array==null)
 831                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 832             Contract.Ensures((Contract.Result<int>() >= array.GetLowerBound(0) && Contract.Result<int>() <= array.GetUpperBound(0)) || (Contract.Result<int>() < array.GetLowerBound(0) && ~Contract.Result<int>() <= array.GetUpperBound(0) + 1));
 833             Contract.EndContractBlock();
 834             int lb = array.GetLowerBound(0);
 835             return BinarySearch(array, lb, array.Length, value, null);
 836         }
 837
 838         // Searches a section of an array for a given element using a binary search
 839         // algorithm. Elements of the array are compared to the search value using
 840         // the IComparable interface, which must be implemented by all
 841         // elements of the array and the given search value. This method assumes
 842         // that the array is already sorted according to the IComparable
 843         // interface; if this is not the case, the result will be incorrect.
 844         //
 845         // The method returns the index of the given value in the array. If the
 846         // array does not contain the given value, the method returns a negative
 847         // integer. The bitwise complement operator (~) can be applied to a
 848         // negative result to produce the index of the first element (if any) that
 849         // is larger than the given search value.
 850         //
 851         [Pure]
 852         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 853         public static int BinarySearch(Array array, int index, int length, Object value) {
 854             return BinarySearch(array, index, length, value, null);
 855         }
 856
 857         // Searches an array for a given element using a binary search algorithm.
 858         // Elements of the array are compared to the search value using the given
 859         // IComparer interface. If comparer is null, elements of the
 860         // array are compared to the search value using the IComparable
 861         // interface, which in that case must be implemented by all elements of the
 862         // array and the given search value. This method assumes that the array is
 863         // already sorted; if this is not the case, the result will be incorrect.
 864         //
 865         // The method returns the index of the given value in the array. If the
 866         // array does not contain the given value, the method returns a negative
 867         // integer. The bitwise complement operator (~) can be applied to a
 868         // negative result to produce the index of the first element (if any) that
 869         // is larger than the given search value.
 870         //
 871         [Pure]
 872         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 873         public static int BinarySearch(Array array, Object value, IComparer comparer) {
 874             if (array==null)
 875                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 876             Contract.EndContractBlock();
 877             int lb = array.GetLowerBound(0);
 878             return BinarySearch(array, lb, array.Length, value, comparer);
 879         }
 880
 881         // Searches a section of an array for a given element using a binary search
 882         // algorithm. Elements of the array are compared to the search value using
 883         // the given IComparer interface. If comparer is null,
 884         // elements of the array are compared to the search value using the
 885         // IComparable interface, which in that case must be implemented by
 886         // all elements of the array and the given search value. This method
 887         // assumes that the array is already sorted; if this is not the case, the
 888         // result will be incorrect.
 889         //
 890         // The method returns the index of the given value in the array. If the
 891         // array does not contain the given value, the method returns a negative
 892         // integer. The bitwise complement operator (~) can be applied to a
 893         // negative result to produce the index of the first element (if any) that
 894         // is larger than the given search value.
 895         //
 896         [Pure]
 897         [System.Security.SecuritySafeCritical]  // auto-generated
 898         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 899         public static int BinarySearch(Array array, int index, int length, Object value, IComparer comparer) {
 900             if (array==null)
 901                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 902             Contract.EndContractBlock();
 903             int lb = array.GetLowerBound(0);
 904             if (index < lb)
 905                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
 906             if (length < 0)
 907                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
 908             if (array.Length - (index - lb) < length)
 909                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
 910             if (array.Rank != 1)
 911                 ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
 912
 913             if (comparer == null) comparer = Comparer.Default;
 914             if (comparer == Comparer.Default) {
 915                 int retval;
 916                 bool r = TrySZBinarySearch(array, index, length, value, out retval);
 917                 if (r)
 918                     return retval;
 919             }
 920
 921             int lo = index;
 922             int hi = index + length - 1;
 923             Object[] objArray = array as Object[];
 924             if(objArray != null) {
 925                 while (lo <= hi) {
 926                     // i might overflow if lo and hi are both large positive numbers.
 927                     int i = GetMedian(lo, hi);
 928
 929                     int c = 0;
 930                     try {
 931                         c = comparer.Compare(objArray[i], value);
 932                     }
 933                     catch (Exception e) {
 934                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
 935                     }
 936                     if (c == 0) return i;
 937                     if (c < 0) {
 938                         lo = i + 1;
 939                     }
 940                     else {
 941                         hi = i - 1;
 942                     }
 943                 }
 944             }
 945             else {
 946                 while (lo <= hi) {
 947                     int i = GetMedian(lo, hi);
 948
 949                     int c = 0;
 950                     try {
 951                         c = comparer.Compare(array.GetValue(i), value);
 952                     }
 953                     catch (Exception e) {
 954                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
 955                     }
 956                     if (c == 0) return i;
 957                     if (c < 0) {
 958                         lo = i + 1;
 959                     }
 960                     else {
 961                         hi = i - 1;
 962                     }
 963                 }
 964             }
 965             return ~lo;
 966         }
 967
 968         [System.Security.SecurityCritical]  // auto-generated
 969         [MethodImplAttribute(MethodImplOptions.InternalCall)]
 970         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 971         private static extern bool TrySZBinarySearch(Array sourceArray, int sourceIndex, int count, Object value, out int retVal);
 972
 973         [Pure]
 974         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 975         public static int BinarySearch<T>(T[] array, T value) {
 976             if (array==null)
 977                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 978             Contract.EndContractBlock();
 979             return BinarySearch<T>(array, 0, array.Length, value, null);
 980         }
 981
 982         [Pure]
 983         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 984         public static int BinarySearch<T>(T[] array, T value, System.Collections.Generic.IComparer<T> comparer) {
 985             if (array==null)
 986                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
 987             Contract.EndContractBlock();
 988             return BinarySearch<T>(array, 0, array.Length, value, comparer);
 989         }
 990
 991         [Pure]
 992         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 993         public static int BinarySearch<T>(T[] array, int index, int length, T value) {
 994             return BinarySearch<T>(array, index, length, value, null);
 995         }
 996
 997         [Pure]
 998         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
 999         public static int BinarySearch<T>(T[] array, int index, int length, T value, System.Collections.Generic.IComparer<T> comparer) {
1000             if (array==null)
1001                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1002             if (index < 0)
1003                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1004             if (length < 0)
1005                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
1006
1007             if (array.Length - index < length)
1008                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
1009             Contract.EndContractBlock();
1010
1011             return ArraySortHelper<T>.Default.BinarySearch(array, index, length, value, comparer);
1012         }
1013
1014         public static TOutput[] ConvertAll<TInput, TOutput>(TInput[] array, Converter<TInput,TOutput> converter) {
1015             if( array == null) {
1016                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1017             }
1018
1019             if( converter == null) {
1020                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.converter);
1021             }
1022             Contract.Ensures(Contract.Result<TOutput[]>() != null);
1023             Contract.Ensures(Contract.Result<TOutput[]>().Length == array.Length);
1024             Contract.EndContractBlock();
1025
1026             TOutput[] newArray = new TOutput[array.Length];
1027             for( int i = 0; i< array.Length; i++) {
1028                 newArray[i] = converter(array[i]);
1029             }
1030             return newArray;
1031         }
1032
1033         // CopyTo copies a collection into an Array, starting at a particular
1034         // index into the array.
1035         //
1036         // This method is to support the ICollection interface, and calls
1037         // Array.Copy internally.  If you aren't using ICollection explicitly,
1038         // call Array.Copy to avoid an extra indirection.
1039         //
1040         [Pure]
1041         public void CopyTo(Array array, int index)
1042         {
1043             if (array != null && array.Rank != 1)
1044                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
1045             Contract.EndContractBlock();
1046             // Note: Array.Copy throws a RankException and we want a consistent ArgumentException for all the IList CopyTo methods.
1047             Array.Copy(this, GetLowerBound(0), array, index, Length);
1048         }
1049
1050         [Pure]
1051         [ComVisible(false)]
1052         public void CopyTo(Array array, long index)
1053         {
1054             if (index > Int32.MaxValue || index < Int32.MinValue)
1055                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
1056             Contract.EndContractBlock();
1057
1058             this.CopyTo(array, (int) index);
1059         }
1060
1061         [Pure]
1062         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1063         public static T[] Empty<T>()
1064         {
1065             Contract.Ensures(Contract.Result<T[]>() != null);
1066             Contract.Ensures(Contract.Result<T[]>().Length == 0);
1067             Contract.EndContractBlock();
1068
1069             return EmptyArray<T>.Value;
1070         }
1071
1072         public static bool Exists<T>(T[] array, Predicate<T> match) {
1073             return Array.FindIndex(array, match) != -1;
1074         }
1075
1076         public static T Find<T>(T[] array, Predicate<T> match) {
1077             if( array == null) {
1078                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1079             }
1080
1081             if( match == null) {
1082                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
1083             }
1084             Contract.EndContractBlock();
1085
1086             for(int i = 0 ; i < array.Length; i++) {
1087                 if(match(array[i])) {
1088                     return array[i];
1089                 }
1090             }
1091             return default(T);
1092         }
1093
1094         public static T[] FindAll<T>(T[] array, Predicate<T> match) {
1095             if( array == null) {
1096                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1097             }
1098
1099             if( match == null) {
1100                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
1101             }
1102             Contract.EndContractBlock();
1103
1104             List<T> list = new List<T>();
1105             for(int i = 0 ; i < array.Length; i++) {
1106                 if(match(array[i])) {
1107                     list.Add(array[i]);
1108                 }
1109             }
1110             return list.ToArray();
1111         }
1112
1113         public static int FindIndex<T>(T[] array, Predicate<T> match) {
1114             if (array==null) {
1115                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1116             }
1117             Contract.Ensures(Contract.Result<int>() < array.Length);
1118             Contract.EndContractBlock();
1119
1120             return FindIndex(array, 0, array.Length, match);
1121         }
1122
1123         public static int FindIndex<T>(T[] array, int startIndex, Predicate<T> match) {
1124             if (array==null) {
1125                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1126             }
1127             Contract.Ensures(Contract.Result<int>() < array.Length);
1128             Contract.EndContractBlock();
1129
1130             return FindIndex(array, startIndex, array.Length - startIndex, match);
1131         }
1132
1133         public static int FindIndex<T>(T[] array, int startIndex, int count, Predicate<T> match) {
1134             if (array==null) {
1135                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1136             }
1137
1138             if( startIndex < 0 || startIndex > array.Length ) {
1139                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
1140             }
1141
1142             if (count < 0 || startIndex > array.Length - count) {
1143                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
1144             }
1145
1146             if( match == null) {
1147                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
1148             }
1149             Contract.Ensures(Contract.Result<int>() < array.Length);
1150             Contract.EndContractBlock();
1151
1152             int endIndex = startIndex + count;
1153             for( int i = startIndex; i < endIndex; i++) {
1154                 if( match(array[i])) return i;
1155             }
1156             return -1;
1157         }
1158
1159         public static T FindLast<T>(T[] array, Predicate<T> match) {
1160             if( array == null) {
1161                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1162             }
1163
1164             if( match == null) {
1165                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
1166             }
1167             Contract.EndContractBlock();
1168
1169             for(int i = array.Length - 1 ; i >= 0; i--) {
1170                 if(match(array[i])) {
1171                     return array[i];
1172                 }
1173             }
1174             return default(T);
1175         }
1176
1177         public static int FindLastIndex<T>(T[] array, Predicate<T> match) {
1178             if( array == null) {
1179                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1180             }
1181             Contract.EndContractBlock();
1182
1183             return FindLastIndex(array, array.Length - 1, array.Length, match);
1184         }
1185
1186         public static int FindLastIndex<T>(T[] array, int startIndex, Predicate<T> match) {
1187             if( array == null) {
1188                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1189             }
1190             Contract.EndContractBlock();
1191
1192             return FindLastIndex(array, startIndex, startIndex + 1, match);
1193         }
1194
1195         public static int FindLastIndex<T>(T[] array, int startIndex, int count, Predicate<T> match) {
1196             if( array == null) {
1197                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1198             }
1199
1200             if( match == null) {
1201                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
1202             }
1203             Contract.EndContractBlock();
1204
1205             if(array.Length == 0) {
1206                 // Special case for 0 length List
1207                 if( startIndex != -1) {
1208                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
1209                 }
1210             }
1211             else {
1212                 // Make sure we're not out of range
1213                 if ( startIndex < 0 || startIndex >= array.Length) {
1214                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
1215                 }
1216             }
1217
1218             // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
1219             if (count < 0 || startIndex - count + 1 < 0) {
1220                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
1221             }
1222
1223             int endIndex = startIndex - count;
1224             for( int i = startIndex; i > endIndex; i--) {
1225                 if( match(array[i])) {
1226                     return i;
1227                 }
1228             }
1229             return -1;
1230         }
1231
1232         public static void ForEach<T>(T[] array, Action<T> action) {
1233             if( array == null) {
1234                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1235             }
1236
1237             if( action == null) {
1238                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.action);
1239             }
1240             Contract.EndContractBlock();
1241
1242             for(int i = 0 ; i < array.Length; i++) {
1243                 action(array[i]);
1244             }
1245         }
1246
1247         // GetEnumerator returns an IEnumerator over this Array.
1248         //
1249         // Currently, only one dimensional arrays are supported.
1250         //
1251         public IEnumerator GetEnumerator()
1252         {
1253             int lowerBound = GetLowerBound(0);
1254             if (Rank == 1 && lowerBound == 0)
1255                 return new SZArrayEnumerator(this);
1256             else
1257                 return new ArrayEnumerator(this, lowerBound, Length);
1258         }
1259
1260         // Returns the index of the first occurrence of a given value in an array.
1261         // The array is searched forwards, and the elements of the array are
1262         // compared to the given value using the Object.Equals method.
1263         //
1264         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1265         public static int IndexOf(Array array, Object value) {
1266             if (array==null)
1267                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1268             Contract.Ensures(Contract.Result<int>() < array.GetLowerBound(0) + array.Length);
1269             Contract.EndContractBlock();
1270             int lb = array.GetLowerBound(0);
1271             return IndexOf(array, value, lb, array.Length);
1272         }
1273
1274         // Returns the index of the first occurrence of a given value in a range of
1275         // an array. The array is searched forwards, starting at index
1276         // startIndex and ending at the last element of the array. The
1277         // elements of the array are compared to the given value using the
1278         // Object.Equals method.
1279         //
1280         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1281         public static int IndexOf(Array array, Object value, int startIndex) {
1282             if (array==null)
1283                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1284             Contract.Ensures(Contract.Result<int>() < array.GetLowerBound(0) + array.Length);
1285             Contract.EndContractBlock();
1286             int lb = array.GetLowerBound(0);
1287             return IndexOf(array, value, startIndex, array.Length - startIndex + lb);
1288         }
1289
1290         // Returns the index of the first occurrence of a given value in a range of
1291         // an array. The array is searched forwards, starting at index
1292         // startIndex and upto count elements. The
1293         // elements of the array are compared to the given value using the
1294         // Object.Equals method.
1295         //
1296         [System.Security.SecuritySafeCritical]  // auto-generated
1297         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1298         public static int IndexOf(Array array, Object value, int startIndex, int count) {
1299             if (array==null)
1300                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1301             if (array.Rank != 1)
1302                 ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
1303             Contract.Ensures(Contract.Result<int>() < array.GetLowerBound(0) + array.Length);
1304             Contract.EndContractBlock();
1305
1306             int lb = array.GetLowerBound(0);
1307             if (startIndex < lb || startIndex > array.Length + lb)
1308                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
1309             if (count < 0 || count > array.Length - startIndex + lb)
1310                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
1311
1312             // Try calling a quick native method to handle primitive types.
1313             int retVal;
1314             bool r = TrySZIndexOf(array, startIndex, count, value, out retVal);
1315             if (r)
1316                 return retVal;
1317
1318             Object[] objArray = array as Object[];
1319             int endIndex = startIndex + count;
1320             if (objArray != null) {
1321                 if (value == null) {
1322                     for (int i = startIndex; i < endIndex; i++) {
1323                         if (objArray[i] == null) return i;
1324                     }
1325                 }
1326                 else {
1327                     for (int i = startIndex; i < endIndex; i++) {
1328                         Object obj = objArray[i];
1329                         if (obj != null && obj.Equals(value)) return i;
1330                     }
1331                 }
1332             }
1333             else {
1334                 for (int i = startIndex; i < endIndex; i++) {
1335                     Object obj = array.GetValue(i);
1336                     if( obj == null) {
1337                         if(value == null) return i;
1338                     }
1339                     else {
1340                         if( obj.Equals(value)) return i;
1341                     }
1342                 }
1343             }
1344             // Return one less than the lower bound of the array.  This way,
1345             // for arrays with a lower bound of -1 we will not return -1 when the
1346             // item was not found.  And for SZArrays (the vast majority), -1 still
1347             // works for them.
1348             return lb-1;
1349         }
1350
1351         [Pure]
1352         public static int IndexOf<T>(T[] array, T value) {
1353             if (array==null) {
1354                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1355             }
1356             Contract.Ensures((Contract.Result<int>() < 0) ||
1357                 (Contract.Result<int>() >= 0 && Contract.Result<int>() < array.Length && EqualityComparer<T>.Default.Equals(value, array[Contract.Result<int>()])));
1358             Contract.EndContractBlock();
1359
1360             return IndexOf(array, value, 0, array.Length);
1361         }
1362
1363         public static int IndexOf<T>(T[] array, T value, int startIndex) {
1364             if (array==null) {
1365                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1366             }
1367             Contract.Ensures(Contract.Result<int>() < array.Length);
1368             Contract.EndContractBlock();
1369
1370             return IndexOf(array, value, startIndex, array.Length - startIndex);
1371         }
1372
1373         public static int IndexOf<T>(T[] array, T value, int startIndex, int count) {
1374             if (array==null) {
1375                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1376             }
1377
1378             if (startIndex < 0 || startIndex > array.Length ) {
1379                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
1380             }
1381
1382             if (count < 0 || count > array.Length - startIndex) {
1383                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
1384             }
1385             Contract.Ensures(Contract.Result<int>() < array.Length);
1386             Contract.EndContractBlock();
1387
1388             return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
1389         }
1390
1391         [System.Security.SecurityCritical]  // auto-generated
1392         [MethodImplAttribute(MethodImplOptions.InternalCall)]
1393         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1394         private static extern bool TrySZIndexOf(Array sourceArray, int sourceIndex, int count, Object value, out int retVal);
1395
1396
1397         // Returns the index of the last occurrence of a given value in an array.
1398         // The array is searched backwards, and the elements of the array are
1399         // compared to the given value using the Object.Equals method.
1400         //
1401         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1402         public static int LastIndexOf(Array array, Object value) {
1403             if (array==null)
1404                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1405             Contract.Ensures(Contract.Result<int>() < array.GetLowerBound(0) + array.Length);
1406             Contract.EndContractBlock();
1407             int lb = array.GetLowerBound(0);
1408             return LastIndexOf(array, value, array.Length - 1 + lb, array.Length);
1409         }
1410
1411         // Returns the index of the last occurrence of a given value in a range of
1412         // an array. The array is searched backwards, starting at index
1413         // startIndex and ending at index 0. The elements of the array are
1414         // compared to the given value using the Object.Equals method.
1415         //
1416         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1417         public static int LastIndexOf(Array array, Object value, int startIndex) {
1418             if (array == null)
1419                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1420             Contract.Ensures(Contract.Result<int>() < array.GetLowerBound(0) + array.Length);
1421             Contract.EndContractBlock();
1422             int lb = array.GetLowerBound(0);
1423             return LastIndexOf(array, value, startIndex, startIndex + 1 - lb);
1424         }
1425
1426         // Returns the index of the last occurrence of a given value in a range of
1427         // an array. The array is searched backwards, starting at index
1428         // startIndex and counting uptocount elements. The elements of
1429         // the array are compared to the given value using the Object.Equals
1430         // method.
1431         //
1432         [System.Security.SecuritySafeCritical]  // auto-generated
1433         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1434         public static int LastIndexOf(Array array, Object value, int startIndex, int count) {
1435             if (array==null)
1436                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1437             Contract.Ensures(Contract.Result<int>() < array.GetLowerBound(0) + array.Length);
1438             Contract.EndContractBlock();
1439             int lb = array.GetLowerBound(0);
1440             if (array.Length == 0) {
1441                 return lb-1;
1442             }
1443
1444             if (startIndex < lb || startIndex >= array.Length + lb)
1445                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
1446             if (count < 0)
1447                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
1448             if (count > startIndex - lb + 1)
1449                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.endIndex, ExceptionResource.ArgumentOutOfRange_EndIndexStartIndex);
1450             if (array.Rank != 1)
1451                 ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
1452
1453             // Try calling a quick native method to handle primitive types.
1454             int retVal;
1455             bool r = TrySZLastIndexOf(array, startIndex, count, value, out retVal);
1456             if (r)
1457                 return retVal;
1458
1459             Object[] objArray = array as Object[];
1460             int endIndex = startIndex - count + 1;
1461             if (objArray!=null) {
1462                 if (value == null) {
1463                     for (int i = startIndex; i >= endIndex; i--) {
1464                         if (objArray[i] == null) return i;
1465                     }
1466                 }
1467                 else {
1468                     for (int i = startIndex; i >= endIndex; i--) {
1469                         Object obj = objArray[i];
1470                         if (obj != null && obj.Equals(value)) return i;
1471                     }
1472                 }
1473             }
1474             else {
1475                 for (int i = startIndex; i >= endIndex; i--) {
1476                     Object obj = array.GetValue(i);
1477                     if( obj == null) {
1478                         if(value == null) return i;
1479                     }
1480                     else {
1481                         if( obj.Equals(value)) return i;
1482                     }
1483                 }
1484             }
1485             return lb-1;  // Return lb-1 for arrays with negative lower bounds.
1486         }
1487
1488         public static int LastIndexOf<T>(T[] array, T value) {
1489             if (array==null) {
1490                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1491             }
1492             Contract.Ensures(Contract.Result<int>() < array.Length);
1493             Contract.EndContractBlock();
1494
1495             return LastIndexOf(array, value, array.Length - 1, array.Length);
1496         }
1497
1498         public static int LastIndexOf<T>(T[] array, T value, int startIndex) {
1499             if (array==null) {
1500                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1501             }
1502             Contract.Ensures(Contract.Result<int>() < array.Length);
1503             Contract.EndContractBlock();
1504             // if array is empty and startIndex is 0, we need to pass 0 as count
1505             return LastIndexOf(array, value, startIndex, (array.Length == 0)? 0 : (startIndex + 1));
1506         }
1507
1508         public static int LastIndexOf<T>(T[] array, T value, int startIndex, int count) {
1509             if (array==null) {
1510                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1511             }
1512             Contract.Ensures(Contract.Result<int>() < array.Length);
1513             Contract.EndContractBlock();
1514
1515             if(array.Length == 0) {
1516                 //
1517                 // Special case for 0 length List
1518                 // accept -1 and 0 as valid startIndex for compablility reason.
1519                 //
1520                 if( startIndex != -1 && startIndex != 0) {
1521                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
1522                 }
1523
1524                 // only 0 is a valid value for count if array is empty
1525                 if( count != 0) {
1526                     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
1527                 }
1528                 return -1;
1529             }
1530
1531             // Make sure we're not out of range
1532             if ( startIndex < 0 || startIndex >= array.Length) {
1533                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
1534             }
1535
1536             // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
1537             if (count < 0 || startIndex - count + 1 < 0) {
1538                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
1539             }
1540
1541             return EqualityComparer<T>.Default.LastIndexOf(array, value, startIndex, count);
1542         }
1543
1544         [System.Security.SecurityCritical]  // auto-generated
1545         [MethodImplAttribute(MethodImplOptions.InternalCall)]
1546         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
1547         private static extern bool TrySZLastIndexOf(Array sourceArray, int sourceIndex, int count, Object value, out int retVal);
1548
1549
1550         // Reverses all elements of the given array. Following a call to this
1551         // method, an element previously located at index i will now be
1552         // located at index length - i - 1, where length is the
1553         // length of the array.
1554         //
1555         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1556         public static void Reverse(Array array) {
1557             if (array==null)
1558                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1559             Contract.EndContractBlock();
1560             Reverse(array, array.GetLowerBound(0), array.Length);
1561         }
1562
1563         // Reverses the elements in a range of an array. Following a call to this
1564         // method, an element in the range given by index and count
1565         // which was previously located at index i will now be located at
1566         // index index + (index + count - i - 1).
1567         // Reliability note: This may fail because it may have to box objects.
1568         //
1569         [System.Security.SecuritySafeCritical]  // auto-generated
1570         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1571         public static void Reverse(Array array, int index, int length) {
1572             if (array==null)
1573                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1574             int lowerBound = array.GetLowerBound(0);
1575             if (index < lowerBound)
1576                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1577             if (length < 0)
1578                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
1579
1580             if (array.Length - (index - lowerBound) < length)
1581                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
1582             if (array.Rank != 1)
1583                 ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
1584             Contract.EndContractBlock();
1585
1586             bool r = TrySZReverse(array, index, length);
1587             if (r)
1588                 return;
1589
1590             int i = index;
1591             int j = index + length - 1;
1592             Object[] objArray = array as Object[];
1593             if (objArray!=null) {
1594                 while (i < j) {
1595                     Object temp = objArray[i];
1596                     objArray[i] = objArray[j];
1597                     objArray[j] = temp;
1598                     i++;
1599                     j--;
1600                 }
1601             }
1602             else {
1603                 while (i < j) {
1604                     Object temp = array.GetValue(i);
1605                     array.SetValue(array.GetValue(j), i);
1606                     array.SetValue(temp, j);
1607                     i++;
1608                     j--;
1609                 }
1610             }
1611         }
1612
1613         [System.Security.SecurityCritical]  // auto-generated
1614         [MethodImplAttribute(MethodImplOptions.InternalCall)]
1615         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1616         private static extern bool TrySZReverse(Array array, int index, int count);
1617
1618         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1619         public static void Reverse<T>(T[] array)
1620         {
1621             if (array == null)
1622                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1623             Contract.EndContractBlock();
1624             Reverse(array, 0, array.Length);
1625         }
1626
1627         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1628         public static void Reverse<T>(T[] array, int index, int length)
1629         {
1630             if (array == null)
1631                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1632             if (index < 0)
1633                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1634             if (length < 0)
1635                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
1636             if (array.Length - index < length)
1637                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
1638             Contract.EndContractBlock();
1639
1640             int i = index;
1641             int j = index + length - 1;
1642             while (i < j)
1643             {
1644                 T temp = array[i];
1645                 array[i] = array[j];
1646                 array[j] = temp;
1647                 i++;
1648                 j--;
1649             }
1650         }
1651
1652         // Sorts the elements of an array. The sort compares the elements to each
1653         // other using the IComparable interface, which must be implemented
1654         // by all elements of the array.
1655         //
1656         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1657         public static void Sort(Array array) {
1658             if (array==null)
1659                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1660             Contract.EndContractBlock();
1661             Sort(array, null, array.GetLowerBound(0), array.Length, null);
1662         }
1663
1664         // Sorts the elements of two arrays based on the keys in the first array.
1665         // Elements in the keys array specify the sort keys for
1666         // corresponding elements in the items array. The sort compares the
1667         // keys to each other using the IComparable interface, which must be
1668         // implemented by all elements of the keys array.
1669         //
1670         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1671         public static void Sort(Array keys, Array items) {
1672             if (keys==null)
1673                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
1674             Contract.EndContractBlock();
1675             Sort(keys, items, keys.GetLowerBound(0), keys.Length, null);
1676         }
1677
1678         // Sorts the elements in a section of an array. The sort compares the
1679         // elements to each other using the IComparable interface, which
1680         // must be implemented by all elements in the given section of the array.
1681         //
1682         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1683         public static void Sort(Array array, int index, int length) {
1684             Sort(array, null, index, length, null);
1685         }
1686
1687         // Sorts the elements in a section of two arrays based on the keys in the
1688         // first array. Elements in the keys array specify the sort keys for
1689         // corresponding elements in the items array. The sort compares the
1690         // keys to each other using the IComparable interface, which must be
1691         // implemented by all elements of the keys array.
1692         //
1693         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1694         public static void Sort(Array keys, Array items, int index, int length) {
1695             Sort(keys, items, index, length, null);
1696         }
1697
1698         // Sorts the elements of an array. The sort compares the elements to each
1699         // other using the given IComparer interface. If comparer is
1700         // null, the elements are compared to each other using the
1701         // IComparable interface, which in that case must be implemented by
1702         // all elements of the array.
1703         //
1704         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1705         public static void Sort(Array array, IComparer comparer) {
1706             if (array==null)
1707                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1708             Contract.EndContractBlock();
1709             Sort(array, null, array.GetLowerBound(0), array.Length, comparer);
1710         }
1711
1712         // Sorts the elements of two arrays based on the keys in the first array.
1713         // Elements in the keys array specify the sort keys for
1714         // corresponding elements in the items array. The sort compares the
1715         // keys to each other using the given IComparer interface. If
1716         // comparer is null, the elements are compared to each other using
1717         // the IComparable interface, which in that case must be implemented
1718         // by all elements of the keys array.
1719         //
1720         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1721         public static void Sort(Array keys, Array items, IComparer comparer) {
1722             if (keys==null)
1723                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
1724             Contract.EndContractBlock();
1725             Sort(keys, items, keys.GetLowerBound(0), keys.Length, comparer);
1726         }
1727
1728         // Sorts the elements in a section of an array. The sort compares the
1729         // elements to each other using the given IComparer interface. If
1730         // comparer is null, the elements are compared to each other using
1731         // the IComparable interface, which in that case must be implemented
1732         // by all elements in the given section of the array.
1733         //
1734         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1735         public static void Sort(Array array, int index, int length, IComparer comparer) {
1736             Sort(array, null, index, length, comparer);
1737         }
1738
1739         // Sorts the elements in a section of two arrays based on the keys in the
1740         // first array. Elements in the keys array specify the sort keys for
1741         // corresponding elements in the items array. The sort compares the
1742         // keys to each other using the given IComparer interface. If
1743         // comparer is null, the elements are compared to each other using
1744         // the IComparable interface, which in that case must be implemented
1745         // by all elements of the given section of the keys array.
1746         //
1747         [System.Security.SecuritySafeCritical]  // auto-generated
1748         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1749         public static void Sort(Array keys, Array items, int index, int length, IComparer comparer) {
1750             if (keys==null)
1751                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
1752             if (keys.Rank != 1 || (items != null && items.Rank != 1))
1753                 ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
1754             int keysLowerBound = keys.GetLowerBound(0);
1755             if (items != null && keysLowerBound != items.GetLowerBound(0))
1756                 ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_LowerBoundsMustMatch);
1757             if (index < keysLowerBound)
1758                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1759             if (length < 0)
1760                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
1761
1762             if (keys.Length - (index - keysLowerBound) < length || (items != null && (index - keysLowerBound) > items.Length - length))
1763                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
1764
1765             Contract.EndContractBlock();
1766
1767             if (length > 1) {
1768                 if (comparer == Comparer.Default || comparer == null) {
1769                     bool r = TrySZSort(keys, items, index, index + length - 1);
1770                     if (r)
1771                         return;
1772                 }
1773
1774                 Object[] objKeys = keys as Object[];
1775                 Object[] objItems = null;
1776                 if (objKeys != null)
1777                     objItems = items as Object[];
1778                 if (objKeys != null && (items==null || objItems != null)) {
1779                     SorterObjectArray sorter = new SorterObjectArray(objKeys, objItems, comparer);
1780                     sorter.Sort(index, length);
1781                 }
1782                 else {
1783                     SorterGenericArray sorter = new SorterGenericArray(keys, items, comparer);
1784                     sorter.Sort(index, length);
1785                 }
1786             }
1787         }
1788
1789         [System.Security.SecurityCritical]  // auto-generated
1790         [MethodImplAttribute(MethodImplOptions.InternalCall)]
1791         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1792         private static extern bool TrySZSort(Array keys, Array items, int left, int right);
1793
1794         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1795         public static void Sort<T>(T[] array) {
1796             if (array==null)
1797                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1798             Contract.EndContractBlock();
1799             Sort<T>(array, 0, array.Length, null);
1800         }
1801
1802         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1803         public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items) {
1804             if (keys==null)
1805                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
1806             Contract.EndContractBlock();
1807             Sort<TKey, TValue>(keys, items, 0, keys.Length, null);
1808         }
1809
1810         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1811         public static void Sort<T>(T[] array, int index, int length) {
1812             Sort<T>(array, index, length, null);
1813         }
1814
1815         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1816         public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length) {
1817             Sort<TKey, TValue>(keys, items, index, length, null);
1818         }
1819
1820         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1821         public static void Sort<T>(T[] array, System.Collections.Generic.IComparer<T> comparer) {
1822             if (array == null)
1823                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1824             Contract.EndContractBlock();
1825             Sort<T>(array, 0, array.Length, comparer);
1826         }
1827
1828         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1829         public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, System.Collections.Generic.IComparer<TKey> comparer) {
1830             if (keys==null)
1831                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
1832             Contract.EndContractBlock();
1833             Sort<TKey, TValue>(keys, items, 0, keys.Length, comparer);
1834         }
1835
1836         [System.Security.SecuritySafeCritical]  // auto-generated
1837         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1838         public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer) {
1839             if (array==null)
1840                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1841             if (index < 0)
1842                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1843             if (length < 0)
1844                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
1845             if (array.Length - index < length)
1846                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
1847             Contract.EndContractBlock();
1848
1849             if (length > 1) {
1850                 if ( comparer == null || comparer == Comparer<T>.Default ) {
1851                     if(TrySZSort(array, null, index, index + length - 1)) {
1852                         return;
1853                     }
1854                 }
1855
1856                 ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
1857             }
1858         }
1859
1860         [System.Security.SecuritySafeCritical]  // auto-generated
1861         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
1862         public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, System.Collections.Generic.IComparer<TKey> comparer) {
1863             if (keys==null)
1864                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
1865             if (index < 0)
1866                 ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
1867             if (length < 0)
1868                 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
1869             if (keys.Length - index < length || (items != null && index > items.Length - length))
1870                 ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
1871             Contract.EndContractBlock();
1872
1873             if (length > 1) {
1874                 if ( comparer == null || comparer == Comparer<TKey>.Default ) {
1875                     if(TrySZSort(keys, items, index, index + length - 1)) {
1876                         return;
1877                     }
1878                 }
1879
1880                 if (items == null)
1881                 {
1882                     Sort<TKey>(keys, index, length, comparer);
1883                     return;
1884                 }
1885
1886                 ArraySortHelper<TKey, TValue>.Default.Sort(keys, items, index, length, comparer);
1887             }
1888         }
1889
1890         public static void Sort<T>(T[] array, Comparison<T> comparison) {
1891             if( array == null) {
1892                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1893             }
1894
1895             if( comparison == null) {
1896                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparison);
1897             }
1898             Contract.EndContractBlock();
1899
1900             IComparer<T> comparer = Comparer<T>.Create(comparison);
1901             Array.Sort(array, comparer);
1902         }
1903
1904         public static bool TrueForAll<T>(T[] array, Predicate<T> match) {
1905             if( array == null) {
1906                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
1907             }
1908
1909             if( match == null) {
1910                 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
1911             }
1912             Contract.EndContractBlock();
1913
1914             for(int i = 0 ; i < array.Length; i++) {
1915                 if( !match(array[i])) {
1916                     return false;
1917                 }
1918             }
1919             return true;
1920         }
1921
1922
1923         // Private value type used by the Sort methods.
1924         private struct SorterObjectArray
1925         {
1926             private Object[] keys;
1927             private Object[] items;
1928             private IComparer comparer;
1929
1930             internal SorterObjectArray(Object[] keys, Object[] items, IComparer comparer) {
1931                 if (comparer == null) comparer = Comparer.Default;
1932                 this.keys = keys;
1933                 this.items = items;
1934                 this.comparer = comparer;
1935             }
1936
1937             internal void SwapIfGreaterWithItems(int a, int b)
1938             {
1939                 if (a != b)
1940                 {
1941                     if (comparer.Compare(keys[a], keys[b]) > 0)
1942                     {
1943                         Object temp = keys[a];
1944                         keys[a] = keys[b];
1945                         keys[b] = temp;
1946                         if (items != null)
1947                         {
1948                             Object item = items[a];
1949                             items[a] = items[b];
1950                             items[b] = item;
1951                         }
1952                     }
1953                 }
1954             }
1955
1956             private void Swap(int i, int j)
1957             {
1958                 Object t = keys[i];
1959                 keys[i] = keys[j];
1960                 keys[j] = t;
1961
1962                 if (items != null)
1963                 {
1964                     Object item = items[i];
1965                     items[i] = items[j];
1966                     items[j] = item;
1967                 }
1968             }
1969
1970             internal void Sort(int left, int length)
1971             {
1972 #if FEATURE_CORECLR
1973                 // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
1974                 // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
1975                 // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
1976
1977                 IntrospectiveSort(left, length);
1978 #else
1979                 if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
1980                 {
1981                     IntrospectiveSort(left, length);
1982                 }
1983                 else
1984                 {
1985                     DepthLimitedQuickSort(left, length + left - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
1986                 }
1987 #endif
1988             }
1989
1990 #if !FEATURE_CORECLR
1991             private void DepthLimitedQuickSort(int left, int right, int depthLimit)
1992             {
1993                 // Can use the much faster jit helpers for array access.
1994                 do
1995                 {
1996                     if (depthLimit == 0)
1997                     {
1998                         // Add a try block here to detect IComparers (or their
1999                         // underlying IComparables, etc) that are bogus.
2000                         try
2001                         {
2002                             Heapsort(left, right);
2003                             return;
2004                         }
2005                         catch (IndexOutOfRangeException)
2006                         {
2007                             ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_BogusIComparer, ExceptionArgument.comparer);
2008                         }
2009                         catch (Exception e)
2010                         {
2011                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
2012                         }
2013                     }
2014
2015                     int i = left;
2016                     int j = right;
2017
2018                     // pre-sort the low, middle (pivot), and high values in place.
2019                     // this improves performance in the face of already sorted data, or
2020                     // data that is made up of multiple sorted runs appended together.
2021                     int middle = GetMedian(i, j);
2022
2023                     // Add a try block here to detect IComparers (or their
2024                     // underlying IComparables, etc) that are bogus.
2025                     try
2026                     {
2027                         SwapIfGreaterWithItems(i, middle); // swap the low with the mid point
2028                         SwapIfGreaterWithItems(i, j);      // swap the low with the high
2029                         SwapIfGreaterWithItems(middle, j); // swap the middle with the high
2030                     }
2031                     catch (Exception e)
2032                     {
2033                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
2034                     }
2035                     Object x = keys[middle];
2036                     do
2037                     {
2038                         // Add a try block here to detect IComparers (or their
2039                         // underlying IComparables, etc) that are bogus.
2040                         try
2041                         {
2042                             while (comparer.Compare(keys[i], x) < 0) i++;
2043                             while (comparer.Compare(x, keys[j]) < 0) j--;
2044                         }
2045                         catch (IndexOutOfRangeException)
2046                         {
2047                             ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_BogusIComparer, ExceptionArgument.comparer);
2048                         }
2049                         catch (Exception e)
2050                         {
2051                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
2052                         }
2053                         Contract.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
2054                         if (i > j) break;
2055                         if (i < j)
2056                         {
2057                             Object key = keys[i];
2058                             keys[i] = keys[j];
2059                             keys[j] = key;
2060                             if (items != null)
2061                             {
2062                                 Object item = items[i];
2063                                 items[i] = items[j];
2064                                 items[j] = item;
2065                             }
2066                         }
2067                         i++;
2068                         j--;
2069                     } while (i <= j);
2070
2071                     // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
2072                     // following calls recursively sort the smaller half.  So we subtract one from depthLimit here so
2073                     // both sorts see the new value.
2074                     depthLimit--;
2075
2076                     if (j - left <= right - i)
2077                     {
2078                         if (left < j) DepthLimitedQuickSort(left, j, depthLimit);
2079                         left = i;
2080                     }
2081                     else
2082                     {
2083                         if (i < right) DepthLimitedQuickSort(i, right, depthLimit);
2084                         right = j;
2085                     }
2086                 } while (left < right);
2087             }
2088 #endif
2089
2090             private void IntrospectiveSort(int left, int length)
2091             {
2092                 if (length < 2)
2093                     return;
2094
2095                 try
2096                 {
2097                     IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
2098                 }
2099                 catch (IndexOutOfRangeException)
2100                 {
2101                     IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
2102                 }
2103                 catch (Exception e)
2104                 {
2105                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
2106                 }
2107             }
2108
2109             private void IntroSort(int lo, int hi, int depthLimit)
2110             {
2111                 while (hi > lo)
2112                 {
2113                     int partitionSize = hi - lo + 1;
2114                     if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
2115                     {
2116                         if (partitionSize == 1)
2117                         {
2118                             return;
2119                         }
2120                         if (partitionSize == 2)
2121                         {
2122                             SwapIfGreaterWithItems(lo, hi);
2123                             return;
2124                         }
2125                         if (partitionSize == 3)
2126                         {
2127                             SwapIfGreaterWithItems(lo, hi-1);
2128                             SwapIfGreaterWithItems(lo, hi);
2129                             SwapIfGreaterWithItems(hi-1, hi);
2130                             return;
2131                         }
2132
2133                         InsertionSort(lo, hi);
2134                         return;
2135                     }
2136
2137                     if (depthLimit == 0)
2138                     {
2139                         Heapsort(lo, hi);
2140                         return;
2141                     }
2142                     depthLimit--;
2143
2144                     int p = PickPivotAndPartition(lo, hi);
2145                     IntroSort(p + 1, hi, depthLimit);
2146                     hi = p - 1;
2147                 }
2148             }
2149
2150             private int PickPivotAndPartition(int lo, int hi)
2151             {
2152                 // Compute median-of-three.  But also partition them, since we've done the comparison.
2153                 int mid = lo + (hi - lo) / 2;
2154                 // Sort lo, mid and hi appropriately, then pick mid as the pivot.
2155                 SwapIfGreaterWithItems(lo, mid);
2156                 SwapIfGreaterWithItems(lo, hi);
2157                 SwapIfGreaterWithItems(mid, hi);
2158
2159                 Object pivot = keys[mid];
2160                 Swap(mid, hi - 1);
2161                 int left = lo, right = hi - 1;  // We already partitioned lo and hi and put the pivot in hi - 1.  And we pre-increment & decrement below.
2162
2163                 while (left < right)
2164                 {
2165                     while (comparer.Compare(keys[++left], pivot) < 0) ;
2166                     while (comparer.Compare(pivot, keys[--right]) < 0) ;
2167
2168                     if(left >= right)
2169                         break;
2170
2171                     Swap(left, right);
2172                 }
2173
2174                 // Put pivot in the right location.
2175                 Swap(left, (hi - 1));
2176                 return left;
2177             }
2178
2179             private void Heapsort(int lo, int hi)
2180             {
2181                 int n = hi - lo + 1;
2182                 for (int i = n / 2; i >= 1; i = i - 1)
2183                 {
2184                     DownHeap(i, n, lo);
2185                 }
2186                 for (int i = n; i > 1; i = i - 1)
2187                 {
2188                     Swap(lo, lo + i - 1);
2189
2190                     DownHeap(1, i - 1, lo);
2191                 }
2192             }
2193
2194             private void DownHeap(int i, int n, int lo)
2195             {
2196                 Object d = keys[lo + i - 1];
2197                 Object dt = (items != null) ? items[lo + i - 1] : null;
2198                 int child;
2199                 while (i <= n / 2)
2200                 {
2201                     child = 2 * i;
2202                     if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
2203                     {
2204                         child++;
2205                     }
2206                     if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
2207                         break;
2208                     keys[lo + i - 1] = keys[lo + child - 1];
2209                     if(items != null)
2210                         items[lo + i - 1] = items[lo + child - 1];
2211                     i = child;
2212                 }
2213                 keys[lo + i - 1] = d;
2214                 if (items != null)
2215                     items[lo + i - 1] = dt;
2216             }
2217
2218             private void InsertionSort(int lo, int hi)
2219             {
2220                 int i, j;
2221                 Object t, ti;
2222                 for (i = lo; i < hi; i++)
2223                 {
2224                     j = i;
2225                     t = keys[i + 1];
2226                     ti = (items != null) ? items[i + 1] : null;
2227                     while (j >= lo && comparer.Compare(t, keys[j]) < 0)
2228                     {
2229                         keys[j + 1] = keys[j];
2230                         if(items != null)
2231                             items[j + 1] = items[j];
2232                         j--;
2233                     }
2234                     keys[j + 1] = t;
2235                     if(items != null)
2236                         items[j + 1] = ti;
2237                 }
2238             }
2239         }
2240
2241         // Private value used by the Sort methods for instances of Array.
2242         // This is slower than the one for Object[], since we can't use the JIT helpers
2243         // to access the elements.  We must use GetValue & SetValue.
2244         private struct SorterGenericArray
2245         {
2246             private Array keys;
2247             private Array items;
2248             private IComparer comparer;
2249
2250             internal SorterGenericArray(Array keys, Array items, IComparer comparer)
2251             {
2252                 if (comparer == null) comparer = Comparer.Default;
2253                 this.keys = keys;
2254                 this.items = items;
2255                 this.comparer = comparer;
2256             }
2257
2258             internal void SwapIfGreaterWithItems(int a, int b)
2259             {
2260                 if (a != b)
2261                 {
2262                     if (comparer.Compare(keys.GetValue(a), keys.GetValue(b)) > 0)
2263                     {
2264                         Object key = keys.GetValue(a);
2265                         keys.SetValue(keys.GetValue(b), a);
2266                         keys.SetValue(key, b);
2267                         if (items != null)
2268                         {
2269                             Object item = items.GetValue(a);
2270                             items.SetValue(items.GetValue(b), a);
2271                             items.SetValue(item, b);
2272                         }
2273                     }
2274                 }
2275             }
2276
2277             private void Swap(int i, int j)
2278             {
2279                 Object t1 = keys.GetValue(i);
2280                 keys.SetValue(keys.GetValue(j), i);
2281                 keys.SetValue(t1, j);
2282
2283                 if(items != null)
2284                 {
2285                     Object t2 = items.GetValue(i);
2286                     items.SetValue(items.GetValue(j), i);
2287                     items.SetValue(t2, j);
2288                 }
2289             }
2290
2291             internal void Sort(int left, int length)
2292             {
2293 #if FEATURE_CORECLR
2294                 // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade
2295                 // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka
2296                 // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort.
2297
2298                 IntrospectiveSort(left, length);
2299 #else
2300                 if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
2301                 {
2302                     IntrospectiveSort(left, length);
2303                 }
2304                 else
2305                 {
2306                     DepthLimitedQuickSort(left, length + left - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold);
2307                 }
2308 #endif
2309             }
2310
2311 #if !FEATURE_CORECLR
2312             private void DepthLimitedQuickSort(int left, int right, int depthLimit)
2313             {
2314                 // Must use slow Array accessors (GetValue & SetValue)
2315                 do
2316                 {
2317                     if (depthLimit == 0)
2318                     {
2319                         // Add a try block here to detect IComparers (or their
2320                         // underlying IComparables, etc) that are bogus.
2321                         try
2322                         {
2323                             Heapsort(left, right);
2324                             return;
2325                         }
2326                         catch (IndexOutOfRangeException)
2327                         {
2328                             ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_BogusIComparer, ExceptionArgument.comparer);
2329                         }
2330                         catch (Exception e)
2331                         {
2332                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
2333                         }
2334                     }
2335
2336                     int i = left;
2337                     int j = right;
2338
2339                     // pre-sort the low, middle (pivot), and high values in place.
2340                     // this improves performance in the face of already sorted data, or
2341                     // data that is made up of multiple sorted runs appended together.
2342                     int middle = GetMedian(i, j);
2343                     try
2344                     {
2345                         SwapIfGreaterWithItems(i, middle); // swap the low with the mid point
2346                         SwapIfGreaterWithItems(i, j);      // swap the low with the high
2347                         SwapIfGreaterWithItems(middle, j); // swap the middle with the high
2348                     }
2349                     catch (Exception e)
2350                     {
2351                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
2352                     }
2353
2354                     Object x = keys.GetValue(middle);
2355                     do
2356                     {
2357                         // Add a try block here to detect IComparers (or their
2358                         // underlying IComparables, etc) that are bogus.
2359                         try
2360                         {
2361                             while (comparer.Compare(keys.GetValue(i), x) < 0) i++;
2362                             while (comparer.Compare(x, keys.GetValue(j)) < 0) j--;
2363                         }
2364                         catch (IndexOutOfRangeException)
2365                         {
2366                             ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_BogusIComparer, ExceptionArgument.comparer);
2367                         }
2368                         catch (Exception e)
2369                         {
2370                             ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
2371                         }
2372                         Contract.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
2373                         if (i > j) break;
2374                         if (i < j)
2375                         {
2376                             Object key = keys.GetValue(i);
2377                             keys.SetValue(keys.GetValue(j), i);
2378                             keys.SetValue(key, j);
2379                             if (items != null)
2380                             {
2381                                 Object item = items.GetValue(i);
2382                                 items.SetValue(items.GetValue(j), i);
2383                                 items.SetValue(item, j);
2384                             }
2385                         }
2386                         if (i != Int32.MaxValue) ++i;
2387                         if (j != Int32.MinValue) --j;
2388                     } while (i <= j);
2389
2390                     // The next iteration of the while loop is to "recursively" sort the larger half of the array and the
2391                     // following calls recursively sort the smaller half.  So we subtract one from depthLimit here so
2392                     // both sorts see the new value.
2393                     depthLimit--;
2394
2395                     if (j - left <= right - i)
2396                     {
2397                         if (left < j) DepthLimitedQuickSort(left, j, depthLimit);
2398                         left = i;
2399                     }
2400                     else
2401                     {
2402                         if (i < right) DepthLimitedQuickSort(i, right, depthLimit);
2403                         right = j;
2404                     }
2405                 } while (left < right);
2406             }
2407 #endif
2408
2409             private void IntrospectiveSort(int left, int length)
2410             {
2411                 if (length < 2)
2412                     return;
2413
2414                 try
2415                 {
2416                     IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
2417                 }
2418                 catch (IndexOutOfRangeException)
2419                 {
2420                     IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
2421                 }
2422                 catch (Exception e)
2423                 {
2424                     ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
2425                 }
2426             }
2427
2428             private void IntroSort(int lo, int hi, int depthLimit)
2429             {
2430                 while (hi > lo)
2431                 {
2432                     int partitionSize = hi - lo + 1;
2433                     if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
2434                     {
2435                         if (partitionSize == 1)
2436                         {
2437                             return;
2438                         }
2439                         if (partitionSize == 2)
2440                         {
2441                             SwapIfGreaterWithItems(lo, hi);
2442                             return;
2443                         }
2444                         if (partitionSize == 3)
2445                         {
2446                             SwapIfGreaterWithItems(lo, hi-1);
2447                             SwapIfGreaterWithItems(lo, hi);
2448                             SwapIfGreaterWithItems(hi-1, hi);
2449                             return;
2450                         }
2451
2452                         InsertionSort(lo, hi);
2453                         return;
2454                     }
2455
2456                     if (depthLimit == 0)
2457                     {
2458                         Heapsort(lo, hi);
2459                         return;
2460                     }
2461                     depthLimit--;
2462
2463                     int p = PickPivotAndPartition(lo, hi);
2464                     IntroSort(p + 1, hi, depthLimit);
2465                     hi = p - 1;
2466                 }
2467             }
2468
2469             private int PickPivotAndPartition(int lo, int hi)
2470             {
2471                 // Compute median-of-three.  But also partition them, since we've done the comparison.
2472                 int mid = lo + (hi - lo) / 2;
2473
2474                 SwapIfGreaterWithItems(lo, mid);
2475                 SwapIfGreaterWithItems(lo, hi);
2476                 SwapIfGreaterWithItems(mid, hi);
2477
2478                 Object pivot = keys.GetValue(mid);
2479                 Swap(mid, hi - 1);
2480                 int left = lo, right = hi - 1;  // We already partitioned lo and hi and put the pivot in hi - 1.  And we pre-increment & decrement below.
2481
2482                 while (left < right)
2483                 {
2484                     while (comparer.Compare(keys.GetValue(++left), pivot) < 0) ;
2485                     while (comparer.Compare(pivot, keys.GetValue(--right)) < 0) ;
2486
2487                     if (left >= right)
2488                         break;
2489
2490                     Swap(left, right);
2491                 }
2492
2493                 // Put pivot in the right location.
2494                 Swap(left, (hi - 1));
2495                 return left;
2496             }
2497
2498             private void Heapsort(int lo, int hi)
2499             {
2500                 int n = hi - lo + 1;
2501                 for (int i = n / 2; i >= 1; i = i - 1)
2502                 {
2503                     DownHeap(i, n, lo);
2504                 }
2505                 for (int i = n; i > 1; i = i - 1)
2506                 {
2507                     Swap(lo, lo + i - 1);
2508
2509                     DownHeap(1, i - 1, lo);
2510                 }
2511             }
2512
2513             private void DownHeap(int i, int n, int lo)
2514             {
2515                 Object d = keys.GetValue(lo + i - 1);
2516                 Object dt = (items != null)? items.GetValue(lo + i - 1) : null;
2517                 int child;
2518                 while (i <= n / 2)
2519                 {
2520                     child = 2 * i;
2521                     if (child < n && comparer.Compare(keys.GetValue(lo + child - 1), keys.GetValue(lo + child)) < 0)
2522                     {
2523                         child++;
2524                     }
2525
2526                     if (!(comparer.Compare(d, keys.GetValue(lo + child - 1)) < 0))
2527                         break;
2528
2529                     keys.SetValue(keys.GetValue(lo + child - 1), lo + i - 1);
2530                     if(items != null)
2531                         items.SetValue(items.GetValue(lo + child - 1), lo + i - 1);
2532                     i = child;
2533                 }
2534                 keys.SetValue(d, lo + i - 1);
2535                 if(items != null)
2536                     items.SetValue(dt, lo + i - 1);
2537             }
2538
2539             private void InsertionSort(int lo, int hi)
2540             {
2541                 int i, j;
2542                 Object t, dt;
2543                 for (i = lo; i < hi; i++)
2544                 {
2545                     j = i;
2546                     t = keys.GetValue(i + 1);
2547                     dt = (items != null)? items.GetValue(i + 1) : null;
2548
2549                     while (j >= lo && comparer.Compare(t, keys.GetValue(j)) < 0)
2550                     {
2551                         keys.SetValue(keys.GetValue(j), j + 1);
2552                         if(items != null)
2553                             items.SetValue(items.GetValue(j), j + 1);
2554                         j--;
2555                     }
2556
2557                     keys.SetValue(t, j + 1);
2558                     if(items != null)
2559                         items.SetValue(dt, j + 1);
2560                 }
2561             }
2562         }
2563
2564         [Serializable] private sealed class SZArrayEnumerator : IEnumerator, ICloneable
2565         {
2566             private Array _array;
2567             private int _index;
2568             private int _endIndex; // cache array length, since it's a little slow.
2569
2570             internal SZArrayEnumerator(Array array) {
2571                 Contract.Assert(array.Rank == 1 && array.GetLowerBound(0) == 0, "SZArrayEnumerator only works on single dimension arrays w/ a lower bound of zero.");
2572                 _array = array;
2573                 _index = -1;
2574                 _endIndex = array.Length;
2575             }
2576
2577             public Object Clone()
2578             {
2579                 return MemberwiseClone();
2580             }
2581
2582             public bool MoveNext() {
2583                 if (_index < _endIndex) {
2584                     _index++;
2585                     return (_index < _endIndex);
2586                 }
2587                 return false;
2588             }
2589
2590             public Object Current {
2591                 get {
2592                     if (_index < 0) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
2593                     if (_index >= _endIndex) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
2594                     return _array.GetValue(_index);
2595                 }
2596             }
2597
2598             public void Reset() {
2599                 _index = -1;
2600             }
2601         }
2602
2603         [Serializable] private sealed class ArrayEnumerator : IEnumerator, ICloneable
2604         {
2605             private Array array;
2606             private int index;
2607             private int endIndex;
2608             private int startIndex;    // Save for Reset.
2609             private int[] _indices;    // The current position in a multidim array
2610             private bool _complete;
2611
2612             internal ArrayEnumerator(Array array, int index, int count) {
2613                 this.array = array;
2614                 this.index = index - 1;
2615                 startIndex = index;
2616                 endIndex = index + count;
2617                 _indices = new int[array.Rank];
2618                 int checkForZero = 1;  // Check for dimensions of size 0.
2619                 for(int i=0; i<array.Rank; i++) {
2620                     _indices[i] = array.GetLowerBound(i);
2621                     checkForZero *= array.GetLength(i);
2622                 }
2623                 // To make MoveNext simpler, decrement least significant index.
2624                 _indices[_indices.Length-1]--;
2625                 _complete = (checkForZero == 0);
2626             }
2627
2628             private void IncArray() {
2629                 // This method advances us to the next valid array index,
2630                 // handling all the multiple dimension & bounds correctly.
2631                 // Think of it like an odometer in your car - we start with
2632                 // the last digit, increment it, and check for rollover.  If
2633                 // it rolls over, we set all digits to the right and including
2634                 // the current to the appropriate lower bound.  Do these overflow
2635                 // checks for each dimension, and if the most significant digit
2636                 // has rolled over it's upper bound, we're done.
2637                 //
2638                 int rank = array.Rank;
2639                 _indices[rank-1]++;
2640                 for(int dim=rank-1; dim>=0; dim--) {
2641                     if (_indices[dim] > array.GetUpperBound(dim)) {
2642                         if (dim==0) {
2643                             _complete = true;
2644                             break;
2645                         }
2646                         for(int j=dim; j<rank; j++)
2647                             _indices[j] = array.GetLowerBound(j);
2648                         _indices[dim-1]++;
2649                     }
2650                 }
2651             }
2652
2653             public Object Clone()
2654             {
2655                 return MemberwiseClone();
2656             }
2657
2658             public bool MoveNext() {
2659                 if (_complete) {
2660                     index = endIndex;
2661                     return false;
2662                 }
2663                 index++;
2664                 IncArray();
2665                 return !_complete;
2666             }
2667
2668             public Object Current {
2669                 get {
2670                     if (index < startIndex) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
2671                     if (_complete) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
2672                     return array.GetValue(_indices);
2673                 }
2674             }
2675
2676             public void Reset() {
2677                 index = startIndex - 1;
2678                 int checkForZero = 1;
2679                 for(int i=0; i<array.Rank; i++) {
2680                     _indices[i] = array.GetLowerBound(i);
2681                     checkForZero *= array.GetLength(i);
2682                 }
2683                 _complete = (checkForZero == 0);
2684                 // To make MoveNext simpler, decrement least significant index.
2685                 _indices[_indices.Length-1]--;
2686             }
2687         }
2688
2689
2690         // if this is an array of value classes and that value class has a default constructor
2691         // then this calls this default constructor on every element in the value class array.
2692         // otherwise this is a no-op.  Generally this method is called automatically by the compiler
2693         [System.Security.SecuritySafeCritical]  // auto-generated
2694         [MethodImplAttribute(MethodImplOptions.InternalCall)]
2695         public extern void Initialize();
2696     }
2697
2698
2699
2700
2701
2702
2703
2704     //----------------------------------------------------------------------------------------
2705     // ! READ THIS BEFORE YOU WORK ON THIS CLASS.
2706     //
2707     // The methods on this class must be written VERY carefully to avoid introducing security holes.
2708     // That's because they are invoked with special "this"! The "this" object
2709     // for all of these methods are not SZArrayHelper objects. Rather, they are of type U[]
2710     // where U[] is castable to T[]. No actual SZArrayHelper object is ever instantiated. Thus, you will
2711     // see a lot of expressions that cast "this" "T[]".
2712     //
2713     // This class is needed to allow an SZ array of type T[] to expose IList<T>,
2714     // IList<T.BaseType>, etc., etc. all the way up to IList<Object>. When the following call is
2715     // made:
2716     //
2717     //   ((IList<T>) (new U[n])).SomeIListMethod()
2718     //
2719     // the interface stub dispatcher treats this as a special case, loads up SZArrayHelper,
2720     // finds the corresponding generic method (matched simply by method name), instantiates
2721     // it for type <T> and executes it.
2722     //
2723     // The "T" will reflect the interface used to invoke the method. The actual runtime "this" will be
2724     // array that is castable to "T[]" (i.e. for primitivs and valuetypes, it will be exactly
2725     // "T[]" - for orefs, it may be a "U[]" where U derives from T.)
2726     //----------------------------------------------------------------------------------------
2727     sealed class SZArrayHelper {
2728         // It is never legal to instantiate this class.
2729         private SZArrayHelper() {
2730             Contract.Assert(false, "Hey! How'd I get here?");
2731         }
2732
2733         // -----------------------------------------------------------
2734         // ------- Implement IEnumerable<T> interface methods --------
2735         // -----------------------------------------------------------
2736         [SecuritySafeCritical]
2737         internal IEnumerator<T> GetEnumerator<T>() {
2738             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
2739             //! or you may introduce a security hole!
2740             T[] _this = JitHelpers.UnsafeCast<T[]>(this);
2741             int length = _this.Length;
2742             return length == 0 ? SZGenericArrayEnumerator<T>.Empty : new SZGenericArrayEnumerator<T>(_this, length);
2743         }
2744
2745         // -----------------------------------------------------------
2746         // ------- Implement ICollection<T> interface methods --------
2747         // -----------------------------------------------------------
2748         [SecuritySafeCritical]
2749         void CopyTo<T>(T[] array, int index) {
2750             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
2751             //! or you may introduce a security hole!
2752
2753             T[] _this = JitHelpers.UnsafeCast<T[]>(this);
2754             Array.Copy(_this, 0, array, index, _this.Length);
2755         }
2756
2757         [SecuritySafeCritical]
2758         internal int get_Count<T>() {
2759             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
2760             //! or you may introduce a security hole!
2761             T[] _this = JitHelpers.UnsafeCast<T[]>(this);
2762             return _this.Length;
2763         }
2764
2765         // -----------------------------------------------------------
2766         // ---------- Implement IList<T> interface methods -----------
2767         // -----------------------------------------------------------
2768         [SecuritySafeCritical]
2769         internal T get_Item<T>(int index) {
2770             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
2771             //! or you may introduce a security hole!
2772             T[] _this = JitHelpers.UnsafeCast<T[]>(this);
2773             if ((uint)index >= (uint)_this.Length) {
2774                 ThrowHelper.ThrowArgumentOutOfRange_IndexException();
2775             }
2776
2777             return _this[index];
2778         }
2779
2780         [SecuritySafeCritical]
2781         internal void set_Item<T>(int index, T value) {
2782             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
2783             //! or you may introduce a security hole!
2784             T[] _this = JitHelpers.UnsafeCast<T[]>(this);
2785             if ((uint)index >= (uint)_this.Length) {
2786                 ThrowHelper.ThrowArgumentOutOfRange_IndexException();
2787             }
2788
2789             _this[index] = value;
2790         }
2791
2792         void Add<T>(T value) {
2793             // Not meaningful for arrays.
2794             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
2795         }
2796
2797         [SecuritySafeCritical]
2798         bool Contains<T>(T value) {
2799             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
2800             //! or you may introduce a security hole!
2801             T[] _this = JitHelpers.UnsafeCast<T[]>(this);
2802             return Array.IndexOf(_this, value) != -1;
2803         }
2804
2805         bool get_IsReadOnly<T>() {
2806             return true;
2807         }
2808
2809         void Clear<T>() {
2810             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
2811             //! or you may introduce a security hole!
2812
2813             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ReadOnlyCollection);
2814         }
2815
2816         [SecuritySafeCritical]
2817         int IndexOf<T>(T value) {
2818             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
2819             //! or you may introduce a security hole!
2820             T[] _this = JitHelpers.UnsafeCast<T[]>(this);
2821             return Array.IndexOf(_this, value);
2822         }
2823
2824         void Insert<T>(int index, T value) {
2825             // Not meaningful for arrays
2826             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
2827         }
2828
2829         bool Remove<T>(T value) {
2830             // Not meaningful for arrays
2831             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
2832             return default(bool);
2833         }
2834
2835         void RemoveAt<T>(int index) {
2836             // Not meaningful for arrays
2837             ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
2838         }
2839
2840         // This is a normal generic Enumerator for SZ arrays. It doesn't have any of the "this" stuff
2841         // that SZArrayHelper does.
2842         //
2843         [Serializable] private sealed class SZGenericArrayEnumerator<T> : IEnumerator<T> {
2844             private T[] _array;
2845             private int _index;
2846             private int _endIndex; // cache array length, since it's a little slow.
2847
2848             // Passing -1 for endIndex so that MoveNext always returns false without mutating _index
2849             internal static readonly SZGenericArrayEnumerator<T> Empty = new SZGenericArrayEnumerator<T>(null, -1);
2850
2851             internal SZGenericArrayEnumerator(T[] array, int endIndex) {
2852                 // We allow passing null array in case of empty enumerator.
2853                 Contract.Assert(array != null || endIndex == -1, "endIndex should be -1 in the case of a null array (for the empty enumerator).");
2854                 _array = array;
2855                 _index = -1;
2856                 _endIndex = endIndex;
2857             }
2858
2859             public bool MoveNext() {
2860                 if (_index < _endIndex) {
2861                     _index++;
2862                     return (_index < _endIndex);
2863                 }
2864                 return false;
2865             }
2866
2867             public T Current {
2868                 get {
2869                     if (_index < 0) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumNotStarted);
2870                     if (_index >= _endIndex) ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumEnded);
2871                     return _array[_index];
2872                 }
2873             }
2874
2875             object IEnumerator.Current {
2876                 get {
2877                     return Current;
2878                 }
2879             }
2880
2881             void IEnumerator.Reset() {
2882                 _index = -1;
2883             }
2884
2885             public void Dispose()
2886             {
2887             }
2888         }
2889     }
2890 }
2891
2892 // Useful in number of places that return an empty byte array to avoid unnecessary memory allocation.
2893 internal static class EmptyArray<T>
2894 {
2895     public static readonly T[] Value = new T[0];
2896 }