ProxySorter.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-5.1.0).
003  * Copyright (c) 2007-2019 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 java.util.List;
023 
024 /**
025  * This sorting methods doesn't sort a given array directly, instead
026  * an index lookup array is returned which allows to access the array in
027  * an sorted order.
028  *
029  <pre>{@code
030  * final double[] array = new Random().doubles(100).toArray();
031  * final int[] proxy = ProxySorter.sort(array);
032  *
033  * // 'Classical' array sort.
034  * final double[] sorted = array.clone();
035  * Arrays.sort(sorted);
036  *
037  * // Iterating the array in ascending order.
038  * for (int i = 0; i < array.length; ++i) {
039  *     assert sorted[i] == array[proxy[i]];
040  * }
041  * }</pre>
042  *
043  * The minimal requirement of the proxy-sorter will be an access function and
044  * the number of elements you want to sort.
045  <pre>{@code
046  * final IntFunction<String> access = ...;
047  * final int length = 100;
048  * final int[] proxy = ProxySorter.sort(
049  *     access, length,
050  *     (a, i, j) -> a.apply(i).compareTo(a.apply(j))
051  * );
052  * }</pre>
053  * @apiNote
054  * The most general sorting method is {@link #sort(Object, int, Comparator)}.
055  * All other sorting methods can be created with this method.
056  *
057  @see #sort(Object, int, Comparator)
058  @see Comparator
059  *
060  @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
061  @version 5.1
062  @since 5.1
063  */
064 public final class ProxySorter {
065 
066     /**
067      * The comparator used for comparing two array elements at the specified
068      * indexes.
069      <pre>{@code
070      * final ProxySorter.Comparator<double[]> comparator =
071      *     (a, i, j) -> Double.compare(a[i], a[j]);
072      * }</pre>
073      * The example above shows how to create a comparator for {@code double[]}
074      * arrays.
075      *
076      @see ProxySorter#sort(Object, int, Comparator)
077      @see ProxySorter
078      *
079      @param <T> the array type, e.g. {@code int[]}, {@code double[]} or
080      *            {@code Seq<String>}
081      *
082      @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
083      @version 5.1
084      @since 5.1
085      */
086     @FunctionalInterface
087     public static interface Comparator<T> {
088 
089         /**
090          * Compares the two array elements, specified by its indices, for order.
091          * Returns a negative integer, zero, or a positive integer as the first
092          * argument is less than, equal to, or greater than the second.
093          *
094          @see java.util.Comparator#compare(Object, Object)
095          *
096          @param array the array where the two comparing elements are fetched
097          @param i the index of the first array element
098          @param j the index of the second array element
099          @return a negative integer, zero, or a positive integer as the first
100          *         argument is less than, equal to, or greater than the second.
101          @throws NullPointerException if an argument is null and this
102          *         comparator does not permit null arguments
103          */
104         public int compare(final T array, final int i, final int j);
105 
106         /**
107          * Returns a comparator that imposes the reverse ordering of this
108          * comparator.
109          *
110          @return a comparator that imposes the reverse ordering of this
111          *         comparator.
112          */
113         public default Comparator<T> reversed() {
114             return (a, i, j-> compare(a, j, i);
115         }
116 
117     }
118 
119     private ProxySorter() {
120     }
121 
122     /**
123      * Sorting the given array by creating an index lookup array. The original
124      * array is not touched and the returned array can then be used for
125      * iterating the array in ascending order.
126      *
127      <pre>{@code
128      * final double[] array = ...;
129      * final int[] sorted = ProxySorter.sort(
130      *     array, array.length,
131      *     (a, i, j) -> Doubler.compare(a[i], a[j])
132      * );
133      * for (int i : sorted) {
134      *     System.out.println(array[i]);
135      * }
136      * }</pre>
137      *
138      @param array the array which is sorted
139      @param length the array length
140      @param comparator the array element comparator
141      @param <T> the array type
142      @return the sorted index array
143      @throws NullPointerException if one of the array is {@code null}
144      */
145     public static <T> int[] sort(
146         final T array,
147         final int length,
148         final Comparator<? super T> comparator
149     ) {
150         return TimProxySorter.sort(array, length, comparator);
151     }
152 
153 
154     /* *************************************************************************
155      * Derived sorting methods.
156      * ************************************************************************/
157 
158     /**
159      * Sorting the given array by creating an index lookup array.
160      *
161      @see #sort(Object, int, Comparator)
162      *
163      @param array the array to sort
164      @return the <em>sorted</em> index lookup array
165      @throws NullPointerException if the array is {@code null}
166      */
167     public static int[] sort(final int[] array) {
168         return sort(array, array.length, ProxySorter::compare);
169     }
170 
171     private static int compare(final int[] a, final int i, final int j) {
172         return Integer.compare(a[i], a[j]);
173     }
174 
175     /**
176      * Sorting the given array by creating an index lookup array.
177      *
178      @see #sort(Object, int, Comparator)
179      *
180      @param array the array to sort
181      @return the <em>sorted</em> index lookup array
182      @throws NullPointerException if the array is {@code null}
183      */
184     public static int[] sort(final long[] array) {
185         return sort(array, array.length, ProxySorter::compare);
186     }
187 
188     private static int compare(final long[] a, final int i, final int j) {
189         return Long.compare(a[i], a[j]);
190     }
191 
192     /**
193      * Sorting the given array by creating an index lookup array.
194      *
195      @see #sort(Object, int, Comparator)
196      *
197      @param array the array to sort
198      @return the <em>sorted</em> index lookup array
199      @throws NullPointerException if the array is {@code null}
200      */
201     public static int[] sort(final double[] array) {
202         return sort(array, array.length, ProxySorter::compare);
203     }
204 
205     private static int compare(final double[] a, final int i, final int j) {
206         return Double.compare(a[i], a[j]);
207     }
208 
209     /**
210      * Sorting the given array by creating an index lookup array.
211      *
212      @see #sort(Object, int, Comparator)
213      *
214      @param <T> the array element type
215      @param array the array to sort
216      @param comparator the array element comparator
217      @return the <em>sorted</em> index lookup array
218      @throws NullPointerException if one of the arguments is {@code null}
219      */
220     public static <T> int[] sort(
221         final T[] array,
222         final java.util.Comparator<? super T> comparator
223     ) {
224         return sort(
225             array, array.length,
226             (a, i, j-> comparator.compare(a[i], a[j])
227         );
228     }
229 
230     /**
231      * Sorting the given array by creating an index lookup array.
232      *
233      @see #sort(Object, int, Comparator)
234      *
235      @param <T> the array element type
236      @param array the array to sort
237      @return the <em>sorted</em> index lookup array
238      @throws NullPointerException if the array is {@code null}
239      */
240     public static <T extends Comparable<? super T>> int[] sort(final T[] array) {
241         return sort(
242             array, array.length,
243             (a, i, j-> a[i].compareTo(a[j])
244         );
245     }
246 
247     /**
248      * Sorting the given array by creating an index lookup array.
249      *
250      @see #sort(Object, int, Comparator)
251      *
252      @param <T> the array element type
253      @param array the array to sort
254      @param comparator the array element comparator
255      @return the <em>sorted</em> index lookup array
256      @throws NullPointerException if one of the arguments is {@code null}
257      */
258     public static <T> int[] sort(
259         final Seq<? extends T> array,
260         final java.util.Comparator<? super T> comparator
261     ) {
262         return sort(
263             array, array.size(),
264             (a, i, j-> comparator.compare(a.get(i), a.get(j))
265         );
266     }
267 
268     /**
269      * Sorting the given array by creating an index lookup array.
270      *
271      @see #sort(Object, int, Comparator)
272      *
273      @param <T> the array element type
274      @param array the array to sort
275      @return the <em>sorted</em> index lookup array
276      @throws NullPointerException if the array is {@code null}
277      */
278     public static <T extends Comparable<? super T>>
279     int[] sort(final Seq<? extends T> array) {
280         return sort(
281             array, array.size(),
282             (a, i, j-> a.get(i).compareTo(a.get(j))
283         );
284     }
285 
286     /**
287      * Sorting the given array by creating an index lookup array.
288      *
289      @see #sort(Object, int, Comparator)
290      *
291      @param <T> the array element type
292      @param array the array to sort
293      @param comparator the array element comparator
294      @return the <em>sorted</em> index lookup array
295      @throws NullPointerException if one of the arguments is {@code null}
296      */
297     public static <T> int[] sort(
298         final List<? extends T> array,
299         final java.util.Comparator<? super T> comparator
300     ) {
301         return sort(
302             array, array.size(),
303             (a, i, j-> comparator.compare(a.get(i), a.get(j))
304         );
305     }
306 
307     /**
308      * Sorting the given array by creating an index lookup array.
309      *
310      @see #sort(Object, int, Comparator)
311      *
312      @param <T> the array element type
313      @param array the array to sort
314      @return the <em>sorted</em> index lookup array
315      @throws NullPointerException if the array is {@code null}
316      */
317     public static <T extends Comparable<? super T>>
318     int[] sort(final List<? extends T> array) {
319         return sort(
320             array, array.size(),
321             (a, i, j-> a.get(i).compareTo(a.get(j))
322         );
323     }
324 
325     /* *************************************************************************
326      * Some helper methods.
327      * ************************************************************************/
328 
329     /**
330      * Create an initial indexes array of the given {@code length}.
331      *
332      @param length the length of the indexes array
333      @return the initialized indexes array
334      */
335     static int[] indexes(final int length) {
336         return init(new int[length]);
337     }
338 
339     /**
340      * Initializes the given {@code indexes} array.
341      *
342      @param indexes the indexes array to initialize
343      @return the initialized indexes array
344      @throws NullPointerException if the given {@code indexes} array is
345      *         {@code null}
346      */
347     static int[] init(final int[] indexes) {
348         for (int i = 0; i < indexes.length; ++i) {
349             indexes[i= i;
350         }
351         return indexes;
352     }
353 
354 }