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
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- CompositeTypefaceMetrics.cs
- KeyedHashAlgorithm.cs
- ReceiveMessageContent.cs
- WasHttpHandlersInstallComponent.cs
- IncrementalReadDecoders.cs
- DataErrorValidationRule.cs
- WSHttpBinding.cs
- ToolStripItemTextRenderEventArgs.cs
- InputBuffer.cs
- RenderOptions.cs
- ListViewCommandEventArgs.cs
- BaseCodePageEncoding.cs
- ResourceProviderFactory.cs
- SafeIUnknown.cs
- ObjectMemberMapping.cs
- HostedImpersonationContext.cs
- Transform3DGroup.cs
- RepeatBehavior.cs
- PermissionAttributes.cs
- TemplateXamlTreeBuilder.cs
- ImportedNamespaceContextItem.cs
- StaticSiteMapProvider.cs
- ResourceProperty.cs
- SpellCheck.cs
- PriorityChain.cs
- InstanceStoreQueryResult.cs
- xamlnodes.cs
- ColorTranslator.cs
- EntityDataSourceEntityTypeFilterItem.cs
- WebScriptMetadataMessageEncoderFactory.cs
- TypeNameConverter.cs
- WebPartZoneCollection.cs
- PlainXmlSerializer.cs
- DataSysAttribute.cs
- CopyAction.cs
- SafeLocalAllocation.cs
- Int64Converter.cs
- ObjectDataSourceDesigner.cs
- MenuTracker.cs
- _RequestCacheProtocol.cs
- NoPersistScope.cs
- Stream.cs
- HtmlControl.cs
- WebRequestModuleElementCollection.cs
- VideoDrawing.cs
- Wizard.cs
- XmlDataSourceDesigner.cs
- EmptyEnumerable.cs
- PeerApplicationLaunchInfo.cs
- MulticastIPAddressInformationCollection.cs
- ViewBox.cs
- regiisutil.cs
- RSAPKCS1SignatureFormatter.cs
- OrderPreservingPipeliningSpoolingTask.cs
- ToolStripContainer.cs
- BitmapPalette.cs
- AnimatedTypeHelpers.cs
- GeneralTransform3D.cs
- SymbolTable.cs
- NeutralResourcesLanguageAttribute.cs
- ViewStateException.cs
- DataTableNameHandler.cs
- ApplicationFileParser.cs
- ConfigXmlAttribute.cs
- objectquery_tresulttype.cs
- SizeLimitedCache.cs
- LineGeometry.cs
- MetadataAssemblyHelper.cs
- ActivityStatusChangeEventArgs.cs
- FormattedTextSymbols.cs
- WebBrowserDesigner.cs
- Panel.cs
- NativeMethodsCLR.cs
- D3DImage.cs
- WebSysDefaultValueAttribute.cs
- StructuredTypeEmitter.cs
- AccessorTable.cs
- ScriptingScriptResourceHandlerSection.cs
- EntityClassGenerator.cs
- IncrementalCompileAnalyzer.cs
- ImageButton.cs
- PhotoPrintingIntent.cs
- Model3DGroup.cs
- Vector3DIndependentAnimationStorage.cs
- ExpressionList.cs
- WebReferencesBuildProvider.cs
- DataGridViewCheckBoxCell.cs
- SharedPersonalizationStateInfo.cs
- XmlSchemaObjectCollection.cs
- ViewGenerator.cs
- Attributes.cs
- _LoggingObject.cs
- SourceInterpreter.cs
- SafeFileMappingHandle.cs
- ColumnHeader.cs
- DataGridViewCellParsingEventArgs.cs
- ObjectDataSourceDesigner.cs
- autovalidator.cs
- TreeWalker.cs
- ObjectSelectorEditor.cs