mcs/class/corlib/coreclr/SorterArray.cs

   1 using System.Collections;
   2 using System.Collections.Generic;
   3
   4 namespace System
   5 {
   6         partial class Array
   7         {
   8         // Private value type used by the Sort methods.
   9         private struct SorterObjectArray
  10         {
  11             private Object[] keys;
  12             private Object[] items;
  13             private IComparer comparer;
  14
  15             internal SorterObjectArray(Object[] keys, Object[] items, IComparer comparer)
  16             {
  17                 if (comparer == null) comparer = Comparer.Default;
  18                 this.keys = keys;
  19                 this.items = items;
  20                 this.comparer = comparer;
  21             }
  22
  23             internal void SwapIfGreaterWithItems(int a, int b)
  24             {
  25                 if (a != b)
  26                 {
  27                     if (comparer.Compare(keys[a], keys[b]) > 0)
  28                     {
  29                         Object temp = keys[a];
  30                         keys[a] = keys[b];
  31                         keys[b] = temp;
  32                         if (items != null)
  33                         {
  34                             Object item = items[a];
  35                             items[a] = items[b];
  36                             items[b] = item;
  37                         }
  38                     }
  39                 }
  40             }
  41
  42             private void Swap(int i, int j)
  43             {
  44                 Object t = keys[i];
  45                 keys[i] = keys[j];
  46                 keys[j] = t;
  47
  48                 if (items != null)
  49                 {
  50                     Object item = items[i];
  51                     items[i] = items[j];
  52                     items[j] = item;
  53                 }
  54             }
  55
  56             internal void Sort(int left, int length)
  57             {
  58                 IntrospectiveSort(left, length);
  59             }
  60
  61             private void IntrospectiveSort(int left, int length)
  62             {
  63                 if (length < 2)
  64                     return;
  65
  66                 try
  67                 {
  68                     IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
  69                 }
  70                 catch (IndexOutOfRangeException)
  71                 {
  72                     IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
  73                 }
  74                 catch (Exception e)
  75                 {
  76                     throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
  77                 }
  78             }
  79
  80             private void IntroSort(int lo, int hi, int depthLimit)
  81             {
  82                 while (hi > lo)
  83                 {
  84                     int partitionSize = hi - lo + 1;
  85                     if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
  86                     {
  87                         if (partitionSize == 1)
  88                         {
  89                             return;
  90                         }
  91                         if (partitionSize == 2)
  92                         {
  93                             SwapIfGreaterWithItems(lo, hi);
  94                             return;
  95                         }
  96                         if (partitionSize == 3)
  97                         {
  98                             SwapIfGreaterWithItems(lo, hi - 1);
  99                             SwapIfGreaterWithItems(lo, hi);
 100                             SwapIfGreaterWithItems(hi - 1, hi);
 101                             return;
 102                         }
 103
 104                         InsertionSort(lo, hi);
 105                         return;
 106                     }
 107
 108                     if (depthLimit == 0)
 109                     {
 110                         Heapsort(lo, hi);
 111                         return;
 112                     }
 113                     depthLimit--;
 114
 115                     int p = PickPivotAndPartition(lo, hi);
 116                     IntroSort(p + 1, hi, depthLimit);
 117                     hi = p - 1;
 118                 }
 119             }
 120
 121             private int PickPivotAndPartition(int lo, int hi)
 122             {
 123                 // Compute median-of-three.  But also partition them, since we've done the comparison.
 124                 int mid = lo + (hi - lo) / 2;
 125                 // Sort lo, mid and hi appropriately, then pick mid as the pivot.
 126                 SwapIfGreaterWithItems(lo, mid);
 127                 SwapIfGreaterWithItems(lo, hi);
 128                 SwapIfGreaterWithItems(mid, hi);
 129
 130                 Object pivot = keys[mid];
 131                 Swap(mid, hi - 1);
 132                 int left = lo, right = hi - 1;  // We already partitioned lo and hi and put the pivot in hi - 1.  And we pre-increment & decrement below.
 133
 134                 while (left < right)
 135                 {
 136                     while (comparer.Compare(keys[++left], pivot) < 0) ;
 137                     while (comparer.Compare(pivot, keys[--right]) < 0) ;
 138
 139                     if (left >= right)
 140                         break;
 141
 142                     Swap(left, right);
 143                 }
 144
 145                 // Put pivot in the right location.
 146                 Swap(left, (hi - 1));
 147                 return left;
 148             }
 149
 150             private void Heapsort(int lo, int hi)
 151             {
 152                 int n = hi - lo + 1;
 153                 for (int i = n / 2; i >= 1; i = i - 1)
 154                 {
 155                     DownHeap(i, n, lo);
 156                 }
 157                 for (int i = n; i > 1; i = i - 1)
 158                 {
 159                     Swap(lo, lo + i - 1);
 160
 161                     DownHeap(1, i - 1, lo);
 162                 }
 163             }
 164
 165             private void DownHeap(int i, int n, int lo)
 166             {
 167                 Object d = keys[lo + i - 1];
 168                 Object dt = (items != null) ? items[lo + i - 1] : null;
 169                 int child;
 170                 while (i <= n / 2)
 171                 {
 172                     child = 2 * i;
 173                     if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
 174                     {
 175                         child++;
 176                     }
 177                     if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
 178                         break;
 179                     keys[lo + i - 1] = keys[lo + child - 1];
 180                     if (items != null)
 181                         items[lo + i - 1] = items[lo + child - 1];
 182                     i = child;
 183                 }
 184                 keys[lo + i - 1] = d;
 185                 if (items != null)
 186                     items[lo + i - 1] = dt;
 187             }
 188
 189             private void InsertionSort(int lo, int hi)
 190             {
 191                 int i, j;
 192                 Object t, ti;
 193                 for (i = lo; i < hi; i++)
 194                 {
 195                     j = i;
 196                     t = keys[i + 1];
 197                     ti = (items != null) ? items[i + 1] : null;
 198                     while (j >= lo && comparer.Compare(t, keys[j]) < 0)
 199                     {
 200                         keys[j + 1] = keys[j];
 201                         if (items != null)
 202                             items[j + 1] = items[j];
 203                         j--;
 204                     }
 205                     keys[j + 1] = t;
 206                     if (items != null)
 207                         items[j + 1] = ti;
 208                 }
 209             }
 210         }
 211
 212         // Private value used by the Sort methods for instances of Array.
 213         // This is slower than the one for Object[], since we can't use the JIT helpers
 214         // to access the elements.  We must use GetValue & SetValue.
 215         private struct SorterGenericArray
 216         {
 217             private Array keys;
 218             private Array items;
 219             private IComparer comparer;
 220
 221             internal SorterGenericArray(Array keys, Array items, IComparer comparer)
 222             {
 223                 if (comparer == null) comparer = Comparer.Default;
 224                 this.keys = keys;
 225                 this.items = items;
 226                 this.comparer = comparer;
 227             }
 228
 229             internal void SwapIfGreaterWithItems(int a, int b)
 230             {
 231                 if (a != b)
 232                 {
 233                     if (comparer.Compare(keys.GetValue(a), keys.GetValue(b)) > 0)
 234                     {
 235                         Object key = keys.GetValue(a);
 236                         keys.SetValue(keys.GetValue(b), a);
 237                         keys.SetValue(key, b);
 238                         if (items != null)
 239                         {
 240                             Object item = items.GetValue(a);
 241                             items.SetValue(items.GetValue(b), a);
 242                             items.SetValue(item, b);
 243                         }
 244                     }
 245                 }
 246             }
 247
 248             private void Swap(int i, int j)
 249             {
 250                 Object t1 = keys.GetValue(i);
 251                 keys.SetValue(keys.GetValue(j), i);
 252                 keys.SetValue(t1, j);
 253
 254                 if (items != null)
 255                 {
 256                     Object t2 = items.GetValue(i);
 257                     items.SetValue(items.GetValue(j), i);
 258                     items.SetValue(t2, j);
 259                 }
 260             }
 261
 262             internal void Sort(int left, int length)
 263             {
 264                 IntrospectiveSort(left, length);
 265             }
 266
 267             private void IntrospectiveSort(int left, int length)
 268             {
 269                 if (length < 2)
 270                     return;
 271
 272                 try
 273                 {
 274                     IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length));
 275                 }
 276                 catch (IndexOutOfRangeException)
 277                 {
 278                     IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
 279                 }
 280                 catch (Exception e)
 281                 {
 282                     throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e);
 283                 }
 284             }
 285
 286             private void IntroSort(int lo, int hi, int depthLimit)
 287             {
 288                 while (hi > lo)
 289                 {
 290                     int partitionSize = hi - lo + 1;
 291                     if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
 292                     {
 293                         if (partitionSize == 1)
 294                         {
 295                             return;
 296                         }
 297                         if (partitionSize == 2)
 298                         {
 299                             SwapIfGreaterWithItems(lo, hi);
 300                             return;
 301                         }
 302                         if (partitionSize == 3)
 303                         {
 304                             SwapIfGreaterWithItems(lo, hi - 1);
 305                             SwapIfGreaterWithItems(lo, hi);
 306                             SwapIfGreaterWithItems(hi - 1, hi);
 307                             return;
 308                         }
 309
 310                         InsertionSort(lo, hi);
 311                         return;
 312                     }
 313
 314                     if (depthLimit == 0)
 315                     {
 316                         Heapsort(lo, hi);
 317                         return;
 318                     }
 319                     depthLimit--;
 320
 321                     int p = PickPivotAndPartition(lo, hi);
 322                     IntroSort(p + 1, hi, depthLimit);
 323                     hi = p - 1;
 324                 }
 325             }
 326
 327             private int PickPivotAndPartition(int lo, int hi)
 328             {
 329                 // Compute median-of-three.  But also partition them, since we've done the comparison.
 330                 int mid = lo + (hi - lo) / 2;
 331
 332                 SwapIfGreaterWithItems(lo, mid);
 333                 SwapIfGreaterWithItems(lo, hi);
 334                 SwapIfGreaterWithItems(mid, hi);
 335
 336                 Object pivot = keys.GetValue(mid);
 337                 Swap(mid, hi - 1);
 338                 int left = lo, right = hi - 1;  // We already partitioned lo and hi and put the pivot in hi - 1.  And we pre-increment & decrement below.
 339
 340                 while (left < right)
 341                 {
 342                     while (comparer.Compare(keys.GetValue(++left), pivot) < 0) ;
 343                     while (comparer.Compare(pivot, keys.GetValue(--right)) < 0) ;
 344
 345                     if (left >= right)
 346                         break;
 347
 348                     Swap(left, right);
 349                 }
 350
 351                 // Put pivot in the right location.
 352                 Swap(left, (hi - 1));
 353                 return left;
 354             }
 355
 356             private void Heapsort(int lo, int hi)
 357             {
 358                 int n = hi - lo + 1;
 359                 for (int i = n / 2; i >= 1; i = i - 1)
 360                 {
 361                     DownHeap(i, n, lo);
 362                 }
 363                 for (int i = n; i > 1; i = i - 1)
 364                 {
 365                     Swap(lo, lo + i - 1);
 366
 367                     DownHeap(1, i - 1, lo);
 368                 }
 369             }
 370
 371             private void DownHeap(int i, int n, int lo)
 372             {
 373                 Object d = keys.GetValue(lo + i - 1);
 374                 Object dt = (items != null) ? items.GetValue(lo + i - 1) : null;
 375                 int child;
 376                 while (i <= n / 2)
 377                 {
 378                     child = 2 * i;
 379                     if (child < n && comparer.Compare(keys.GetValue(lo + child - 1), keys.GetValue(lo + child)) < 0)
 380                     {
 381                         child++;
 382                     }
 383
 384                     if (!(comparer.Compare(d, keys.GetValue(lo + child - 1)) < 0))
 385                         break;
 386
 387                     keys.SetValue(keys.GetValue(lo + child - 1), lo + i - 1);
 388                     if (items != null)
 389                         items.SetValue(items.GetValue(lo + child - 1), lo + i - 1);
 390                     i = child;
 391                 }
 392                 keys.SetValue(d, lo + i - 1);
 393                 if (items != null)
 394                     items.SetValue(dt, lo + i - 1);
 395             }
 396
 397             private void InsertionSort(int lo, int hi)
 398             {
 399                 int i, j;
 400                 Object t, dt;
 401                 for (i = lo; i < hi; i++)
 402                 {
 403                     j = i;
 404                     t = keys.GetValue(i + 1);
 405                     dt = (items != null) ? items.GetValue(i + 1) : null;
 406
 407                     while (j >= lo && comparer.Compare(t, keys.GetValue(j)) < 0)
 408                     {
 409                         keys.SetValue(keys.GetValue(j), j + 1);
 410                         if (items != null)
 411                             items.SetValue(items.GetValue(j), j + 1);
 412                         j--;
 413                     }
 414
 415                     keys.SetValue(t, j + 1);
 416                     if (items != null)
 417                         items.SetValue(dt, j + 1);
 418                 }
 419             }
 420         }
 421     }
 422 }