The Labs \ Source Viewer \ SSCLI \ System \ SZArrayHelper

  1. // ==++==
  2. //
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. //
  14. // ==--==
  15. /*============================================================
  16. **
  17. ** Class:  Array
  18. **
  19. ** Purpose: Base class which can be used to access any array
  20. **
  21. ===========================================================*/
  22. namespace System
  23. {
  24.    
  25.     using System;
  26.     using System.Collections;
  27.     using System.Collections.Generic;
  28.     using System.Collections.ObjectModel;
  29.     using System.Runtime.InteropServices;
  30.     using System.Runtime.CompilerServices;
  31.     using System.Runtime.ConstrainedExecution;
  32.    
  33.     [Serializable()]
  34.     [ComVisible(true)]
  35.     public abstract class Array : ICloneable, IList
  36.     {
  37.         /// <internalonly/>
  38.         private Array()
  39.         {
  40.         }
  41.        
  42.         public static ReadOnlyCollection<T> AsReadOnly<T>(T[] array)
  43.         {
  44.             if (array == null) {
  45.                 throw new ArgumentNullException("array");
  46.             }
  47.            
  48.             // T[] implements IList<T>.
  49.             return new ReadOnlyCollection<T>(array);
  50.         }
  51.        
  52.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  53.         public static void Resize<T>(ref T[] array, int newSize)
  54.         {
  55.             if (newSize < 0)
  56.                 throw new ArgumentOutOfRangeException("newSize", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  57.            
  58.             T[] larray = array;
  59.             if (larray == null) {
  60.                 array = new T[newSize];
  61.                 return;
  62.             }
  63.            
  64.             if (larray.Length != newSize) {
  65.                 T[] newArray = new T[newSize];
  66.                 Array.Copy(larray, 0, newArray, 0, larray.Length > newSize ? newSize : larray.Length);
  67.                 array = newArray;
  68.             }
  69.         }
  70.        
  71.         // Create instance will create an array
  72.         unsafe public static Array CreateInstance(Type elementType, int length)
  73.         {
  74.             if (elementType == null)
  75.                 throw new ArgumentNullException("elementType");
  76.             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
  77.             if (t == null)
  78.                 throw new ArgumentException(Environment.GetResourceString("Arg_MustBeType"), "elementType");
  79.             if (length < 0)
  80.                 throw new ArgumentOutOfRangeException("length", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  81.             return InternalCreate((void*)t.TypeHandle.Value, 1, &length, null);
  82.         }
  83.        
  84.         unsafe public static Array CreateInstance(Type elementType, int length1, int length2)
  85.         {
  86.             if (elementType == null)
  87.                 throw new ArgumentNullException("elementType");
  88.             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
  89.             if (t == null)
  90.                 throw new ArgumentException(Environment.GetResourceString("Arg_MustBeType"), "elementType");
  91.             if (length1 < 0 || length2 < 0)
  92.                 throw new ArgumentOutOfRangeException((length1 < 0 ? "length1" : "length2"), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  93.             int* pLengths = stackalloc int[2];
  94.             pLengths[0] = length1;
  95.             pLengths[1] = length2;
  96.             return InternalCreate((void*)t.TypeHandle.Value, 2, pLengths, null);
  97.         }
  98.        
  99.         unsafe public static Array CreateInstance(Type elementType, int length1, int length2, int length3)
  100.         {
  101.             if (elementType == null)
  102.                 throw new ArgumentNullException("elementType");
  103.             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
  104.             if (t == null)
  105.                 throw new ArgumentException(Environment.GetResourceString("Arg_MustBeType"), "elementType");
  106.             if (length1 < 0 || length2 < 0 || length3 < 0) {
  107.                 string arg = "length1";
  108.                 if (length2 < 0)
  109.                     arg = "length2";
  110.                 if (length3 < 0)
  111.                     arg = "length3";
  112.                 throw new ArgumentOutOfRangeException(arg, Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  113.             }
  114.             int* pLengths = stackalloc int[3];
  115.             pLengths[0] = length1;
  116.             pLengths[1] = length2;
  117.             pLengths[2] = length3;
  118.             return InternalCreate((void*)t.TypeHandle.Value, 3, pLengths, null);
  119.         }
  120.        
  121.         unsafe public static Array CreateInstance(Type elementType, params int[] lengths)
  122.         {
  123.             if (elementType == null)
  124.                 throw new ArgumentNullException("elementType");
  125.             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
  126.             if (t == null)
  127.                 throw new ArgumentException(Environment.GetResourceString("Arg_MustBeType"), "elementType");
  128.             if (lengths == null)
  129.                 throw new ArgumentNullException("lengths");
  130.             if (lengths.Length == 0)
  131.                 throw new ArgumentException(Environment.GetResourceString("Arg_NeedAtLeast1Rank"));
  132.            
  133.             // Check to make sure the lenghts are all positive. Note that we check this here to give
  134.             // a good exception message if they are not; however we check this again inside the execution
  135.             // engine's low level allocation function after having made a copy of the array to prevent a
  136.             // malicious caller from mutating the array after this check.
  137.             for (int i = 0; i < lengths.Length; i++)
  138.                 if (lengths[i] < 0)
  139.                     throw new ArgumentOutOfRangeException("lengths[" + i + ']', Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  140.            
  141.             fixed (int* pLengths = lengths)
  142.                 return InternalCreate((void*)t.TypeHandle.Value, lengths.Length, pLengths, null);
  143.         }
  144.        
  145.         public static Array CreateInstance(Type elementType, params long[] lengths)
  146.         {
  147.             if (lengths == null) {
  148.                 throw new ArgumentNullException("lengths");
  149.             }
  150.            
  151.             int[] intLengths = new int[lengths.Length];
  152.            
  153.             for (int i = 0; i < lengths.Length; ++i) {
  154.                 long len = lengths[i];
  155.                 if (len > Int32.MaxValue || len < Int32.MinValue)
  156.                     throw new ArgumentOutOfRangeException("len", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  157.                 intLengths[i] = (int)len;
  158.             }
  159.            
  160.             return Array.CreateInstance(elementType, intLengths);
  161.         }
  162.        
  163.        
  164.         unsafe public static Array CreateInstance(Type elementType, int[] lengths, int[] lowerBounds)
  165.         {
  166.             if (elementType == null)
  167.                 throw new ArgumentNullException("elementType");
  168.             RuntimeType t = elementType.UnderlyingSystemType as RuntimeType;
  169.             if (t == null)
  170.                 throw new ArgumentException(Environment.GetResourceString("Arg_MustBeType"), "elementType");
  171.             if (lengths == null)
  172.                 throw new ArgumentNullException("lengths");
  173.             if (lowerBounds == null)
  174.                 throw new ArgumentNullException("lowerBounds");
  175.            
  176.             // Check to make sure the lenghts are all positive. Note that we check this here to give
  177.             // a good exception message if they are not; however we check this again inside the execution
  178.             // engine's low level allocation function after having made a copy of the array to prevent a
  179.             // malicious caller from mutating the array after this check.
  180.             for (int i = 0; i < lengths.Length; i++)
  181.                 if (lengths[i] < 0)
  182.                     throw new ArgumentOutOfRangeException("lengths[" + i + ']', Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  183.            
  184.             if (lengths.Length != lowerBounds.Length)
  185.                 throw new ArgumentException(Environment.GetResourceString("Arg_RanksAndBounds"));
  186.             if (lengths.Length == 0)
  187.                 throw new ArgumentException(Environment.GetResourceString("Arg_NeedAtLeast1Rank"));
  188.            
  189.             fixed (int* pLengths = lengths)
  190.                 fixed (int* pLowerBounds = lowerBounds)
  191.                     return InternalCreate((void*)t.TypeHandle.Value, lengths.Length, pLengths, pLowerBounds);
  192.         }
  193.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  194.         unsafe private static extern Array InternalCreate(void* elementType, int rank, int* pLengths, int* pLowerBounds);
  195.        
  196.         // Copies length elements from sourceArray, starting at index 0, to
  197.         // destinationArray, starting at index 0.
  198.         //
  199.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  200.         public static void Copy(Array sourceArray, Array destinationArray, int length)
  201.         {
  202.             if (sourceArray == null)
  203.                 throw new ArgumentNullException("sourceArray");
  204.             if (destinationArray == null)
  205.                 throw new ArgumentNullException("destinationArray");
  206.             Copy(sourceArray, sourceArray.GetLowerBound(0), destinationArray, destinationArray.GetLowerBound(0), length, false);
  207.         }
  208.        
  209.         // Copies length elements from sourceArray, starting at sourceIndex, to
  210.         // destinationArray, starting at destinationIndex.
  211.         //
  212.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  213.         public static void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
  214.         {
  215.             Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, false);
  216.         }
  217.        
  218.         // Reliability-wise, this method will either possibly corrupt your
  219.         // instance & might fail when called from within a CER, or if the
  220.         // reliable flag is true, it will either always succeed or always
  221.         // throw an exception with no side effects.
  222.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  223.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  224.         static internal extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);
  225.        
  226.         // Provides a strong exception guarantee - either it succeeds, or
  227.         // it throws an exception with no side effects. The arrays must be
  228.         // compatible array types based on the array element type - this
  229.         // method does not support casting, boxing, or primitive widening.
  230.         // It will up-cast, assuming the array types are correct.
  231.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  232.         public static void ConstrainedCopy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
  233.         {
  234.             Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, true);
  235.         }
  236.        
  237.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  238.         public static void Copy(Array sourceArray, Array destinationArray, long length)
  239.         {
  240.             if (length > Int32.MaxValue || length < Int32.MinValue)
  241.                 throw new ArgumentOutOfRangeException("length", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  242.            
  243.             Array.Copy(sourceArray, destinationArray, (int)length);
  244.         }
  245.        
  246.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  247.         public static void Copy(Array sourceArray, long sourceIndex, Array destinationArray, long destinationIndex, long length)
  248.         {
  249.             if (sourceIndex > Int32.MaxValue || sourceIndex < Int32.MinValue)
  250.                 throw new ArgumentOutOfRangeException("sourceIndex", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  251.             if (destinationIndex > Int32.MaxValue || destinationIndex < Int32.MinValue)
  252.                 throw new ArgumentOutOfRangeException("destinationIndex", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  253.             if (length > Int32.MaxValue || length < Int32.MinValue)
  254.                 throw new ArgumentOutOfRangeException("length", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  255.            
  256.             Array.Copy(sourceArray, (int)sourceIndex, destinationArray, (int)destinationIndex, (int)length);
  257.         }
  258.        
  259.        
  260.         // Sets length elements in array to 0 (or null for Object arrays), starting
  261.         // at index.
  262.         //
  263.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  264.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  265.         public static extern void Clear(Array array, int index, int length);
  266.        
  267.         // The various Get values...
  268.         unsafe public object GetValue(params int[] indices)
  269.         {
  270.             if (indices == null)
  271.                 throw new ArgumentNullException("indices");
  272.             if (Rank != indices.Length)
  273.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankIndices"));
  274.            
  275.             TypedReference elemref = new TypedReference();
  276.             fixed (int* pIndices = indices)
  277.                 InternalGetReference(&elemref, indices.Length, pIndices);
  278.             return TypedReference.InternalToObject(&elemref);
  279.         }
  280.        
  281.         unsafe public object GetValue(int index)
  282.         {
  283.             if (Rank != 1)
  284.                 throw new ArgumentException(Environment.GetResourceString("Arg_Need1DArray"));
  285.            
  286.             TypedReference elemref = new TypedReference();
  287.             InternalGetReference(&elemref, 1, &index);
  288.             return TypedReference.InternalToObject(&elemref);
  289.         }
  290.        
  291.         unsafe public object GetValue(int index1, int index2)
  292.         {
  293.             if (Rank != 2)
  294.                 throw new ArgumentException(Environment.GetResourceString("Arg_Need2DArray"));
  295.            
  296.             int* pIndices = stackalloc int[2];
  297.             pIndices[0] = index1;
  298.             pIndices[1] = index2;
  299.            
  300.             TypedReference elemref = new TypedReference();
  301.             InternalGetReference(&elemref, 2, pIndices);
  302.             return TypedReference.InternalToObject(&elemref);
  303.         }
  304.        
  305.         unsafe public object GetValue(int index1, int index2, int index3)
  306.         {
  307.             if (Rank != 3)
  308.                 throw new ArgumentException(Environment.GetResourceString("Arg_Need3DArray"));
  309.            
  310.             int* pIndices = stackalloc int[3];
  311.             pIndices[0] = index1;
  312.             pIndices[1] = index2;
  313.             pIndices[2] = index3;
  314.            
  315.             TypedReference elemref = new TypedReference();
  316.             InternalGetReference(&elemref, 3, pIndices);
  317.             return TypedReference.InternalToObject(&elemref);
  318.         }
  319.        
  320.         [ComVisible(false)]
  321.         public object GetValue(long index)
  322.         {
  323.             if (index > Int32.MaxValue || index < Int32.MinValue)
  324.                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  325.            
  326.             return this.GetValue((int)index);
  327.         }
  328.        
  329.         [ComVisible(false)]
  330.         public object GetValue(long index1, long index2)
  331.         {
  332.             if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
  333.                 throw new ArgumentOutOfRangeException("index1", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  334.             if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
  335.                 throw new ArgumentOutOfRangeException("index2", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  336.            
  337.             return this.GetValue((int)index1, (int)index2);
  338.         }
  339.        
  340.         [ComVisible(false)]
  341.         public object GetValue(long index1, long index2, long index3)
  342.         {
  343.             if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
  344.                 throw new ArgumentOutOfRangeException("index1", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  345.             if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
  346.                 throw new ArgumentOutOfRangeException("index2", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  347.             if (index3 > Int32.MaxValue || index3 < Int32.MinValue)
  348.                 throw new ArgumentOutOfRangeException("index3", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  349.            
  350.             return this.GetValue((int)index1, (int)index2, (int)index3);
  351.         }
  352.        
  353.         [ComVisible(false)]
  354.         public object GetValue(params long[] indices)
  355.         {
  356.             if (indices == null)
  357.                 throw new ArgumentNullException("indices");
  358.             if (Rank != indices.Length)
  359.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankIndices"));
  360.            
  361.             int[] intIndices = new int[indices.Length];
  362.            
  363.             for (int i = 0; i < indices.Length; ++i) {
  364.                 long index = indices[i];
  365.                 if (index > Int32.MaxValue || index < Int32.MinValue)
  366.                     throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  367.                 intIndices[i] = (int)index;
  368.             }
  369.            
  370.             return this.GetValue(intIndices);
  371.         }
  372.        
  373.        
  374.         unsafe public void SetValue(object value, int index)
  375.         {
  376.             if (Rank != 1)
  377.                 throw new ArgumentException(Environment.GetResourceString("Arg_Need1DArray"));
  378.            
  379.             TypedReference elemref = new TypedReference();
  380.             InternalGetReference(&elemref, 1, &index);
  381.             InternalSetValue(&elemref, value);
  382.         }
  383.        
  384.         unsafe public void SetValue(object value, int index1, int index2)
  385.         {
  386.             if (Rank != 2)
  387.                 throw new ArgumentException(Environment.GetResourceString("Arg_Need2DArray"));
  388.            
  389.             int* pIndices = stackalloc int[2];
  390.             pIndices[0] = index1;
  391.             pIndices[1] = index2;
  392.            
  393.             TypedReference elemref = new TypedReference();
  394.             InternalGetReference(&elemref, 2, pIndices);
  395.             InternalSetValue(&elemref, value);
  396.         }
  397.        
  398.         unsafe public void SetValue(object value, int index1, int index2, int index3)
  399.         {
  400.             if (Rank != 3)
  401.                 throw new ArgumentException(Environment.GetResourceString("Arg_Need3DArray"));
  402.            
  403.             int* pIndices = stackalloc int[3];
  404.             pIndices[0] = index1;
  405.             pIndices[1] = index2;
  406.             pIndices[2] = index3;
  407.            
  408.             TypedReference elemref = new TypedReference();
  409.             InternalGetReference(&elemref, 3, pIndices);
  410.             InternalSetValue(&elemref, value);
  411.         }
  412.        
  413.         unsafe public void SetValue(object value, params int[] indices)
  414.         {
  415.             if (indices == null)
  416.                 throw new ArgumentNullException("indices");
  417.             if (Rank != indices.Length)
  418.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankIndices"));
  419.            
  420.             TypedReference elemref = new TypedReference();
  421.             fixed (int* pIndices = indices)
  422.                 InternalGetReference(&elemref, indices.Length, pIndices);
  423.             InternalSetValue(&elemref, value);
  424.         }
  425.        
  426.         [ComVisible(false)]
  427.         public void SetValue(object value, long index)
  428.         {
  429.             if (index > Int32.MaxValue || index < Int32.MinValue)
  430.                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  431.            
  432.             this.SetValue(value, (int)index);
  433.         }
  434.        
  435.         [ComVisible(false)]
  436.         public void SetValue(object value, long index1, long index2)
  437.         {
  438.             if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
  439.                 throw new ArgumentOutOfRangeException("index1", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  440.             if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
  441.                 throw new ArgumentOutOfRangeException("index2", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  442.            
  443.             this.SetValue(value, (int)index1, (int)index2);
  444.         }
  445.        
  446.         [ComVisible(false)]
  447.         public void SetValue(object value, long index1, long index2, long index3)
  448.         {
  449.             if (index1 > Int32.MaxValue || index1 < Int32.MinValue)
  450.                 throw new ArgumentOutOfRangeException("index1", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  451.             if (index2 > Int32.MaxValue || index2 < Int32.MinValue)
  452.                 throw new ArgumentOutOfRangeException("index2", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  453.             if (index3 > Int32.MaxValue || index3 < Int32.MinValue)
  454.                 throw new ArgumentOutOfRangeException("index3", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  455.            
  456.             this.SetValue(value, (int)index1, (int)index2, (int)index3);
  457.         }
  458.        
  459.         [ComVisible(false)]
  460.         public void SetValue(object value, params long[] indices)
  461.         {
  462.             if (indices == null)
  463.                 throw new ArgumentNullException("indices");
  464.             if (Rank != indices.Length)
  465.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankIndices"));
  466.            
  467.             int[] intIndices = new int[indices.Length];
  468.            
  469.             for (int i = 0; i < indices.Length; ++i) {
  470.                 long index = indices[i];
  471.                 if (index > Int32.MaxValue || index < Int32.MinValue)
  472.                     throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  473.                 intIndices[i] = (int)index;
  474.             }
  475.            
  476.             this.SetValue(value, intIndices);
  477.         }
  478.        
  479.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  480.         // reference to TypedReference is banned, so have to pass result as pointer
  481.         unsafe private extern void InternalGetReference(void* elemRef, int rank, int* pIndices);
  482.        
  483.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  484.         unsafe private static extern void InternalSetValue(void* target, object value);
  485.        
  486.         public extern int Length {
  487.             [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  488.             [MethodImpl(MethodImplOptions.InternalCall)]
  489.             get;
  490.         }
  491.        
  492.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  493.         private static int GetMedian(int low, int hi)
  494.         {
  495.             BCLDebug.Assert(hi - low >= 0, "Length overflow!");
  496.             return low + ((hi - low) >> 1);
  497.         }
  498.        
  499.         // current Pivot algorithm: median-of-3
  500.         private static object GetPivotValue(IComparer comparer, Array keys, int left, int right)
  501.         {
  502.             object leftVal = keys.GetValue(left);
  503.             object medianVal = keys.GetValue(GetMedian(left, right));
  504.             object rightVal = keys.GetValue(right);
  505.             bool leftLessThanMedian;
  506.             bool medianLessThanRight;
  507.             bool rightLessThanLeft;
  508.            
  509.             try {
  510.                 leftLessThanMedian = comparer.Compare(leftVal, medianVal) <= 0;
  511.                 medianLessThanRight = comparer.Compare(medianVal, rightVal) <= 0;
  512.                 rightLessThanLeft = comparer.Compare(rightVal, leftVal) <= 0;
  513.             }
  514.             catch (Exception e) {
  515.                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  516.             }
  517.             catch {
  518.                 throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"));
  519.             }
  520.            
  521.             if (leftLessThanMedian) {
  522.                 if (medianLessThanRight)
  523.                     return medianVal;
  524.                 if (rightLessThanLeft)
  525.                     return rightVal;
  526.                 return leftVal;
  527.             }
  528.             else {
  529.                 if (!rightLessThanLeft)
  530.                     return leftVal;
  531.                 if (!medianLessThanRight)
  532.                     return medianVal;
  533.                 return rightVal;
  534.             }
  535.         }
  536.        
  537.         [ComVisible(false)]
  538.         public long LongLength {
  539.             [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  540.             get { return Length; }
  541.         }
  542.        
  543.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  544.         public extern int GetLength(int dimension);
  545.        
  546.         [ComVisible(false)]
  547.         public long GetLongLength(int dimension)
  548.         {
  549.             return GetLength(dimension);
  550.         }
  551.        
  552.         public extern int Rank {
  553.             [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  554.             [MethodImplAttribute(MethodImplOptions.InternalCall)]
  555.             get;
  556.         }
  557.        
  558.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  559.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  560.         public extern int GetUpperBound(int dimension);
  561.        
  562.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  563.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  564.         public extern int GetLowerBound(int dimension);
  565.        
  566.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
  567.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  568.         internal extern int GetDataPtrOffsetInternal();
  569.        
  570.         // Number of elements in the Array.
  571.         int ICollection.Count {
  572.             get { return Length; }
  573.         }
  574.        
  575.        
  576.         // Returns an object appropriate for synchronizing access to this
  577.         // Array.
  578.         public object SyncRoot {
  579.             get { return this; }
  580.         }
  581.        
  582.         // Is this Array read-only?
  583.         public bool IsReadOnly {
  584.             get { return false; }
  585.         }
  586.        
  587.         public bool IsFixedSize {
  588.             get { return true; }
  589.         }
  590.        
  591.         // Is this Array synchronized (i.e., thread-safe)? If you want a synchronized
  592.         // collection, you can use SyncRoot as an object to synchronize your
  593.         // collection with. You could also call GetSynchronized()
  594.         // to get a synchronized wrapper around the Array.
  595.         public bool IsSynchronized {
  596.             get { return false; }
  597.         }
  598.        
  599.        
  600.         object IList.this[int index]
  601.         {
  602.             get { return GetValue(index); }
  603.             set { SetValue(value, index); }
  604.         }
  605.        
  606.         int IList.Add(object value)
  607.         {
  608.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection"));
  609.         }
  610.        
  611.         bool IList.Contains(object value)
  612.         {
  613.             return Array.IndexOf(this, value) >= this.GetLowerBound(0);
  614.         }
  615.        
  616.         void IList.Clear()
  617.         {
  618.             Array.Clear(this, 0, this.Length);
  619.         }
  620.        
  621.         int IList.IndexOf(object value)
  622.         {
  623.             return Array.IndexOf(this, value);
  624.         }
  625.        
  626.         void IList.Insert(int index, object value)
  627.         {
  628.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection"));
  629.         }
  630.        
  631.         void IList.Remove(object value)
  632.         {
  633.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection"));
  634.         }
  635.        
  636.         void IList.RemoveAt(int index)
  637.         {
  638.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection"));
  639.         }
  640.        
  641.         // Make a new array which is a deep copy of the original array.
  642.         //
  643.         public object Clone()
  644.         {
  645.             return MemberwiseClone();
  646.         }
  647.        
  648.         // Searches an array for a given element using a binary search algorithm.
  649.         // Elements of the array are compared to the search value using the
  650.         // IComparable interface, which must be implemented by all elements
  651.         // of the array and the given search value. This method assumes that the
  652.         // array is already sorted according to the IComparable interface;
  653.         // if this is not the case, the result will be incorrect.
  654.         //
  655.         // The method returns the index of the given value in the array. If the
  656.         // array does not contain the given value, the method returns a negative
  657.         // integer. The bitwise complement operator (~) can be applied to a
  658.         // negative result to produce the index of the first element (if any) that
  659.         // is larger than the given search value.
  660.         //
  661.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  662.         public static int BinarySearch(Array array, object value)
  663.         {
  664.             if (array == null)
  665.                 throw new ArgumentNullException("array");
  666.             int lb = array.GetLowerBound(0);
  667.             return BinarySearch(array, lb, array.Length, value, null);
  668.         }
  669.        
  670.         // Searches a section of an array for a given element using a binary search
  671.         // algorithm. Elements of the array are compared to the search value using
  672.         // the IComparable interface, which must be implemented by all
  673.         // elements of the array and the given search value. This method assumes
  674.         // that the array is already sorted according to the IComparable
  675.         // interface; if this is not the case, the result will be incorrect.
  676.         //
  677.         // The method returns the index of the given value in the array. If the
  678.         // array does not contain the given value, the method returns a negative
  679.         // integer. The bitwise complement operator (~) can be applied to a
  680.         // negative result to produce the index of the first element (if any) that
  681.         // is larger than the given search value.
  682.         //
  683.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  684.         public static int BinarySearch(Array array, int index, int length, object value)
  685.         {
  686.             return BinarySearch(array, index, length, value, null);
  687.         }
  688.        
  689.         // Searches an array for a given element using a binary search algorithm.
  690.         // Elements of the array are compared to the search value using the given
  691.         // IComparer interface. If comparer is null, elements of the
  692.         // array are compared to the search value using the IComparable
  693.         // interface, which in that case must be implemented by all elements of the
  694.         // array and the given search value. This method assumes that the array is
  695.         // already sorted; if this is not the case, the result will be incorrect.
  696.         //
  697.         // The method returns the index of the given value in the array. If the
  698.         // array does not contain the given value, the method returns a negative
  699.         // integer. The bitwise complement operator (~) can be applied to a
  700.         // negative result to produce the index of the first element (if any) that
  701.         // is larger than the given search value.
  702.         //
  703.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  704.         public static int BinarySearch(Array array, object value, IComparer comparer)
  705.         {
  706.             if (array == null)
  707.                 throw new ArgumentNullException("array");
  708.             int lb = array.GetLowerBound(0);
  709.             return BinarySearch(array, lb, array.Length, value, comparer);
  710.         }
  711.        
  712.         // Searches a section of an array for a given element using a binary search
  713.         // algorithm. Elements of the array are compared to the search value using
  714.         // the given IComparer interface. If comparer is null,
  715.         // elements of the array are compared to the search value using the
  716.         // IComparable interface, which in that case must be implemented by
  717.         // all elements of the array and the given search value. This method
  718.         // assumes that the array is already sorted; if this is not the case, the
  719.         // result will be incorrect.
  720.         //
  721.         // The method returns the index of the given value in the array. If the
  722.         // array does not contain the given value, the method returns a negative
  723.         // integer. The bitwise complement operator (~) can be applied to a
  724.         // negative result to produce the index of the first element (if any) that
  725.         // is larger than the given search value.
  726.         //
  727.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  728.         public static int BinarySearch(Array array, int index, int length, object value, IComparer comparer)
  729.         {
  730.             if (array == null)
  731.                 throw new ArgumentNullException("array");
  732.             int lb = array.GetLowerBound(0);
  733.             if (index < lb || length < 0)
  734.                 throw new ArgumentOutOfRangeException((index < lb ? "index" : "length"), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  735.             if (array.Length - (index - lb) < length)
  736.                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  737.             if (array.Rank != 1)
  738.                 throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
  739.            
  740.             if (comparer == null)
  741.                 comparer = Comparer.Default;
  742.             if (comparer == Comparer.Default) {
  743.                 int retval;
  744.                 bool r = TrySZBinarySearch(array, index, length, value, out retval);
  745.                 if (r)
  746.                     return retval;
  747.             }
  748.            
  749.             int lo = index;
  750.             int hi = index + length - 1;
  751.             object[] objArray = array as object[];
  752.             if (objArray != null) {
  753.                 while (lo <= hi) {
  754.                     // i might overflow if lo and hi are both large positive numbers.
  755.                     int i = GetMedian(lo, hi);
  756.                    
  757.                     int c;
  758.                     try {
  759.                         c = comparer.Compare(objArray[i], value);
  760.                     }
  761.                     catch (Exception e) {
  762.                         throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  763.                     }
  764.                     catch {
  765.                         throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"));
  766.                     }
  767.                     if (c == 0)
  768.                         return i;
  769.                     if (c < 0) {
  770.                         lo = i + 1;
  771.                     }
  772.                     else {
  773.                         hi = i - 1;
  774.                     }
  775.                 }
  776.             }
  777.             else {
  778.                 while (lo <= hi) {
  779.                     int i = GetMedian(lo, hi);
  780.                    
  781.                     int c;
  782.                     try {
  783.                         c = comparer.Compare(array.GetValue(i), value);
  784.                     }
  785.                     catch (Exception e) {
  786.                         throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  787.                     }
  788.                     catch {
  789.                         throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"));
  790.                     }
  791.                     if (c == 0)
  792.                         return i;
  793.                     if (c < 0) {
  794.                         lo = i + 1;
  795.                     }
  796.                     else {
  797.                         hi = i - 1;
  798.                     }
  799.                 }
  800.             }
  801.             return ~lo;
  802.         }
  803.        
  804.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  805.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  806.         private static extern bool TrySZBinarySearch(Array sourceArray, int sourceIndex, int count, object value, out int retVal);
  807.        
  808.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  809.         public static int BinarySearch<T>(T[] array, T value)
  810.         {
  811.             if (array == null)
  812.                 throw new ArgumentNullException("array");
  813.             return BinarySearch<T>(array, 0, array.Length, value, null);
  814.         }
  815.        
  816.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  817.         public static int BinarySearch<T>(T[] array, T value, System.Collections.Generic.IComparer<T> comparer)
  818.         {
  819.             if (array == null)
  820.                 throw new ArgumentNullException("array");
  821.             return BinarySearch<T>(array, 0, array.Length, value, comparer);
  822.         }
  823.        
  824.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  825.         public static int BinarySearch<T>(T[] array, int index, int length, T value)
  826.         {
  827.             return BinarySearch<T>(array, index, length, value, null);
  828.         }
  829.        
  830.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  831.         public static int BinarySearch<T>(T[] array, int index, int length, T value, System.Collections.Generic.IComparer<T> comparer)
  832.         {
  833.             if (array == null)
  834.                 throw new ArgumentNullException("array");
  835.             if (index < 0 || length < 0)
  836.                 throw new ArgumentOutOfRangeException((index < 0 ? "index" : "length"), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  837.             if (array.Length - index < length)
  838.                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  839.            
  840.             return ArraySortHelper<T>.Default.BinarySearch(array, index, length, value, comparer);
  841.         }
  842.        
  843.         public static TOutput[] ConvertAll<TInput, TOutput>(TInput[] array, Converter<TInput, TOutput> converter)
  844.         {
  845.             if (array == null) {
  846.                 throw new ArgumentNullException("array");
  847.             }
  848.            
  849.             if (converter == null) {
  850.                 throw new ArgumentNullException("converter");
  851.             }
  852.            
  853.             TOutput[] newArray = new TOutput[array.Length];
  854.             for (int i = 0; i < array.Length; i++) {
  855.                 newArray[i] = converter(array[i]);
  856.             }
  857.             return newArray;
  858.         }
  859.        
  860.         // CopyTo copies a collection into an Array, starting at a particular
  861.         // index into the array.
  862.         //
  863.         // This method is to support the ICollection interface, and calls
  864.         // Array.Copy internally. If you aren't using ICollection explicitly,
  865.         // call Array.Copy to avoid an extra indirection.
  866.         //
  867.         public void CopyTo(Array array, int index)
  868.         {
  869.             if (array != null && array.Rank != 1)
  870.                 throw new ArgumentException(Environment.GetResourceString("Arg_RankMultiDimNotSupported"));
  871.             // Note: Array.Copy throws a RankException and we want a consistent ArgumentException for all the IList CopyTo methods.
  872.             Array.Copy(this, GetLowerBound(0), array, index, Length);
  873.         }
  874.        
  875.         [ComVisible(false)]
  876.         public void CopyTo(Array array, long index)
  877.         {
  878.             if (index > Int32.MaxValue || index < Int32.MinValue)
  879.                 throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_HugeArrayNotSupported"));
  880.            
  881.             this.CopyTo(array, (int)index);
  882.         }
  883.        
  884.         public static bool Exists<T>(T[] array, Predicate<T> match)
  885.         {
  886.             return Array.FindIndex(array, match) != -1;
  887.         }
  888.        
  889.         public static T Find<T>(T[] array, Predicate<T> match)
  890.         {
  891.             if (array == null) {
  892.                 throw new ArgumentNullException("array");
  893.             }
  894.            
  895.             if (match == null) {
  896.                 throw new ArgumentNullException("match");
  897.             }
  898.            
  899.             for (int i = 0; i < array.Length; i++) {
  900.                 if (match(array[i])) {
  901.                     return array[i];
  902.                 }
  903.             }
  904.             return default(T);
  905.         }
  906.        
  907.         public static T[] FindAll<T>(T[] array, Predicate<T> match)
  908.         {
  909.             if (array == null) {
  910.                 throw new ArgumentNullException("array");
  911.             }
  912.            
  913.             if (match == null) {
  914.                 throw new ArgumentNullException("match");
  915.             }
  916.            
  917.             List<T> list = new List<T>();
  918.             for (int i = 0; i < array.Length; i++) {
  919.                 if (match(array[i])) {
  920.                     list.Add(array[i]);
  921.                 }
  922.             }
  923.             return list.ToArray();
  924.         }
  925.        
  926.         public static int FindIndex<T>(T[] array, Predicate<T> match)
  927.         {
  928.             if (array == null) {
  929.                 throw new ArgumentNullException("array");
  930.             }
  931.            
  932.             return FindIndex(array, 0, array.Length, match);
  933.         }
  934.        
  935.         public static int FindIndex<T>(T[] array, int startIndex, Predicate<T> match)
  936.         {
  937.             if (array == null) {
  938.                 throw new ArgumentNullException("array");
  939.             }
  940.            
  941.             return FindIndex(array, startIndex, array.Length - startIndex, match);
  942.         }
  943.        
  944.         public static int FindIndex<T>(T[] array, int startIndex, int count, Predicate<T> match)
  945.         {
  946.             if (array == null) {
  947.                 throw new ArgumentNullException("array");
  948.             }
  949.            
  950.             if (startIndex < 0 || startIndex > array.Length) {
  951.                 throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  952.             }
  953.            
  954.             if (count < 0 || startIndex > array.Length - count) {
  955.                 throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
  956.             }
  957.            
  958.             if (match == null) {
  959.                 throw new ArgumentNullException("match");
  960.             }
  961.            
  962.             int endIndex = startIndex + count;
  963.             for (int i = startIndex; i < endIndex; i++) {
  964.                 if (match(array[i]))
  965.                     return i;
  966.             }
  967.             return -1;
  968.         }
  969.        
  970.         public static T FindLast<T>(T[] array, Predicate<T> match)
  971.         {
  972.             if (array == null) {
  973.                 throw new ArgumentNullException("array");
  974.             }
  975.            
  976.             if (match == null) {
  977.                 throw new ArgumentNullException("match");
  978.             }
  979.            
  980.             for (int i = array.Length - 1; i >= 0; i--) {
  981.                 if (match(array[i])) {
  982.                     return array[i];
  983.                 }
  984.             }
  985.             return default(T);
  986.         }
  987.        
  988.         public static int FindLastIndex<T>(T[] array, Predicate<T> match)
  989.         {
  990.             if (array == null) {
  991.                 throw new ArgumentNullException("array");
  992.             }
  993.            
  994.             return FindLastIndex(array, array.Length - 1, array.Length, match);
  995.         }
  996.        
  997.         public static int FindLastIndex<T>(T[] array, int startIndex, Predicate<T> match)
  998.         {
  999.             if (array == null) {
  1000.                 throw new ArgumentNullException("array");
  1001.             }
  1002.            
  1003.             return FindLastIndex(array, startIndex, startIndex + 1, match);
  1004.         }
  1005.        
  1006.         public static int FindLastIndex<T>(T[] array, int startIndex, int count, Predicate<T> match)
  1007.         {
  1008.             if (array == null) {
  1009.                 throw new ArgumentNullException("array");
  1010.             }
  1011.            
  1012.             if (match == null) {
  1013.                 throw new ArgumentNullException("match");
  1014.             }
  1015.            
  1016.             if (array.Length == 0) {
  1017.                 // Special case for 0 length List
  1018.                 if (startIndex != -1) {
  1019.                     throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  1020.                 }
  1021.             }
  1022.             else {
  1023.                 // Make sure we're not out of range
  1024.                 if (startIndex < 0 || startIndex >= array.Length) {
  1025.                     throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  1026.                 }
  1027.             }
  1028.            
  1029.             // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
  1030.             if (count < 0 || startIndex - count + 1 < 0) {
  1031.                 throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
  1032.             }
  1033.            
  1034.             int endIndex = startIndex - count;
  1035.             for (int i = startIndex; i > endIndex; i--) {
  1036.                 if (match(array[i])) {
  1037.                     return i;
  1038.                 }
  1039.             }
  1040.             return -1;
  1041.         }
  1042.        
  1043.         public static void ForEach<T>(T[] array, Action<T> action)
  1044.         {
  1045.             if (array == null) {
  1046.                 throw new ArgumentNullException("array");
  1047.             }
  1048.            
  1049.             if (action == null) {
  1050.                 throw new ArgumentNullException("action");
  1051.             }
  1052.            
  1053.             for (int i = 0; i < array.Length; i++) {
  1054.                 action(array[i]);
  1055.             }
  1056.         }
  1057.        
  1058.         // GetEnumerator returns an IEnumerator over this Array.
  1059.         //
  1060.         // Currently, only one dimensional arrays are supported.
  1061.         //
  1062.         public IEnumerator GetEnumerator()
  1063.         {
  1064.             int lowerBound = GetLowerBound(0);
  1065.             if (Rank == 1 && lowerBound == 0)
  1066.                 return new SZArrayEnumerator(this);
  1067.             else
  1068.                 return new ArrayEnumerator(this, lowerBound, Length);
  1069.         }
  1070.        
  1071.         // Returns the index of the first occurrence of a given value in an array.
  1072.         // The array is searched forwards, and the elements of the array are
  1073.         // compared to the given value using the Object.Equals method.
  1074.         //
  1075.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  1076.         public static int IndexOf(Array array, object value)
  1077.         {
  1078.             if (array == null)
  1079.                 throw new ArgumentNullException("array");
  1080.             int lb = array.GetLowerBound(0);
  1081.             return IndexOf(array, value, lb, array.Length);
  1082.         }
  1083.        
  1084.         // Returns the index of the first occurrence of a given value in a range of
  1085.         // an array. The array is searched forwards, starting at index
  1086.         // startIndex and ending at the last element of the array. The
  1087.         // elements of the array are compared to the given value using the
  1088.         // Object.Equals method.
  1089.         //
  1090.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  1091.         public static int IndexOf(Array array, object value, int startIndex)
  1092.         {
  1093.             if (array == null)
  1094.                 throw new ArgumentNullException("array");
  1095.             int lb = array.GetLowerBound(0);
  1096.             return IndexOf(array, value, startIndex, array.Length - startIndex + lb);
  1097.         }
  1098.        
  1099.         // Returns the index of the first occurrence of a given value in a range of
  1100.         // an array. The array is searched forwards, starting at index
  1101.         // startIndex and upto count elements. The
  1102.         // elements of the array are compared to the given value using the
  1103.         // Object.Equals method.
  1104.         //
  1105.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  1106.         public static int IndexOf(Array array, object value, int startIndex, int count)
  1107.         {
  1108.             if (array == null)
  1109.                 throw new ArgumentNullException("array");
  1110.             int lb = array.GetLowerBound(0);
  1111.             if (startIndex < lb || startIndex > array.Length + lb)
  1112.                 throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  1113.             if (count < 0 || count > array.Length - startIndex + lb)
  1114.                 throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
  1115.             if (array.Rank != 1)
  1116.                 throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
  1117.            
  1118.             // Try calling a quick native method to handle primitive types.
  1119.             int retVal;
  1120.             bool r = TrySZIndexOf(array, startIndex, count, value, out retVal);
  1121.             if (r)
  1122.                 return retVal;
  1123.            
  1124.             object[] objArray = array as object[];
  1125.             int endIndex = startIndex + count;
  1126.             if (objArray != null) {
  1127.                 if (value == null) {
  1128.                     for (int i = startIndex; i < endIndex; i++) {
  1129.                         if (objArray[i] == null)
  1130.                             return i;
  1131.                     }
  1132.                 }
  1133.                 else {
  1134.                     for (int i = startIndex; i < endIndex; i++) {
  1135.                         object obj = objArray[i];
  1136.                         if (obj != null && obj.Equals(value))
  1137.                             return i;
  1138.                     }
  1139.                 }
  1140.             }
  1141.             else {
  1142.                 for (int i = startIndex; i < endIndex; i++) {
  1143.                     object obj = array.GetValue(i);
  1144.                     if (obj == null) {
  1145.                         if (value == null)
  1146.                             return i;
  1147.                     }
  1148.                     else {
  1149.                         if (obj.Equals(value))
  1150.                             return i;
  1151.                     }
  1152.                 }
  1153.             }
  1154.             // Return one less than the lower bound of the array. This way,
  1155.             // for arrays with a lower bound of -1 we will not return -1 when the
  1156.             // item was not found. And for SZArrays (the vast majority), -1 still
  1157.             // works for them.
  1158.             return lb - 1;
  1159.         }
  1160.        
  1161.         public static int IndexOf<T>(T[] array, T value)
  1162.         {
  1163.             if (array == null) {
  1164.                 throw new ArgumentNullException("array");
  1165.             }
  1166.            
  1167.             return IndexOf(array, value, 0, array.Length);
  1168.         }
  1169.        
  1170.         public static int IndexOf<T>(T[] array, T value, int startIndex)
  1171.         {
  1172.             if (array == null) {
  1173.                 throw new ArgumentNullException("array");
  1174.             }
  1175.            
  1176.             return IndexOf(array, value, startIndex, array.Length - startIndex);
  1177.         }
  1178.        
  1179.         public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
  1180.         {
  1181.             if (array == null) {
  1182.                 throw new ArgumentNullException("array");
  1183.             }
  1184.            
  1185.             if (startIndex < 0 || startIndex > array.Length) {
  1186.                 throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  1187.             }
  1188.            
  1189.             if (count < 0 || count > array.Length - startIndex) {
  1190.                 throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
  1191.             }
  1192.            
  1193.             return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
  1194.         }
  1195.        
  1196.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  1197.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  1198.         private static extern bool TrySZIndexOf(Array sourceArray, int sourceIndex, int count, object value, out int retVal);
  1199.        
  1200.        
  1201.         // Returns the index of the last occurrence of a given value in an array.
  1202.         // The array is searched backwards, and the elements of the array are
  1203.         // compared to the given value using the Object.Equals method.
  1204.         //
  1205.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  1206.         public static int LastIndexOf(Array array, object value)
  1207.         {
  1208.             if (array == null)
  1209.                 throw new ArgumentNullException("array");
  1210.             int lb = array.GetLowerBound(0);
  1211.             return LastIndexOf(array, value, array.Length - 1 + lb, array.Length);
  1212.         }
  1213.        
  1214.         // Returns the index of the last occurrence of a given value in a range of
  1215.         // an array. The array is searched backwards, starting at index
  1216.         // startIndex and ending at index 0. The elements of the array are
  1217.         // compared to the given value using the Object.Equals method.
  1218.         //
  1219.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  1220.         public static int LastIndexOf(Array array, object value, int startIndex)
  1221.         {
  1222.             if (array == null)
  1223.                 throw new ArgumentNullException("array");
  1224.             int lb = array.GetLowerBound(0);
  1225.             return LastIndexOf(array, value, startIndex, startIndex + 1 - lb);
  1226.         }
  1227.        
  1228.         // Returns the index of the last occurrence of a given value in a range of
  1229.         // an array. The array is searched backwards, starting at index
  1230.         // startIndex and counting uptocount elements. The elements of
  1231.         // the array are compared to the given value using the Object.Equals
  1232.         // method.
  1233.         //
  1234.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  1235.         public static int LastIndexOf(Array array, object value, int startIndex, int count)
  1236.         {
  1237.             if (array == null)
  1238.                 throw new ArgumentNullException("array");
  1239.             int lb = array.GetLowerBound(0);
  1240.             if (array.Length == 0) {
  1241.                 return lb - 1;
  1242.             }
  1243.            
  1244.             if (startIndex < lb || startIndex >= array.Length + lb)
  1245.                 throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  1246.             if (count < 0)
  1247.                 throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
  1248.             if (count > startIndex - lb + 1)
  1249.                 throw new ArgumentOutOfRangeException("endIndex", Environment.GetResourceString("ArgumentOutOfRange_EndIndexStartIndex"));
  1250.             if (array.Rank != 1)
  1251.                 throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
  1252.            
  1253.             // Try calling a quick native method to handle primitive types.
  1254.             int retVal;
  1255.             bool r = TrySZLastIndexOf(array, startIndex, count, value, out retVal);
  1256.             if (r)
  1257.                 return retVal;
  1258.            
  1259.             object[] objArray = array as object[];
  1260.             int endIndex = startIndex - count + 1;
  1261.             if (objArray != null) {
  1262.                 if (value == null) {
  1263.                     for (int i = startIndex; i >= endIndex; i--) {
  1264.                         if (objArray[i] == null)
  1265.                             return i;
  1266.                     }
  1267.                 }
  1268.                 else {
  1269.                     for (int i = startIndex; i >= endIndex; i--) {
  1270.                         object obj = objArray[i];
  1271.                         if (obj != null && obj.Equals(value))
  1272.                             return i;
  1273.                     }
  1274.                 }
  1275.             }
  1276.             else {
  1277.                 for (int i = startIndex; i >= endIndex; i--) {
  1278.                     object obj = array.GetValue(i);
  1279.                     if (obj == null) {
  1280.                         if (value == null)
  1281.                             return i;
  1282.                     }
  1283.                     else {
  1284.                         if (obj.Equals(value))
  1285.                             return i;
  1286.                     }
  1287.                 }
  1288.             }
  1289.             return lb - 1;
  1290.             // Return lb-1 for arrays with negative lower bounds.
  1291.         }
  1292.        
  1293.         public static int LastIndexOf<T>(T[] array, T value)
  1294.         {
  1295.             if (array == null) {
  1296.                 throw new ArgumentNullException("array");
  1297.             }
  1298.            
  1299.             return LastIndexOf(array, value, array.Length - 1, array.Length);
  1300.         }
  1301.        
  1302.         public static int LastIndexOf<T>(T[] array, T value, int startIndex)
  1303.         {
  1304.             if (array == null) {
  1305.                 throw new ArgumentNullException("array");
  1306.             }
  1307.            
  1308.             // if array is empty and startIndex is 0, we need to pass 0 as count
  1309.             return LastIndexOf(array, value, startIndex, (array.Length == 0) ? 0 : (startIndex + 1));
  1310.         }
  1311.        
  1312.         public static int LastIndexOf<T>(T[] array, T value, int startIndex, int count)
  1313.         {
  1314.             if (array == null) {
  1315.                 throw new ArgumentNullException("array");
  1316.             }
  1317.            
  1318.             if (array.Length == 0) {
  1319.                 //
  1320.                 // Special case for 0 length List
  1321.                 // accept -1 and 0 as valid startIndex for compablility reason.
  1322.                 //
  1323.                 if (startIndex != -1 && startIndex != 0) {
  1324.                     throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  1325.                 }
  1326.                
  1327.                 // only 0 is a valid value for count if array is empty
  1328.                 if (count != 0) {
  1329.                     throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
  1330.                 }
  1331.                 return -1;
  1332.             }
  1333.            
  1334.             // Make sure we're not out of range
  1335.             if (startIndex < 0 || startIndex >= array.Length) {
  1336.                 throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index"));
  1337.             }
  1338.            
  1339.             // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0.
  1340.             if (count < 0 || startIndex - count + 1 < 0) {
  1341.                 throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count"));
  1342.             }
  1343.            
  1344.             return EqualityComparer<T>.Default.LastIndexOf(array, value, startIndex, count);
  1345.         }
  1346.        
  1347.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  1348.         [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
  1349.         private static extern bool TrySZLastIndexOf(Array sourceArray, int sourceIndex, int count, object value, out int retVal);
  1350.        
  1351.        
  1352.         // Reverses all elements of the given array. Following a call to this
  1353.         // method, an element previously located at index i will now be
  1354.         // located at index length - i - 1, where length is the
  1355.         // length of the array.
  1356.         //
  1357.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1358.         public static void Reverse(Array array)
  1359.         {
  1360.             if (array == null)
  1361.                 throw new ArgumentNullException("array");
  1362.             Reverse(array, array.GetLowerBound(0), array.Length);
  1363.         }
  1364.        
  1365.         // Reverses the elements in a range of an array. Following a call to this
  1366.         // method, an element in the range given by index and count
  1367.         // which was previously located at index i will now be located at
  1368.         // index index + (index + count - i - 1).
  1369.         // Reliability note: This may fail because it may have to box objects.
  1370.         //
  1371.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1372.         public static void Reverse(Array array, int index, int length)
  1373.         {
  1374.             if (array == null)
  1375.                 throw new ArgumentNullException("array");
  1376.             if (index < array.GetLowerBound(0) || length < 0)
  1377.                 throw new ArgumentOutOfRangeException((index < 0 ? "index" : "length"), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  1378.             if (array.Length - (index - array.GetLowerBound(0)) < length)
  1379.                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  1380.             if (array.Rank != 1)
  1381.                 throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
  1382.            
  1383.             bool r = TrySZReverse(array, index, length);
  1384.             if (r)
  1385.                 return;
  1386.            
  1387.             int i = index;
  1388.             int j = index + length - 1;
  1389.             object[] objArray = array as object[];
  1390.             if (objArray != null) {
  1391.                 while (i < j) {
  1392.                     object temp = objArray[i];
  1393.                     objArray[i] = objArray[j];
  1394.                     objArray[j] = temp;
  1395.                     i++;
  1396.                     j--;
  1397.                 }
  1398.             }
  1399.             else {
  1400.                 while (i < j) {
  1401.                     object temp = array.GetValue(i);
  1402.                     array.SetValue(array.GetValue(j), i);
  1403.                     array.SetValue(temp, j);
  1404.                     i++;
  1405.                     j--;
  1406.                 }
  1407.             }
  1408.         }
  1409.        
  1410.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  1411.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1412.         private static extern bool TrySZReverse(Array array, int index, int count);
  1413.        
  1414.         // Sorts the elements of an array. The sort compares the elements to each
  1415.         // other using the IComparable interface, which must be implemented
  1416.         // by all elements of the array.
  1417.         //
  1418.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1419.         public static void Sort(Array array)
  1420.         {
  1421.             if (array == null)
  1422.                 throw new ArgumentNullException("array");
  1423.             Sort(array, null, array.GetLowerBound(0), array.Length, null);
  1424.         }
  1425.        
  1426.         // Sorts the elements of two arrays based on the keys in the first array.
  1427.         // Elements in the keys array specify the sort keys for
  1428.         // corresponding elements in the items array. The sort compares the
  1429.         // keys to each other using the IComparable interface, which must be
  1430.         // implemented by all elements of the keys array.
  1431.         //
  1432.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1433.         public static void Sort(Array keys, Array items)
  1434.         {
  1435.             if (keys == null)
  1436.                 throw new ArgumentNullException("keys");
  1437.             Sort(keys, items, keys.GetLowerBound(0), keys.Length, null);
  1438.         }
  1439.        
  1440.         // Sorts the elements in a section of an array. The sort compares the
  1441.         // elements to each other using the IComparable interface, which
  1442.         // must be implemented by all elements in the given section of the array.
  1443.         //
  1444.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1445.         public static void Sort(Array array, int index, int length)
  1446.         {
  1447.             Sort(array, null, index, length, null);
  1448.         }
  1449.        
  1450.         // Sorts the elements in a section of two arrays based on the keys in the
  1451.         // first array. Elements in the keys array specify the sort keys for
  1452.         // corresponding elements in the items array. The sort compares the
  1453.         // keys to each other using the IComparable interface, which must be
  1454.         // implemented by all elements of the keys array.
  1455.         //
  1456.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1457.         public static void Sort(Array keys, Array items, int index, int length)
  1458.         {
  1459.             Sort(keys, items, index, length, null);
  1460.         }
  1461.        
  1462.         // Sorts the elements of an array. The sort compares the elements to each
  1463.         // other using the given IComparer interface. If comparer is
  1464.         // null, the elements are compared to each other using the
  1465.         // IComparable interface, which in that case must be implemented by
  1466.         // all elements of the array.
  1467.         //
  1468.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1469.         public static void Sort(Array array, IComparer comparer)
  1470.         {
  1471.             if (array == null)
  1472.                 throw new ArgumentNullException("array");
  1473.             Sort(array, null, array.GetLowerBound(0), array.Length, comparer);
  1474.         }
  1475.        
  1476.         // Sorts the elements of two arrays based on the keys in the first array.
  1477.         // Elements in the keys array specify the sort keys for
  1478.         // corresponding elements in the items array. The sort compares the
  1479.         // keys to each other using the given IComparer interface. If
  1480.         // comparer is null, the elements are compared to each other using
  1481.         // the IComparable interface, which in that case must be implemented
  1482.         // by all elements of the keys array.
  1483.         //
  1484.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1485.         public static void Sort(Array keys, Array items, IComparer comparer)
  1486.         {
  1487.             if (keys == null)
  1488.                 throw new ArgumentNullException("keys");
  1489.             Sort(keys, items, keys.GetLowerBound(0), keys.Length, comparer);
  1490.         }
  1491.        
  1492.         // Sorts the elements in a section of an array. The sort compares the
  1493.         // elements to each other using the given IComparer interface. If
  1494.         // comparer is null, the elements are compared to each other using
  1495.         // the IComparable interface, which in that case must be implemented
  1496.         // by all elements in the given section of the array.
  1497.         //
  1498.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1499.         public static void Sort(Array array, int index, int length, IComparer comparer)
  1500.         {
  1501.             Sort(array, null, index, length, comparer);
  1502.         }
  1503.        
  1504.         // Sorts the elements in a section of two arrays based on the keys in the
  1505.         // first array. Elements in the keys array specify the sort keys for
  1506.         // corresponding elements in the items array. The sort compares the
  1507.         // keys to each other using the given IComparer interface. If
  1508.         // comparer is null, the elements are compared to each other using
  1509.         // the IComparable interface, which in that case must be implemented
  1510.         // by all elements of the given section of the keys array.
  1511.         //
  1512.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1513.         public static void Sort(Array keys, Array items, int index, int length, IComparer comparer)
  1514.         {
  1515.             if (keys == null)
  1516.                 throw new ArgumentNullException("keys");
  1517.             if (keys.Rank != 1 || (items != null && items.Rank != 1))
  1518.                 throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
  1519.             if (items != null && keys.GetLowerBound(0) != items.GetLowerBound(0))
  1520.                 throw new ArgumentException(Environment.GetResourceString("Arg_LowerBoundsMustMatch"));
  1521.             if (index < keys.GetLowerBound(0) || length < 0)
  1522.                 throw new ArgumentOutOfRangeException((length < 0 ? "length" : "index"), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  1523.             if (keys.Length - (index - keys.GetLowerBound(0)) < length || (items != null && (index - items.GetLowerBound(0)) > items.Length - length))
  1524.                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  1525.            
  1526.            
  1527.             if (length > 1) {
  1528.                 if (comparer == Comparer.Default || comparer == null) {
  1529.                     bool r = TrySZSort(keys, items, index, index + length - 1);
  1530.                     if (r)
  1531.                         return;
  1532.                 }
  1533.                
  1534.                 object[] objKeys = keys as object[];
  1535.                 object[] objItems = null;
  1536.                 if (objKeys != null)
  1537.                     objItems = items as object[];
  1538.                 if (objKeys != null && (items == null || objItems != null)) {
  1539.                     SorterObjectArray sorter = new SorterObjectArray(objKeys, objItems, comparer);
  1540.                     sorter.QuickSort(index, index + length - 1);
  1541.                 }
  1542.                 else {
  1543.                     SorterGenericArray sorter = new SorterGenericArray(keys, items, comparer);
  1544.                     sorter.QuickSort(index, index + length - 1);
  1545.                 }
  1546.             }
  1547.         }
  1548.        
  1549.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  1550.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1551.         private static extern bool TrySZSort(Array keys, Array items, int left, int right);
  1552.        
  1553.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1554.         public static void Sort<T>(T[] array)
  1555.         {
  1556.             if (array == null)
  1557.                 throw new ArgumentNullException("array");
  1558.             Sort<T>(array, array.GetLowerBound(0), array.Length, null);
  1559.         }
  1560.        
  1561.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1562.         public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items)
  1563.         {
  1564.             if (keys == null)
  1565.                 throw new ArgumentNullException("keys");
  1566.             Sort<TKey, TValue>(keys, items, 0, keys.Length, null);
  1567.         }
  1568.        
  1569.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1570.         public static void Sort<T>(T[] array, int index, int length)
  1571.         {
  1572.             Sort<T>(array, index, length, null);
  1573.         }
  1574.        
  1575.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1576.         public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length)
  1577.         {
  1578.             Sort<TKey, TValue>(keys, items, index, length, null);
  1579.         }
  1580.        
  1581.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1582.         public static void Sort<T>(T[] array, System.Collections.Generic.IComparer<T> comparer)
  1583.         {
  1584.             if (array == null)
  1585.                 throw new ArgumentNullException("array");
  1586.             Sort<T>(array, 0, array.Length, comparer);
  1587.         }
  1588.        
  1589.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1590.         public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, System.Collections.Generic.IComparer<TKey> comparer)
  1591.         {
  1592.             if (keys == null)
  1593.                 throw new ArgumentNullException("keys");
  1594.             Sort<TKey, TValue>(keys, items, 0, keys.Length, comparer);
  1595.         }
  1596.        
  1597.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1598.         public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer)
  1599.         {
  1600.             if (array == null)
  1601.                 throw new ArgumentNullException("array");
  1602.             if (index < 0 || length < 0)
  1603.                 throw new ArgumentOutOfRangeException((length < 0 ? "length" : "index"), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  1604.             if (array.Length - index < length)
  1605.                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  1606.            
  1607.             if (length > 1) {
  1608.                 if (comparer == null || comparer == Comparer<T>.Default) {
  1609.                     if (TrySZSort(array, null, index, index + length - 1)) {
  1610.                         return;
  1611.                     }
  1612.                 }
  1613.                
  1614.                 ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
  1615.             }
  1616.         }
  1617.        
  1618.         [ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
  1619.         public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, System.Collections.Generic.IComparer<TKey> comparer)
  1620.         {
  1621.             if (keys == null)
  1622.                 throw new ArgumentNullException("keys");
  1623.             if (index < 0 || length < 0)
  1624.                 throw new ArgumentOutOfRangeException((length < 0 ? "length" : "index"), Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
  1625.             if (keys.Length - index < length || (items != null && index > items.Length - length))
  1626.                 throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
  1627.            
  1628.             if (length > 1) {
  1629.                 if (comparer == null || comparer == Comparer<TKey>.Default) {
  1630.                     if (TrySZSort(keys, items, index, index + length - 1)) {
  1631.                         return;
  1632.                     }
  1633.                 }
  1634.                
  1635.                 ArraySortHelper<TKey>.Default.Sort(keys, items, index, length, comparer);
  1636.             }
  1637.         }
  1638.        
  1639.         public static void Sort<T>(T[] array, Comparison<T> comparison)
  1640.         {
  1641.             if (array == null) {
  1642.                 throw new ArgumentNullException("array");
  1643.             }
  1644.            
  1645.             if (comparison == null) {
  1646.                 throw new ArgumentNullException("comparison");
  1647.             }
  1648.            
  1649.             IComparer<T> comparer = new FunctorComparer<T>(comparison);
  1650.             Array.Sort(array, comparer);
  1651.         }
  1652.        
  1653.         public static bool TrueForAll<T>(T[] array, Predicate<T> match)
  1654.         {
  1655.             if (array == null) {
  1656.                 throw new ArgumentNullException("array");
  1657.             }
  1658.            
  1659.             if (match == null) {
  1660.                 throw new ArgumentNullException("match");
  1661.             }
  1662.            
  1663.             for (int i = 0; i < array.Length; i++) {
  1664.                 if (!match(array[i])) {
  1665.                     return false;
  1666.                 }
  1667.             }
  1668.             return true;
  1669.         }
  1670.        
  1671.         internal sealed class FunctorComparer<T> : IComparer<T>
  1672.         {
  1673.             Comparison<T> comparison;
  1674.             Comparer<T> c = Comparer<T>.Default;
  1675.            
  1676.             public FunctorComparer(Comparison<T> comparison)
  1677.             {
  1678.                 this.comparison = comparison;
  1679.             }
  1680.            
  1681.             public int Compare(T x, T y)
  1682.             {
  1683.                 return comparison(x, y);
  1684.             }
  1685.         }
  1686.        
  1687.        
  1688.         // Private value type used by the Sort methods.
  1689.         private struct SorterObjectArray
  1690.         {
  1691.             private object[] keys;
  1692.             private object[] items;
  1693.             private IComparer comparer;
  1694.            
  1695.             internal SorterObjectArray(object[] keys, object[] items, IComparer comparer)
  1696.             {
  1697.                 if (comparer == null)
  1698.                     comparer = Comparer.Default;
  1699.                 this.keys = keys;
  1700.                 this.items = items;
  1701.                 this.comparer = comparer;
  1702.             }
  1703.            
  1704.             internal void QuickSort(int left, int right)
  1705.             {
  1706.                 // Can use the much faster jit helpers for array access.
  1707.                 do {
  1708.                     int i = left;
  1709.                     int j = right;
  1710.                     object x = GetPivotValue(comparer, keys, left, right);
  1711.                     do {
  1712.                         // Add a try block here to detect IComparers (or their
  1713.                         // underlying IComparables, etc) that are bogus.
  1714.                         try {
  1715.                             while (comparer.Compare(keys[i], x) < 0)
  1716.                                 i++;
  1717.                             while (comparer.Compare(x, keys[j]) < 0)
  1718.                                 j--;
  1719.                         }
  1720.                         catch (IndexOutOfRangeException) {
  1721.                             throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", x, x.GetType().Name, comparer));
  1722.                         }
  1723.                         catch (Exception e) {
  1724.                             throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  1725.                         }
  1726.                         catch {
  1727.                             throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"));
  1728.                         }
  1729.                         BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?");
  1730.                         if (i > j)
  1731.                             break;
  1732.                         if (i < j) {
  1733.                             object key = keys[i];
  1734.                             keys[i] = keys[j];
  1735.                             keys[j] = key;
  1736.                             if (items != null) {
  1737.                                 object item = items[i];
  1738.                                 items[i] = items[j];
  1739.                                 items[j] = item;
  1740.                             }
  1741.                         }
  1742.                         i++;
  1743.                         j--;
  1744.                     }
  1745.                     while (i <= j);
  1746.                     if (j - left <= right - i) {
  1747.                         if (left < j)
  1748.                             QuickSort(left, j);
  1749.                         left = i;
  1750.                     }
  1751.                     else {
  1752.                         if (i < right)
  1753.                             QuickSort(i, right);
  1754.                         right = j;
  1755.                     }
  1756.                 }
  1757.                 while (left < right);
  1758.             }
  1759.         }
  1760.        
  1761.         // Private value used by the Sort methods for instances of Array.
  1762.         // This is slower than the one for Object[], since we can't use the JIT helpers
  1763.         // to access the elements. We must use GetValue & SetValue.
  1764.         private struct SorterGenericArray
  1765.         {
  1766.             private Array keys;
  1767.             private Array items;
  1768.             private IComparer comparer;
  1769.            
  1770.             internal SorterGenericArray(Array keys, Array items, IComparer comparer)
  1771.             {
  1772.                 if (comparer == null)
  1773.                     comparer = Comparer.Default;
  1774.                 this.keys = keys;
  1775.                 this.items = items;
  1776.                 this.comparer = comparer;
  1777.             }
  1778.            
  1779.             internal void QuickSort(int left, int right)
  1780.             {
  1781.                 // Must use slow Array accessors (GetValue & SetValue)
  1782.                 do {
  1783.                     int i = left;
  1784.                     int j = right;
  1785.                     object x = GetPivotValue(comparer, keys, left, right);
  1786.                     do {
  1787.                         // Add a try block here to detect IComparers (or their
  1788.                         // underlying IComparables, etc) that are bogus.
  1789.                         try {
  1790.                             while (comparer.Compare(keys.GetValue(i), x) < 0)
  1791.                                 i++;
  1792.                             while (comparer.Compare(x, keys.GetValue(j)) < 0)
  1793.                                 j--;
  1794.                         }
  1795.                         catch (IndexOutOfRangeException) {
  1796.                             throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", x, x.GetType().Name, comparer));
  1797.                         }
  1798.                         catch (Exception e) {
  1799.                             throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  1800.                         }
  1801.                         catch {
  1802.                             throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"));
  1803.                         }
  1804.                         BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?");
  1805.                         if (i > j)
  1806.                             break;
  1807.                         if (i < j) {
  1808.                             object key = keys.GetValue(i);
  1809.                             keys.SetValue(keys.GetValue(j), i);
  1810.                             keys.SetValue(key, j);
  1811.                             if (items != null) {
  1812.                                 object item = items.GetValue(i);
  1813.                                 items.SetValue(items.GetValue(j), i);
  1814.                                 items.SetValue(item, j);
  1815.                             }
  1816.                         }
  1817.                         if (i != Int32.MaxValue)
  1818.                             ++i;
  1819.                         if (j != Int32.MinValue)
  1820.                             --j;
  1821.                     }
  1822.                     while (i <= j);
  1823.                     if (j - left <= right - i) {
  1824.                         if (left < j)
  1825.                             QuickSort(left, j);
  1826.                         left = i;
  1827.                     }
  1828.                     else {
  1829.                         if (i < right)
  1830.                             QuickSort(i, right);
  1831.                         right = j;
  1832.                     }
  1833.                 }
  1834.                 while (left < right);
  1835.             }
  1836.         }
  1837.        
  1838.         [Serializable()]
  1839.         private sealed class SZArrayEnumerator : IEnumerator, ICloneable
  1840.         {
  1841.             private Array _array;
  1842.             private int _index;
  1843.             private int _endIndex;
  1844.             // cache array length, since it's a little slow.
  1845.             internal SZArrayEnumerator(Array array)
  1846.             {
  1847.                 BCLDebug.Assert(array.Rank == 1 && array.GetLowerBound(0) == 0, "SZArrayEnumerator only works on single dimension arrays w/ a lower bound of zero.");
  1848.                 _array = array;
  1849.                 _index = -1;
  1850.                 _endIndex = array.Length;
  1851.             }
  1852.            
  1853.             public object Clone()
  1854.             {
  1855.                 return MemberwiseClone();
  1856.             }
  1857.            
  1858.             public bool MoveNext()
  1859.             {
  1860.                 if (_index < _endIndex) {
  1861.                     _index++;
  1862.                     return (_index < _endIndex);
  1863.                 }
  1864.                 return false;
  1865.             }
  1866.            
  1867.             public object Current {
  1868.                 get {
  1869.                     if (_index < 0)
  1870.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
  1871.                     if (_index >= _endIndex)
  1872.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
  1873.                     return _array.GetValue(_index);
  1874.                 }
  1875.             }
  1876.            
  1877.             public void Reset()
  1878.             {
  1879.                 _index = -1;
  1880.             }
  1881.         }
  1882.        
  1883.         [Serializable()]
  1884.         private sealed class ArrayEnumerator : IEnumerator, ICloneable
  1885.         {
  1886.             private Array array;
  1887.             private int index;
  1888.             private int endIndex;
  1889.             private int startIndex;
  1890.             // Save for Reset.
  1891.             private int[] _indices;
  1892.             // The current position in a multidim array
  1893.             private bool _complete;
  1894.            
  1895.             internal ArrayEnumerator(Array array, int index, int count)
  1896.             {
  1897.                 this.array = array;
  1898.                 this.index = index - 1;
  1899.                 startIndex = index;
  1900.                 endIndex = index + count;
  1901.                 _indices = new int[array.Rank];
  1902.                 int checkForZero = 1;
  1903.                 // Check for dimensions of size 0.
  1904.                 for (int i = 0; i < array.Rank; i++) {
  1905.                     _indices[i] = array.GetLowerBound(i);
  1906.                     checkForZero *= array.GetLength(i);
  1907.                 }
  1908.                 // To make MoveNext simpler, decrement least significant index.
  1909.                 _indices[_indices.Length - 1]--;
  1910.                 _complete = (checkForZero == 0);
  1911.             }
  1912.            
  1913.             private void IncArray()
  1914.             {
  1915.                 // This method advances us to the next valid array index,
  1916.                 // handling all the multiple dimension & bounds correctly.
  1917.                 // Think of it like an odometer in your car - we start with
  1918.                 // the last digit, increment it, and check for rollover. If
  1919.                 // it rolls over, we set all digits to the right and including
  1920.                 // the current to the appropriate lower bound. Do these overflow
  1921.                 // checks for each dimension, and if the most significant digit
  1922.                 // has rolled over it's upper bound, we're done.
  1923.                 //
  1924.                 int rank = array.Rank;
  1925.                 _indices[rank - 1]++;
  1926.                 for (int dim = rank - 1; dim >= 0; dim--) {
  1927.                     if (_indices[dim] > array.GetUpperBound(dim)) {
  1928.                         if (dim == 0) {
  1929.                             _complete = true;
  1930.                             break;
  1931.                         }
  1932.                         for (int j = dim; j < rank; j++)
  1933.                             _indices[j] = array.GetLowerBound(j);
  1934.                         _indices[dim - 1]++;
  1935.                     }
  1936.                 }
  1937.             }
  1938.            
  1939.             public object Clone()
  1940.             {
  1941.                 return MemberwiseClone();
  1942.             }
  1943.            
  1944.             public bool MoveNext()
  1945.             {
  1946.                 if (_complete) {
  1947.                     index = endIndex;
  1948.                     return false;
  1949.                 }
  1950.                 index++;
  1951.                 IncArray();
  1952.                 return !_complete;
  1953.             }
  1954.            
  1955.             public object Current {
  1956.                 get {
  1957.                     if (index < startIndex)
  1958.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
  1959.                     if (_complete)
  1960.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
  1961.                     return array.GetValue(_indices);
  1962.                 }
  1963.             }
  1964.            
  1965.             public void Reset()
  1966.             {
  1967.                 index = startIndex - 1;
  1968.                 int checkForZero = 1;
  1969.                 for (int i = 0; i < array.Rank; i++) {
  1970.                     _indices[i] = array.GetLowerBound(i);
  1971.                     checkForZero *= array.GetLength(i);
  1972.                 }
  1973.                 _complete = (checkForZero == 0);
  1974.                 // To make MoveNext simpler, decrement least significant index.
  1975.                 _indices[_indices.Length - 1]--;
  1976.             }
  1977.         }
  1978.        
  1979.        
  1980.         // if this is an array of value classes and that value class has a default constructor
  1981.         // then this calls this default constructor on every elemen in the value class array.
  1982.         // otherwise this is a no-op. Generally this method is called automatically by the compiler
  1983.         [MethodImplAttribute(MethodImplOptions.InternalCall)]
  1984.         public extern void Initialize();
  1985.     }
  1986.    
  1987.    
  1988.    
  1989.    
  1990.    
  1991.    
  1992.    
  1993.     //----------------------------------------------------------------------------------------
  1994.     // ! READ THIS BEFORE YOU WORK ON THIS CLASS.
  1995.     //
  1996.     // The methods on this class must be written VERY carefully to avoid introducing security holes.
  1997.     // That's because they are invoked with special "this"! The "this" object
  1998.     // for all of these methods are not SZArrayHelper objects. Rather, they are of type U[]
  1999.     // where U[] is castable to T[]. No actual SZArrayHelper object is ever instantiated. Thus, you will
  2000.     // see a lot of expressions that cast "this" "T[]".
  2001.     //
  2002.     // This class is needed to allow an SZ array of type T[] to expose IList<T>,
  2003.     // IList<T.BaseType>, etc., etc. all the way up to IList<Object>. When the following call is
  2004.     // made:
  2005.     //
  2006.     // ((IList<T>) (new U[n])).SomeIListMethod()
  2007.     //
  2008.     // the interface stub dispatcher treats this as a special case, loads up SZArrayHelper,
  2009.     // finds the corresponding generic method (matched simply by method name), instantiates
  2010.     // it for type <T> and executes it.
  2011.     //
  2012.     // The "T" will reflect the interface used to invoke the method. The actual runtime "this" will be
  2013.     // array that is castable to "T[]" (i.e. for primitivs and valuetypes, it will be exactly
  2014.     // "T[]" - for orefs, it may be a "U[]" where U derives from T.)
  2015.     //----------------------------------------------------------------------------------------
  2016.     sealed class SZArrayHelper
  2017.     {
  2018.         // It is never legal to instantiate this class.
  2019.         private SZArrayHelper()
  2020.         {
  2021.             BCLDebug.Assert(false, "Hey! How'd I get here?");
  2022.         }
  2023.        
  2024.        
  2025.         // -----------------------------------------------------------
  2026.         // ------- Implement IEnumerable<T> interface methods --------
  2027.         // -----------------------------------------------------------
  2028.         internal IEnumerator<T> GetEnumerator<T>()
  2029.         {
  2030.             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
  2031.             //! or you may introduce a security hole!
  2032.             return new SZGenericArrayEnumerator<T>(this as T[]);
  2033.         }
  2034.        
  2035.         // -----------------------------------------------------------
  2036.         // ------- Implement ICollection<T> interface methods --------
  2037.         // -----------------------------------------------------------
  2038.         void CopyTo<T>(T[] array, int index)
  2039.         {
  2040.             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
  2041.             //! or you may introduce a security hole!
  2042.            
  2043.             if (array != null && array.Rank != 1)
  2044.                 throw new ArgumentException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
  2045.            
  2046.             T[] _this = this as T[];
  2047.             BCLDebug.Assert(_this != null, "this should be a T[]");
  2048.             Array.Copy(_this, 0, array, index, _this.Length);
  2049.         }
  2050.        
  2051.         internal int get_Count<T>()
  2052.         {
  2053.             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
  2054.             //! or you may introduce a security hole!
  2055.             T[] _this = this as T[];
  2056.             BCLDebug.Assert(_this != null, "this should be a T[]");
  2057.             return _this.Length;
  2058.         }
  2059.        
  2060.         // -----------------------------------------------------------
  2061.         // ---------- Implement IList<T> interface methods -----------
  2062.         // -----------------------------------------------------------
  2063.         internal T get_Item<T>(int index)
  2064.         {
  2065.             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
  2066.             //! or you may introduce a security hole!
  2067.             T[] _this = this as T[];
  2068.             BCLDebug.Assert(_this != null, "this should be a T[]");
  2069.             if ((uint)index >= (uint)_this.Length) {
  2070.                 ThrowHelper.ThrowArgumentOutOfRangeException();
  2071.             }
  2072.            
  2073.             return _this[index];
  2074.         }
  2075.        
  2076.         internal void set_Item<T>(int index, T value)
  2077.         {
  2078.             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
  2079.             //! or you may introduce a security hole!
  2080.             T[] _this = this as T[];
  2081.             BCLDebug.Assert(_this != null, "this should be a T[]");
  2082.             if ((uint)index >= (uint)_this.Length) {
  2083.                 ThrowHelper.ThrowArgumentOutOfRangeException();
  2084.             }
  2085.            
  2086.             _this[index] = value;
  2087.         }
  2088.        
  2089.         void Add<T>(T value)
  2090.         {
  2091.             // Not meaningful for arrays.
  2092.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection"));
  2093.         }
  2094.        
  2095.         bool Contains<T>(T value)
  2096.         {
  2097.             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
  2098.             //! or you may introduce a security hole!
  2099.             T[] _this = this as T[];
  2100.             BCLDebug.Assert(_this != null, "this should be a T[]");
  2101.             return Array.IndexOf(_this, value) != -1;
  2102.         }
  2103.        
  2104.         bool get_IsReadOnly<T>()
  2105.         {
  2106.             return true;
  2107.         }
  2108.        
  2109.         void Clear<T>()
  2110.         {
  2111.             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
  2112.             //! or you may introduce a security hole!
  2113.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_ReadOnlyCollection"));
  2114.         }
  2115.        
  2116.         int IndexOf<T>(T value)
  2117.         {
  2118.             //! Warning: "this" is an array, not an SZArrayHelper. See comments above
  2119.             //! or you may introduce a security hole!
  2120.             T[] _this = this as T[];
  2121.             BCLDebug.Assert(_this != null, "this should be a T[]");
  2122.             return Array.IndexOf(_this, value);
  2123.         }
  2124.        
  2125.         void Insert<T>(int index, T value)
  2126.         {
  2127.             // Not meaningful for arrays
  2128.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection"));
  2129.         }
  2130.        
  2131.         bool Remove<T>(T value)
  2132.         {
  2133.             // Not meaningful for arrays
  2134.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection"));
  2135.         }
  2136.        
  2137.         void RemoveAt<T>(int index)
  2138.         {
  2139.             // Not meaningful for arrays
  2140.             throw new NotSupportedException(Environment.GetResourceString("NotSupported_FixedSizeCollection"));
  2141.         }
  2142.        
  2143.         // This is a normal generic Enumerator for SZ arrays. It doesn't have any of the "this" voodoo
  2144.         // that SZArrayHelper does.
  2145.         //
  2146.         [Serializable()]
  2147.         private sealed class SZGenericArrayEnumerator<T> : IEnumerator<T>
  2148.         {
  2149.             private T[] _array;
  2150.             private int _index;
  2151.             private int _endIndex;
  2152.             // cache array length, since it's a little slow.
  2153.             internal SZGenericArrayEnumerator(T[] array)
  2154.             {
  2155.                 BCLDebug.Assert(array.Rank == 1 && array.GetLowerBound(0) == 0, "SZArrayEnumerator<T> only works on single dimension arrays w/ a lower bound of zero.");
  2156.                 _array = array;
  2157.                 _index = -1;
  2158.                 _endIndex = array.Length;
  2159.             }
  2160.            
  2161.             public bool MoveNext()
  2162.             {
  2163.                 if (_index < _endIndex) {
  2164.                     _index++;
  2165.                     return (_index < _endIndex);
  2166.                 }
  2167.                 return false;
  2168.             }
  2169.            
  2170.             public T Current {
  2171.                 get {
  2172.                     if (_index < 0)
  2173.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumNotStarted));
  2174.                     if (_index >= _endIndex)
  2175.                         throw new InvalidOperationException(Environment.GetResourceString(ResId.InvalidOperation_EnumEnded));
  2176.                     return _array[_index];
  2177.                 }
  2178.             }
  2179.            
  2180.             object IEnumerator.Current {
  2181.                 get { return Current; }
  2182.             }
  2183.            
  2184.             void IEnumerator.Reset()
  2185.             {
  2186.                 _index = -1;
  2187.             }
  2188.            
  2189.             public void Dispose()
  2190.             {
  2191.             }
  2192.         }
  2193.     }
  2194. }

Developer Fusion