ArraySortHelper.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ DotNET / DotNET / 8.0 / untmp / whidbey / REDBITS / ndp / clr / src / BCL / System / Collections / Generic / ArraySortHelper.cs / 2 / 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; 

    [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")]
    internal class ArraySortHelper
    { 
        static ArraySortHelper defaultArraySortHelper;
 
        public static ArraySortHelper Default { 
            get {
                ArraySortHelper sorter = defaultArraySortHelper; 
                if( sorter != null) {
                    return sorter;
                }
                return CreateArraySortHelper(); 
            }
        } 
 
        private static ArraySortHelper CreateArraySortHelper() {
            if (typeof(IComparable).IsAssignableFrom(typeof(T))) { 
                defaultArraySortHelper = (ArraySortHelper)(typeof(GenericArraySortHelper).TypeHandle.CreateInstanceForAnotherGenericParameter(typeof(T)));
            }
            else {
                defaultArraySortHelper = new ArraySortHelper(); 
            }
            return defaultArraySortHelper; 
        } 

        public void Sort(T[] items, int index, int length, IComparer comparer) { 
            Sort(items, (object[])null, index, length, comparer);
        }

        public virtual void Sort(T[] 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!"); 
 
            if( comparer == null || comparer == Comparer.Default ) {
                comparer = Comparer.Default; 
            }

            QuickSort(keys, values, index, index + (length - 1), comparer);
        } 

 
        private void SwapIfGreaterWithItems(T[] keys, TValue[] values, IComparer comparer, int a, int b) { 
            if (a != b) {
                try { 
                    if (comparer.Compare(keys[a], keys[b]) > 0) {
                        T key = keys[a];
                        keys[a] = keys[b];
                        keys[b] = key; 
                        if (values != null) {
                            TValue value = values[a]; 
                            values[a] = values[b]; 
                            values[b] = value;
                        } 
                    }
                }
                catch (IndexOutOfRangeException) {
                    throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", keys[b], keys[b].GetType().Name, comparer)); 
                }
                catch (Exception e) { 
                    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); 
                }
            } 
        }


        private void QuickSort(T[] 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 
 
                T x = keys[middle];
                do { 
                    // Add a try block here to detect IComparers (or their
                    // underlying IComparables, etc) that are bogus.
                    try {
                        while (comparer.Compare(keys[i], x) < 0) i++; 
                        while (comparer.Compare(x, keys[j]) < 0) j--;
                    } 
                    catch (IndexOutOfRangeException) { 
                        throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", x, x.GetType().Name, comparer));
                    } 
                    catch (Exception e) {
                        throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
                    }
                    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; 
                        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); 
        }

        public virtual 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!");
 
            if (comparer == null) { 
                comparer = System.Collections.Generic.Comparer.Default;
            } 

            int lo = index;
            int hi = index + length - 1;
            while (lo <= hi) { 
                int i = lo + ((hi -lo) >> 1);
                int order; 
                try { 
                    order = comparer.Compare(array[i], value);
                } 
                catch (Exception e) {
                    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
                }
 
                if (order == 0) return i;
                if (order < 0) { 
                    lo = i + 1; 
                }
                else { 
                    hi = i - 1;
                }
            }
 
            return ~lo;
        } 
    } 

 
    [Serializable()]
    internal class GenericArraySortHelper: ArraySortHelper where T: IComparable {
        public override 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!");
 
            if( comparer == null || comparer == Comparer.Default ) { 
                return BinarySearch(array, index, length, value);
            } 
            else {
                return base.BinarySearch(array, index, length, value, comparer);
            }
        } 

        public override void Sort(T[] 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!");
 
            if( comparer == null || comparer == Comparer.Default ) {
                // call the fatser version of QuickSort if the user doesn't provide a comparer
                QuickSort(keys, values, index, index + length -1);
            } 
            else {
                base.Sort(keys, values, index, length, comparer); 
            } 
        }
 
        // 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 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; 
                try {
                    if( array[i] == null) {
                        order = (value == null) ? 0 : -1;
                    } 
                    else {
                        order = array[i].CompareTo(value); 
                    } 
                }
                catch (Exception e) { 
                    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
                }

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

            return ~lo; 
        }
 
 
        private void SwapIfGreaterWithItems(T[] keys, TValue[] values, int a, int b) {
            if (a != b) { 
                try {
                    if (keys[a] == null || keys[a].CompareTo(keys[b]) > 0) {
                        T key = keys[a];
                        keys[a] = keys[b]; 
                        keys[b] = key;
                        if (values != null) { 
                            TValue value = values[a]; 
                            values[a] = values[b];
                            values[b] = value; 
                        }
                    }
                }
                catch (IndexOutOfRangeException) { 
                    throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", keys[b], keys[b].GetType().Name, null));
                } 
                catch (Exception e) { 
                    throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
                } 
            }
        }

        private void QuickSort(T[] 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

                T x = keys[middle];
                do { 
                    // Add a try block here to detect IComparers (or their
                    // underlying IComparables, etc) that are bogus. 
                    try { 
                        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--;
                        } 
                    } 
                    catch (IndexOutOfRangeException) {
                        throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", x, x.GetType().Name, null)); 
                    }
                    catch (Exception e) {
                        throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
                    } 
                    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;
                        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);
        }
    }
}
                        

                        

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