The Labs \ Source Viewer \ SSCLI \ System.Collections.Generic \ GenericArraySortHelper

  1. // ==++==
  2. //
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. //
  14. // ==--==
  15. /*============================================================
  16. **
  17. ** Class:  ArraySortHelper
  18. **
  19. **
  20. ** Purpose: class to sort arrays
  21. **
  22. **
  23. ===========================================================*/
  24. namespace System.Collections.Generic
  25. {
  26.    
  27.     using System;
  28.     using System.Globalization;
  29.     using System.Runtime.CompilerServices;
  30.    
  31.     [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")]
  32.     internal class ArraySortHelper<T>
  33.     {
  34.         static ArraySortHelper<T> defaultArraySortHelper;
  35.        
  36.         public static ArraySortHelper<T> Default {
  37.             get {
  38.                 ArraySortHelper<T> sorter = defaultArraySortHelper;
  39.                 if (sorter != null) {
  40.                     return sorter;
  41.                 }
  42.                 return CreateArraySortHelper();
  43.             }
  44.         }
  45.        
  46.         private static ArraySortHelper<T> CreateArraySortHelper()
  47.         {
  48.             if (typeof(IComparable<T>).IsAssignableFrom(typeof(T))) {
  49.                 defaultArraySortHelper = (ArraySortHelper<T>)(typeof(GenericArraySortHelper<string>).TypeHandle.CreateInstanceForAnotherGenericParameter(typeof(T)));
  50.             }
  51.             else {
  52.                 defaultArraySortHelper = new ArraySortHelper<T>();
  53.             }
  54.             return defaultArraySortHelper;
  55.         }
  56.        
  57.         public void Sort(T[] items, int index, int length, IComparer<T> comparer)
  58.         {
  59.             Sort<object>(items, (object[])null, index, length, comparer);
  60.         }
  61.        
  62.         public virtual void Sort<TValue>(T[] keys, TValue[] values, int index, int length, IComparer<T> comparer)
  63.         {
  64.             BCLDebug.Assert(keys != null, "Check the arguments in the caller!");
  65.             BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
  66.            
  67.             if (comparer == null || comparer == Comparer<T>.Default) {
  68.                 comparer = Comparer<T>.Default;
  69.             }
  70.            
  71.             QuickSort(keys, values, index, index + (length - 1), comparer);
  72.         }
  73.        
  74.         private void QuickSort<TValue>(T[] keys, TValue[] values, int left, int right, IComparer<T> comparer)
  75.         {
  76.             do {
  77.                 int i = left;
  78.                 int j = right;
  79.                 T x = keys[i + ((j - i) >> 1)];
  80.                 do {
  81.                     // Add a try block here to detect IComparers (or their
  82.                     // underlying IComparables, etc) that are bogus.
  83.                     try {
  84.                         while (comparer.Compare(keys[i], x) < 0)
  85.                             i++;
  86.                         while (comparer.Compare(x, keys[j]) < 0)
  87.                             j--;
  88.                     }
  89.                     catch (IndexOutOfRangeException) {
  90.                         throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", x, x.GetType().Name, comparer));
  91.                     }
  92.                     catch (Exception e) {
  93.                         throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  94.                     }
  95.                     BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?");
  96.                     if (i > j)
  97.                         break;
  98.                     if (i < j) {
  99.                         T key = keys[i];
  100.                         keys[i] = keys[j];
  101.                         keys[j] = key;
  102.                         if (values != null) {
  103.                             TValue value = values[i];
  104.                             values[i] = values[j];
  105.                             values[j] = value;
  106.                         }
  107.                     }
  108.                     i++;
  109.                     j--;
  110.                 }
  111.                 while (i <= j);
  112.                 if (j - left <= right - i) {
  113.                     if (left < j)
  114.                         QuickSort(keys, values, left, j, comparer);
  115.                     left = i;
  116.                 }
  117.                 else {
  118.                     if (i < right)
  119.                         QuickSort(keys, values, i, right, comparer);
  120.                     right = j;
  121.                 }
  122.             }
  123.             while (left < right);
  124.         }
  125.        
  126.         public virtual int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
  127.         {
  128.             BCLDebug.Assert(array != null, "Check the arguments in the caller!");
  129.             BCLDebug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
  130.            
  131.             if (comparer == null) {
  132.                 comparer = System.Collections.Generic.Comparer<T>.Default;
  133.             }
  134.            
  135.             int lo = index;
  136.             int hi = index + length - 1;
  137.             while (lo <= hi) {
  138.                 int i = lo + ((hi - lo) >> 1);
  139.                 int order;
  140.                 try {
  141.                     order = comparer.Compare(array[i], value);
  142.                 }
  143.                 catch (Exception e) {
  144.                     throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  145.                 }
  146.                
  147.                 if (order == 0)
  148.                     return i;
  149.                 if (order < 0) {
  150.                     lo = i + 1;
  151.                 }
  152.                 else {
  153.                     hi = i - 1;
  154.                 }
  155.             }
  156.            
  157.             return ~lo;
  158.         }
  159.     }
  160.    
  161.    
  162.     [Serializable()]
  163.     internal class GenericArraySortHelper<T> : ArraySortHelper<T> where T : IComparable<T>
  164.     {
  165.         public override int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer)
  166.         {
  167.             BCLDebug.Assert(array != null, "Check the arguments in the caller!");
  168.             BCLDebug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!");
  169.            
  170.             if (comparer == null || comparer == Comparer<T>.Default) {
  171.                 return BinarySearch(array, index, length, value);
  172.             }
  173.             else {
  174.                 return base.BinarySearch(array, index, length, value, comparer);
  175.             }
  176.         }
  177.        
  178.         public override void Sort<TValue>(T[] keys, TValue[] values, int index, int length, IComparer<T> comparer)
  179.         {
  180.             BCLDebug.Assert(keys != null, "Check the arguments in the caller!");
  181.             BCLDebug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!");
  182.            
  183.             if (comparer == null || comparer == Comparer<T>.Default) {
  184.                 // call the fatser version of QuickSort if the user doesn't provide a comparer
  185.                 QuickSort(keys, values, index, index + length - 1);
  186.             }
  187.             else {
  188.                 base.Sort(keys, values, index, length, comparer);
  189.             }
  190.         }
  191.        
  192.         // This function is called when the user doesn't specify any comparer.
  193.         // Since T is constrained here, we can call IComparable<T>.CompareTo here.
  194.         // We can avoid boxing for value type and casting for reference types.
  195.         private int BinarySearch(T[] array, int index, int length, T value)
  196.         {
  197.             int lo = index;
  198.             int hi = index + length - 1;
  199.             while (lo <= hi) {
  200.                 int i = lo + ((hi - lo) >> 1);
  201.                 int order;
  202.                 try {
  203.                     if (array[i] == null) {
  204.                         order = (value == null) ? 0 : -1;
  205.                     }
  206.                     else {
  207.                         order = array[i].CompareTo(value);
  208.                     }
  209.                 }
  210.                 catch (Exception e) {
  211.                     throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  212.                 }
  213.                
  214.                 if (order == 0)
  215.                     return i;
  216.                 if (order < 0) {
  217.                     lo = i + 1;
  218.                 }
  219.                 else {
  220.                     hi = i - 1;
  221.                 }
  222.             }
  223.            
  224.             return ~lo;
  225.         }
  226.        
  227.         private void QuickSort<TValue>(T[] keys, TValue[] values, int left, int right)
  228.         {
  229.             // The code in this function looks very similar to QuickSort in ArraySortHelper<T> class.
  230.             // The difference is that T is constrainted to IComparable<T> here.
  231.             // So the IL code will be different. This function is faster than the one in ArraySortHelper<T>.
  232.             do {
  233.                 int i = left;
  234.                 int j = right;
  235.                 T x = keys[i + ((j - i) >> 1)];
  236.                 do {
  237.                     // Add a try block here to detect IComparers (or their
  238.                     // underlying IComparables, etc) that are bogus.
  239.                     try {
  240.                         if (x == null) {
  241.                             // if x null, the loop to find two elements to be switched can be reduced.
  242.                             while (keys[j] != null)
  243.                                 j--;
  244.                         }
  245.                         else {
  246.                             while (x.CompareTo(keys[i]) > 0)
  247.                                 i++;
  248.                             while (x.CompareTo(keys[j]) < 0)
  249.                                 j--;
  250.                         }
  251.                     }
  252.                     catch (IndexOutOfRangeException) {
  253.                         throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", x, x.GetType().Name, null));
  254.                     }
  255.                     catch (Exception e) {
  256.                         throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e);
  257.                     }
  258.                     BCLDebug.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?");
  259.                     if (i > j)
  260.                         break;
  261.                     if (i < j) {
  262.                         T key = keys[i];
  263.                         keys[i] = keys[j];
  264.                         keys[j] = key;
  265.                         if (values != null) {
  266.                             TValue value = values[i];
  267.                             values[i] = values[j];
  268.                             values[j] = value;
  269.                         }
  270.                     }
  271.                     i++;
  272.                     j--;
  273.                 }
  274.                 while (i <= j);
  275.                 if (j - left <= right - i) {
  276.                     if (left < j)
  277.                         QuickSort(keys, values, left, j);
  278.                     left = i;
  279.                 }
  280.                 else {
  281.                     if (i < right)
  282.                         QuickSort(keys, values, i, right);
  283.                     right = j;
  284.                 }
  285.             }
  286.             while (left < right);
  287.         }
  288.     }
  289. }

Developer Fusion