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 */
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 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 */
066public 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}