001 /*
002 * Java Genetic Algorithm Library (jenetics-8.0.0).
003 * Copyright (c) 2007-2024 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
019 */
020 package io.jenetics.util;
021
022 import static java.util.Objects.checkFromToIndex;
023
024 import java.util.List;
025
026 /**
027 * This sorting methods doesn't sort a given array directly; instead,
028 * an index lookup array is returned which allows accessing the array in a
029 * sorted order.
030 * {@snippet lang="java":
031 * final double[] array = new Random().doubles(100).toArray();
032 * final int[] proxy = ProxySorter.sort(array);
033 *
034 * // 'Classical' array sort.
035 * final double[] sorted = array.clone();
036 * Arrays.sort(sorted);
037 *
038 * // Iterating the array in ascending order.
039 * for (int i = 0; i < array.length; ++i) {
040 * assert sorted[i] == array[proxy[i]];
041 * }
042 * }
043 *
044 * The minimal requirement of the proxy-sorter will be an access function and
045 * the number of elements you want to sort.
046 * {@snippet lang="java":
047 * final IntFunction<String> access = null; // @replace substring='null' replacement="..."
048 * final int length = 100;
049 * final int[] proxy = ProxySorter.sort(
050 * access, length,
051 * (a, i, j) -> a.apply(i).compareTo(a.apply(j))
052 * );
053 * }
054 * @apiNote
055 * The most general sorting method is {@link #sort(Object, int, Comparator)}.
056 * All other sorting methods can be created with this method.
057 *
058 * @see #sort(Object, int, Comparator)
059 * @see Comparator
060 *
061 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
062 * @version 6.3
063 * @since 5.1
064 */
065 public final class ProxySorter {
066
067 /**
068 * The comparator used for comparing two array elements at the specified
069 * indexes.
070 * {@snippet lang="java":
071 * final ProxySorter.Comparator<double[]> comparator =
072 * (a, i, j) -> Double.compare(a[i], a[j]);
073 * }
074 * The example above shows how to create a comparator for {@code double[]}
075 * arrays.
076 *
077 * @see ProxySorter#sort(Object, int, Comparator)
078 * @see ProxySorter
079 *
080 * @param <T> the array type, e.g. {@code int[]}, {@code double[]} or
081 * {@code Seq<String>}
082 *
083 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
084 * @version 5.1
085 * @since 5.1
086 */
087 @FunctionalInterface
088 public interface Comparator<T> {
089
090 /**
091 * Compares the two array elements, specified by its indices, for order.
092 * Returns a negative integer, zero, or a positive integer as the first
093 * argument is less than, equal to, or greater than the second.
094 *
095 * @see java.util.Comparator#compare(Object, Object)
096 *
097 * @param array the array where the two comparing elements are fetched
098 * @param i the index of the first array element
099 * @param j the index of the second array element
100 * @return a negative integer, zero, or a positive integer as the first
101 * argument is less than, equal to, or greater than the second.
102 * @throws NullPointerException if an argument is null and this
103 * comparator does not permit null arguments
104 */
105 int compare(final T array, final int i, final int j);
106
107 /**
108 * Returns a comparator that imposes the reverse ordering of this
109 * comparator.
110 *
111 * @return a comparator that imposes the reverse ordering of this
112 * comparator.
113 */
114 default Comparator<T> reversed() {
115 return (a, i, j) -> compare(a, j, i);
116 }
117
118 }
119
120 @FunctionalInterface
121 interface Sorter<T> {
122 int[] sort(
123 final T array,
124 final int from,
125 final int to,
126 final Comparator<? super T> comparator
127 );
128
129 default int[] sort(
130 final T array,
131 final int length,
132 final Comparator<? super T> comparator
133 ) {
134 return sort(array, 0, length, comparator);
135 }
136 }
137
138 private ProxySorter() {
139 }
140
141 /**
142 * Sorting the given array by creating an index lookup array. The original
143 * array is not touched, and the returned array can then be used for
144 * iterating the array in ascending order.
145 * {@snippet lang="java":
146 * final double[] array = null; // @replace substring='null' replacement="..."
147 * final int[] sorted = ProxySorter.sort(
148 * array, 5, array.length,
149 * (a, i, j) -> Doubler.compare(a[i], a[j])
150 * );
151 * for (int i : sorted) {
152 * System.out.println(array[i]);
153 * }
154 * }
155 *
156 * @since 6.3
157 *
158 * @param array the array which is sorted
159 * @param from the index of the first element (inclusive) to be sorted
160 * @param to the index of the last element (exclusive) to be sorted
161 * @param comparator the array element comparator
162 * @param <T> the array type
163 * @return the sorted index array
164 * @throws NullPointerException if one of the arrays or comparator is
165 * {@code null}
166 * @throws IllegalArgumentException if {@code from > to}
167 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
168 */
169 public static <T> int[] sort(
170 final T array,
171 final int from,
172 final int to,
173 final Comparator<? super T> comparator
174 ) {
175 return TimProxySorter.sort(array, from, to, comparator);
176 }
177
178 /**
179 * Sorting the given array by creating an index lookup array. The original
180 * array is not touched, and the returned array can then be used for
181 * iterating the array in ascending order.
182 * {@snippet lang="java":
183 * final double[] array = null; // @replace substring='null' replacement="..."
184 * final int[] sorted = ProxySorter.sort(
185 * array, array.length,
186 * (a, i, j) -> Doubler.compare(a[i], a[j])
187 * );
188 * for (int i : sorted) {
189 * System.out.println(array[i]);
190 * }
191 * }
192 *
193 * @param array the array which is sorted
194 * @param length the array length
195 * @param comparator the array element comparator
196 * @param <T> the array type
197 * @return the sorted index array
198 * @throws NullPointerException if one of the arrays is {@code null}
199 * @throws IllegalArgumentException if {@code length < 0}
200 */
201 public static <T> int[] sort(
202 final T array,
203 final int length,
204 final Comparator<? super T> comparator
205 ) {
206 return sort(array, 0, length, comparator);
207 }
208
209
210 /* *************************************************************************
211 * Derived sorting methods.
212 * ************************************************************************/
213
214 /**
215 * Sorting the given array by creating an index lookup array.
216 *
217 * @see #sort(Object, int, Comparator)
218 *
219 * @param array the array to sort
220 * @return the <em>sorted</em> index lookup array
221 * @throws NullPointerException if the array is {@code null}
222 */
223 public static int[] sort(final int[] array) {
224 return sort(array, array.length, ProxySorter::compare);
225 }
226
227 private static int compare(final int[] a, final int i, final int j) {
228 return Integer.compare(a[i], a[j]);
229 }
230
231 /**
232 * Sorting the given array by creating an index lookup array.
233 *
234 * @see #sort(Object, int, int, Comparator)
235 *
236 * @since 6.3
237 *
238 * @param array the array to sort
239 * @param from the index of the first element (inclusive) to be sorted
240 * @param to the index of the last element (exclusive) to be sorted
241 * @return the <em>sorted</em> index lookup array
242 * @throws IllegalArgumentException if {@code from > to}
243 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
244 */
245 public static int[] sort(final int[] array, final int from, final int to) {
246 checkFromToIndex(from, to, array.length);
247 return sort(array, from, to, ProxySorter::compare);
248 }
249
250 /**
251 * Sorting the given array by creating an index lookup array.
252 *
253 * @see #sort(Object, int, Comparator)
254 *
255 * @param array the array to sort
256 * @return the <em>sorted</em> index lookup array
257 * @throws NullPointerException if the array is {@code null}
258 */
259 public static int[] sort(final long[] array) {
260 return sort(array, array.length, ProxySorter::compare);
261 }
262
263 private static int compare(final long[] a, final int i, final int j) {
264 return Long.compare(a[i], a[j]);
265 }
266
267 /**
268 * Sorting the given array by creating an index lookup array.
269 *
270 * @see #sort(Object, int, int, Comparator)
271 *
272 * @since 6.3
273 *
274 * @param array the array to sort
275 * @param from the index of the first element (inclusive) to be sorted
276 * @param to the index of the last element (exclusive) to be sorted
277 * @return the <em>sorted</em> index lookup array
278 * @throws IllegalArgumentException if {@code from > to}
279 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
280 */
281 public static int[] sort(final long[] array, final int from, final int to) {
282 checkFromToIndex(from, to, array.length);
283 return sort(array, from, to, ProxySorter::compare);
284 }
285
286 /**
287 * Sorting the given array by creating an index lookup array.
288 *
289 * @see #sort(Object, int, Comparator)
290 *
291 * @param array the array to sort
292 * @return the <em>sorted</em> index lookup array
293 * @throws NullPointerException if the array is {@code null}
294 */
295 public static int[] sort(final double[] array) {
296 return sort(array, array.length, ProxySorter::compare);
297 }
298
299 private static int compare(final double[] a, final int i, final int j) {
300 return Double.compare(a[i], a[j]);
301 }
302
303 /**
304 * Sorting the given array by creating an index lookup array.
305 *
306 * @see #sort(Object, int, int, Comparator)
307 *
308 * @since 6.3
309 *
310 * @param array the array to sort
311 * @param from the index of the first element (inclusive) to be sorted
312 * @param to the index of the last element (exclusive) to be sorted
313 * @return the <em>sorted</em> index lookup array
314 * @throws IllegalArgumentException if {@code from > to}
315 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
316 */
317 public static int[] sort(final double[] array, final int from, final int to) {
318 checkFromToIndex(from, to, array.length);
319 return sort(array, from, to, ProxySorter::compare);
320 }
321
322 /**
323 * Sorting the given array by creating an index lookup array.
324 *
325 * @see #sort(Object, int, Comparator)
326 *
327 * @param <T> the array element type
328 * @param array the array to sort
329 * @param comparator the array element comparator
330 * @return the <em>sorted</em> index lookup array
331 * @throws NullPointerException if one of the arguments is {@code null}
332 */
333 public static <T> int[] sort(
334 final T[] array,
335 final java.util.Comparator<? super T> comparator
336 ) {
337 return sort(
338 array, array.length,
339 (a, i, j) -> comparator.compare(a[i], a[j])
340 );
341 }
342
343 /**
344 * Sorting the given array by creating an index lookup array.
345 *
346 * @see #sort(Object, int, int, Comparator)
347 *
348 * @since 6.3
349 *
350 * @param <T> the array element type
351 * @param array the array to sort
352 * @param from the index of the first element (inclusive) to be sorted
353 * @param to the index of the last element (exclusive) to be sorted
354 * @param comparator the array element comparator
355 * @return the <em>sorted</em> index lookup array
356 * @throws NullPointerException if one of the arguments is {@code null}
357 * @throws IllegalArgumentException if {@code from > to}
358 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
359 */
360 public static <T> int[] sort(
361 final T[] array,
362 final int from,
363 final int to,
364 final java.util.Comparator<? super T> comparator
365 ) {
366 checkFromToIndex(from, to, array.length);
367 return sort(
368 array, from, to,
369 (a, i, j) -> comparator.compare(a[i], a[j])
370 );
371 }
372
373 /**
374 * Sorting the given array by creating an index lookup array.
375 *
376 * @see #sort(Object, int, Comparator)
377 *
378 * @param <T> the array element type
379 * @param array the array to sort
380 * @return the <em>sorted</em> index lookup array
381 * @throws NullPointerException if the array is {@code null}
382 */
383 public static <T extends Comparable<? super T>> int[] sort(final T[] array) {
384 return sort(
385 array, array.length,
386 (a, i, j) -> a[i].compareTo(a[j])
387 );
388 }
389
390 /**
391 * Sorting the given array by creating an index lookup array.
392 *
393 * @see #sort(Object, int, int, Comparator)
394 *
395 * @since 6.3
396 *
397 * @param <T> the array element type
398 * @param array the array to sort
399 * @param from the index of the first element (inclusive) to be sorted
400 * @param to the index of the last element (exclusive) to be sorted
401 * @return the <em>sorted</em> index lookup array
402 * @throws NullPointerException if the array is {@code null}
403 * @throws IllegalArgumentException if {@code from > to}
404 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
405 */
406 public static <T extends Comparable<? super T>> int[] sort(
407 final T[] array,
408 final int from,
409 final int to
410 ) {
411 checkFromToIndex(from, to, array.length);
412 return sort(
413 array, from, to,
414 (a, i, j) -> a[i].compareTo(a[j])
415 );
416 }
417
418 /**
419 * Sorting the given array by creating an index lookup array.
420 *
421 * @see #sort(Object, int, Comparator)
422 *
423 * @param <T> the array element type
424 * @param array the array to sort
425 * @param comparator the array element comparator
426 * @return the <em>sorted</em> index lookup array
427 * @throws NullPointerException if one of the arguments is {@code null}
428 */
429 public static <T> int[] sort(
430 final BaseSeq<? extends T> array,
431 final java.util.Comparator<? super T> comparator
432 ) {
433 return sort(
434 array, array.length(),
435 (a, i, j) -> comparator.compare(a.get(i), a.get(j))
436 );
437 }
438
439 /**
440 * Sorting the given array by creating an index lookup array.
441 *
442 * @see #sort(Object, int, int, Comparator)
443 *
444 * @since 6.3
445 *
446 * @param <T> the array element type
447 * @param array the array to sort
448 * @param from the index of the first element (inclusive) to be sorted
449 * @param to the index of the last element (exclusive) to be sorted
450 * @param comparator the array element comparator
451 * @return the <em>sorted</em> index lookup array
452 * @throws NullPointerException if one of the arguments is {@code null}
453 * @throws IllegalArgumentException if {@code from > to}
454 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
455 */
456 public static <T> int[] sort(
457 final BaseSeq<? extends T> array,
458 final int from,
459 final int to,
460 final java.util.Comparator<? super T> comparator
461 ) {
462 checkFromToIndex(from, to, array.length());
463 return sort(
464 array, from, to,
465 (a, i, j) -> comparator.compare(a.get(i), a.get(j))
466 );
467 }
468
469 /**
470 * Sorting the given array by creating an index lookup array.
471 *
472 * @see #sort(Object, int, Comparator)
473 *
474 * @param <T> the array element type
475 * @param array the array to sort
476 * @return the <em>sorted</em> index lookup array
477 * @throws NullPointerException if the array is {@code null}
478 */
479 public static <T extends Comparable<? super T>>
480 int[] sort(final BaseSeq<? extends T> array) {
481 return sort(
482 array, array.length(),
483 (a, i, j) -> a.get(i).compareTo(a.get(j))
484 );
485 }
486
487 /**
488 * Sorting the given array by creating an index lookup array.
489 *
490 * @see #sort(Object, int, int, Comparator)
491 *
492 * @since 6.3
493 *
494 * @param <T> the array element type
495 * @param array the array to sort
496 * @param from the index of the first element (inclusive) to be sorted
497 * @param to the index of the last element (exclusive) to be sorted
498 * @return the <em>sorted</em> index lookup array
499 * @throws NullPointerException if the array is {@code null}
500 * @throws IllegalArgumentException if {@code from > to}
501 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
502 */
503 public static <T extends Comparable<? super T>>
504 int[] sort(final BaseSeq<? extends T> array, final int from, final int to) {
505 checkFromToIndex(from, to, array.length());
506 return sort(
507 array, from, to,
508 (a, i, j) -> a.get(i).compareTo(a.get(j))
509 );
510 }
511
512 /**
513 * Sorting the given array by creating an index lookup array.
514 *
515 * @see #sort(Object, int, Comparator)
516 *
517 * @param <T> the array element type
518 * @param array the array to sort
519 * @param comparator the array element comparator
520 * @return the <em>sorted</em> index lookup array
521 * @throws NullPointerException if one of the arguments is {@code null}
522 */
523 public static <T> int[] sort(
524 final List<? extends T> array,
525 final java.util.Comparator<? super T> comparator
526 ) {
527 return sort(
528 array, array.size(),
529 (a, i, j) -> comparator.compare(a.get(i), a.get(j))
530 );
531 }
532
533 /**
534 * Sorting the given array by creating an index lookup array.
535 *
536 * @see #sort(Object, int, int, Comparator)
537 *
538 * @since 6.3
539 *
540 * @param <T> the array element type
541 * @param array the array to sort
542 * @param from the index of the first element (inclusive) to be sorted
543 * @param to the index of the last element (exclusive) to be sorted
544 * @param comparator the array element comparator
545 * @return the <em>sorted</em> index lookup array
546 * @throws NullPointerException if one of the arguments is {@code null}
547 * @throws IllegalArgumentException if {@code from > to}
548 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
549 */
550 public static <T> int[] sort(
551 final List<? extends T> array,
552 final int from,
553 final int to,
554 final java.util.Comparator<? super T> comparator
555 ) {
556 checkFromToIndex(from, to, array.size());
557 return sort(
558 array, from, to,
559 (a, i, j) -> comparator.compare(a.get(i), a.get(j))
560 );
561 }
562
563 /**
564 * Sorting the given array by creating an index lookup array.
565 *
566 * @see #sort(Object, int, Comparator)
567 *
568 * @param <T> the array element type
569 * @param array the array to sort
570 * @return the <em>sorted</em> index lookup array
571 * @throws NullPointerException if the array is {@code null}
572 */
573 public static <T extends Comparable<? super T>>
574 int[] sort(final List<? extends T> array) {
575 return sort(
576 array, array.size(),
577 (a, i, j) -> a.get(i).compareTo(a.get(j))
578 );
579 }
580
581 /**
582 * Sorting the given array by creating an index lookup array.
583 *
584 * @see #sort(Object, int, int, Comparator)
585 *
586 * @since 6.3
587 *
588 * @param <T> the array element type
589 * @param array the array to sort
590 * @param from the index of the first element (inclusive) to be sorted
591 * @param to the index of the last element (exclusive) to be sorted
592 * @return the <em>sorted</em> index lookup array
593 * @throws NullPointerException if the array is {@code null}
594 * @throws IllegalArgumentException if {@code from > to}
595 * @throws IndexOutOfBoundsException if the sub-range is out of bounds
596 */
597 public static <T extends Comparable<? super T>>
598 int[] sort(final List<? extends T> array, final int from, final int to) {
599 checkFromToIndex(from, to, array.size());
600 return sort(
601 array, from, to,
602 (a, i, j) -> a.get(i).compareTo(a.get(j))
603 );
604 }
605
606 /* *************************************************************************
607 * Some helper methods.
608 * ************************************************************************/
609
610 /**
611 * Create an initial indexes array of the given {@code length}.
612 *
613 * @param length the length of the indexes array
614 * @return the initialized indexes array
615 */
616 static int[] indexes(final int length) {
617 return init(new int[length]);
618 }
619
620 /**
621 * Initializes the given {@code indexes} array.
622 *
623 * @param indexes the index array to initialize
624 * @return the initialized indexes array
625 * @throws NullPointerException if the given {@code indexes} array is
626 * {@code null}
627 */
628 private static int[] init(final int[] indexes) {
629 for (int i = 0; i < indexes.length; ++i) {
630 indexes[i] = i;
631 }
632 return indexes;
633 }
634
635 }
|