1 /*
2 * Copyright (C) 2012 Alberto Irurueta Carro (alberto@irurueta.com)
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package com.irurueta.sorting;
17
18 import java.util.Comparator;
19
20 /**
21 * Sorts instances of type T in provided arrays using Heapsort method.
22 *
23 * @param <T> Type of instances being sorted.
24 * <p>
25 * This class is based on algorithm found at
26 * Numerical Recipes. 3rd Edition. Cambridge Press. Chapter 8. p. 428
27 * Knuth. D.E. 1997, Sorting and Searching, 3rd ed., vol. 3 of The Art of
28 * Computer Programming (Reading, MA: Addison-Wesley)
29 * Sedgewick, R. 1998. Algorithms in C, 3rd ed. (Reading, MA: Addison-
30 * Wesley), Chapter 11.
31 */
32 @SuppressWarnings("Duplicates")
33 public class HeapsortSorter<T> extends Sorter<T> {
34
35 /**
36 * Sorts provided array in ascending order so that {@code
37 * array[i - 1] < array[i]} for any valid i.
38 * This method modifies provided array so that
39 * after execution of this method array elements are ordered.
40 *
41 * @param array Array to be sorted. After execution of this method
42 * elements in array between fromIndex (inclusive) and toIndex
43 * (exclusive) are modified so that they are on ascending order.
44 * @param fromIndex Index were sorting starts (inclusive).
45 * @param toIndex Index were sorting stops (exclusive).
46 * @param comparator Determines whether an element is greater or lower
47 * than another one.
48 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
49 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
50 * {@code toIndex > array.length}.
51 */
52 @Override
53 public void sort(final T[] array, final int fromIndex, final int toIndex, final Comparator<T> comparator) {
54
55 if (fromIndex > toIndex) {
56 throw new IllegalArgumentException();
57 }
58 if (fromIndex < 0 || toIndex > array.length) {
59 throw new ArrayIndexOutOfBoundsException();
60 }
61 if (fromIndex == toIndex) {
62 return;
63 }
64
65 int i;
66 final var n = toIndex - fromIndex;
67
68 for (i = n / 2 - 1; i >= 0; i--) {
69 siftDown(array, i, n - 1, comparator, fromIndex);
70 }
71 for (i = n - 1; i > 0; i--) {
72 swap(array, fromIndex, i + fromIndex);
73 siftDown(array, 0, i - 1, comparator, fromIndex);
74 }
75 }
76
77 /**
78 * Sorts provided array in ascending order so that {@code
79 * array[i - 1] < array[i]} for any valid i.
80 * This method modifies provided array so that
81 * after execution of this method array elements are ordered.
82 * An array containing the original indices where elements were
83 * located is returned so that other arrays or collections can be kept
84 * in the same order.
85 *
86 * @param array Array to be sorted. After execution of this method
87 * elements in array between fromIndex (inclusive) and toIndex
88 * (exclusive) are modified so that they are on ascending order.
89 * @param fromIndex Index were sorting starts (inclusive).
90 * @param toIndex Index were sorting stops (exclusive).
91 * @param comparator Determines whether an element is greater or lower
92 * than another one.
93 * @return Array containing original location of elements that have been
94 * sorted. Only elements between fromIndex (inclusive) and toIndex
95 * (exclusive) are modified, the remaining ones are kept in natural
96 * order.
97 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
98 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
99 * {@code toIndex > array.length}.
100 */
101 @Override
102 public int[] sortWithIndices(final T[] array, final int fromIndex, final int toIndex,
103 final Comparator<T> comparator) {
104
105 if (fromIndex > toIndex) {
106 throw new IllegalArgumentException();
107 }
108 if (fromIndex < 0 || toIndex > array.length) {
109 throw new ArrayIndexOutOfBoundsException();
110 }
111
112 final var indices = getInitialIndicesVector(array.length);
113 if (fromIndex == toIndex) {
114 return indices;
115 }
116
117 int i;
118 final var n = toIndex - fromIndex;
119
120 for (i = n / 2 - 1; i >= 0; i--) {
121 siftDownWithIndices(array, indices, i, n - 1, comparator, fromIndex);
122 }
123 for (i = n - 1; i > 0; i--) {
124 swap(array, fromIndex, i + fromIndex);
125 swapIndices(indices, fromIndex, i + fromIndex);
126 siftDownWithIndices(array, indices, 0, i - 1, comparator, fromIndex);
127 }
128
129 return indices;
130 }
131
132 /**
133 * Returns sorting method of this class.
134 *
135 * @return Sorting method.
136 */
137 @Override
138 public SortingMethod getMethod() {
139 return SortingMethod.HEAPSORT_SORTING_METHOD;
140 }
141
142 /**
143 * Sorts provided array in ascending order so that {@code
144 * array[i - 1] < array[i]} for any valid i.
145 * This method modifies provided array so that
146 * after execution of this method array elements are ordered.
147 *
148 * @param array Array to be sorted. After execution of this method
149 * elements in array between fromIndex (inclusive) and toIndex
150 * (exclusive) are modified so that they are on ascending order.
151 * @param fromIndex Index were sorting starts (inclusive).
152 * @param toIndex Index were sorting stops (exclusive).
153 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
154 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
155 * {@code toIndex > array.length}.
156 */
157 @Override
158 public void sort(final double[] array, final int fromIndex, final int toIndex) {
159
160 if (fromIndex > toIndex) {
161 throw new IllegalArgumentException();
162 }
163 if (fromIndex < 0 || toIndex > array.length) {
164 throw new ArrayIndexOutOfBoundsException();
165 }
166 if (fromIndex == toIndex) {
167 return;
168 }
169
170 int i;
171 final var n = toIndex - fromIndex;
172
173 for (i = n / 2 - 1; i >= 0; i--) {
174 siftDown(array, i, n - 1, fromIndex);
175 }
176 for (i = n - 1; i > 0; i--) {
177 swap(array, fromIndex, i + fromIndex);
178 siftDown(array, 0, i - 1, fromIndex);
179 }
180 }
181
182 /**
183 * Sorts provided array in ascending order so that {@code
184 * array[i - 1] < array[i]} for any valid i.
185 * This method modifies provided array so that
186 * after execution of this method array elements are ordered.
187 * An array containing the original indices where elements were
188 * located is returned so that other arrays or collections can be kept
189 * in the same order.
190 *
191 * @param array Array to be sorted. After execution of this method
192 * elements in array between fromIndex (inclusive) and toIndex
193 * (exclusive) are modified so that they are on ascending order.
194 * @param fromIndex Index were sorting starts (inclusive).
195 * @param toIndex Index were sorting stops (exclusive).
196 * @return Array containing original location of elements that have been
197 * sorted. Only elements between fromIndex (inclusive) and toIndex
198 * (exclusive) are modified, the remaining ones are kept in natural
199 * order.
200 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
201 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
202 * {@code toIndex > array.length}.
203 */
204 @Override
205 public int[] sortWithIndices(final double[] array, final int fromIndex, final int toIndex) {
206
207 if (fromIndex > toIndex) {
208 throw new IllegalArgumentException();
209 }
210 if (fromIndex < 0 || toIndex > array.length) {
211 throw new ArrayIndexOutOfBoundsException();
212 }
213
214 final int[] indices = getInitialIndicesVector(array.length);
215 if (fromIndex == toIndex) {
216 return indices;
217 }
218
219 int i;
220 final var n = toIndex - fromIndex;
221
222 for (i = n / 2 - 1; i >= 0; i--) {
223 siftDownWithIndices(array, indices, i, n - 1, fromIndex);
224 }
225 for (i = n - 1; i > 0; i--) {
226 swap(array, fromIndex, i + fromIndex);
227 swapIndices(indices, fromIndex, i + fromIndex);
228 siftDownWithIndices(array, indices, 0, i - 1, fromIndex);
229 }
230
231 return indices;
232 }
233
234 /**
235 * Sorts provided array in ascending order so that {@code
236 * array[i - 1] < array[i]} for any valid i.
237 * This method modifies provided array so that
238 * after execution of this method array elements are ordered.
239 *
240 * @param array Array to be sorted. After execution of this method
241 * elements in array between fromIndex (inclusive) and toIndex
242 * (exclusive) are modified so that they are on ascending order.
243 * @param fromIndex Index were sorting starts (inclusive).
244 * @param toIndex Index were sorting stops (exclusive).
245 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
246 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
247 * {@code toIndex > array.length}.
248 */
249 @Override
250 public void sort(final float[] array, final int fromIndex, final int toIndex) {
251
252 if (fromIndex > toIndex) {
253 throw new IllegalArgumentException();
254 }
255 if (fromIndex < 0 || toIndex > array.length) {
256 throw new ArrayIndexOutOfBoundsException();
257 }
258 if (fromIndex == toIndex) {
259 return;
260 }
261
262 int i;
263 final var n = toIndex - fromIndex;
264
265 for (i = n / 2 - 1; i >= 0; i--) {
266 siftDown(array, i, n - 1, fromIndex);
267 }
268 for (i = n - 1; i > 0; i--) {
269 swap(array, fromIndex, i + fromIndex);
270 siftDown(array, 0, i - 1, fromIndex);
271 }
272 }
273
274 /**
275 * Sorts provided array in ascending order so that {@code
276 * array[i - 1] < array[i]} for any valid i.
277 * This method modifies provided array so that
278 * after execution of this method array elements are ordered.
279 * An array containing the original indices where elements were
280 * located is returned so that other arrays or collections can be kept
281 * in the same order.
282 *
283 * @param array Array to be sorted. After execution of this method
284 * elements in array between fromIndex (inclusive) and toIndex
285 * (exclusive) are modified so that they are on ascending order.
286 * @param fromIndex Index were sorting starts (inclusive).
287 * @param toIndex Index were sorting stops (exclusive).
288 * @return Array containing original location of elements that have been
289 * sorted. Only elements between fromIndex (inclusive) and toIndex
290 * (exclusive) are modified, the remaining ones are kept in natural
291 * order.
292 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
293 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
294 * {@code toIndex > array.length}.
295 */
296 @Override
297 public int[] sortWithIndices(final float[] array, final int fromIndex, final int toIndex) {
298
299 if (fromIndex > toIndex) {
300 throw new IllegalArgumentException();
301 }
302 if (fromIndex < 0 || toIndex > array.length) {
303 throw new ArrayIndexOutOfBoundsException();
304 }
305
306 final var indices = getInitialIndicesVector(array.length);
307 if (fromIndex == toIndex) {
308 return indices;
309 }
310
311 int i;
312 final var n = toIndex - fromIndex;
313
314 for (i = n / 2 - 1; i >= 0; i--) {
315 siftDownWithIndices(array, indices, i, n - 1, fromIndex);
316 }
317 for (i = n - 1; i > 0; i--) {
318 swap(array, fromIndex, i + fromIndex);
319 swapIndices(indices, fromIndex, i + fromIndex);
320 siftDownWithIndices(array, indices, 0, i - 1, fromIndex);
321 }
322
323 return indices;
324 }
325
326 /**
327 * Sorts provided array in ascending order so that {@code
328 * array[i - 1] < array[i]} for any valid i.
329 * This method modifies provided array so that
330 * after execution of this method array elements are ordered.
331 *
332 * @param array Array to be sorted. After execution of this method
333 * elements in array between fromIndex (inclusive) and toIndex
334 * (exclusive) are modified so that they are on ascending order.
335 * @param fromIndex Index were sorting starts (inclusive).
336 * @param toIndex Index were sorting stops (exclusive).
337 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
338 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
339 * {@code toIndex > array.length}.
340 */
341 @Override
342 public void sort(final int[] array, final int fromIndex, final int toIndex) {
343
344 if (fromIndex > toIndex) {
345 throw new IllegalArgumentException();
346 }
347 if (fromIndex < 0 || toIndex > array.length) {
348 throw new ArrayIndexOutOfBoundsException();
349 }
350 if (fromIndex == toIndex) {
351 return;
352 }
353
354 int i;
355 final var n = toIndex - fromIndex;
356
357 for (i = n / 2 - 1; i >= 0; i--) {
358 siftDown(array, i, n - 1, fromIndex);
359 }
360 for (i = n - 1; i > 0; i--) {
361 swap(array, fromIndex, i + fromIndex);
362 siftDown(array, 0, i - 1, fromIndex);
363 }
364 }
365
366 /**
367 * Sorts provided array in ascending order so that {@code
368 * array[i - 1] < array[i]} for any valid i.
369 * This method modifies provided array so that
370 * after execution of this method array elements are ordered.
371 * An array containing the original indices where elements were
372 * located is returned so that other arrays or collections can be kept
373 * in the same order.
374 *
375 * @param array Array to be sorted. After execution of this method
376 * elements in array between fromIndex (inclusive) and toIndex
377 * (exclusive) are modified so that they are on ascending order.
378 * @param fromIndex Index were sorting starts (inclusive).
379 * @param toIndex Index were sorting stops (exclusive).
380 * @return Array containing original location of elements that have been
381 * sorted. Only elements between fromIndex (inclusive) and toIndex
382 * (exclusive) are modified, the remaining ones are kept in natural
383 * order.
384 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
385 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
386 * {@code toIndex > array.length}.
387 */
388 @Override
389 public int[] sortWithIndices(final int[] array, final int fromIndex, final int toIndex) {
390
391 if (fromIndex > toIndex) {
392 throw new IllegalArgumentException();
393 }
394 if (fromIndex < 0 || toIndex > array.length) {
395 throw new ArrayIndexOutOfBoundsException();
396 }
397
398 final int[] indices = getInitialIndicesVector(array.length);
399 if (fromIndex == toIndex) {
400 return indices;
401 }
402
403 int i;
404 final var n = toIndex - fromIndex;
405
406 for (i = n / 2 - 1; i >= 0; i--) {
407 siftDownWithIndices(array, indices, i, n - 1, fromIndex);
408 }
409 for (i = n - 1; i > 0; i--) {
410 swap(array, fromIndex, i + fromIndex);
411 swapIndices(indices, fromIndex, i + fromIndex);
412 siftDownWithIndices(array, indices, 0, i - 1, fromIndex);
413 }
414
415 return indices;
416 }
417
418 /**
419 * Sorts provided array in ascending order so that {@code
420 * array[i - 1] < array[i]} for any valid i.
421 * This method modifies provided array so that
422 * after execution of this method array elements are ordered.
423 *
424 * @param array Array to be sorted. After execution of this method
425 * elements in array between fromIndex (inclusive) and toIndex
426 * (exclusive) are modified so that they are on ascending order.
427 * @param fromIndex Index were sorting starts (inclusive).
428 * @param toIndex Index were sorting stops (exclusive).
429 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
430 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
431 * {@code toIndex > array.length}.
432 */
433 @Override
434 public void sort(final long[] array, final int fromIndex, final int toIndex) {
435
436 if (fromIndex > toIndex) {
437 throw new IllegalArgumentException();
438 }
439 if (fromIndex < 0 || toIndex > array.length) {
440 throw new ArrayIndexOutOfBoundsException();
441 }
442 if (fromIndex == toIndex) {
443 return;
444 }
445
446 int i;
447 final var n = toIndex - fromIndex;
448
449 for (i = n / 2 - 1; i >= 0; i--) {
450 siftDown(array, i, n - 1, fromIndex);
451 }
452 for (i = n - 1; i > 0; i--) {
453 swap(array, fromIndex, i + fromIndex);
454 siftDown(array, 0, i - 1, fromIndex);
455 }
456 }
457
458 /**
459 * Sorts provided array in ascending order so that {@code
460 * array[i - 1] < array[i]} for any valid i.
461 * This method modifies provided array so that
462 * after execution of this method array elements are ordered.
463 * An array containing the original indices where elements were
464 * located is returned so that other arrays or collections can be kept
465 * in the same order.
466 *
467 * @param array Array to be sorted. After execution of this method
468 * elements in array between fromIndex (inclusive) and toIndex
469 * (exclusive) are modified so that they are on ascending order.
470 * @param fromIndex Index were sorting starts (inclusive).
471 * @param toIndex Index were sorting stops (exclusive).
472 * @return Array containing original location of elements that have been
473 * sorted. Only elements between fromIndex (inclusive) and toIndex
474 * (exclusive) are modified, the remaining ones are kept in natural
475 * order.
476 * @throws IllegalArgumentException If {@code fromIndex > toIndex}.
477 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
478 * {@code toIndex > array.length}.
479 */
480 @Override
481 public int[] sortWithIndices(final long[] array, final int fromIndex, final int toIndex) {
482
483 if (fromIndex > toIndex) {
484 throw new IllegalArgumentException();
485 }
486 if (fromIndex < 0 || toIndex > array.length) {
487 throw new ArrayIndexOutOfBoundsException();
488 }
489
490 final var indices = getInitialIndicesVector(array.length);
491 if (fromIndex == toIndex) {
492 return indices;
493 }
494
495 int i;
496 final var n = toIndex - fromIndex;
497
498 for (i = n / 2 - 1; i >= 0; i--) {
499 siftDownWithIndices(array, indices, i, n - 1, fromIndex);
500 }
501 for (i = n - 1; i > 0; i--) {
502 swap(array, fromIndex, i + fromIndex);
503 swapIndices(indices, fromIndex, i + fromIndex);
504 siftDownWithIndices(array, indices, 0, i - 1, fromIndex);
505 }
506
507 return indices;
508 }
509
510 /**
511 * Internal method to reorder sub-array ra.
512 *
513 * @param ra sub-array ra.
514 * @param l l value.
515 * @param r r value.
516 * @param comparator a comparator.
517 * @param fromIndex initial position.
518 */
519 private void siftDown(final T[] ra, final int l, final int r, final Comparator<T> comparator, final int fromIndex) {
520 int j;
521 int jold;
522 final var a = ra[l + fromIndex];
523 jold = l;
524 j = 2 * l + 1;
525 while (j <= r) {
526 if (j < r && comparator.compare(ra[j + fromIndex], ra[j + 1 + fromIndex]) < 0) {
527 j++;
528 }
529 if (comparator.compare(a, ra[j + fromIndex]) >= 0) {
530 break;
531 }
532 ra[jold + fromIndex] = ra[j + fromIndex];
533 jold = j;
534 j = 2 * j + 1;
535 }
536 ra[jold + fromIndex] = a;
537 }
538
539 /**
540 * Internal method to reorder sub-array ra along with its corresponding
541 * indices.
542 *
543 * @param ra sub-array ra.
544 * @param rb sub-array rb.
545 * @param l l value.
546 * @param r r value.
547 * @param comparator a comparator.
548 * @param fromIndex initial position.
549 */
550 private void siftDownWithIndices(final T[] ra, final int[] rb, final int l, final int r,
551 final Comparator<T> comparator, final int fromIndex) {
552 int j;
553 int jold;
554 final var a = ra[l + fromIndex];
555 final var b = rb[l + fromIndex];
556 jold = l;
557 j = 2 * l + 1;
558 while (j <= r) {
559 if (j < r && comparator.compare(ra[j + fromIndex], ra[j + 1 + fromIndex]) < 0) {
560 j++;
561 }
562 if (comparator.compare(a, ra[j + fromIndex]) >= 0) {
563 break;
564 }
565 ra[jold + fromIndex] = ra[j + fromIndex];
566 rb[jold + fromIndex] = rb[j + fromIndex];
567 jold = j;
568 j = 2 * j + 1;
569 }
570 ra[jold + fromIndex] = a;
571 rb[jold + fromIndex] = b;
572 }
573
574 /**
575 * Swaps values in array of indices at locations posA and posB.
576 *
577 * @param indices array containing indices to be swapped.
578 * @param posA Location to be swapped.
579 * @param posB Location to be swapped.
580 */
581 private void swapIndices(final int[] indices, final int posA, final int posB) {
582 final var value = indices[posA];
583 indices[posA] = indices[posB];
584 indices[posB] = value;
585 }
586
587 /**
588 * Internal method to reorder sub-array ra.
589 *
590 * @param ra sub-array ra.
591 * @param l l value.
592 * @param r r value.
593 * @param fromIndex initial position.
594 */
595 private void siftDown(final double[] ra, final int l, final int r, final int fromIndex) {
596 int j;
597 int jold;
598 final var a = ra[l + fromIndex];
599 jold = l;
600 j = 2 * l + 1;
601 while (j <= r) {
602 if (j < r && ra[j + fromIndex] < ra[j + 1 + fromIndex]) {
603 j++;
604 }
605 if (a >= ra[j + fromIndex]) {
606 break;
607 }
608 ra[jold + fromIndex] = ra[j + fromIndex];
609 jold = j;
610 j = 2 * j + 1;
611 }
612 ra[jold + fromIndex] = a;
613 }
614
615 /**
616 * Internal method to reorder sub-array ra along with its corresponding
617 * indices.
618 *
619 * @param ra sub-array ra.
620 * @param rb sub-array rb.
621 * @param l l value.
622 * @param r r value.
623 * @param fromIndex initial position.
624 */
625 private void siftDownWithIndices(final double[] ra, final int[] rb, final int l, final int r, final int fromIndex) {
626 int j;
627 int jold;
628 final var a = ra[l + fromIndex];
629 final var b = rb[l + fromIndex];
630 jold = l;
631 j = 2 * l + 1;
632 while (j <= r) {
633 if (j < r && ra[j + fromIndex] < ra[j + 1 + fromIndex]) {
634 j++;
635 }
636 if (a >= ra[j + fromIndex]) {
637 break;
638 }
639 ra[jold + fromIndex] = ra[j + fromIndex];
640 rb[jold + fromIndex] = rb[j + fromIndex];
641 jold = j;
642 j = 2 * j + 1;
643 }
644 ra[jold + fromIndex] = a;
645 rb[jold + fromIndex] = b;
646 }
647
648 /**
649 * Internal method to reorder sub-array ra.
650 *
651 * @param ra sub-array ra.
652 * @param l l value.
653 * @param r r value.
654 * @param fromIndex initial position.
655 */
656 private void siftDown(final float[] ra, final int l, final int r, final int fromIndex) {
657 int j;
658 int jold;
659 final var a = ra[l + fromIndex];
660 jold = l;
661 j = 2 * l + 1;
662 while (j <= r) {
663 if (j < r && ra[j + fromIndex] < ra[j + 1 + fromIndex]) {
664 j++;
665 }
666 if (a >= ra[j + fromIndex]) {
667 break;
668 }
669 ra[jold + fromIndex] = ra[j + fromIndex];
670 jold = j;
671 j = 2 * j + 1;
672 }
673 ra[jold + fromIndex] = a;
674 }
675
676 /**
677 * Internal method to reorder sub-array ra along with its corresponding
678 * indices.
679 *
680 * @param ra sub-array ra.
681 * @param rb sub-array rb.
682 * @param l l value.
683 * @param r r value.
684 * @param fromIndex initial position.
685 */
686 private void siftDownWithIndices(final float[] ra, final int[] rb, final int l, final int r, final int fromIndex) {
687 int j;
688 int jold;
689 final var a = ra[l + fromIndex];
690 final var b = rb[l + fromIndex];
691 jold = l;
692 j = 2 * l + 1;
693 while (j <= r) {
694 if (j < r && ra[j + fromIndex] < ra[j + 1 + fromIndex]) {
695 j++;
696 }
697 if (a >= ra[j + fromIndex]) {
698 break;
699 }
700 ra[jold + fromIndex] = ra[j + fromIndex];
701 rb[jold + fromIndex] = rb[j + fromIndex];
702 jold = j;
703 j = 2 * j + 1;
704 }
705 ra[jold + fromIndex] = a;
706 rb[jold + fromIndex] = b;
707 }
708
709 /**
710 * Internal method to reorder sub-array ra.
711 *
712 * @param ra sub-array ra.
713 * @param l l value.
714 * @param r r value.
715 * @param fromIndex initial position.
716 */
717 private void siftDown(final int[] ra, final int l, final int r, final int fromIndex) {
718 int j;
719 int jold;
720 final var a = ra[l + fromIndex];
721 jold = l;
722 j = 2 * l + 1;
723 while (j <= r) {
724 if (j < r && ra[j + fromIndex] < ra[j + 1 + fromIndex]) {
725 j++;
726 }
727 if (a >= ra[j + fromIndex]) {
728 break;
729 }
730 ra[jold + fromIndex] = ra[j + fromIndex];
731 jold = j;
732 j = 2 * j + 1;
733 }
734 ra[jold + fromIndex] = a;
735 }
736
737 /**
738 * Internal method to reorder sub-array ra along with its corresponding
739 * indices.
740 *
741 * @param ra sub-array ra.
742 * @param rb sub-array rb.
743 * @param l l value.
744 * @param r r value.
745 * @param fromIndex initial position.
746 */
747 private void siftDownWithIndices(final int[] ra, final int[] rb, final int l, final int r, final int fromIndex) {
748 int j;
749 int jold;
750 final var a = ra[l + fromIndex];
751 final var b = rb[l + fromIndex];
752 jold = l;
753 j = 2 * l + 1;
754 while (j <= r) {
755 if (j < r && ra[j + fromIndex] < ra[j + 1 + fromIndex]) {
756 j++;
757 }
758 if (a >= ra[j + fromIndex]) {
759 break;
760 }
761 ra[jold + fromIndex] = ra[j + fromIndex];
762 rb[jold + fromIndex] = rb[j + fromIndex];
763 jold = j;
764 j = 2 * j + 1;
765 }
766 ra[jold + fromIndex] = a;
767 rb[jold + fromIndex] = b;
768 }
769
770 /**
771 * Internal method to reorder sub-array ra.
772 *
773 * @param ra sub-array ra.
774 * @param l l value.
775 * @param r r value.
776 * @param fromIndex initial value.
777 */
778 private void siftDown(long[] ra, int l, int r, int fromIndex) {
779 int j;
780 int jold;
781 final var a = ra[l + fromIndex];
782 jold = l;
783 j = 2 * l + 1;
784 while (j <= r) {
785 if (j < r && ra[j + fromIndex] < ra[j + 1 + fromIndex]) {
786 j++;
787 }
788 if (a >= ra[j + fromIndex]) {
789 break;
790 }
791 ra[jold + fromIndex] = ra[j + fromIndex];
792 jold = j;
793 j = 2 * j + 1;
794 }
795 ra[jold + fromIndex] = a;
796 }
797
798 /**
799 * Internal method to reorder sub-array ra along with its corresponding
800 * indices.
801 *
802 * @param ra sub-array ra.
803 * @param rb sub-array rb.
804 * @param l l value.
805 * @param r r value.
806 * @param fromIndex initial value.
807 */
808 private void siftDownWithIndices(final long[] ra, final int[] rb, final int l, final int r, final int fromIndex) {
809 int j;
810 int jold;
811 final var a = ra[l + fromIndex];
812 final var b = rb[l + fromIndex];
813 jold = l;
814 j = 2 * l + 1;
815 while (j <= r) {
816 if (j < r && ra[j + fromIndex] < ra[j + 1 + fromIndex]) {
817 j++;
818 }
819 if (a >= ra[j + fromIndex]) {
820 break;
821 }
822 ra[jold + fromIndex] = ra[j + fromIndex];
823 rb[jold + fromIndex] = rb[j + fromIndex];
824 jold = j;
825 j = 2 * j + 1;
826 }
827 ra[jold + fromIndex] = a;
828 rb[jold + fromIndex] = b;
829 }
830 }