001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.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 */
020package io.jenetics.util;
021
022import static java.util.Objects.checkFromToIndex;
023
024import 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 */
065public 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 subrange 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 subrange 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 subrange 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 subrange 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 subrange 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 subrange 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 subrange 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 subrange 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}