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}