1 /* 2 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.util; 27 28 import java.io.Serializable; 29 import java.util.function.Function; 30 import java.util.function.ToIntFunction; 31 import java.util.function.ToLongFunction; 32 import java.util.function.ToDoubleFunction; 33 import java.util.Comparators; 34 35 /** 36 * A comparison function, which imposes a <i>total ordering</i> on some 37 * collection of objects. Comparators can be passed to a sort method (such 38 * as {@link Collections#sort(List,Comparator) Collections.sort} or {@link 39 * Arrays#sort(Object[],Comparator) Arrays.sort}) to allow precise control 40 * over the sort order. Comparators can also be used to control the order of 41 * certain data structures (such as {@link SortedSet sorted sets} or {@link 42 * SortedMap sorted maps}), or to provide an ordering for collections of 43 * objects that don't have a {@link Comparable natural ordering}.<p> 44 * 45 * The ordering imposed by a comparator <tt>c</tt> on a set of elements 46 * <tt>S</tt> is said to be <i>consistent with equals</i> if and only if 47 * <tt>c.compare(e1, e2)==0</tt> has the same boolean value as 48 * <tt>e1.equals(e2)</tt> for every <tt>e1</tt> and <tt>e2</tt> in 49 * <tt>S</tt>.<p> 50 * 51 * Caution should be exercised when using a comparator capable of imposing an 52 * ordering inconsistent with equals to order a sorted set (or sorted map). 53 * Suppose a sorted set (or sorted map) with an explicit comparator <tt>c</tt> 54 * is used with elements (or keys) drawn from a set <tt>S</tt>. If the 55 * ordering imposed by <tt>c</tt> on <tt>S</tt> is inconsistent with equals, 56 * the sorted set (or sorted map) will behave "strangely." In particular the 57 * sorted set (or sorted map) will violate the general contract for set (or 58 * map), which is defined in terms of <tt>equals</tt>.<p> 59 * 60 * For example, suppose one adds two elements {@code a} and {@code b} such that 61 * {@code (a.equals(b) && c.compare(a, b) != 0)} 62 * to an empty {@code TreeSet} with comparator {@code c}. 63 * The second {@code add} operation will return 64 * true (and the size of the tree set will increase) because {@code a} and 65 * {@code b} are not equivalent from the tree set's perspective, even though 66 * this is contrary to the specification of the 67 * {@link Set#add Set.add} method.<p> 68 * 69 * Note: It is generally a good idea for comparators to also implement 70 * <tt>java.io.Serializable</tt>, as they may be used as ordering methods in 71 * serializable data structures (like {@link TreeSet}, {@link TreeMap}). In 72 * order for the data structure to serialize successfully, the comparator (if 73 * provided) must implement <tt>Serializable</tt>.<p> 74 * 75 * For the mathematically inclined, the <i>relation</i> that defines the 76 * <i>imposed ordering</i> that a given comparator <tt>c</tt> imposes on a 77 * given set of objects <tt>S</tt> is:<pre> 78 * {(x, y) such that c.compare(x, y) <= 0}. 79 * </pre> The <i>quotient</i> for this total order is:<pre> 80 * {(x, y) such that c.compare(x, y) == 0}. 81 * </pre> 82 * 83 * It follows immediately from the contract for <tt>compare</tt> that the 84 * quotient is an <i>equivalence relation</i> on <tt>S</tt>, and that the 85 * imposed ordering is a <i>total order</i> on <tt>S</tt>. When we say that 86 * the ordering imposed by <tt>c</tt> on <tt>S</tt> is <i>consistent with 87 * equals</i>, we mean that the quotient for the ordering is the equivalence 88 * relation defined by the objects' {@link Object#equals(Object) 89 * equals(Object)} method(s):<pre> 90 * {(x, y) such that x.equals(y)}. </pre> 91 * 92 * <p>Unlike {@code Comparable}, a comparator may optionally permit 93 * comparison of null arguments, while maintaining the requirements for 94 * an equivalence relation. 95 * 96 * <p>This interface is a member of the 97 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 98 * Java Collections Framework</a>. 99 * 100 * @param <T> the type of objects that may be compared by this comparator 101 * 102 * @author Josh Bloch 103 * @author Neal Gafter 104 * @see Comparable 105 * @see java.io.Serializable 106 * @since 1.2 107 */ 108 @FunctionalInterface 109 public interface Comparator<T> { 110 /** 111 * Compares its two arguments for order. Returns a negative integer, 112 * zero, or a positive integer as the first argument is less than, equal 113 * to, or greater than the second.<p> 114 * 115 * In the foregoing description, the notation 116 * <tt>sgn(</tt><i>expression</i><tt>)</tt> designates the mathematical 117 * <i>signum</i> function, which is defined to return one of <tt>-1</tt>, 118 * <tt>0</tt>, or <tt>1</tt> according to whether the value of 119 * <i>expression</i> is negative, zero or positive.<p> 120 * 121 * The implementor must ensure that <tt>sgn(compare(x, y)) == 122 * -sgn(compare(y, x))</tt> for all <tt>x</tt> and <tt>y</tt>. (This 123 * implies that <tt>compare(x, y)</tt> must throw an exception if and only 124 * if <tt>compare(y, x)</tt> throws an exception.)<p> 125 * 126 * The implementor must also ensure that the relation is transitive: 127 * <tt>((compare(x, y)>0) && (compare(y, z)>0))</tt> implies 128 * <tt>compare(x, z)>0</tt>.<p> 129 * 130 * Finally, the implementor must ensure that <tt>compare(x, y)==0</tt> 131 * implies that <tt>sgn(compare(x, z))==sgn(compare(y, z))</tt> for all 132 * <tt>z</tt>.<p> 133 * 134 * It is generally the case, but <i>not</i> strictly required that 135 * <tt>(compare(x, y)==0) == (x.equals(y))</tt>. Generally speaking, 136 * any comparator that violates this condition should clearly indicate 137 * this fact. The recommended language is "Note: this comparator 138 * imposes orderings that are inconsistent with equals." 139 * 140 * @param o1 the first object to be compared. 141 * @param o2 the second object to be compared. 142 * @return a negative integer, zero, or a positive integer as the 143 * first argument is less than, equal to, or greater than the 144 * second. 145 * @throws NullPointerException if an argument is null and this 146 * comparator does not permit null arguments 147 * @throws ClassCastException if the arguments' types prevent them from 148 * being compared by this comparator. 149 */ 150 int compare(T o1, T o2); 151 152 /** 153 * Indicates whether some other object is "equal to" this 154 * comparator. This method must obey the general contract of 155 * {@link Object#equals(Object)}. Additionally, this method can return 156 * <tt>true</tt> <i>only</i> if the specified object is also a comparator 157 * and it imposes the same ordering as this comparator. Thus, 158 * <code>comp1.equals(comp2)</code> implies that <tt>sgn(comp1.compare(o1, 159 * o2))==sgn(comp2.compare(o1, o2))</tt> for every object reference 160 * <tt>o1</tt> and <tt>o2</tt>.<p> 161 * 162 * Note that it is <i>always</i> safe <i>not</i> to override 163 * <tt>Object.equals(Object)</tt>. However, overriding this method may, 164 * in some cases, improve performance by allowing programs to determine 165 * that two distinct comparators impose the same order. 166 * 167 * @param obj the reference object with which to compare. 168 * @return <code>true</code> only if the specified object is also 169 * a comparator and it imposes the same ordering as this 170 * comparator. 171 * @see Object#equals(Object) 172 * @see Object#hashCode() 173 */ 174 boolean equals(Object obj); 175 176 /** 177 * Returns a comparator that imposes the reverse ordering of this 178 * comparator. 179 * 180 * @return A comparator that imposes the reverse ordering of this 181 * comparator. 182 * @since 1.8 183 */ 184 default Comparator<T> reversed() { 185 return (Comparator<T>) Collections.reverseOrder(this); 186 } 187 188 /** 189 * Returns a comparator that imposes the reverse of the <em>natural 190 * ordering</em>. 191 * 192 * <p>The returned comparator is serializable. Try to compare null with 193 * returned comparator will throw {@link NullPointerException}. 194 * 195 * @param <T> The {@link Comparable} type of element to be compared 196 * @return A comparator that imposes the reverse of the <i>natural 197 * ordering</i> on a collection of objects that implement 198 * the {@link Comparable} interface. 199 * @see Comparable 200 * @since 1.8 201 */ 202 public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() { 203 return Collections.reverseOrder(); 204 } 205 206 /** 207 * Returns a comparator compares {@link Comparable} type in natural order. 208 * 209 * <p>The returned comparator is serializable. Try to compare null with 210 * returned comparator will throw {@link NullPointerException}. 211 * 212 * @param <T> The {@link Comparable} type of element to be compared 213 * @return A comparator that imposes the <i>natural ordering</i> on a 214 * collection of objects that implement the {@link Comparable} 215 * interface. 216 * @see Comparable 217 * @since 1.8 218 */ 219 public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() { 220 return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE; 221 } 222 223 /** 224 * Returns a null-friendly comparator that considers {@code null} to be 225 * less than non-null. When both are {@code null}, they are considered 226 * equal. If both are non-null, the specified {@code Comparator} is used 227 * to determine the order. 228 * 229 * <p>The returned comparator is serializable if the specified comparator 230 * is serializable. 231 * 232 * @param <T> the type of the elements to be compared 233 * @param comparator A {@code Comparator} for comparing non-null values 234 * @return A comparator that considers {@code null} to be less than non-null. 235 * @since 1.8 236 */ 237 public static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator) { 238 return new Comparators.NullComparator(-1, comparator); 239 } 240 241 /** 242 * Returns a null-friendly comparator that considers {@code null} to be 243 * greater than non-null. When both are {@code null}, they are considered 244 * equal. If both are non-null, the specified {@code Comparator} is used 245 * to determine the order. 246 * 247 * <p>The returned comparator is serializable if the specified comparator 248 * is serializable. 249 * 250 * @param <T> the type of the elements to be compared 251 * @param comparator A {@code Comparator} for comparing non-null values 252 * @return A comparator that considers {@code null} to be greater than non-null. 253 * @since 1.8 254 */ 255 public static <T> Comparator<T> nullsLast(Comparator<? super T> comparator) { 256 return new Comparators.NullComparator(1, comparator); 257 } 258 259 /** 260 * Accepts a function that extracts a sort key from a type {@code T}, and 261 * returns a {@code Comparator<T>} that compares by that sort key using 262 * the specified {@link Comparator}. For example, to obtain a {@code 263 * Comparator} that compares {@code Person} objects by their last name 264 * ignoring case differences, 265 * 266 * <pre>{@code 267 * Comparator<People> cmp = Comparator.comparing( 268 * Person::getLastName, 269 * String.CASE_INSENSITIVE_ORDER); 270 * }</pre> 271 * 272 * <p> The returned comparator is serializable if the specified function 273 * and comparator are both serializable. 274 * 275 * @param <T> The type of element to be compared 276 * @param <U> The type of the sort key 277 * @param keyExtractor the function used to extract the sort key 278 * @param keyComparator the {@code Comparator} used to compare the sort key 279 * @return A comparator that compares by an extracted key using the 280 * specified {@code Comparator} 281 * @throws NullPointerException if the argument is null 282 * @since 1.8 283 */ 284 public static <T, U> Comparator<T> comparing( 285 Function<? super T, ? extends U> keyExtractor, 286 Comparator<? super U> keyComparator) 287 { 288 Objects.requireNonNull(keyExtractor); 289 Objects.requireNonNull(keyComparator); 290 return (Comparator<T> & Serializable) 291 (c1, c2) -> keyComparator.compare(keyExtractor.apply(c1), 292 keyExtractor.apply(c2)); 293 } 294 295 /** 296 * Accepts a function that extracts a {@link java.lang.Comparable 297 * Comparable} sort key from a type {@code T}, and returns a {@code 298 * Comparator<T>} that compares by that sort key. For example, to obtain 299 * a {@code Comparator} that compares {@code Person} objects by their last 300 * name, 301 * 302 * <pre>{@code 303 * Comparator<People> byLastName = Comparator.comparing(Person::getLastName); 304 * }</pre> 305 * 306 * <p> The returned comparator is serializable if the specified function 307 * is also serializable. 308 * 309 * @param <T> The type of element to be compared 310 * @param <U> The type of the {@code Comparable} sort key 311 * @param keyExtractor the function used to extract the {@link 312 * Comparable} sort key 313 * @return A comparator that compares by an extracted key 314 * @throws NullPointerException if the argument is null 315 * @since 1.8 316 */ 317 public static <T, U extends Comparable<? super U>> Comparator<T> comparing( 318 Function<? super T, ? extends U> keyExtractor) 319 { 320 Objects.requireNonNull(keyExtractor); 321 return (Comparator<T> & Serializable) 322 (c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2)); 323 } 324 325 /** 326 * Accepts a function that extracts an {@code int} sort key from a type 327 * {@code T}, and returns a {@code Comparator<T>} that compares by that 328 * sort key. For example, to obtain a {@code Comparator} that compares 329 * {@code Person} objects by their age, 330 * 331 * <pre>{@code 332 * Comparator<People> byAge = Comparator.comparing(Person::getAge); 333 * }</pre> 334 * 335 * <p> The returned comparator is serializable if the specified function 336 * is also serializable. 337 * 338 * @param <T> The type of element to be compared 339 * @param keyExtractor the function used to extract the integer sort key 340 * @return A comparator that compares by an extracted key 341 * @see #comparing(Function) 342 * @throws NullPointerException if the argument is null 343 * @since 1.8 344 */ 345 public static <T> Comparator<T> comparing(ToIntFunction<? super T> keyExtractor) { 346 Objects.requireNonNull(keyExtractor); 347 return (Comparator<T> & Serializable) 348 (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2)); 349 } 350 351 /** 352 * Accepts a function that extracts a {@code long} sort key from a type 353 * {@code T}, and returns a {@code Comparator<T>} that compares by that 354 * sort key. 355 * 356 * <p> The returned comparator is serializable if the specified function 357 * is also serializable. 358 * 359 * @param <T> The type of element to be compared 360 * @param keyExtractor the function used to extract the long sort key 361 * @return A comparator that compares by an extracted key 362 * @see #comparing(Function) 363 * @throws NullPointerException if the argument is null 364 * @since 1.8 365 */ 366 public static <T> Comparator<T> comparing(ToLongFunction<? super T> keyExtractor) { 367 Objects.requireNonNull(keyExtractor); 368 return (Comparator<T> & Serializable) 369 (c1, c2) -> Long.compare(keyExtractor.applyAsLong(c1), keyExtractor.applyAsLong(c2)); 370 } 371 372 /** 373 * Accepts a function that extracts a {@code double} sort key from a type 374 * {@code T}, and returns a {@code Comparator<T>} that compares by that 375 * sort key. 376 * 377 * <p> The returned comparator is serializable if the specified function 378 * is also serializable. 379 * 380 * @param <T> The type of element to be compared 381 * @param keyExtractor the function used to extract the double sort key 382 * @return A comparator that compares by an extracted key 383 * @see #comparing(Function) 384 * @throws NullPointerException if the argument is null 385 * @since 1.8 386 */ 387 public static<T> Comparator<T> comparing(ToDoubleFunction<? super T> keyExtractor) { 388 Objects.requireNonNull(keyExtractor); 389 return (Comparator<T> & Serializable) 390 (c1, c2) -> Double.compare(keyExtractor.applyAsDouble(c1), keyExtractor.applyAsDouble(c2)); 391 } 392 393 /** 394 * Constructs a lexicographic order comparator with another comparator. 395 * If this {@code Comparator} considers two elements equal, i.e. 396 * {@code compare(a, b) == 0}, {@code other} is used to determine the order. 397 * 398 * <p> For example, to sort a collection of {@code String} based on the 399 * length and then case-insensitive natural ordering, the comparator can 400 * be construcred using following code, 401 * 402 * <pre>{@code 403 * Comparator<String> cmp = Comparator.comparing(String::length) 404 * .thenComparing(String.CASE_INSENSITIVE_ORDER); 405 * }</pre> 406 * 407 * <p> The returned comparator is serializable if the specified comparator 408 * is also serializable. 409 * 410 * @param <T> The type of elements compared by the returned comparator. 411 * @param other the other comparator to be used when this comparator 412 * compares two objects that are equal. 413 * @return A lexicographic order comparator composed of this and then the 414 * other comparator 415 * @throws NullPointerException if the argument is null. 416 * @since 1.8 417 */ 418 default Comparator<T> thenComparing(Comparator<? super T> other) { 419 Objects.requireNonNull(other); 420 return (Comparator<T> & Serializable) (c1, c2) -> { 421 int res = compare(c1, c2); 422 return (res != 0) ? res : other.compare(c1, c2); 423 }; 424 } 425 426 /** 427 * Constructs a lexicographic order comparator with a function that 428 * extracts a key to be compared with the given {@code Comparator}. 429 * 430 * @implSpec This default implementation calls {@code 431 * thenComparing(comparing(keyExtractor, cmp))}. 432 * 433 * @param <T> The type of elements compared by the returned comparator. 434 * @param <U> The type of the sort key 435 * @param keyExtractor the function used to extract the sort key 436 * @param keyComparator the {@code Comparator} used to compare the sort key 437 * @return A lexicographic order comparator composed of this and then the 438 * key comparator. 439 * @throws NullPointerException if the argument is null. 440 * @see #comparing(Function, Comparator) 441 * @see #thenComparing(Comparator) 442 * @since 1.8 443 */ 444 default <U extends Comparable<? super U>> Comparator<T> thenComparing( 445 Function<? super T, ? extends U> keyExtractor, 446 Comparator<? super U> keyComparator) 447 { 448 return thenComparing(comparing(keyExtractor, keyComparator)); 449 } 450 451 /** 452 * Constructs a lexicographic order comparator with a function that 453 * extracts a {@code Comparable} sort key. 454 * 455 * @implSpec This default implementation calls {@code 456 * thenComparing(comparing(keyExtractor))}. 457 * 458 * @param <T> The type of elements compared by the returned comparator. 459 * @param <U> The type of the {@link Comparable} sort key 460 * @param keyExtractor the function used to extract the {@link 461 * Comparable} sort key 462 * @return A lexicographic order comparator composed of this and then the 463 * {@link Comparable} sort key. 464 * @throws NullPointerException if the argument is null. 465 * @see #comparing(Function) 466 * @see #thenComparing(Comparator) 467 * @since 1.8 468 */ 469 default <U extends Comparable<? super U>> Comparator<T> thenComparing( 470 Function<? super T, ? extends U> keyExtractor) 471 { 472 return thenComparing(comparing(keyExtractor)); 473 } 474 475 /** 476 * Constructs a lexicographic order comparator with a function that 477 * extracts a {@code int} sort key. 478 * 479 * @implSpec This default implementation calls {@code 480 * thenComparing(comparing(keyExtractor))}. 481 * 482 * @param <T> The type of elements compared by the returned comparator. 483 * @param keyExtractor the function used to extract the integer sort key 484 * @return A lexicographic order comparator composed of this and then the 485 * {@code int} sort key 486 * @throws NullPointerException if the argument is null. 487 * @see #comparing(ToIntFunction) 488 * @see #thenComparing(Comparator) 489 * @since 1.8 490 */ 491 default Comparator<T> thenComparing(ToIntFunction<? super T> keyExtractor) { 492 return thenComparing(comparing(keyExtractor)); 493 } 494 495 /** 496 * Constructs a lexicographic order comparator with a function that 497 * extracts a {@code long} sort key. 498 * 499 * @implSpec This default implementation calls {@code 500 * thenComparing(comparing(keyExtractor))}. 501 * 502 * @param <T> The type of elements compared by the returned comparator. 503 * @param keyExtractor the function used to extract the long sort key 504 * @return A lexicographic order comparator composed of this and then the 505 * {@code long} sort key 506 * @throws NullPointerException if the argument is null. 507 * @see #comparing(ToLongFunction) 508 * @see #thenComparing(Comparator) 509 * @since 1.8 510 */ 511 default Comparator<T> thenComparing(ToLongFunction<? super T> keyExtractor) { 512 return thenComparing(comparing(keyExtractor)); 513 } 514 515 /** 516 * Constructs a lexicographic order comparator with a function that 517 * extracts a {@code double} sort key. 518 * 519 * @implSpec This default implementation calls {@code 520 * thenComparing(comparing(keyExtractor))}. 521 * 522 * @param <T> The type of elements compared by the returned comparator. 523 * @param keyExtractor the function used to extract the double sort key 524 * @return A lexicographic order comparator composed of this and then the 525 * {@code double} sort key 526 * @throws NullPointerException if the argument is null. 527 * @see #comparing(ToDoubleFunction) 528 * @see #thenComparing(Comparator) 529 * @since 1.8 530 */ 531 default Comparator<T> thenComparing(ToDoubleFunction<? super T> keyExtractor) { 532 return thenComparing(comparing(keyExtractor)); 533 } 534 }