ArraySortHelper.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / whidbey / NetFXspW7 / ndp / clr / src / BCL / System / Collections / Generic / ArraySortHelper.cs / 1 / ArraySortHelper.cs

                            // ==++== 
//
//   Copyright (c) Microsoft Corporation.  All rights reserved.
//
// ==--== 
/*============================================================
** 
** Class:  ArraySortHelper 
**
** 
** Purpose: class to sort arrays
**
**
===========================================================*/ 
namespace System.Collections.Generic
{ 
    using System; 
    using System.Globalization;
    using System.Runtime.CompilerServices; 

    #region ArraySortHelper for single arrays

    internal interface IArraySortHelper 
    {
        void Sort(TKey[] keys, int index, int length, IComparer comparer); 
        int BinarySearch(TKey[] keys, int index, int length, TKey value, IComparer comparer); 
    }
 
    [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")]
    internal class ArraySortHelper
        : IArraySortHelper
    { 
        static IArraySortHelper defaultArraySortHelper;
 
        public static IArraySortHelper Default 
        {
            get 
            {
                IArraySortHelper sorter = defaultArraySortHelper;
                if (sorter == null)
                    sorter = CreateArraySortHelper(); 

                return sorter; 
            } 
        }
 
        private static IArraySortHelper CreateArraySortHelper()
        {
            if (typeof(IComparable).IsAssignableFrom(typeof(T)))
            { 
                defaultArraySortHelper = (IArraySortHelper)(typeof(GenericArraySortHelper).TypeHandle.Instantiate(new RuntimeTypeHandle[] { typeof(T).TypeHandle })).Allocate();
            } 
            else 
            {
                defaultArraySortHelper = new ArraySortHelper(); 
            }
            return defaultArraySortHelper;
        }
 
        #region IArraySortHelper Members
 
        public void Sort(T[] keys, int index, int length, IComparer comparer) 
        {
            BCLDebug.Assert(keys != null, "Check the arguments in the caller!"); 
            BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");

            // Add a try block here to detect IComparers (or their
            // underlying IComparables, etc) that are bogus. 
            try
            { 
                if (comparer == null) 
                {
                    comparer = Comparer.Default; 
                }

                QuickSort(keys, index, index + (length - 1), comparer);
            } 
            catch (IndexOutOfRangeException)
            { 
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", null, typeof(T).Name, comparer)); 
            }
            catch (Exception e) 
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
            }
        } 

        public int BinarySearch(T[] array, int index, int length, T value, IComparer comparer) 
        { 
            try
            { 
                if (comparer == null)
                {
                    comparer = Comparer.Default;
                } 

                return InternalBinarySearch(array, index, length, value, comparer); 
            } 
            catch (Exception e)
            { 
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
            }
        }
 
        #endregion
 
        internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer comparer) 
        {
            BCLDebug.Assert(array != null, "Check the arguments in the caller!"); 
            BCLDebug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");

            int lo = index;
            int hi = index + length - 1; 
            while (lo <= hi)
            { 
                int i = lo + ((hi - lo) >> 1); 
                int order = comparer.Compare(array[i], value);
 
                if (order == 0) return i;
                if (order < 0)
                {
                    lo = i + 1; 
                }
                else 
                { 
                    hi = i - 1;
                } 
            }

            return ~lo;
        } 

        private static void SwapIfGreaterWithItems(T[] keys, IComparer comparer, int a, int b) 
        { 
            if (a != b)
            { 
                if (comparer.Compare(keys[a], keys[b]) > 0)
                {
                    T key = keys[a];
                    keys[a] = keys[b]; 
                    keys[b] = key;
                } 
            } 
        }
 
        internal static void QuickSort(T[] keys, int left, int right, IComparer comparer)
        {
            do
            { 
                int i = left;
                int j = right; 
 
                // pre-sort the low, middle (pivot), and high values in place.
                // this improves performance in the face of already sorted data, or 
                // data that is made up of multiple sorted runs appended together.
                int middle = i + ((j - i) >> 1);
                SwapIfGreaterWithItems(keys, comparer, i, middle);  // swap the low with the mid point
                SwapIfGreaterWithItems(keys, comparer, i, j);   // swap the low with the high 
                SwapIfGreaterWithItems(keys, comparer, middle, j); // swap the middle with the high
 
                T x = keys[middle]; 
                do
                { 
                    while (comparer.Compare(keys[i], x) < 0) i++;
                    while (comparer.Compare(x, keys[j]) < 0) j--;
                    BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
                    if (i > j) break; 
                    if (i < j)
                    { 
                        T key = keys[i]; 
                        keys[i] = keys[j];
                        keys[j] = key; 
                    }
                    i++;
                    j--;
                } while (i <= j); 
                if (j - left <= right - i)
                { 
                    if (left < j) QuickSort(keys, left, j, comparer); 
                    left = i;
                } 
                else
                {
                    if (i < right) QuickSort(keys, i, right, comparer);
                    right = j; 
                }
            } while (left < right); 
        } 
    }
 
    [Serializable()]
    internal class GenericArraySortHelper
        : IArraySortHelper
        where T : IComparable 
    {
        #region IArraySortHelper Members 
 
        public void Sort(T[] keys, int index, int length, IComparer comparer)
        { 
            BCLDebug.Assert(keys != null, "Check the arguments in the caller!");
            BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");

            try 
            {
                if (comparer == null || comparer == Comparer.Default) 
                { 
                    // call the faster version of QuickSort if the user doesn't provide a comparer
                    QuickSort(keys, index, index + (length - 1)); 
                }
                else
                {
                    ArraySortHelper.QuickSort(keys, index, index + (length - 1), comparer); 
                }
            } 
            catch (IndexOutOfRangeException) 
            {
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", default(T), typeof(T).Name, null)); 
            }
            catch (Exception e)
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); 
            }
 
        } 

        public int BinarySearch(T[] array, int index, int length, T value, IComparer comparer) 
        {
            BCLDebug.Assert(array != null, "Check the arguments in the caller!");
            BCLDebug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
 
            try
            { 
                if (comparer == null || comparer == Comparer.Default) 
                {
                    return BinarySearch(array, index, length, value); 
                }
                else
                {
                    return ArraySortHelper.InternalBinarySearch(array, index, length, value, comparer); 
                }
            } 
            catch (Exception e) 
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); 
            }
        }

        #endregion 

        // This function is called when the user doesn't specify any comparer. 
        // Since T is constrained here, we can call IComparable.CompareTo here. 
        // We can avoid boxing for value type and casting for reference types.
        private static int BinarySearch(T[] array, int index, int length, T value) 
        {
            int lo = index;
            int hi = index + length - 1;
            while (lo <= hi) 
            {
                int i = lo + ((hi - lo) >> 1); 
                int order; 
                if (array[i] == null)
                { 
                    order = (value == null) ? 0 : -1;
                }
                else
                { 
                    order = array[i].CompareTo(value);
                } 
 
                if (order == 0)
                { 
                    return i;
                }

                if (order < 0) 
                {
                    lo = i + 1; 
                } 
                else
                { 
                    hi = i - 1;
                }
            }
 
            return ~lo;
        } 
 

        private static void SwapIfGreaterWithItems(T[] keys, int a, int b) 
        {
            if (a != b)
            {
                if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0) 
                {
                    T key = keys[a]; 
                    keys[a] = keys[b]; 
                    keys[b] = key;
                } 
            }
        }

        private static void QuickSort(T[] keys, int left, int right) 
        {
            // The code in this function looks very similar to QuickSort in ArraySortHelper class. 
            // The difference is that T is constrainted to IComparable here. 
            // So the IL code will be different. This function is faster than the one in ArraySortHelper.
 
            do
            {
                int i = left;
                int j = right; 

                // pre-sort the low, middle (pivot), and high values in place. 
                // this improves performance in the face of already sorted data, or 
                // data that is made up of multiple sorted runs appended together.
                int middle = i + ((j - i) >> 1); 
                SwapIfGreaterWithItems(keys, i, middle); // swap the low with the mid point
                SwapIfGreaterWithItems(keys, i, j);      // swap the low with the high
                SwapIfGreaterWithItems(keys, middle, j); // swap the middle with the high
 
                T x = keys[middle];
                do 
                { 
                    if (x == null)
                    { 
                        // if x null, the loop to find two elements to be switched can be reduced.
                        while (keys[j] != null) j--;
                    }
                    else 
                    {
                        while (x.CompareTo(keys[i]) > 0) i++; 
                        while (x.CompareTo(keys[j]) < 0) j--; 
                    }
                    BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?"); 
                    if (i > j) break;
                    if (i < j)
                    {
                        T key = keys[i]; 
                        keys[i] = keys[j];
                        keys[j] = key; 
                    } 
                    i++;
                    j--; 
                } while (i <= j);
                if (j - left <= right - i)
                {
                    if (left < j) QuickSort(keys, left, j); 
                    left = i;
                } 
                else 
                {
                    if (i < right) QuickSort(keys, i, right); 
                    right = j;
                }
            } while (left < right);
        } 
    }
 
    #endregion 

    #region ArraySortHelper for paired key and value arrays 

    internal interface IArraySortHelper
    {
        void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer comparer); 
    }
 
    [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`2")] 
    internal class ArraySortHelper
        : IArraySortHelper 
    {
        static IArraySortHelper defaultArraySortHelper;

        public static IArraySortHelper Default 
        {
            get 
            { 
                IArraySortHelper sorter = defaultArraySortHelper;
                if (sorter == null) 
                    sorter = CreateArraySortHelper();

                return sorter;
            } 
        }
 
        public static IArraySortHelper CreateArraySortHelper() 
        {
            if (typeof(IComparable).IsAssignableFrom(typeof(TKey))) 
            {
                defaultArraySortHelper = (IArraySortHelper)(typeof(GenericArraySortHelper).TypeHandle.Instantiate(new RuntimeTypeHandle[] { typeof(TKey).TypeHandle, typeof(TValue).TypeHandle })).Allocate();
            }
            else 
            {
                defaultArraySortHelper = new ArraySortHelper(); 
            } 
            return defaultArraySortHelper;
        } 

        public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer comparer)
        {
            BCLDebug.Assert(keys != null, "Check the arguments in the caller!"); 
            BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 
            // Add a try block here to detect IComparers (or their 
            // underlying IComparables, etc) that are bogus.
            try 
            {
                if (comparer == null || comparer == Comparer.Default)
                {
                    comparer = Comparer.Default; 
                }
 
                QuickSort(keys, values, index, index + (length - 1), comparer); 
            }
            catch (IndexOutOfRangeException) 
            {
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", null, typeof(TKey).Name, comparer));
            }
            catch (Exception e) 
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); 
            } 
        }
 
        private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, IComparer comparer, int a, int b)
        {
            if (a != b)
            { 
                if (comparer.Compare(keys[a], keys[b]) > 0)
                { 
                    TKey key = keys[a]; 
                    keys[a] = keys[b];
                    keys[b] = key; 
                    if (values != null)
                    {
                        TValue value = values[a];
                        values[a] = values[b]; 
                        values[b] = value;
                    } 
                } 
            }
        } 

        internal static void QuickSort(TKey[] keys, TValue[] values, int left, int right, IComparer comparer)
        {
            do 
            {
                int i = left; 
                int j = right; 

                // pre-sort the low, middle (pivot), and high values in place. 
                // this improves performance in the face of already sorted data, or
                // data that is made up of multiple sorted runs appended together.
                int middle = i + ((j - i) >> 1);
                SwapIfGreaterWithItems(keys, values, comparer, i, middle);  // swap the low with the mid point 
                SwapIfGreaterWithItems(keys, values, comparer, i, j);   // swap the low with the high
                SwapIfGreaterWithItems(keys, values, comparer, middle, j); // swap the middle with the high 
 
                TKey x = keys[middle];
                do 
                {
                    while (comparer.Compare(keys[i], x) < 0) i++;
                    while (comparer.Compare(x, keys[j]) < 0) j--;
                    BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?"); 
                    if (i > j) break;
                    if (i < j) 
                    { 
                        TKey key = keys[i];
                        keys[i] = keys[j]; 
                        keys[j] = key;
                        if (values != null)
                        {
                            TValue value = values[i]; 
                            values[i] = values[j];
                            values[j] = value; 
                        } 
                    }
                    i++; 
                    j--;
                } while (i <= j);
                if (j - left <= right - i)
                { 
                    if (left < j) QuickSort(keys, values, left, j, comparer);
                    left = i; 
                } 
                else
                { 
                    if (i < right) QuickSort(keys, values, i, right, comparer);
                    right = j;
                }
            } while (left < right); 
        }
    } 
 
    internal class GenericArraySortHelper
        : IArraySortHelper 
        where TKey : IComparable
    {
        public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer comparer)
        { 
            BCLDebug.Assert(keys != null, "Check the arguments in the caller!");
            BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); 
 
            // Add a try block here to detect IComparers (or their
            // underlying IComparables, etc) that are bogus. 
            try
            {
                if (comparer == null || comparer == Comparer.Default)
                { 
                    // call the faster version of QuickSort if the user doesn't provide a comparer
                    QuickSort(keys, values, index, index + length - 1); 
                } 
                else
                { 
                    ArraySortHelper.QuickSort(keys, values, index, index + length - 1, comparer);
                }

            } 
            catch (IndexOutOfRangeException)
            { 
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", null, typeof(TKey).Name, null)); 
            }
            catch (Exception e) 
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
            }
        } 

        private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, int a, int b) 
        { 
            if (a != b)
            { 
                if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0)
                {
                    TKey key = keys[a];
                    keys[a] = keys[b]; 
                    keys[b] = key;
                    if (values != null) 
                    { 
                        TValue value = values[a];
                        values[a] = values[b]; 
                        values[b] = value;
                    }
                }
            } 
        }
 
        private static void QuickSort(TKey[] keys, TValue[] values, int left, int right) 
        {
            // The code in this function looks very similar to QuickSort in ArraySortHelper class. 
            // The difference is that T is constrainted to IComparable here.
            // So the IL code will be different. This function is faster than the one in ArraySortHelper.

            do 
            {
                int i = left; 
                int j = right; 

                // pre-sort the low, middle (pivot), and high values in place. 
                // this improves performance in the face of already sorted data, or
                // data that is made up of multiple sorted runs appended together.
                int middle = i + ((j - i) >> 1);
                SwapIfGreaterWithItems(keys, values, i, middle); // swap the low with the mid point 
                SwapIfGreaterWithItems(keys, values, i, j);      // swap the low with the high
                SwapIfGreaterWithItems(keys, values, middle, j); // swap the middle with the high 
 
                TKey x = keys[middle];
                do 
                {
                    if (x == null)
                    {
                        // if x null, the loop to find two elements to be switched can be reduced. 
                        while (keys[j] != null) j--;
                    } 
                    else 
                    {
                        while (x.CompareTo(keys[i]) > 0) i++; 
                        while (x.CompareTo(keys[j]) < 0) j--;
                    }
                    BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
                    if (i > j) break; 
                    if (i < j)
                    { 
                        TKey key = keys[i]; 
                        keys[i] = keys[j];
                        keys[j] = key; 
                        if (values != null)
                        {
                            TValue value = values[i];
                            values[i] = values[j]; 
                            values[j] = value;
                        } 
                    } 
                    i++;
                    j--; 
                } while (i <= j);
                if (j - left <= right - i)
                {
                    if (left < j) QuickSort(keys, values, left, j); 
                    left = i;
                } 
                else 
                {
                    if (i < right) QuickSort(keys, values, i, right); 
                    right = j;
                }
            } while (left < right);
        } 
    }
 
    #endregion 
}
 


// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
// ==++== 
//
//   Copyright (c) Microsoft Corporation.  All rights reserved.
//
// ==--== 
/*============================================================
** 
** Class:  ArraySortHelper 
**
** 
** Purpose: class to sort arrays
**
**
===========================================================*/ 
namespace System.Collections.Generic
{ 
    using System; 
    using System.Globalization;
    using System.Runtime.CompilerServices; 

    #region ArraySortHelper for single arrays

    internal interface IArraySortHelper 
    {
        void Sort(TKey[] keys, int index, int length, IComparer comparer); 
        int BinarySearch(TKey[] keys, int index, int length, TKey value, IComparer comparer); 
    }
 
    [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")]
    internal class ArraySortHelper
        : IArraySortHelper
    { 
        static IArraySortHelper defaultArraySortHelper;
 
        public static IArraySortHelper Default 
        {
            get 
            {
                IArraySortHelper sorter = defaultArraySortHelper;
                if (sorter == null)
                    sorter = CreateArraySortHelper(); 

                return sorter; 
            } 
        }
 
        private static IArraySortHelper CreateArraySortHelper()
        {
            if (typeof(IComparable).IsAssignableFrom(typeof(T)))
            { 
                defaultArraySortHelper = (IArraySortHelper)(typeof(GenericArraySortHelper).TypeHandle.Instantiate(new RuntimeTypeHandle[] { typeof(T).TypeHandle })).Allocate();
            } 
            else 
            {
                defaultArraySortHelper = new ArraySortHelper(); 
            }
            return defaultArraySortHelper;
        }
 
        #region IArraySortHelper Members
 
        public void Sort(T[] keys, int index, int length, IComparer comparer) 
        {
            BCLDebug.Assert(keys != null, "Check the arguments in the caller!"); 
            BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");

            // Add a try block here to detect IComparers (or their
            // underlying IComparables, etc) that are bogus. 
            try
            { 
                if (comparer == null) 
                {
                    comparer = Comparer.Default; 
                }

                QuickSort(keys, index, index + (length - 1), comparer);
            } 
            catch (IndexOutOfRangeException)
            { 
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", null, typeof(T).Name, comparer)); 
            }
            catch (Exception e) 
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
            }
        } 

        public int BinarySearch(T[] array, int index, int length, T value, IComparer comparer) 
        { 
            try
            { 
                if (comparer == null)
                {
                    comparer = Comparer.Default;
                } 

                return InternalBinarySearch(array, index, length, value, comparer); 
            } 
            catch (Exception e)
            { 
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
            }
        }
 
        #endregion
 
        internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer comparer) 
        {
            BCLDebug.Assert(array != null, "Check the arguments in the caller!"); 
            BCLDebug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");

            int lo = index;
            int hi = index + length - 1; 
            while (lo <= hi)
            { 
                int i = lo + ((hi - lo) >> 1); 
                int order = comparer.Compare(array[i], value);
 
                if (order == 0) return i;
                if (order < 0)
                {
                    lo = i + 1; 
                }
                else 
                { 
                    hi = i - 1;
                } 
            }

            return ~lo;
        } 

        private static void SwapIfGreaterWithItems(T[] keys, IComparer comparer, int a, int b) 
        { 
            if (a != b)
            { 
                if (comparer.Compare(keys[a], keys[b]) > 0)
                {
                    T key = keys[a];
                    keys[a] = keys[b]; 
                    keys[b] = key;
                } 
            } 
        }
 
        internal static void QuickSort(T[] keys, int left, int right, IComparer comparer)
        {
            do
            { 
                int i = left;
                int j = right; 
 
                // pre-sort the low, middle (pivot), and high values in place.
                // this improves performance in the face of already sorted data, or 
                // data that is made up of multiple sorted runs appended together.
                int middle = i + ((j - i) >> 1);
                SwapIfGreaterWithItems(keys, comparer, i, middle);  // swap the low with the mid point
                SwapIfGreaterWithItems(keys, comparer, i, j);   // swap the low with the high 
                SwapIfGreaterWithItems(keys, comparer, middle, j); // swap the middle with the high
 
                T x = keys[middle]; 
                do
                { 
                    while (comparer.Compare(keys[i], x) < 0) i++;
                    while (comparer.Compare(x, keys[j]) < 0) j--;
                    BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
                    if (i > j) break; 
                    if (i < j)
                    { 
                        T key = keys[i]; 
                        keys[i] = keys[j];
                        keys[j] = key; 
                    }
                    i++;
                    j--;
                } while (i <= j); 
                if (j - left <= right - i)
                { 
                    if (left < j) QuickSort(keys, left, j, comparer); 
                    left = i;
                } 
                else
                {
                    if (i < right) QuickSort(keys, i, right, comparer);
                    right = j; 
                }
            } while (left < right); 
        } 
    }
 
    [Serializable()]
    internal class GenericArraySortHelper
        : IArraySortHelper
        where T : IComparable 
    {
        #region IArraySortHelper Members 
 
        public void Sort(T[] keys, int index, int length, IComparer comparer)
        { 
            BCLDebug.Assert(keys != null, "Check the arguments in the caller!");
            BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");

            try 
            {
                if (comparer == null || comparer == Comparer.Default) 
                { 
                    // call the faster version of QuickSort if the user doesn't provide a comparer
                    QuickSort(keys, index, index + (length - 1)); 
                }
                else
                {
                    ArraySortHelper.QuickSort(keys, index, index + (length - 1), comparer); 
                }
            } 
            catch (IndexOutOfRangeException) 
            {
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", default(T), typeof(T).Name, null)); 
            }
            catch (Exception e)
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); 
            }
 
        } 

        public int BinarySearch(T[] array, int index, int length, T value, IComparer comparer) 
        {
            BCLDebug.Assert(array != null, "Check the arguments in the caller!");
            BCLDebug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
 
            try
            { 
                if (comparer == null || comparer == Comparer.Default) 
                {
                    return BinarySearch(array, index, length, value); 
                }
                else
                {
                    return ArraySortHelper.InternalBinarySearch(array, index, length, value, comparer); 
                }
            } 
            catch (Exception e) 
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); 
            }
        }

        #endregion 

        // This function is called when the user doesn't specify any comparer. 
        // Since T is constrained here, we can call IComparable.CompareTo here. 
        // We can avoid boxing for value type and casting for reference types.
        private static int BinarySearch(T[] array, int index, int length, T value) 
        {
            int lo = index;
            int hi = index + length - 1;
            while (lo <= hi) 
            {
                int i = lo + ((hi - lo) >> 1); 
                int order; 
                if (array[i] == null)
                { 
                    order = (value == null) ? 0 : -1;
                }
                else
                { 
                    order = array[i].CompareTo(value);
                } 
 
                if (order == 0)
                { 
                    return i;
                }

                if (order < 0) 
                {
                    lo = i + 1; 
                } 
                else
                { 
                    hi = i - 1;
                }
            }
 
            return ~lo;
        } 
 

        private static void SwapIfGreaterWithItems(T[] keys, int a, int b) 
        {
            if (a != b)
            {
                if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0) 
                {
                    T key = keys[a]; 
                    keys[a] = keys[b]; 
                    keys[b] = key;
                } 
            }
        }

        private static void QuickSort(T[] keys, int left, int right) 
        {
            // The code in this function looks very similar to QuickSort in ArraySortHelper class. 
            // The difference is that T is constrainted to IComparable here. 
            // So the IL code will be different. This function is faster than the one in ArraySortHelper.
 
            do
            {
                int i = left;
                int j = right; 

                // pre-sort the low, middle (pivot), and high values in place. 
                // this improves performance in the face of already sorted data, or 
                // data that is made up of multiple sorted runs appended together.
                int middle = i + ((j - i) >> 1); 
                SwapIfGreaterWithItems(keys, i, middle); // swap the low with the mid point
                SwapIfGreaterWithItems(keys, i, j);      // swap the low with the high
                SwapIfGreaterWithItems(keys, middle, j); // swap the middle with the high
 
                T x = keys[middle];
                do 
                { 
                    if (x == null)
                    { 
                        // if x null, the loop to find two elements to be switched can be reduced.
                        while (keys[j] != null) j--;
                    }
                    else 
                    {
                        while (x.CompareTo(keys[i]) > 0) i++; 
                        while (x.CompareTo(keys[j]) < 0) j--; 
                    }
                    BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?"); 
                    if (i > j) break;
                    if (i < j)
                    {
                        T key = keys[i]; 
                        keys[i] = keys[j];
                        keys[j] = key; 
                    } 
                    i++;
                    j--; 
                } while (i <= j);
                if (j - left <= right - i)
                {
                    if (left < j) QuickSort(keys, left, j); 
                    left = i;
                } 
                else 
                {
                    if (i < right) QuickSort(keys, i, right); 
                    right = j;
                }
            } while (left < right);
        } 
    }
 
    #endregion 

    #region ArraySortHelper for paired key and value arrays 

    internal interface IArraySortHelper
    {
        void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer comparer); 
    }
 
    [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`2")] 
    internal class ArraySortHelper
        : IArraySortHelper 
    {
        static IArraySortHelper defaultArraySortHelper;

        public static IArraySortHelper Default 
        {
            get 
            { 
                IArraySortHelper sorter = defaultArraySortHelper;
                if (sorter == null) 
                    sorter = CreateArraySortHelper();

                return sorter;
            } 
        }
 
        public static IArraySortHelper CreateArraySortHelper() 
        {
            if (typeof(IComparable).IsAssignableFrom(typeof(TKey))) 
            {
                defaultArraySortHelper = (IArraySortHelper)(typeof(GenericArraySortHelper).TypeHandle.Instantiate(new RuntimeTypeHandle[] { typeof(TKey).TypeHandle, typeof(TValue).TypeHandle })).Allocate();
            }
            else 
            {
                defaultArraySortHelper = new ArraySortHelper(); 
            } 
            return defaultArraySortHelper;
        } 

        public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer comparer)
        {
            BCLDebug.Assert(keys != null, "Check the arguments in the caller!"); 
            BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
 
            // Add a try block here to detect IComparers (or their 
            // underlying IComparables, etc) that are bogus.
            try 
            {
                if (comparer == null || comparer == Comparer.Default)
                {
                    comparer = Comparer.Default; 
                }
 
                QuickSort(keys, values, index, index + (length - 1), comparer); 
            }
            catch (IndexOutOfRangeException) 
            {
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", null, typeof(TKey).Name, comparer));
            }
            catch (Exception e) 
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); 
            } 
        }
 
        private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, IComparer comparer, int a, int b)
        {
            if (a != b)
            { 
                if (comparer.Compare(keys[a], keys[b]) > 0)
                { 
                    TKey key = keys[a]; 
                    keys[a] = keys[b];
                    keys[b] = key; 
                    if (values != null)
                    {
                        TValue value = values[a];
                        values[a] = values[b]; 
                        values[b] = value;
                    } 
                } 
            }
        } 

        internal static void QuickSort(TKey[] keys, TValue[] values, int left, int right, IComparer comparer)
        {
            do 
            {
                int i = left; 
                int j = right; 

                // pre-sort the low, middle (pivot), and high values in place. 
                // this improves performance in the face of already sorted data, or
                // data that is made up of multiple sorted runs appended together.
                int middle = i + ((j - i) >> 1);
                SwapIfGreaterWithItems(keys, values, comparer, i, middle);  // swap the low with the mid point 
                SwapIfGreaterWithItems(keys, values, comparer, i, j);   // swap the low with the high
                SwapIfGreaterWithItems(keys, values, comparer, middle, j); // swap the middle with the high 
 
                TKey x = keys[middle];
                do 
                {
                    while (comparer.Compare(keys[i], x) < 0) i++;
                    while (comparer.Compare(x, keys[j]) < 0) j--;
                    BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?"); 
                    if (i > j) break;
                    if (i < j) 
                    { 
                        TKey key = keys[i];
                        keys[i] = keys[j]; 
                        keys[j] = key;
                        if (values != null)
                        {
                            TValue value = values[i]; 
                            values[i] = values[j];
                            values[j] = value; 
                        } 
                    }
                    i++; 
                    j--;
                } while (i <= j);
                if (j - left <= right - i)
                { 
                    if (left < j) QuickSort(keys, values, left, j, comparer);
                    left = i; 
                } 
                else
                { 
                    if (i < right) QuickSort(keys, values, i, right, comparer);
                    right = j;
                }
            } while (left < right); 
        }
    } 
 
    internal class GenericArraySortHelper
        : IArraySortHelper 
        where TKey : IComparable
    {
        public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer comparer)
        { 
            BCLDebug.Assert(keys != null, "Check the arguments in the caller!");
            BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); 
 
            // Add a try block here to detect IComparers (or their
            // underlying IComparables, etc) that are bogus. 
            try
            {
                if (comparer == null || comparer == Comparer.Default)
                { 
                    // call the faster version of QuickSort if the user doesn't provide a comparer
                    QuickSort(keys, values, index, index + length - 1); 
                } 
                else
                { 
                    ArraySortHelper.QuickSort(keys, values, index, index + length - 1, comparer);
                }

            } 
            catch (IndexOutOfRangeException)
            { 
                throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", null, typeof(TKey).Name, null)); 
            }
            catch (Exception e) 
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
            }
        } 

        private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, int a, int b) 
        { 
            if (a != b)
            { 
                if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0)
                {
                    TKey key = keys[a];
                    keys[a] = keys[b]; 
                    keys[b] = key;
                    if (values != null) 
                    { 
                        TValue value = values[a];
                        values[a] = values[b]; 
                        values[b] = value;
                    }
                }
            } 
        }
 
        private static void QuickSort(TKey[] keys, TValue[] values, int left, int right) 
        {
            // The code in this function looks very similar to QuickSort in ArraySortHelper class. 
            // The difference is that T is constrainted to IComparable here.
            // So the IL code will be different. This function is faster than the one in ArraySortHelper.

            do 
            {
                int i = left; 
                int j = right; 

                // pre-sort the low, middle (pivot), and high values in place. 
                // this improves performance in the face of already sorted data, or
                // data that is made up of multiple sorted runs appended together.
                int middle = i + ((j - i) >> 1);
                SwapIfGreaterWithItems(keys, values, i, middle); // swap the low with the mid point 
                SwapIfGreaterWithItems(keys, values, i, j);      // swap the low with the high
                SwapIfGreaterWithItems(keys, values, middle, j); // swap the middle with the high 
 
                TKey x = keys[middle];
                do 
                {
                    if (x == null)
                    {
                        // if x null, the loop to find two elements to be switched can be reduced. 
                        while (keys[j] != null) j--;
                    } 
                    else 
                    {
                        while (x.CompareTo(keys[i]) > 0) i++; 
                        while (x.CompareTo(keys[j]) < 0) j--;
                    }
                    BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right)  Sort failed - Is your IComparer bogus?");
                    if (i > j) break; 
                    if (i < j)
                    { 
                        TKey key = keys[i]; 
                        keys[i] = keys[j];
                        keys[j] = key; 
                        if (values != null)
                        {
                            TValue value = values[i];
                            values[i] = values[j]; 
                            values[j] = value;
                        } 
                    } 
                    i++;
                    j--; 
                } while (i <= j);
                if (j - left <= right - i)
                {
                    if (left < j) QuickSort(keys, values, left, j); 
                    left = i;
                } 
                else 
                {
                    if (i < right) QuickSort(keys, values, i, right); 
                    right = j;
                }
            } while (left < right);
        } 
    }
 
    #endregion 
}
 


// File provided for Reference Use Only by Microsoft Corporation (c) 2007.

                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK