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