001/*
002 * Copyright 2014 Alex Kasko (alexkasko.com)
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.alexkasko.unsafe.offheaplong;
018
019/**
020 * <p>alexkasko: borrowed from {@code https://android.googlesource.com/platform/libcore/+/android-4.2.2_r1/luni/src/main/java/java/util/DualPivotQuicksort.java}
021 * and adapted to {@link OffHeapLongAddressable}.
022 *
023 * <p>This class implements the Dual-Pivot Quicksort algorithm by
024 * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm
025 * offers O(n log(n)) performance on many data sets that cause other
026 * quicksorts to degrade to quadratic performance, and is typically
027 * faster than traditional (one-pivot) Quicksort implementations.
028 *
029 * @author Vladimir Yaroslavskiy
030 * @author Jon Bentley
031 * @author Josh Bloch
032 *
033 * @version 2009.11.29 m765.827.12i
034 */
035public class OffHeapLongSorter {
036
037    /**
038     * If the length of an array to be sorted is less than this
039     * constant, insertion sort is used in preference to Quicksort.
040     */
041    private static final int INSERTION_SORT_THRESHOLD = 32;
042
043    /**
044     * Sorts the specified off-heap collection into ascending order.
045     *
046     * @param a the off-heap collection to be sorted
047     */
048    public static void sort(OffHeapLongAddressable a) {
049        sort(a, 0, a.size());
050    }
051
052    /**
053     * Sorts the specified range of the off-heap collection into ascending order. The range
054     * to be sorted extends from the index {@code fromIndex}, inclusive, to
055     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
056     * the range to be sorted is empty (and the call is a no-op).
057     *
058     * @param a the off-heap collection to be sorted
059     * @param fromIndex the index of the first element, inclusive, to be sorted
060     * @param toIndex the index of the last element, exclusive, to be sorted
061     * @throws IllegalArgumentException {@code if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())}
062     */
063    public static void sort(OffHeapLongAddressable a, long fromIndex, long toIndex) {
064        if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size()) {
065            throw new IllegalArgumentException("Illegal input, collection size: [" + a.size() + "], " +
066                    "fromIndex: [" + fromIndex + "], toIndex: [" + toIndex + "]");
067        }
068        doSort(a, fromIndex, toIndex - 1);
069    }
070
071    /**
072     * Sorts the specified off-heap collection into ascending order.
073     *
074     * @param a the off-heap collection to be sorted
075     * @param comp comparator that defines sort order
076     */
077    public static void sort(OffHeapLongAddressable a, OffHeapLongComparator comp) {
078        sort(a, 0, a.size(), comp);
079    }
080
081    /**
082     * Sorts the specified range of the off-heap collection into ascending order. The range
083     * to be sorted extends from the index {@code fromIndex}, inclusive, to
084     * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
085     * the range to be sorted is empty (and the call is a no-op).
086     *
087     * @param a the off-heap collection to be sorted
088     * @param fromIndex the index of the first element, inclusive, to be sorted
089     * @param toIndex the index of the last element, exclusive, to be sorted
090     * @param comp comparator that defines sort order
091     * @throws IllegalArgumentException {@code if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size())}
092     */
093    public static void sort(OffHeapLongAddressable a, long fromIndex, long toIndex, OffHeapLongComparator comp) {
094        if (fromIndex < 0 || fromIndex > toIndex || toIndex > a.size()) {
095            throw new IllegalArgumentException("Illegal input, collection size: [" + a.size() + "], " +
096                    "fromIndex: [" + fromIndex + "], toIndex: [" + toIndex + "]");
097        }
098        doSortWithComparator(a, fromIndex, toIndex - 1, new LongComp(comp));
099    }
100
101    /**
102     * Sorts the specified range of the off-heap collection into ascending order. This
103     * method differs from the public {@code sort} method in that the
104     * {@code right} index is inclusive, and it does no range checking on
105     * {@code left} or {@code right}.
106     *
107     * @param a the off-heap collection to be sorted
108     * @param left the index of the first element, inclusive, to be sorted
109     * @param right the index of the last element, inclusive, to be sorted
110     */
111    private static void doSort(OffHeapLongAddressable a, long left, long right) {
112        // Use insertion sort on tiny arrays
113        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
114            for (long i = left + 1; i <= right; i++) {
115                long ai = a.get(i);
116                long j;
117                for (j = i - 1; j >= left && ai < a.get(j); j--) {
118                    a.set(j + 1, a.get(j));
119                }
120                a.set(j + 1, ai);
121            }
122        } else { // Use Dual-Pivot Quicksort on large arrays
123            dualPivotQuicksort(a, left, right);
124        }
125    }
126
127    /**
128     * Sorts the specified range of the off-heap collection into ascending order by the
129     * Dual-Pivot Quicksort algorithm.
130     *
131     * @param a the off-heap collection to be sorted
132     * @param left the index of the first element, inclusive, to be sorted
133     * @param right the index of the last element, inclusive, to be sorted
134     */
135    private static void dualPivotQuicksort(OffHeapLongAddressable a, long left, long right) {
136        // Compute indices of five evenly spaced elements
137        long sixth = (right - left + 1) / 6;
138        long e1 = left  + sixth;
139        long e5 = right - sixth;
140        long e3 = (left + right) >>> 1; // The midpoint
141        long e4 = e3 + sixth;
142        long e2 = e3 - sixth;
143
144        // Sort these elements using a 5-element sorting network
145        long ae1 = a.get(e1), ae2 = a.get(e2), ae3 = a.get(e3), ae4 = a.get(e4), ae5 = a.get(e5);
146
147        if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; }
148        if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
149        if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; }
150        if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
151        if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; }
152        if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; }
153        if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; }
154        if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
155        if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
156
157        a.set(e1, ae1); a.set(e3, ae3); a.set(e5, ae5);
158
159        /*
160         * Use the second and fourth of the five sorted elements as pivots.
161         * These values are inexpensive approximations of the first and
162         * second terciles of the array. Note that pivot1 <= pivot2.
163         *
164         * The pivots are stored in local variables, and the first and
165         * the last of the elements to be sorted are moved to the locations
166         * formerly occupied by the pivots. When partitioning is complete,
167         * the pivots are swapped back into their final positions, and
168         * excluded from subsequent sorting.
169         */
170        long pivot1 = ae2; a.set(e2, a.get(left));
171        long pivot2 = ae4; a.set(e4, a.get(right));
172
173        // Pointers
174        long less  = left  + 1; // The index of first element of center part
175        long great = right - 1; // The index before first element of right part
176
177        boolean pivotsDiffer = (pivot1 != pivot2);
178
179        if (pivotsDiffer) {
180            /*
181             * Partitioning:
182             *
183             *   left part         center part                    right part
184             * +------------------------------------------------------------+
185             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
186             * +------------------------------------------------------------+
187             *              ^                          ^       ^
188             *              |                          |       |
189             *             less                        k     great
190             *
191             * Invariants:
192             *
193             *              all in (left, less)   < pivot1
194             *    pivot1 <= all in [less, k)     <= pivot2
195             *              all in (great, right) > pivot2
196             *
197             * Pointer k is the first index of ?-part
198             */
199            outer:
200            for (long k = less; k <= great; k++) {
201                long ak = a.get(k);
202                if (ak < pivot1) { // Move a[k] to left part
203                    if (k != less) {
204                        a.set(k, a.get(less));
205                        a.set(less, ak);
206                    }
207                    less++;
208                } else if (ak > pivot2) { // Move a[k] to right part
209                    while (a.get(great) > pivot2) {
210                        if (great-- == k) {
211                            break outer;
212                        }
213                    }
214                    if (a.get(great) < pivot1) {
215                        a.set(k, a.get(less));
216                        a.set(less++, a.get(great));
217                        a.set(great--, ak);
218                    } else { // pivot1 <= a[great] <= pivot2
219                        a.set(k, a.get(great));
220                        a.set(great--, ak);
221                    }
222                }
223            }
224        } else { // Pivots are equal
225            /*
226             * Partition degenerates to the traditional 3-way,
227             * or "Dutch National Flag", partition:
228             *
229             *   left part   center part            right part
230             * +----------------------------------------------+
231             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
232             * +----------------------------------------------+
233             *              ^            ^       ^
234             *              |            |       |
235             *             less          k     great
236             *
237             * Invariants:
238             *
239             *   all in (left, less)   < pivot
240             *   all in [less, k)     == pivot
241             *   all in (great, right) > pivot
242             *
243             * Pointer k is the first index of ?-part
244             */
245            for (long k = less; k <= great; k++) {
246                long ak = a.get(k);
247                if (ak == pivot1) {
248                    continue;
249                }
250                if (ak < pivot1) { // Move a[k] to left part
251                    if (k != less) {
252                        a.set(k, a.get(less));
253                        a.set(less, ak);
254                    }
255                    less++;
256                } else { // (a[k] > pivot1) -  Move a[k] to right part
257                    /*
258                     * We know that pivot1 == a[e3] == pivot2. Thus, we know
259                     * that great will still be >= k when the following loop
260                     * terminates, even though we don't test for it explicitly.
261                     * In other words, a[e3] acts as a sentinel for great.
262                     */
263                    while (a.get(great) > pivot1) {
264                        great--;
265                    }
266                    if (a.get(great) < pivot1) {
267                        a.set(k, a.get(less));
268                        a.set(less++, a.get(great));
269                        a.set(great--, ak);
270                    } else { // a[great] == pivot1
271                        a.set(k, pivot1);
272                        a.set(great--, ak);
273                    }
274                }
275            }
276        }
277
278        // Swap pivots into their final positions
279        a.set(left, a.get(less - 1)); a.set(less - 1, pivot1);
280        a.set(right, a.get(great + 1)); a.set(great + 1, pivot2);
281
282        // Sort left and right parts recursively, excluding known pivot values
283        doSort(a, left,   less - 2);
284        doSort(a, great + 2, right);
285
286        /*
287         * If pivot1 == pivot2, all elements from center
288         * part are equal and, therefore, already sorted
289         */
290        if (!pivotsDiffer) {
291            return;
292        }
293
294        /*
295         * If center part is too large (comprises > 2/3 of the array),
296         * swap internal pivot values to ends
297         */
298        if (less < e1 && great > e5) {
299            while (a.get(less) == pivot1) {
300                less++;
301            }
302            while (a.get(great) == pivot2) {
303                great--;
304            }
305
306            /*
307             * Partitioning:
308             *
309             *   left part       center part                   right part
310             * +----------------------------------------------------------+
311             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
312             * +----------------------------------------------------------+
313             *              ^                        ^       ^
314             *              |                        |       |
315             *             less                      k     great
316             *
317             * Invariants:
318             *
319             *              all in (*, less)  == pivot1
320             *     pivot1 < all in [less, k)   < pivot2
321             *              all in (great, *) == pivot2
322             *
323             * Pointer k is the first index of ?-part
324             */
325            outer:
326            for (long k = less; k <= great; k++) {
327                long ak = a.get(k);
328                if (ak == pivot2) { // Move a[k] to right part
329                    while (a.get(great) == pivot2) {
330                        if (great-- == k) {
331                            break outer;
332                        }
333                    }
334                    if (a.get(great) == pivot1) {
335                        a.set(k, a.get(less));
336                        a.set(less++, pivot1);
337                    } else { // pivot1 < a[great] < pivot2
338                        a.set(k, a.get(great));
339                    }
340                    a.set(great--, pivot2);
341                } else if (ak == pivot1) { // Move a[k] to left part
342                    a.set(k, a.get(less));
343                    a.set(less++, pivot1);
344                }
345            }
346        }
347
348        // Sort center part recursively, excluding known pivot values
349        doSort(a, less, great);
350    }
351
352    /**
353     * Sorts the specified range of the off-heap collection into ascending order. This
354     * method differs from the public {@code sort} method in that the
355     * {@code right} index is inclusive, and it does no range checking on
356     * {@code left} or {@code right}.
357     *
358     * @param a     the off-heap collection to be sorted
359     * @param left  the index of the first element, inclusive, to be sorted
360     * @param right the index of the last element, inclusive, to be sorted
361     * @param comp  comparator that defines sort order
362     */
363    private static void doSortWithComparator(OffHeapLongAddressable a, long left, long right, LongComp comp) {
364        // Use insertion sort on tiny arrays
365        if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
366            for (long i = left + 1; i <= right; i++) {
367                long ai = a.get(i);
368                long j;
369                for (j = i - 1; j >= left && comp.lt(ai, a.get(j)); j--) {
370                    a.set(j + 1, a.get(j));
371                }
372                a.set(j + 1, ai);
373            }
374        } else { // Use Dual-Pivot Quicksort on large arrays
375            dualPivotQuicksortWithComparator(a, left, right, comp);
376        }
377    }
378
379     /**
380      * Sorts the specified range of the off-heap collection into ascending order by the
381      * Dual-Pivot Quicksort algorithm.
382      *
383      * @param a the off-heap collection to be sorted
384      * @param left the index of the first element, inclusive, to be sorted
385      * @param right the index of the last element, inclusive, to be sorted
386      * @param comp  comparator that defines sort order
387      */
388    private static void dualPivotQuicksortWithComparator(OffHeapLongAddressable a, long left, long right, LongComp comp) {
389        // Compute indices of five evenly spaced elements
390        long sixth = (right - left + 1) / 6;
391        long e1 = left  + sixth;
392        long e5 = right - sixth;
393        long e3 = (left + right) >>> 1; // The midpoint
394        long e4 = e3 + sixth;
395        long e2 = e3 - sixth;
396
397        // Sort these elements using a 5-element sorting network
398        long ae1 = a.get(e1), ae2 = a.get(e2), ae3 = a.get(e3), ae4 = a.get(e4), ae5 = a.get(e5);
399
400        if (comp.gt(ae1, ae2)) { long t = ae1; ae1 = ae2; ae2 = t; }
401        if (comp.gt(ae4, ae5)) { long t = ae4; ae4 = ae5; ae5 = t; }
402        if (comp.gt(ae1, ae3)) { long t = ae1; ae1 = ae3; ae3 = t; }
403        if (comp.gt(ae2, ae3)) { long t = ae2; ae2 = ae3; ae3 = t; }
404        if (comp.gt(ae1, ae4)) { long t = ae1; ae1 = ae4; ae4 = t; }
405        if (comp.gt(ae3, ae4)) { long t = ae3; ae3 = ae4; ae4 = t; }
406        if (comp.gt(ae2, ae5)) { long t = ae2; ae2 = ae5; ae5 = t; }
407        if (comp.gt(ae2, ae3)) { long t = ae2; ae2 = ae3; ae3 = t; }
408        if (comp.gt(ae4, ae5)) { long t = ae4; ae4 = ae5; ae5 = t; }
409
410        a.set(e1, ae1); a.set(e3, ae3); a.set(e5, ae5);
411
412        /*
413         * Use the second and fourth of the five sorted elements as pivots.
414         * These values are inexpensive approximations of the first and
415         * second terciles of the array. Note that pivot1 <= pivot2.
416         *
417         * The pivots are stored in local variables, and the first and
418         * the last of the elements to be sorted are moved to the locations
419         * formerly occupied by the pivots. When partitioning is complete,
420         * the pivots are swapped back into their final positions, and
421         * excluded from subsequent sorting.
422         */
423        a.set(e2, a.get(left));
424        a.set(e4, a.get(right));
425
426        // Pointers
427        long less  = left  + 1; // The index of first element of center part
428        long great = right - 1; // The index before first element of right part
429
430        boolean pivotsDiffer = !comp.eq(ae2, ae4);
431
432        if (pivotsDiffer) {
433            /*
434             * Partitioning:
435             *
436             *   left part         center part                    right part
437             * +------------------------------------------------------------+
438             * | < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2 |
439             * +------------------------------------------------------------+
440             *              ^                          ^       ^
441             *              |                          |       |
442             *             less                        k     great
443             *
444             * Invariants:
445             *
446             *              all in (left, less)   < pivot1
447             *    pivot1 <= all in [less, k)     <= pivot2
448             *              all in (great, right) > pivot2
449             *
450             * Pointer k is the first index of ?-part
451             */
452            outer:
453            for (long k = less; k <= great; k++) {
454                long ak = a.get(k);
455                if (comp.lt(ak, ae2)) { // Move a[k] to left part
456                    if (k != less) {
457                        a.set(k, a.get(less));
458                        a.set(less, ak);
459                    }
460                    less++;
461                } else if (comp.gt(ak, ae4)) { // Move a[k] to right part
462                    long agreat;
463                    while (comp.gt((agreat = a.get(great)), ae4)) {
464                        if (great-- == k) {
465                            break outer;
466                        }
467                    }
468                    if (comp.lt(agreat, ae2)) {
469                        a.set(k, a.get(less));
470                        a.set(less++, agreat);
471                        a.set(great--, ak);
472                    } else { // pivot1 <= a[great] <= pivot2
473                        a.set(k, agreat);
474                        a.set(great--, ak);
475                    }
476                }
477            }
478        } else { // Pivots are equal
479            /*
480             * Partition degenerates to the traditional 3-way,
481             * or "Dutch National Flag", partition:
482             *
483             *   left part   center part            right part
484             * +----------------------------------------------+
485             * |  < pivot  |  == pivot  |    ?    |  > pivot  |
486             * +----------------------------------------------+
487             *              ^            ^       ^
488             *              |            |       |
489             *             less          k     great
490             *
491             * Invariants:
492             *
493             *   all in (left, less)   < pivot
494             *   all in [less, k)     == pivot
495             *   all in (great, right) > pivot
496             *
497             * Pointer k is the first index of ?-part
498             */
499            for (long k = less; k <= great; k++) {
500                long ak = a.get(k);
501                if (comp.eq(ak, ae2)) {
502                    continue;
503                }
504                if (comp.lt(ak, ae2)) { // Move a[k] to left part
505                    if (k != less) {
506                        a.set(k, a.get(less));
507                        a.set(less, ak);
508                    }
509                    less++;
510                } else { // (a[k] > pivot1) -  Move a[k] to right part
511                    /*
512                     * We know that pivot1 == a[e3] == pivot2. Thus, we know
513                     * that great will still be >= k when the following loop
514                     * terminates, even though we don't test for it explicitly.
515                     * In other words, a[e3] acts as a sentinel for great.
516                     */
517                    long agreat;
518                    while (comp.gt((agreat = a.get(great)), ae2)) {
519                        great--;
520                    }
521                    if (comp.lt(agreat, ae2)) {
522                        a.set(k, a.get(less));
523                        a.set(less++, agreat);
524                        a.set(great--, ak);
525                    } else { // a[great] == pivot1
526                        a.set(k, agreat);
527                        a.set(great--, ak);
528                    }
529                }
530            }
531        }
532
533        // Swap pivots into their final positions
534        a.set(left, a.get(less - 1)); a.set(less - 1, ae2);
535        a.set(right, a.get(great + 1)); a.set(great + 1, ae4);
536
537        // Sort left and right parts recursively, excluding known pivot values
538        doSortWithComparator(a, left,   less - 2, comp);
539        doSortWithComparator(a, great + 2, right, comp);
540
541        /*
542         * If pivot1 == pivot2, all elements from center
543         * part are equal and, therefore, already sorted
544         */
545        if (!pivotsDiffer) {
546            return;
547        }
548
549        /*
550         * If center part is too large (comprises > 2/3 of the array),
551         * swap internal pivot values to ends
552         */
553        if (less < e1 && great > e5) {
554            while (comp.eq(a.get(less), ae2)) {
555                less++;
556            }
557            while (comp.eq(a.get(great), ae4)) {
558                great--;
559            }
560
561            /*
562             * Partitioning:
563             *
564             *   left part       center part                   right part
565             * +----------------------------------------------------------+
566             * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
567             * +----------------------------------------------------------+
568             *              ^                        ^       ^
569             *              |                        |       |
570             *             less                      k     great
571             *
572             * Invariants:
573             *
574             *              all in (*, less)  == pivot1
575             *     pivot1 < all in [less, k)   < pivot2
576             *              all in (great, *) == pivot2
577             *
578             * Pointer k is the first index of ?-part
579             */
580            outer:
581            for (long k = less; k <= great; k++) {
582                long ak = a.get(k);
583                if (comp.eq(ak, ae4)) { // Move a[k] to right part
584                    long agreat;
585                    while (comp.eq((agreat = a.get(great)), ae4)) {
586                        if (great-- == k) {
587                            break outer;
588                        }
589                    }
590                    if (comp.eq(agreat, ae2)) {
591                        a.set(k, a.get(less));
592                        a.set(less++, agreat);
593                    } else { // pivot1 < a[great] < pivot2
594                        a.set(k, agreat);
595                    }
596                    a.set(great--, ak);
597                } else if (comp.eq(ak, ae2)) { // Move a[k] to left part
598                    a.set(k, a.get(less));
599                    a.set(less++, ak);
600                }
601            }
602        }
603
604        // Sort center part recursively, excluding known pivot values
605        doSortWithComparator(a, less, great, comp);
606    }
607
608    private static class LongComp {
609        final OffHeapLongComparator comp;
610
611        LongComp(OffHeapLongComparator comp) {
612            this.comp = comp;
613        }
614
615        boolean gt(long l1, long l2) {
616            return comp.compare(l1, l2) > 0;
617        }
618
619        boolean lt(long l1, long l2) {
620            return comp.compare(l1, l2) < 0;
621        }
622
623        boolean eq(long l1, long l2) {
624            return 0 == comp.compare(l1, l2);
625        }
626    }
627}