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

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