--- /dev/null
+/*
+ * Copyright (c) 2009, 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation. Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package intervalstore.nonc;
+
+import intervalstore.api.IntervalI;
+
+/**
+ * A dual pivot quicksort for int[] where the int is a pointer to something for
+ * which the value needs to be checked. This class is not used; it was just an
+ * idea I was trying. But it is sort of cool, so I am keeping it in the package
+ * for possible future use.
+ *
+ * Adapted from Java 7 java.util.DualPivotQuicksort -- int[] only. The only
+ * difference is that wherever an a[] value is compared, we use val(a[i])
+ * instead of a[i] itself. Pretty straightforward. Could be adapted for general
+ * use. Why didn't they do this in Java?
+ *
+ * val(i) is just a hack here, of course. A more general implementation might
+ * use a Function call.
+ *
+ * Just thought it was cool that you can do this.
+ *
+ * @author Bob Hanson 2019.09.02
+ *
+ */
+
+class IntervalEndSorter
+{
+
+ private IntervalI[] intervals;
+
+ private int val(int i)
+ {
+ return intervals[i].getEnd();
+ }
+
+ /*
+ * Tuning parameters.
+ */
+
+ /**
+ * The maximum number of runs in merge sort.
+ */
+ private static final int MAX_RUN_COUNT = 67;
+
+ /**
+ * The maximum length of run in merge sort.
+ */
+ private static final int MAX_RUN_LENGTH = 33;
+
+ /**
+ * If the length of an array to be sorted is less than this constant,
+ * Quicksort is used in preference to merge sort.
+ */
+ private static final int QUICKSORT_THRESHOLD = 286;
+
+ /**
+ * If the length of an array to be sorted is less than this constant,
+ * insertion sort is used in preference to Quicksort.
+ */
+ private static final int INSERTION_SORT_THRESHOLD = 47;
+
+ /*
+ * Sorting methods for seven primitive types.
+ */
+
+ /**
+ * Sorts the specified range of the array using the given workspace array
+ * slice if possible for merging
+ *
+ * @param a
+ * the array to be sorted
+ * @param left
+ * the index of the first element, inclusive, to be sorted
+ * @param right
+ * the index of the last element, inclusive, to be sorted
+ * @param work
+ * a workspace array (slice)
+ * @param workBase
+ * origin of usable space in work array
+ * @param workLen
+ * usable size of work array
+ */
+ void sort(int[] a, IntervalI[] intervals, int len)
+ {
+ this.intervals = intervals;
+
+ int left = 0, right = len - 1;
+ // Use Quicksort on small arrays
+ if (right - left < QUICKSORT_THRESHOLD)
+ {
+ sort(a, left, right, true);
+ return;
+ }
+
+ /*
+ * Index run[i] is the start of i-th run
+ * (ascending or descending sequence).
+ */
+ int[] run = new int[MAX_RUN_COUNT + 1];
+ int count = 0;
+ run[0] = left;
+
+ // Check if the array is nearly sorted
+ for (int k = left; k < right; run[count] = k)
+ {
+ switch (Integer.signum(val(a[k + 1]) - val(a[k])))
+ {
+ case 1:
+ // ascending
+ while (++k <= right && val(a[k - 1]) <= val(a[k]))
+ ;
+ break;
+ case -1:
+ // descending
+ while (++k <= right && val(a[k - 1]) >= val(a[k]))
+ ;
+ for (int lo = run[count] - 1, hi = k; ++lo < --hi;)
+ {
+ int t = a[lo];
+ a[lo] = a[hi];
+ a[hi] = t;
+ }
+ break;
+ default:
+ // equal
+ for (int m = MAX_RUN_LENGTH; ++k <= right
+ && val(a[k - 1]) == val(a[k]);)
+ {
+ if (--m == 0)
+ {
+ sort(a, left, right, true);
+ return;
+ }
+ }
+ }
+
+ /*
+ * The array is not highly structured,
+ * use Quicksort instead of merge sort.
+ */
+ if (++count == MAX_RUN_COUNT)
+ {
+ sort(a, left, right, true);
+ return;
+ }
+ }
+
+ // Check special cases
+ // Implementation note: variable "right" is increased by 1.
+ if (run[count] == right++)
+ { // The last run contains one element
+ run[++count] = right;
+ }
+ else if (count == 1)
+ { // The array is already sorted
+ return;
+ }
+
+ // Determine alternation base for merge
+ byte odd = 0;
+ for (int n = 1; (n <<= 1) < count; odd ^= 1)
+ ;
+
+ // Use or create temporary array b for merging
+ int[] b; // temp array; alternates with a
+ int ao, bo; // array offsets from 'left'
+ int blen = right - left; // space needed for b
+ int[] work = new int[blen];
+ int workBase = 0;
+ if (odd == 0)
+ {
+ System.arraycopy(a, left, work, workBase, blen);
+ b = a;
+ bo = 0;
+ a = work;
+ ao = workBase - left;
+ }
+ else
+ {
+ b = work;
+ ao = 0;
+ bo = workBase - left;
+ }
+
+ // Merging
+ for (int last; count > 1; count = last)
+ {
+ for (int k = (last = 0) + 2; k <= count; k += 2)
+ {
+ int hi = run[k], mi = run[k - 1];
+ for (int i = run[k - 2], p = i, q = mi; i < hi; ++i)
+ {
+ if (q >= hi || p < mi && val(a[p + ao]) <= val(a[q + ao]))
+ {
+ b[i + bo] = a[p++ + ao];
+ }
+ else
+ {
+ b[i + bo] = a[q++ + ao];
+ }
+ }
+ run[++last] = hi;
+ }
+ if ((count & 1) != 0)
+ {
+ for (int i = right, lo = run[count - 1]; --i >= lo; b[i + bo] = a[i
+ + ao])
+ ;
+ run[++last] = right;
+ }
+ int[] t = a;
+ a = b;
+ b = t;
+ int o = ao;
+ ao = bo;
+ bo = o;
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array by Dual-Pivot Quicksort.
+ *
+ * @param a
+ * the array to be sorted
+ * @param left
+ * the index of the first element, inclusive, to be sorted
+ * @param right
+ * the index of the last element, inclusive, to be sorted
+ * @param leftmost
+ * indicates if this part is the leftmost in the range
+ */
+ private void sort(int[] a, int left, int right, boolean leftmost)
+ {
+ int length = right - left + 1;
+
+ // Use insertion sort on tiny arrays
+ if (length < INSERTION_SORT_THRESHOLD)
+ {
+ if (leftmost)
+ {
+ /*
+ * Traditional (without sentinel) insertion sort,
+ * optimized for server VM, is used in case of
+ * the leftmost part.
+ */
+ for (int i = left, j = i; i < right; j = ++i)
+ {
+ int ai = a[i + 1];
+ while (val(ai) < val(a[j]))
+ {
+ a[j + 1] = a[j];
+ if (j-- == left)
+ {
+ break;
+ }
+ }
+ a[j + 1] = ai;
+ }
+ }
+ else
+ {
+ /*
+ * Skip the longest ascending sequence.
+ */
+ do
+ {
+ if (left >= right)
+ {
+ return;
+ }
+ } while (val(a[++left]) >= val(a[left - 1]));
+
+ /*
+ * Every element from adjoining part plays the role
+ * of sentinel, therefore this allows us to avoid the
+ * left range check on each iteration. Moreover, we use
+ * the more optimized algorithm, so called pair insertion
+ * sort, which is faster (in the context of Quicksort)
+ * than traditional implementation of insertion sort.
+ */
+ for (int k = left; ++left <= right; k = ++left)
+ {
+ int a1 = a[k], a2 = a[left];
+
+ if (val(a1) < val(a2))
+ {
+ a2 = a1;
+ a1 = a[left];
+ }
+ while (val(a1) < val(a[--k]))
+ {
+ a[k + 2] = a[k];
+ }
+ a[++k + 1] = a1;
+
+ while (val(a2) < val(a[--k]))
+ {
+ a[k + 1] = a[k];
+ }
+ a[k + 1] = a2;
+ }
+ int last = a[right];
+
+ while (val(last) < val(a[--right]))
+ {
+ a[right + 1] = a[right];
+ }
+ a[right + 1] = last;
+ }
+ return;
+ }
+
+ // Inexpensive approximation of length / 7
+ int seventh = (length >> 3) + (length >> 6) + 1;
+
+ /*
+ * Sort five evenly spaced elements around (and including) the
+ * center element in the range. These elements will be used for
+ * pivot selection as described below. The choice for spacing
+ * these elements was empirically determined to work well on
+ * a wide variety of inputs.
+ */
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e2 = e3 - seventh;
+ int e1 = e2 - seventh;
+ int e4 = e3 + seventh;
+ int e5 = e4 + seventh;
+
+ // Sort these elements using insertion sort
+ if (val(a[e2]) < val(a[e1]))
+ {
+ int t = a[e2];
+ a[e2] = a[e1];
+ a[e1] = t;
+ }
+
+ if (val(a[e3]) < val(a[e2]))
+ {
+ int t = a[e3];
+ a[e3] = a[e2];
+ a[e2] = t;
+ if (val(t) < val(a[e1]))
+ {
+ a[e2] = a[e1];
+ a[e1] = t;
+ }
+ }
+ if (val(a[e4]) < val(a[e3]))
+ {
+ int t = a[e4];
+ a[e4] = a[e3];
+ a[e3] = t;
+ int vt = val(t);
+ if (vt < val(a[e2]))
+ {
+ a[e3] = a[e2];
+ a[e2] = t;
+ if (vt < val(a[e1]))
+ {
+ a[e2] = a[e1];
+ a[e1] = t;
+ }
+ }
+ }
+ if (val(a[e5]) < val(a[e4]))
+ {
+ int t = a[e5];
+ a[e5] = a[e4];
+ a[e4] = t;
+ int vt = val(t);
+ if (vt < val(a[e3]))
+ {
+ a[e4] = a[e3];
+ a[e3] = t;
+ if (vt < val(a[e2]))
+ {
+ a[e3] = a[e2];
+ a[e2] = t;
+ if (vt < val(a[e1]))
+ {
+ a[e2] = a[e1];
+ a[e1] = t;
+ }
+ }
+ }
+ }
+
+ // Pointers
+ int less = left; // The index of the first element of center part
+ int great = right; // The index before the first element of right part
+
+ if (val(a[e1]) != val(a[e2]) && val(a[e2]) != val(a[e3])
+ && val(a[e3]) != val(a[e4]) && val(a[e4]) != val(a[e5]))
+ {
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ */
+ int pivot1 = val(a[e2]);
+ int pivot2 = val(a[e4]);
+ int pivot1k = a[e2];
+ int pivot2k = a[e4];
+
+ /*
+ * The first and the last elements to be sorted are moved to the
+ * locations formerly occupied by the pivots. When partitioning
+ * is complete, the pivots are swapped back into their final
+ * positions, and excluded from subsequent sorting.
+ */
+ a[e2] = a[left];
+ a[e4] = a[right];
+
+ /*
+ * Skip elements, which are less or greater than pivot values.
+ */
+ while (val(a[++less]) < pivot1)
+ ;
+ while (val(a[--great]) > pivot2)
+ ;
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +--------------------------------------------------------------+
+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
+ * +--------------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer: for (int k = less - 1; ++k <= great;)
+ {
+ int ak = a[k];
+ if (val(ak) < pivot1)
+ { // Move a[k] to left part
+ a[k] = a[less];
+ /*
+ * Here and below we use "a[i] = b; i++;" instead
+ * of "a[i++] = b;" due to performance issue.
+ */
+ a[less] = ak;
+ ++less;
+ }
+ else if (val(ak) > pivot2)
+ { // Move a[k] to right part
+ while (val(a[great]) > pivot2)
+ {
+ if (great-- == k)
+ {
+ break outer;
+ }
+ }
+ if (val(a[great]) < pivot1)
+ { // a[great] <= pivot2
+ a[k] = a[less];
+ a[less] = a[great];
+ ++less;
+ }
+ else
+ { // pivot1 <= a[great] <= pivot2
+ a[k] = a[great];
+ }
+ /*
+ * Here and below we use "a[i] = b; i--;" instead
+ * of "a[i--] = b;" due to performance issue.
+ */
+ a[great] = ak;
+ --great;
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1];
+ a[less - 1] = pivot1k;
+ a[right] = a[great + 1];
+ a[great + 1] = pivot2k;
+
+ // Sort left and right parts recursively, excluding known pivots
+ sort(a, left, less - 2, leftmost);
+ sort(a, great + 2, right, false);
+
+ /*
+ * If center part is too large (comprises > 4/7 of the array),
+ * swap internal pivot values to ends.
+ */
+ if (less < e1 && e5 < great)
+ {
+ /*
+ * Skip elements, which are equal to pivot values.
+ */
+ while (val(a[less]) == pivot1)
+ {
+ ++less;
+ }
+
+ while (val(a[great]) == pivot2)
+ {
+ --great;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * +----------------------------------------------------------+
+ * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 |
+ * +----------------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ outer: for (int k = less - 1; ++k <= great;)
+ {
+ int ak = a[k];
+ if (val(ak) == pivot1)
+ { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ ++less;
+ }
+ else if (val(ak) == pivot2)
+ { // Move a[k] to right part
+ while (val(a[great]) == pivot2)
+ {
+ if (great-- == k)
+ {
+ break outer;
+ }
+ }
+ if (val(a[great]) == pivot1)
+ { // a[great] < pivot2
+ a[k] = a[less];
+ /*
+ * Even though a[great] equals to pivot1, the
+ * assignment a[less] = pivot1 may be incorrect,
+ * if a[great] and pivot1 are floating-point zeros
+ * of different signs. Therefore in float and
+ * double sorting methods we have to use more
+ * accurate assignment a[less] = a[great].
+ */
+ a[less] = pivot1k;
+ ++less;
+ }
+ else
+ { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ --great;
+ }
+ }
+ }
+
+ // Sort center part recursively
+ sort(a, less, great, false);
+
+ }
+ else
+ { // Partitioning with one pivot
+ /*
+ * Use the third of the five sorted elements as pivot.
+ * This value is inexpensive approximation of the median.
+ */
+ int pivot = val(a[e3]);
+
+ /*
+ * Partitioning degenerates to the traditional 3-way
+ * (or "Dutch National Flag") schema:
+ *
+ * left part center part right part
+ * +-------------------------------------------------+
+ * | < pivot | == pivot | ? | > pivot |
+ * +-------------------------------------------------+
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part.
+ */
+ for (int k = less; k <= great; ++k)
+ {
+ if (val(a[k]) == pivot)
+ {
+ continue;
+ }
+ int ak = a[k];
+ if (val(ak) < pivot)
+ { // Move a[k] to left part
+ a[k] = a[less];
+ a[less] = ak;
+ ++less;
+ }
+ else
+ { // a[k] > pivot - Move a[k] to right part
+ while (val(a[great]) > pivot)
+ {
+ --great;
+ }
+ if (val(a[great]) < pivot)
+ { // a[great] <= pivot
+ a[k] = a[less];
+ a[less] = a[great];
+ ++less;
+ }
+ else
+ { // a[great] == pivot
+ /*
+ * Even though a[great] equals to pivot, the
+ * assignment a[k] = pivot may be incorrect,
+ * if a[great] and pivot are floating-point
+ * zeros of different signs. Therefore in float
+ * and double sorting methods we have to use
+ * more accurate assignment a[k] = a[great].
+ */
+ // So, guess what?
+ //
+ // Actually, we do need a[great] for IntervalStore,
+ // because here, two, the numbers are not necessarily the same item
+ //
+ // a[k] = pivot;
+ a[k] = a[great];
+ }
+ a[great] = ak;
+ --great;
+ }
+ }
+
+ /*
+ * Sort left and right parts recursively.
+ * All elements from center part are equal
+ * and, therefore, already sorted.
+ */
+ sort(a, left, less - 1, leftmost);
+ sort(a, great + 1, right, false);
+ }
+ }
+
+}
git://source.jalview.org / jalview.git / blobdiff