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 */ 020package io.jenetics.util; 021 022import 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 */ 064public 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}