mcs/class/Mono.C5/C5/Sorting.cs

   1 #if NET_2_0
   2 /*\r
   3  Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft\r
   4  Permission is hereby granted, free of charge, to any person obtaining a copy\r
   5  of this software and associated documentation files (the "Software"), to deal\r
   6  in the Software without restriction, including without limitation the rights\r
   7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell\r
   8  copies of the Software, and to permit persons to whom the Software is\r
   9  furnished to do so, subject to the following conditions:\r
  10  \r
  11  The above copyright notice and this permission notice shall be included in\r
  12  all copies or substantial portions of the Software.\r
  13  \r
  14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\r
  15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\r
  16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\r
  17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\r
  18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\r
  19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\r
  20  SOFTWARE.\r
  21 */\r
  22 using System;\r
  23 using System.Diagnostics;\r
  24 using SCG = System.Collections.Generic;\r
  25 namespace C5\r
  26 {\r
  27   /// <summary>\r
  28   /// A utility class with functions for sorting arrays with respect to an IComparer&lt;T&gt;\r
  29   /// </summary>\r
  30   public class Sorting\r
  31   {\r
  32     Sorting() { }\r
  33 \r
  34     /// <summary>\r
  35     /// Sort part of array in place using IntroSort\r
  36     /// </summary>\r
  37     /// <exception cref="ArgumentOutOfRangeException">If the <code>start</code>\r
  38     /// and <code>count</code> arguments does not describe a valid range.</exception>\r
  39     /// <param name="array">Array to sort</param>\r
  40     /// <param name="start">Index of first position to sort</param>\r
  41     /// <param name="count">Number of elements to sort</param>\r
  42     /// <param name="comparer">IComparer&lt;T&gt; to sort by</param>\r
  43     [Tested]\r
  44     public static void IntroSort<T>(T[] array, int start, int count, SCG.IComparer<T> comparer)\r
  45     {\r
  46       if (start < 0 || count < 0 || start + count > array.Length)\r
  47         throw new ArgumentOutOfRangeException();\r
  48       new Sorter<T>(array, comparer).IntroSort(start, start + count);\r
  49     }\r
  50 \r
  51     /// <summary>\r
  52     /// Sort an array in place using IntroSort and default comparer\r
  53     /// </summary>\r
  54     /// <exception cref="NotComparableException">If T is not comparable</exception>\r
  55     /// <param name="array">Array to sort</param>\r
  56     [Tested]\r
  57     public static void IntroSort<T>(T[] array)\r
  58     {\r
  59       new Sorter<T>(array, Comparer<T>.Default).IntroSort(0, array.Length);\r
  60     }\r
  61 \r
  62 \r
  63     /// <summary>\r
  64     /// Sort part of array in place using Insertion Sort\r
  65     /// </summary>\r
  66     /// <exception cref="ArgumentOutOfRangeException">If the <code>start</code>\r
  67     /// and <code>count</code> arguments does not describe a valid range.</exception>\r
  68     /// <param name="array">Array to sort</param>\r
  69     /// <param name="start">Index of first position to sort</param>\r
  70     /// <param name="count">Number of elements to sort</param>\r
  71     /// <param name="comparer">IComparer&lt;T&gt; to sort by</param>\r
  72     [Tested]\r
  73     public static void InsertionSort<T>(T[] array, int start, int count, SCG.IComparer<T> comparer)\r
  74     {\r
  75       if (start < 0 || count < 0 || start + count > array.Length)\r
  76         throw new ArgumentOutOfRangeException();\r
  77       new Sorter<T>(array, comparer).InsertionSort(start, start + count);\r
  78     }\r
  79 \r
  80 \r
  81     /// <summary>\r
  82     /// Sort part of array in place using Heap Sort\r
  83     /// </summary>\r
  84     /// <exception cref="ArgumentOutOfRangeException">If the <code>start</code>\r
  85     /// and <code>count</code> arguments does not describe a valid range.</exception>\r
  86     /// <param name="array">Array to sort</param>\r
  87     /// <param name="start">Index of first position to sort</param>\r
  88     /// <param name="count">Number of elements to sort</param>\r
  89     /// <param name="comparer">IComparer&lt;T&gt; to sort by</param>\r
  90     [Tested]\r
  91     public static void HeapSort<T>(T[] array, int start, int count, SCG.IComparer<T> comparer)\r
  92     {\r
  93       if (start < 0 || count < 0 || start + count > array.Length)\r
  94         throw new ArgumentOutOfRangeException();\r
  95       new Sorter<T>(array, comparer).HeapSort(start, start + count);\r
  96     }\r
  97 \r
  98 \r
  99     class Sorter<T>\r
 100     {\r
 101       T[] a;\r
 102 \r
 103       SCG.IComparer<T> c;\r
 104 \r
 105 \r
 106       internal Sorter(T[] a, SCG.IComparer<T> c) { this.a = a; this.c = c; }\r
 107 \r
 108 \r
 109       internal void IntroSort(int f, int b)\r
 110       {\r
 111         if (b - f > 31)\r
 112         {\r
 113           int depth_limit = (int)Math.Floor(2.5 * Math.Log(b - f, 2));\r
 114 \r
 115           introSort(f, b, depth_limit);\r
 116         }\r
 117         else\r
 118           InsertionSort(f, b);\r
 119       }\r
 120 \r
 121 \r
 122       private void introSort(int f, int b, int depth_limit)\r
 123       {\r
 124         const int size_threshold = 14;//24;\r
 125 \r
 126         if (depth_limit-- == 0)\r
 127           HeapSort(f, b);\r
 128         else if (b - f <= size_threshold)\r
 129           InsertionSort(f, b);\r
 130         else\r
 131         {\r
 132           int p = partition(f, b);\r
 133 \r
 134           introSort(f, p, depth_limit);\r
 135           introSort(p, b, depth_limit);\r
 136         }\r
 137       }\r
 138 \r
 139 \r
 140       private int compare(T i1, T i2) { return c.Compare(i1, i2); }\r
 141 \r
 142 \r
 143       private int partition(int f, int b)\r
 144       {\r
 145         int bot = f, mid = (b + f) / 2, top = b - 1;\r
 146         T abot = a[bot], amid = a[mid], atop = a[top];\r
 147 \r
 148         if (compare(abot, amid) < 0)\r
 149         {\r
 150           if (compare(atop, abot) < 0)//atop<abot<amid\r
 151           { a[top] = amid; amid = a[mid] = abot; a[bot] = atop; }\r
 152           else if (compare(atop, amid) < 0) //abot<=atop<amid\r
 153           { a[top] = amid; amid = a[mid] = atop; }\r
 154           //else abot<amid<=atop\r
 155         }\r
 156         else\r
 157         {\r
 158           if (compare(amid, atop) > 0) //atop<amid<=abot\r
 159           { a[bot] = atop; a[top] = abot; }\r
 160           else if (compare(abot, atop) > 0) //amid<=atop<abot\r
 161           { a[bot] = amid; amid = a[mid] = atop; a[top] = abot; }\r
 162           else //amid<=abot<=atop\r
 163           { a[bot] = amid; amid = a[mid] = abot; }\r
 164         }\r
 165 \r
 166         int i = bot, j = top;\r
 167 \r
 168         while (true)\r
 169         {\r
 170           while (compare(a[++i], amid) < 0) ;\r
 171 \r
 172           while (compare(amid, a[--j]) < 0) ;\r
 173 \r
 174           if (i < j)\r
 175           {\r
 176             T tmp = a[i]; a[i] = a[j]; a[j] = tmp;\r
 177           }\r
 178           else\r
 179             return i;\r
 180         }\r
 181       }\r
 182 \r
 183 \r
 184       internal void InsertionSort(int f, int b)\r
 185       {\r
 186         for (int j = f + 1; j < b; j++)\r
 187         {\r
 188           T key = a[j], other;\r
 189           int i = j - 1;\r
 190 \r
 191           if (c.Compare(other = a[i], key) > 0)\r
 192           {\r
 193             a[j] = other;\r
 194             while (i > f && c.Compare(other = a[i - 1], key) > 0) { a[i--] = other; }\r
 195 \r
 196             a[i] = key;\r
 197           }\r
 198         }\r
 199       }\r
 200 \r
 201 \r
 202       internal void HeapSort(int f, int b)\r
 203       {\r
 204         for (int i = (b + f) / 2; i >= f; i--) heapify(f, b, i);\r
 205 \r
 206         for (int i = b - 1; i > f; i--)\r
 207         {\r
 208           T tmp = a[f]; a[f] = a[i]; a[i] = tmp;\r
 209           heapify(f, i, f);\r
 210         }\r
 211       }\r
 212 \r
 213 \r
 214       private void heapify(int f, int b, int i)\r
 215       {\r
 216         T pv = a[i], lv, rv, max = pv;\r
 217         int j = i, maxpt = j;\r
 218 \r
 219         while (true)\r
 220         {\r
 221           int l = 2 * j - f + 1, r = l + 1;\r
 222 \r
 223           if (l < b && compare(lv = a[l], max) > 0) { maxpt = l; max = lv; }\r
 224 \r
 225           if (r < b && compare(rv = a[r], max) > 0) { maxpt = r; max = rv; }\r
 226 \r
 227           if (maxpt == j)\r
 228             break;\r
 229 \r
 230           a[j] = max;\r
 231           max = pv;\r
 232           j = maxpt;\r
 233         }\r
 234 \r
 235         if (j > i)\r
 236           a[j] = pv;\r
 237       }\r
 238     }\r
 239   }\r
 240 }
 241 #endif