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}