Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / whidbey / NetFxQFE / 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
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- validationstate.cs
- ExtensibleSyndicationObject.cs
- Command.cs
- InputReportEventArgs.cs
- HttpCachePolicyElement.cs
- HashCodeCombiner.cs
- BmpBitmapEncoder.cs
- MemberCollection.cs
- ListParaClient.cs
- NamespaceList.cs
- PackWebRequestFactory.cs
- XamlFilter.cs
- path.cs
- StaticSiteMapProvider.cs
- CompilerTypeWithParams.cs
- RegistryPermission.cs
- xml.cs
- FirstQueryOperator.cs
- WebBrowserPermission.cs
- DiscoveryServerProtocol.cs
- VectorKeyFrameCollection.cs
- ComponentManagerBroker.cs
- FrameworkElementFactory.cs
- ControllableStoryboardAction.cs
- PageParserFilter.cs
- ADMembershipUser.cs
- LateBoundChannelParameterCollection.cs
- CompoundFileStorageReference.cs
- QueryContinueDragEvent.cs
- WorkflowServiceBuildProvider.cs
- StringAnimationBase.cs
- AssemblyCollection.cs
- ToolStripDropDownButton.cs
- XmlCustomFormatter.cs
- ResourceAttributes.cs
- WasAdminWrapper.cs
- ConfigurationStrings.cs
- ObjectListFieldsPage.cs
- ProgressChangedEventArgs.cs
- AspNetPartialTrustHelpers.cs
- EdmTypeAttribute.cs
- TextFormatterContext.cs
- TransformGroup.cs
- CompModSwitches.cs
- InternalResources.cs
- DataBindingHandlerAttribute.cs
- HtmlPhoneCallAdapter.cs
- WebPartHelpVerb.cs
- MDIControlStrip.cs
- TypeDescriptionProvider.cs
- RuntimeEnvironment.cs
- ProjectionPruner.cs
- FlagsAttribute.cs
- StateRuntime.cs
- AbsoluteQuery.cs
- ActionNotSupportedException.cs
- HashCodeCombiner.cs
- TranslateTransform3D.cs
- RadialGradientBrush.cs
- SplineKeyFrames.cs
- HealthMonitoringSection.cs
- TracingConnectionListener.cs
- AlphaSortedEnumConverter.cs
- OciHandle.cs
- GridViewSelectEventArgs.cs
- DisplayMemberTemplateSelector.cs
- DataFieldConverter.cs
- CodeCatchClause.cs
- EventDescriptor.cs
- WsdlInspector.cs
- StaticFileHandler.cs
- XomlCompilerResults.cs
- FlowDocumentReader.cs
- JapaneseCalendar.cs
- BamlTreeNode.cs
- _ConnectOverlappedAsyncResult.cs
- EntityDataSourceSelectedEventArgs.cs
- AstNode.cs
- FactoryGenerator.cs
- AddInAdapter.cs
- CompiledELinqQueryState.cs
- ApplicationServicesHostFactory.cs
- DatePickerDateValidationErrorEventArgs.cs
- SiteMembershipCondition.cs
- DataServiceQueryOfT.cs
- ConsoleTraceListener.cs
- SqlDataSourceView.cs
- EntityDataSourceContainerNameConverter.cs
- DataGridViewCellParsingEventArgs.cs
- CodePageUtils.cs
- TreeNodeMouseHoverEvent.cs
- AlphaSortedEnumConverter.cs
- SapiAttributeParser.cs
- InfiniteIntConverter.cs
- ObfuscationAttribute.cs
- basecomparevalidator.cs
- NotSupportedException.cs
- ReferenceConverter.cs
- LineServicesRun.cs
- MetadataProperty.cs