src/intervalstore/nonc/IntervalEndSorter.java

   1 /*
   2  * Copyright (c) 2009, 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25
  26 package intervalstore.nonc;
  27
  28 import intervalstore.api.IntervalI;
  29
  30 /**
  31  * A dual pivot quicksort for int[] where the int is a pointer to something for
  32  * which the value needs to be checked. This class is not used; it was just an
  33  * idea I was trying. But it is sort of cool, so I am keeping it in the package
  34  * for possible future use.
  35  *
  36  * Adapted from Java 7 java.util.DualPivotQuicksort -- int[] only. The only
  37  * difference is that wherever an a[] value is compared, we use val(a[i])
  38  * instead of a[i] itself. Pretty straightforward. Could be adapted for general
  39  * use. Why didn't they do this in Java?
  40  *
  41  * val(i) is just a hack here, of course. A more general implementation might
  42  * use a Function call.
  43  *
  44  * Just thought it was cool that you can do this.
  45  *
  46  * @author Bob Hanson 2019.09.02
  47  *
  48  */
  49
  50 class IntervalEndSorter
  51 {
  52
  53   private IntervalI[] intervals;
  54
  55   private int val(int i)
  56   {
  57     return intervals[i].getEnd();
  58   }
  59
  60   /*
  61    * Tuning parameters.
  62    */
  63
  64   /**
  65    * The maximum number of runs in merge sort.
  66    */
  67   private static final int MAX_RUN_COUNT = 67;
  68
  69   /**
  70    * The maximum length of run in merge sort.
  71    */
  72   private static final int MAX_RUN_LENGTH = 33;
  73
  74   /**
  75    * If the length of an array to be sorted is less than this constant,
  76    * Quicksort is used in preference to merge sort.
  77    */
  78   private static final int QUICKSORT_THRESHOLD = 286;
  79
  80   /**
  81    * If the length of an array to be sorted is less than this constant,
  82    * insertion sort is used in preference to Quicksort.
  83    */
  84   private static final int INSERTION_SORT_THRESHOLD = 47;
  85
  86   /*
  87    * Sorting methods for seven primitive types.
  88    */
  89
  90   /**
  91    * Sorts the specified range of the array using the given workspace array
  92    * slice if possible for merging
  93    *
  94    * @param a
  95    *          the array to be sorted
  96    * @param left
  97    *          the index of the first element, inclusive, to be sorted
  98    * @param right
  99    *          the index of the last element, inclusive, to be sorted
 100    * @param work
 101    *          a workspace array (slice)
 102    * @param workBase
 103    *          origin of usable space in work array
 104    * @param workLen
 105    *          usable size of work array
 106    */
 107   void sort(int[] a, IntervalI[] intervals, int len)
 108   {
 109     this.intervals = intervals;
 110
 111     int left = 0, right = len - 1;
 112     // Use Quicksort on small arrays
 113     if (right - left < QUICKSORT_THRESHOLD)
 114     {
 115       sort(a, left, right, true);
 116       return;
 117     }
 118
 119     /*
 120      * Index run[i] is the start of i-th run
 121      * (ascending or descending sequence).
 122      */
 123     int[] run = new int[MAX_RUN_COUNT + 1];
 124     int count = 0;
 125     run[0] = left;
 126
 127     // Check if the array is nearly sorted
 128     for (int k = left; k < right; run[count] = k)
 129     {
 130       switch (Integer.signum(val(a[k + 1]) - val(a[k])))
 131       {
 132       case 1:
 133         // ascending
 134         while (++k <= right && val(a[k - 1]) <= val(a[k]))
 135           ;
 136         break;
 137       case -1:
 138         // descending
 139         while (++k <= right && val(a[k - 1]) >= val(a[k]))
 140           ;
 141         for (int lo = run[count] - 1, hi = k; ++lo < --hi;)
 142         {
 143           int t = a[lo];
 144           a[lo] = a[hi];
 145           a[hi] = t;
 146         }
 147         break;
 148       default:
 149         // equal
 150         for (int m = MAX_RUN_LENGTH; ++k <= right
 151                 && val(a[k - 1]) == val(a[k]);)
 152         {
 153           if (--m == 0)
 154           {
 155             sort(a, left, right, true);
 156             return;
 157           }
 158         }
 159       }
 160
 161       /*
 162        * The array is not highly structured,
 163        * use Quicksort instead of merge sort.
 164        */
 165       if (++count == MAX_RUN_COUNT)
 166       {
 167         sort(a, left, right, true);
 168         return;
 169       }
 170     }
 171
 172     // Check special cases
 173     // Implementation note: variable "right" is increased by 1.
 174     if (run[count] == right++)
 175     { // The last run contains one element
 176       run[++count] = right;
 177     }
 178     else if (count == 1)
 179     { // The array is already sorted
 180       return;
 181     }
 182
 183     // Determine alternation base for merge
 184     byte odd = 0;
 185     for (int n = 1; (n <<= 1) < count; odd ^= 1)
 186       ;
 187
 188     // Use or create temporary array b for merging
 189     int[] b; // temp array; alternates with a
 190     int ao, bo; // array offsets from 'left'
 191     int blen = right - left; // space needed for b
 192     int[] work = new int[blen];
 193     int workBase = 0;
 194     if (odd == 0)
 195     {
 196       System.arraycopy(a, left, work, workBase, blen);
 197       b = a;
 198       bo = 0;
 199       a = work;
 200       ao = workBase - left;
 201     }
 202     else
 203     {
 204       b = work;
 205       ao = 0;
 206       bo = workBase - left;
 207     }
 208
 209     // Merging
 210     for (int last; count > 1; count = last)
 211     {
 212       for (int k = (last = 0) + 2; k <= count; k += 2)
 213       {
 214         int hi = run[k], mi = run[k - 1];
 215         for (int i = run[k - 2], p = i, q = mi; i < hi; ++i)
 216         {
 217           if (q >= hi || p < mi && val(a[p + ao]) <= val(a[q + ao]))
 218           {
 219             b[i + bo] = a[p++ + ao];
 220           }
 221           else
 222           {
 223             b[i + bo] = a[q++ + ao];
 224           }
 225         }
 226         run[++last] = hi;
 227       }
 228       if ((count & 1) != 0)
 229       {
 230         for (int i = right, lo = run[count - 1]; --i >= lo; b[i + bo] = a[i
 231                 + ao])
 232           ;
 233         run[++last] = right;
 234       }
 235       int[] t = a;
 236       a = b;
 237       b = t;
 238       int o = ao;
 239       ao = bo;
 240       bo = o;
 241     }
 242   }
 243
 244   /**
 245    * Sorts the specified range of the array by Dual-Pivot Quicksort.
 246    *
 247    * @param a
 248    *          the array to be sorted
 249    * @param left
 250    *          the index of the first element, inclusive, to be sorted
 251    * @param right
 252    *          the index of the last element, inclusive, to be sorted
 253    * @param leftmost
 254    *          indicates if this part is the leftmost in the range
 255    */
 256   private void sort(int[] a, int left, int right, boolean leftmost)
 257   {
 258     int length = right - left + 1;
 259
 260     // Use insertion sort on tiny arrays
 261     if (length < INSERTION_SORT_THRESHOLD)
 262     {
 263       if (leftmost)
 264       {
 265         /*
 266          * Traditional (without sentinel) insertion sort,
 267          * optimized for server VM, is used in case of
 268          * the leftmost part.
 269          */
 270         for (int i = left, j = i; i < right; j = ++i)
 271         {
 272           int ai = a[i + 1];
 273           while (val(ai) < val(a[j]))
 274           {
 275             a[j + 1] = a[j];
 276             if (j-- == left)
 277             {
 278               break;
 279             }
 280           }
 281           a[j + 1] = ai;
 282         }
 283       }
 284       else
 285       {
 286         /*
 287          * Skip the longest ascending sequence.
 288          */
 289         do
 290         {
 291           if (left >= right)
 292           {
 293             return;
 294           }
 295         } while (val(a[++left]) >= val(a[left - 1]));
 296
 297         /*
 298          * Every element from adjoining part plays the role
 299          * of sentinel, therefore this allows us to avoid the
 300          * left range check on each iteration. Moreover, we use
 301          * the more optimized algorithm, so called pair insertion
 302          * sort, which is faster (in the context of Quicksort)
 303          * than traditional implementation of insertion sort.
 304          */
 305         for (int k = left; ++left <= right; k = ++left)
 306         {
 307           int a1 = a[k], a2 = a[left];
 308
 309           if (val(a1) < val(a2))
 310           {
 311             a2 = a1;
 312             a1 = a[left];
 313           }
 314           while (val(a1) < val(a[--k]))
 315           {
 316             a[k + 2] = a[k];
 317           }
 318           a[++k + 1] = a1;
 319
 320           while (val(a2) < val(a[--k]))
 321           {
 322             a[k + 1] = a[k];
 323           }
 324           a[k + 1] = a2;
 325         }
 326         int last = a[right];
 327
 328         while (val(last) < val(a[--right]))
 329         {
 330           a[right + 1] = a[right];
 331         }
 332         a[right + 1] = last;
 333       }
 334       return;
 335     }
 336
 337     // Inexpensive approximation of length / 7
 338     int seventh = (length >> 3) + (length >> 6) + 1;
 339
 340     /*
 341      * Sort five evenly spaced elements around (and including) the
 342      * center element in the range. These elements will be used for
 343      * pivot selection as described below. The choice for spacing
 344      * these elements was empirically determined to work well on
 345      * a wide variety of inputs.
 346      */
 347     int e3 = (left + right) >>> 1; // The midpoint
 348     int e2 = e3 - seventh;
 349     int e1 = e2 - seventh;
 350     int e4 = e3 + seventh;
 351     int e5 = e4 + seventh;
 352
 353     // Sort these elements using insertion sort
 354     if (val(a[e2]) < val(a[e1]))
 355     {
 356       int t = a[e2];
 357       a[e2] = a[e1];
 358       a[e1] = t;
 359     }
 360
 361     if (val(a[e3]) < val(a[e2]))
 362     {
 363       int t = a[e3];
 364       a[e3] = a[e2];
 365       a[e2] = t;
 366       if (val(t) < val(a[e1]))
 367       {
 368         a[e2] = a[e1];
 369         a[e1] = t;
 370       }
 371     }
 372     if (val(a[e4]) < val(a[e3]))
 373     {
 374       int t = a[e4];
 375       a[e4] = a[e3];
 376       a[e3] = t;
 377       int vt = val(t);
 378       if (vt < val(a[e2]))
 379       {
 380         a[e3] = a[e2];
 381         a[e2] = t;
 382         if (vt < val(a[e1]))
 383         {
 384           a[e2] = a[e1];
 385           a[e1] = t;
 386         }
 387       }
 388     }
 389     if (val(a[e5]) < val(a[e4]))
 390     {
 391       int t = a[e5];
 392       a[e5] = a[e4];
 393       a[e4] = t;
 394       int vt = val(t);
 395       if (vt < val(a[e3]))
 396       {
 397         a[e4] = a[e3];
 398         a[e3] = t;
 399         if (vt < val(a[e2]))
 400         {
 401           a[e3] = a[e2];
 402           a[e2] = t;
 403           if (vt < val(a[e1]))
 404           {
 405             a[e2] = a[e1];
 406             a[e1] = t;
 407           }
 408         }
 409       }
 410     }
 411
 412     // Pointers
 413     int less = left; // The index of the first element of center part
 414     int great = right; // The index before the first element of right part
 415
 416     if (val(a[e1]) != val(a[e2]) && val(a[e2]) != val(a[e3])
 417             && val(a[e3]) != val(a[e4]) && val(a[e4]) != val(a[e5]))
 418     {
 419       /*
 420        * Use the second and fourth of the five sorted elements as pivots.
 421        * These values are inexpensive approximations of the first and
 422        * second terciles of the array. Note that pivot1 <= pivot2.
 423        */
 424       int pivot1 = val(a[e2]);
 425       int pivot2 = val(a[e4]);
 426       int pivot1k = a[e2];
 427       int pivot2k = a[e4];
 428
 429       /*
 430        * The first and the last elements to be sorted are moved to the
 431        * locations formerly occupied by the pivots. When partitioning
 432        * is complete, the pivots are swapped back into their final
 433        * positions, and excluded from subsequent sorting.
 434        */
 435       a[e2] = a[left];
 436       a[e4] = a[right];
 437
 438       /*
 439        * Skip elements, which are less or greater than pivot values.
 440        */
 441       while (val(a[++less]) < pivot1)
 442         ;
 443       while (val(a[--great]) > pivot2)
 444         ;
 445
 446       /*
 447        * Partitioning:
 448        *
 449        *   left part           center part                   right part
 450        * +--------------------------------------------------------------+
 451        * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
 452        * +--------------------------------------------------------------+
 453        *               ^                          ^       ^
 454        *               |                          |       |
 455        *              less                        k     great
 456        *
 457        * Invariants:
 458        *
 459        *              all in (left, less)   < pivot1
 460        *    pivot1 <= all in [less, k)     <= pivot2
 461        *              all in (great, right) > pivot2
 462        *
 463        * Pointer k is the first index of ?-part.
 464        */
 465       outer: for (int k = less - 1; ++k <= great;)
 466       {
 467         int ak = a[k];
 468         if (val(ak) < pivot1)
 469         { // Move a[k] to left part
 470           a[k] = a[less];
 471           /*
 472           * Here and below we use "a[i] = b; i++;" instead
 473           * of "a[i++] = b;" due to performance issue.
 474           */
 475           a[less] = ak;
 476           ++less;
 477         }
 478         else if (val(ak) > pivot2)
 479         { // Move a[k] to right part
 480           while (val(a[great]) > pivot2)
 481           {
 482             if (great-- == k)
 483             {
 484               break outer;
 485             }
 486           }
 487           if (val(a[great]) < pivot1)
 488           { // a[great] <= pivot2
 489             a[k] = a[less];
 490             a[less] = a[great];
 491             ++less;
 492           }
 493           else
 494           { // pivot1 <= a[great] <= pivot2
 495             a[k] = a[great];
 496           }
 497           /*
 498           * Here and below we use "a[i] = b; i--;" instead
 499           * of "a[i--] = b;" due to performance issue.
 500           */
 501           a[great] = ak;
 502           --great;
 503         }
 504       }
 505
 506       // Swap pivots into their final positions
 507       a[left] = a[less - 1];
 508       a[less - 1] = pivot1k;
 509       a[right] = a[great + 1];
 510       a[great + 1] = pivot2k;
 511
 512       // Sort left and right parts recursively, excluding known pivots
 513       sort(a, left, less - 2, leftmost);
 514       sort(a, great + 2, right, false);
 515
 516       /*
 517        * If center part is too large (comprises > 4/7 of the array),
 518        * swap internal pivot values to ends.
 519        */
 520       if (less < e1 && e5 < great)
 521       {
 522         /*
 523          * Skip elements, which are equal to pivot values.
 524          */
 525         while (val(a[less]) == pivot1)
 526         {
 527           ++less;
 528         }
 529
 530         while (val(a[great]) == pivot2)
 531         {
 532           --great;
 533         }
 534
 535         /*
 536          * Partitioning:
 537          *
 538          *   left part         center part                  right part
 539          * +----------------------------------------------------------+
 540          * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
 541          * +----------------------------------------------------------+
 542          *              ^                        ^       ^
 543          *              |                        |       |
 544          *             less                      k     great
 545          *
 546          * Invariants:
 547          *
 548          *              all in (*,  less) == pivot1
 549          *     pivot1 < all in [less,  k)  < pivot2
 550          *              all in (great, *) == pivot2
 551          *
 552          * Pointer k is the first index of ?-part.
 553          */
 554         outer: for (int k = less - 1; ++k <= great;)
 555         {
 556           int ak = a[k];
 557           if (val(ak) == pivot1)
 558           { // Move a[k] to left part
 559             a[k] = a[less];
 560             a[less] = ak;
 561             ++less;
 562           }
 563           else if (val(ak) == pivot2)
 564           { // Move a[k] to right part
 565             while (val(a[great]) == pivot2)
 566             {
 567               if (great-- == k)
 568               {
 569                 break outer;
 570               }
 571             }
 572             if (val(a[great]) == pivot1)
 573             { // a[great] < pivot2
 574               a[k] = a[less];
 575               /*
 576               * Even though a[great] equals to pivot1, the
 577               * assignment a[less] = pivot1 may be incorrect,
 578               * if a[great] and pivot1 are floating-point zeros
 579               * of different signs. Therefore in float and
 580               * double sorting methods we have to use more
 581               * accurate assignment a[less] = a[great].
 582               */
 583               a[less] = pivot1k;
 584               ++less;
 585             }
 586             else
 587             { // pivot1 < a[great] < pivot2
 588               a[k] = a[great];
 589             }
 590             a[great] = ak;
 591             --great;
 592           }
 593         }
 594       }
 595
 596       // Sort center part recursively
 597       sort(a, less, great, false);
 598
 599     }
 600     else
 601     { // Partitioning with one pivot
 602       /*
 603        * Use the third of the five sorted elements as pivot.
 604        * This value is inexpensive approximation of the median.
 605        */
 606       int pivot = val(a[e3]);
 607
 608       /*
 609        * Partitioning degenerates to the traditional 3-way
 610        * (or "Dutch National Flag") schema:
 611        *
 612        *   left part    center part              right part
 613        * +-------------------------------------------------+
 614        * |  < pivot  |   == pivot   |     ?    |  > pivot  |
 615        * +-------------------------------------------------+
 616        *              ^              ^        ^
 617        *              |              |        |
 618        *             less            k      great
 619        *
 620        * Invariants:
 621        *
 622        *   all in (left, less)   < pivot
 623        *   all in [less, k)     == pivot
 624        *   all in (great, right) > pivot
 625        *
 626        * Pointer k is the first index of ?-part.
 627        */
 628       for (int k = less; k <= great; ++k)
 629       {
 630         if (val(a[k]) == pivot)
 631         {
 632           continue;
 633         }
 634         int ak = a[k];
 635         if (val(ak) < pivot)
 636         { // Move a[k] to left part
 637           a[k] = a[less];
 638           a[less] = ak;
 639           ++less;
 640         }
 641         else
 642         { // a[k] > pivot - Move a[k] to right part
 643           while (val(a[great]) > pivot)
 644           {
 645             --great;
 646           }
 647           if (val(a[great]) < pivot)
 648           { // a[great] <= pivot
 649             a[k] = a[less];
 650             a[less] = a[great];
 651             ++less;
 652           }
 653           else
 654           { // a[great] == pivot
 655             /*
 656             * Even though a[great] equals to pivot, the
 657             * assignment a[k] = pivot may be incorrect,
 658             * if a[great] and pivot are floating-point
 659             * zeros of different signs. Therefore in float
 660             * and double sorting methods we have to use
 661             * more accurate assignment a[k] = a[great].
 662             */
 663             // So, guess what?
 664             //
 665             // Actually, we do need a[great] for IntervalStore,
 666             // because here, two, the numbers are not necessarily the same item
 667             //
 668             // a[k] = pivot;
 669             a[k] = a[great];
 670           }
 671           a[great] = ak;
 672           --great;
 673         }
 674       }
 675
 676       /*
 677        * Sort left and right parts recursively.
 678        * All elements from center part are equal
 679        * and, therefore, already sorted.
 680        */
 681       sort(a, left, less - 1, leftmost);
 682       sort(a, great + 1, right, false);
 683     }
 684   }
 685
 686 }