001/* 002 * Copyright (C) 2007 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.collect.CollectPreconditions.checkNonnegative; 021 022import com.google.common.annotations.GwtCompatible; 023import com.google.common.annotations.J2ktIncompatible; 024import com.google.common.annotations.VisibleForTesting; 025import com.google.common.base.Function; 026import java.util.ArrayList; 027import java.util.Arrays; 028import java.util.Collection; 029import java.util.Collections; 030import java.util.Comparator; 031import java.util.HashSet; 032import java.util.Iterator; 033import java.util.List; 034import java.util.Map.Entry; 035import java.util.NoSuchElementException; 036import java.util.SortedMap; 037import java.util.SortedSet; 038import java.util.TreeSet; 039import java.util.concurrent.ConcurrentMap; 040import java.util.concurrent.atomic.AtomicInteger; 041import javax.annotation.CheckForNull; 042import org.checkerframework.checker.nullness.qual.NonNull; 043import org.checkerframework.checker.nullness.qual.Nullable; 044 045/** 046 * A comparator, with additional methods to support common operations. This is an "enriched" version 047 * of {@code Comparator} for pre-Java-8 users, in the same sense that {@link FluentIterable} is an 048 * enriched {@link Iterable} for pre-Java-8 users. 049 * 050 * <h3>Three types of methods</h3> 051 * 052 * Like other fluent types, there are three types of methods present: methods for <i>acquiring</i>, 053 * <i>chaining</i>, and <i>using</i>. 054 * 055 * <h4>Acquiring</h4> 056 * 057 * <p>The common ways to get an instance of {@code Ordering} are: 058 * 059 * <ul> 060 * <li>Subclass it and implement {@link #compare} instead of implementing {@link Comparator} 061 * directly 062 * <li>Pass a <i>pre-existing</i> {@link Comparator} instance to {@link #from(Comparator)} 063 * <li>Use the natural ordering, {@link Ordering#natural} 064 * </ul> 065 * 066 * <h4>Chaining</h4> 067 * 068 * <p>Then you can use the <i>chaining</i> methods to get an altered version of that {@code 069 * Ordering}, including: 070 * 071 * <ul> 072 * <li>{@link #reverse} 073 * <li>{@link #compound(Comparator)} 074 * <li>{@link #onResultOf(Function)} 075 * <li>{@link #nullsFirst} / {@link #nullsLast} 076 * </ul> 077 * 078 * <h4>Using</h4> 079 * 080 * <p>Finally, use the resulting {@code Ordering} anywhere a {@link Comparator} is required, or use 081 * any of its special operations, such as: 082 * 083 * <ul> 084 * <li>{@link #immutableSortedCopy} 085 * <li>{@link #isOrdered} / {@link #isStrictlyOrdered} 086 * <li>{@link #min} / {@link #max} 087 * </ul> 088 * 089 * <h3>Understanding complex orderings</h3> 090 * 091 * <p>Complex chained orderings like the following example can be challenging to understand. 092 * 093 * <pre>{@code 094 * Ordering<Foo> ordering = 095 * Ordering.natural() 096 * .nullsFirst() 097 * .onResultOf(getBarFunction) 098 * .nullsLast(); 099 * }</pre> 100 * 101 * Note that each chaining method returns a new ordering instance which is backed by the previous 102 * instance, but has the chance to act on values <i>before</i> handing off to that backing instance. 103 * As a result, it usually helps to read chained ordering expressions <i>backwards</i>. For example, 104 * when {@code compare} is called on the above ordering: 105 * 106 * <ol> 107 * <li>First, if only one {@code Foo} is null, that null value is treated as <i>greater</i> 108 * <li>Next, non-null {@code Foo} values are passed to {@code getBarFunction} (we will be 109 * comparing {@code Bar} values from now on) 110 * <li>Next, if only one {@code Bar} is null, that null value is treated as <i>lesser</i> 111 * <li>Finally, natural ordering is used (i.e. the result of {@code Bar.compareTo(Bar)} is 112 * returned) 113 * </ol> 114 * 115 * <p>Alas, {@link #reverse} is a little different. As you read backwards through a chain and 116 * encounter a call to {@code reverse}, continue working backwards until a result is determined, and 117 * then reverse that result. 118 * 119 * <h3>Additional notes</h3> 120 * 121 * <p>Except as noted, the orderings returned by the factory methods of this class are serializable 122 * if and only if the provided instances that back them are. For example, if {@code ordering} and 123 * {@code function} can themselves be serialized, then {@code ordering.onResultOf(function)} can as 124 * well. 125 * 126 * <h3>Java 8+ users</h3> 127 * 128 * <p>If you are using Java 8+, this class is now obsolete. Most of its functionality is now 129 * provided by {@link java.util.stream.Stream Stream} and by {@link Comparator} itself, and the rest 130 * can now be found as static methods in our new {@link Comparators} class. See each method below 131 * for further instructions. Whenever possible, you should change any references of type {@code 132 * Ordering} to be of type {@code Comparator} instead. However, at this time we have no plan to 133 * <i>deprecate</i> this class. 134 * 135 * <p>Many replacements involve adopting {@code Stream}, and these changes can sometimes make your 136 * code verbose. Whenever following this advice, you should check whether {@code Stream} could be 137 * adopted more comprehensively in your code; the end result may be quite a bit simpler. 138 * 139 * <h3>See also</h3> 140 * 141 * <p>See the Guava User Guide article on <a href= 142 * "https://github.com/google/guava/wiki/OrderingExplained">{@code Ordering}</a>. 143 * 144 * @author Jesse Wilson 145 * @author Kevin Bourrillion 146 * @since 2.0 147 */ 148@GwtCompatible 149@ElementTypesAreNonnullByDefault 150public abstract class Ordering<T extends @Nullable Object> implements Comparator<T> { 151 // Natural order 152 153 /** 154 * Returns a serializable ordering that uses the natural order of the values. The ordering throws 155 * a {@link NullPointerException} when passed a null parameter. 156 * 157 * <p>The type specification is {@code <C extends Comparable>}, instead of the technically correct 158 * {@code <C extends Comparable<? super C>>}, to support legacy types from before Java 5. 159 * 160 * <p><b>Java 8+ users:</b> use {@link Comparator#naturalOrder} instead. 161 */ 162 @GwtCompatible(serializable = true) 163 @SuppressWarnings({"unchecked", "rawtypes"}) 164 // TODO(kevinb): right way to explain this?? 165 // plus https://github.com/google/guava/issues/989 166 public static <C extends Comparable> Ordering<C> natural() { 167 return (Ordering<C>) NaturalOrdering.INSTANCE; 168 } 169 170 // Static factories 171 172 /** 173 * Returns an ordering based on an <i>existing</i> comparator instance. Note that it is 174 * unnecessary to create a <i>new</i> anonymous inner class implementing {@code Comparator} just 175 * to pass it in here. Instead, simply subclass {@code Ordering} and implement its {@code compare} 176 * method directly. 177 * 178 * <p>The returned object is serializable if {@code comparator} is serializable. 179 * 180 * <p><b>Java 8+ users:</b> this class is now obsolete as explained in the class documentation, so 181 * there is no need to use this method. 182 * 183 * @param comparator the comparator that defines the order 184 * @return comparator itself if it is already an {@code Ordering}; otherwise an ordering that 185 * wraps that comparator 186 */ 187 @GwtCompatible(serializable = true) 188 public static <T extends @Nullable Object> Ordering<T> from(Comparator<T> comparator) { 189 return (comparator instanceof Ordering) 190 ? (Ordering<T>) comparator 191 : new ComparatorOrdering<T>(comparator); 192 } 193 194 /** 195 * Simply returns its argument. 196 * 197 * @deprecated no need to use this 198 */ 199 @GwtCompatible(serializable = true) 200 @Deprecated 201 public static <T extends @Nullable Object> Ordering<T> from(Ordering<T> ordering) { 202 return checkNotNull(ordering); 203 } 204 205 /** 206 * Returns an ordering that compares objects according to the order in which they appear in the 207 * given list. Only objects present in the list (according to {@link Object#equals}) may be 208 * compared. This comparator imposes a "partial ordering" over the type {@code T}. Subsequent 209 * changes to the {@code valuesInOrder} list will have no effect on the returned comparator. Null 210 * values in the list are not supported. 211 * 212 * <p>The returned comparator throws a {@link ClassCastException} when it receives an input 213 * parameter that isn't among the provided values. 214 * 215 * <p>The generated comparator is serializable if all the provided values are serializable. 216 * 217 * @param valuesInOrder the values that the returned comparator will be able to compare, in the 218 * order the comparator should induce 219 * @return the comparator described above 220 * @throws NullPointerException if any of the provided values is null 221 * @throws IllegalArgumentException if {@code valuesInOrder} contains any duplicate values 222 * (according to {@link Object#equals}) 223 */ 224 // TODO(kevinb): provide replacement 225 @GwtCompatible(serializable = true) 226 public static <T> Ordering<T> explicit(List<T> valuesInOrder) { 227 return new ExplicitOrdering<T>(valuesInOrder); 228 } 229 230 /** 231 * Returns an ordering that compares objects according to the order in which they are given to 232 * this method. Only objects present in the argument list (according to {@link Object#equals}) may 233 * be compared. This comparator imposes a "partial ordering" over the type {@code T}. Null values 234 * in the argument list are not supported. 235 * 236 * <p>The returned comparator throws a {@link ClassCastException} when it receives an input 237 * parameter that isn't among the provided values. 238 * 239 * <p>The generated comparator is serializable if all the provided values are serializable. 240 * 241 * @param leastValue the value which the returned comparator should consider the "least" of all 242 * values 243 * @param remainingValuesInOrder the rest of the values that the returned comparator will be able 244 * to compare, in the order the comparator should follow 245 * @return the comparator described above 246 * @throws NullPointerException if any of the provided values is null 247 * @throws IllegalArgumentException if any duplicate values (according to {@link 248 * Object#equals(Object)}) are present among the method arguments 249 */ 250 // TODO(kevinb): provide replacement 251 @GwtCompatible(serializable = true) 252 public static <T> Ordering<T> explicit(T leastValue, T... remainingValuesInOrder) { 253 return explicit(Lists.asList(leastValue, remainingValuesInOrder)); 254 } 255 256 // Ordering<Object> singletons 257 258 /** 259 * Returns an ordering which treats all values as equal, indicating "no ordering." Passing this 260 * ordering to any <i>stable</i> sort algorithm results in no change to the order of elements. 261 * Note especially that {@link #sortedCopy} and {@link #immutableSortedCopy} are stable, and in 262 * the returned instance these are implemented by simply copying the source list. 263 * 264 * <p>Example: 265 * 266 * <pre>{@code 267 * Ordering.allEqual().nullsLast().sortedCopy( 268 * asList(t, null, e, s, null, t, null)) 269 * }</pre> 270 * 271 * <p>Assuming {@code t}, {@code e} and {@code s} are non-null, this returns {@code [t, e, s, t, 272 * null, null, null]} regardless of the true comparison order of those three values (which might 273 * not even implement {@link Comparable} at all). 274 * 275 * <p><b>Warning:</b> by definition, this comparator is not <i>consistent with equals</i> (as 276 * defined {@linkplain Comparator here}). Avoid its use in APIs, such as {@link 277 * TreeSet#TreeSet(Comparator)}, where such consistency is expected. 278 * 279 * <p>The returned comparator is serializable. 280 * 281 * <p><b>Java 8+ users:</b> Use the lambda expression {@code (a, b) -> 0} instead (in certain 282 * cases you may need to cast that to {@code Comparator<YourType>}). 283 * 284 * @since 13.0 285 */ 286 @GwtCompatible(serializable = true) 287 public static Ordering<@Nullable Object> allEqual() { 288 return AllEqualOrdering.INSTANCE; 289 } 290 291 /** 292 * Returns an ordering that compares objects by the natural ordering of their string 293 * representations as returned by {@code toString()}. It does not support null values. 294 * 295 * <p>The comparator is serializable. 296 * 297 * <p><b>Java 8+ users:</b> Use {@code Comparator.comparing(Object::toString)} instead. 298 */ 299 @GwtCompatible(serializable = true) 300 public static Ordering<Object> usingToString() { 301 return UsingToStringOrdering.INSTANCE; 302 } 303 304 /** 305 * Returns an arbitrary ordering over all objects, for which {@code compare(a, b) == 0} implies 306 * {@code a == b} (identity equality). There is no meaning whatsoever to the order imposed, but it 307 * is constant for the life of the VM. 308 * 309 * <p>Because the ordering is identity-based, it is not "consistent with {@link 310 * Object#equals(Object)}" as defined by {@link Comparator}. Use caution when building a {@link 311 * SortedSet} or {@link SortedMap} from it, as the resulting collection will not behave exactly 312 * according to spec. 313 * 314 * <p>This ordering is not serializable, as its implementation relies on {@link 315 * System#identityHashCode(Object)}, so its behavior cannot be preserved across serialization. 316 * 317 * @since 2.0 318 */ 319 // TODO(kevinb): copy to Comparators, etc. 320 @J2ktIncompatible // MapMaker 321 public static Ordering<@Nullable Object> arbitrary() { 322 return ArbitraryOrderingHolder.ARBITRARY_ORDERING; 323 } 324 325 @J2ktIncompatible // MapMaker 326 private static class ArbitraryOrderingHolder { 327 static final Ordering<@Nullable Object> ARBITRARY_ORDERING = new ArbitraryOrdering(); 328 } 329 330 @J2ktIncompatible // MapMaker 331 @VisibleForTesting 332 static class ArbitraryOrdering extends Ordering<@Nullable Object> { 333 334 private final AtomicInteger counter = new AtomicInteger(0); 335 private final ConcurrentMap<Object, Integer> uids = 336 Platform.tryWeakKeys(new MapMaker()).makeMap(); 337 338 private Integer getUid(Object obj) { 339 Integer uid = uids.get(obj); 340 if (uid == null) { 341 // One or more integer values could be skipped in the event of a race 342 // to generate a UID for the same object from multiple threads, but 343 // that shouldn't be a problem. 344 uid = counter.getAndIncrement(); 345 Integer alreadySet = uids.putIfAbsent(obj, uid); 346 if (alreadySet != null) { 347 uid = alreadySet; 348 } 349 } 350 return uid; 351 } 352 353 @Override 354 public int compare(@CheckForNull Object left, @CheckForNull Object right) { 355 if (left == right) { 356 return 0; 357 } else if (left == null) { 358 return -1; 359 } else if (right == null) { 360 return 1; 361 } 362 int leftCode = identityHashCode(left); 363 int rightCode = identityHashCode(right); 364 if (leftCode != rightCode) { 365 return leftCode < rightCode ? -1 : 1; 366 } 367 368 // identityHashCode collision (rare, but not as rare as you'd think) 369 int result = getUid(left).compareTo(getUid(right)); 370 if (result == 0) { 371 throw new AssertionError(); // extremely, extremely unlikely. 372 } 373 return result; 374 } 375 376 @Override 377 public String toString() { 378 return "Ordering.arbitrary()"; 379 } 380 381 /* 382 * We need to be able to mock identityHashCode() calls for tests, because it 383 * can take 1-10 seconds to find colliding objects. Mocking frameworks that 384 * can do magic to mock static method calls still can't do so for a system 385 * class, so we need the indirection. In production, Hotspot should still 386 * recognize that the call is 1-morphic and should still be willing to 387 * inline it if necessary. 388 */ 389 int identityHashCode(Object object) { 390 return System.identityHashCode(object); 391 } 392 } 393 394 // Constructor 395 396 /** 397 * Constructs a new instance of this class (only invokable by the subclass constructor, typically 398 * implicit). 399 */ 400 protected Ordering() {} 401 402 // Instance-based factories (and any static equivalents) 403 404 /** 405 * Returns the reverse of this ordering; the {@code Ordering} equivalent to {@link 406 * Collections#reverseOrder(Comparator)}. 407 * 408 * <p><b>Java 8+ users:</b> Use {@code thisComparator.reversed()} instead. 409 */ 410 // type parameter <S> lets us avoid the extra <String> in statements like: 411 // Ordering<String> o = Ordering.<String>natural().reverse(); 412 @GwtCompatible(serializable = true) 413 public <S extends T> Ordering<S> reverse() { 414 return new ReverseOrdering<S>(this); 415 } 416 417 /** 418 * Returns an ordering that treats {@code null} as less than all other values and uses {@code 419 * this} to compare non-null values. 420 * 421 * <p>The returned object is serializable if this object is serializable. 422 * 423 * <p><b>Java 8+ users:</b> Use {@code Comparator.nullsFirst(thisComparator)} instead. 424 */ 425 // type parameter <S> lets us avoid the extra <String> in statements like: 426 // Ordering<String> o = Ordering.<String>natural().nullsFirst(); 427 @GwtCompatible(serializable = true) 428 public <S extends T> Ordering<@Nullable S> nullsFirst() { 429 return new NullsFirstOrdering<S>(this); 430 } 431 432 /** 433 * Returns an ordering that treats {@code null} as greater than all other values and uses this 434 * ordering to compare non-null values. 435 * 436 * <p>The returned object is serializable if this object is serializable. 437 * 438 * <p><b>Java 8+ users:</b> Use {@code Comparator.nullsLast(thisComparator)} instead. 439 */ 440 // type parameter <S> lets us avoid the extra <String> in statements like: 441 // Ordering<String> o = Ordering.<String>natural().nullsLast(); 442 @GwtCompatible(serializable = true) 443 public <S extends T> Ordering<@Nullable S> nullsLast() { 444 return new NullsLastOrdering<S>(this); 445 } 446 447 /** 448 * Returns a new ordering on {@code F} which orders elements by first applying a function to them, 449 * then comparing those results using {@code this}. For example, to compare objects by their 450 * string forms, in a case-insensitive manner, use: 451 * 452 * <pre>{@code 453 * Ordering.from(String.CASE_INSENSITIVE_ORDER) 454 * .onResultOf(Functions.toStringFunction()) 455 * }</pre> 456 * 457 * <p><b>Java 8+ users:</b> Use {@code Comparator.comparing(function, thisComparator)} instead 458 * (you can omit the comparator if it is the natural order). 459 */ 460 @GwtCompatible(serializable = true) 461 public <F extends @Nullable Object> Ordering<F> onResultOf(Function<F, ? extends T> function) { 462 return new ByFunctionOrdering<>(function, this); 463 } 464 465 <T2 extends T> Ordering<Entry<T2, ?>> onKeys() { 466 return onResultOf(Maps.<T2>keyFunction()); 467 } 468 469 /** 470 * Returns an ordering which first uses the ordering {@code this}, but which in the event of a 471 * "tie", then delegates to {@code secondaryComparator}. For example, to sort a bug list first by 472 * status and second by priority, you might use {@code byStatus.compound(byPriority)}. For a 473 * compound ordering with three or more components, simply chain multiple calls to this method. 474 * 475 * <p>An ordering produced by this method, or a chain of calls to this method, is equivalent to 476 * one created using {@link Ordering#compound(Iterable)} on the same component comparators. 477 * 478 * <p>The returned object is serializable if this object and {@code secondaryComparator} are both 479 * serializable. 480 * 481 * <p><b>Java 8+ users:</b> Use {@code thisComparator.thenComparing(secondaryComparator)} instead. 482 * Depending on what {@code secondaryComparator} is, one of the other overloads of {@code 483 * thenComparing} may be even more useful. 484 */ 485 @GwtCompatible(serializable = true) 486 public <U extends T> Ordering<U> compound(Comparator<? super U> secondaryComparator) { 487 return new CompoundOrdering<U>(this, checkNotNull(secondaryComparator)); 488 } 489 490 /** 491 * Returns an ordering which tries each given comparator in order until a non-zero result is 492 * found, returning that result, and returning zero only if all comparators return zero. The 493 * returned ordering is based on the state of the {@code comparators} iterable at the time it was 494 * provided to this method. 495 * 496 * <p>The returned ordering is equivalent to that produced using {@code 497 * Ordering.from(comp1).compound(comp2).compound(comp3) . . .}. 498 * 499 * <p>The returned object is serializable if each of the {@code comparators} is serializable. 500 * 501 * <p><b>Warning:</b> Supplying an argument with undefined iteration order, such as a {@link 502 * HashSet}, will produce non-deterministic results. 503 * 504 * <p><b>Java 8+ users:</b> Use a chain of calls to {@link Comparator#thenComparing(Comparator)}, 505 * or {@code comparatorCollection.stream().reduce(Comparator::thenComparing).get()} (if the 506 * collection might be empty, also provide a default comparator as the {@code identity} parameter 507 * to {@code reduce}). 508 * 509 * @param comparators the comparators to try in order 510 */ 511 @GwtCompatible(serializable = true) 512 public static <T extends @Nullable Object> Ordering<T> compound( 513 Iterable<? extends Comparator<? super T>> comparators) { 514 return new CompoundOrdering<T>(comparators); 515 } 516 517 /** 518 * Returns a new ordering which sorts iterables by comparing corresponding elements pairwise until 519 * a nonzero result is found; imposes "dictionary order". If the end of one iterable is reached, 520 * but not the other, the shorter iterable is considered to be less than the longer one. For 521 * example, a lexicographical natural ordering over integers considers {@code [] < [1] < [1, 1] < 522 * [1, 2] < [2]}. 523 * 524 * <p>Note that {@code ordering.lexicographical().reverse()} is not equivalent to {@code 525 * ordering.reverse().lexicographical()} (consider how each would order {@code [1]} and {@code [1, 526 * 1]}). 527 * 528 * <p><b>Java 8+ users:</b> Use {@link Comparators#lexicographical(Comparator)} instead. 529 * 530 * @since 2.0 531 */ 532 @GwtCompatible(serializable = true) 533 // type parameter <S> lets us avoid the extra <String> in statements like: 534 // Ordering<Iterable<String>> o = 535 // Ordering.<String>natural().lexicographical(); 536 public <S extends T> Ordering<Iterable<S>> lexicographical() { 537 /* 538 * Note that technically the returned ordering should be capable of 539 * handling not just {@code Iterable<S>} instances, but also any {@code 540 * Iterable<? extends S>}. However, the need for this comes up so rarely 541 * that it doesn't justify making everyone else deal with the very ugly 542 * wildcard. 543 */ 544 return new LexicographicalOrdering<S>(this); 545 } 546 547 // Regular instance methods 548 549 @Override 550 public abstract int compare(@ParametricNullness T left, @ParametricNullness T right); 551 552 /** 553 * Returns the least of the specified values according to this ordering. If there are multiple 554 * least values, the first of those is returned. The iterator will be left exhausted: its {@code 555 * hasNext()} method will return {@code false}. 556 * 557 * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterator).min(thisComparator).get()} instead 558 * (but note that it does not guarantee which tied minimum element is returned). 559 * 560 * @param iterator the iterator whose minimum element is to be determined 561 * @throws NoSuchElementException if {@code iterator} is empty 562 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this 563 * ordering. 564 * @since 11.0 565 */ 566 @ParametricNullness 567 public <E extends T> E min(Iterator<E> iterator) { 568 // let this throw NoSuchElementException as necessary 569 E minSoFar = iterator.next(); 570 571 while (iterator.hasNext()) { 572 minSoFar = min(minSoFar, iterator.next()); 573 } 574 575 return minSoFar; 576 } 577 578 /** 579 * Returns the least of the specified values according to this ordering. If there are multiple 580 * least values, the first of those is returned. 581 * 582 * <p><b>Java 8+ users:</b> If {@code iterable} is a {@link Collection}, use {@code 583 * Collections.min(collection, thisComparator)} instead. Otherwise, use {@code 584 * Streams.stream(iterable).min(thisComparator).get()} instead. Note that these alternatives do 585 * not guarantee which tied minimum element is returned. 586 * 587 * @param iterable the iterable whose minimum element is to be determined 588 * @throws NoSuchElementException if {@code iterable} is empty 589 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this 590 * ordering. 591 */ 592 @ParametricNullness 593 public <E extends T> E min(Iterable<E> iterable) { 594 return min(iterable.iterator()); 595 } 596 597 /** 598 * Returns the lesser of the two values according to this ordering. If the values compare as 0, 599 * the first is returned. 600 * 601 * <p><b>Implementation note:</b> this method is invoked by the default implementations of the 602 * other {@code min} overloads, so overriding it will affect their behavior. 603 * 604 * <p><b>Note:</b> Consider using {@code Comparators.min(a, b, thisComparator)} instead. If {@code 605 * thisComparator} is {@link Ordering#natural}, then use {@code Comparators.min(a, b)}. 606 * 607 * @param a value to compare, returned if less than or equal to b. 608 * @param b value to compare. 609 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this 610 * ordering. 611 */ 612 @ParametricNullness 613 public <E extends T> E min(@ParametricNullness E a, @ParametricNullness E b) { 614 return (compare(a, b) <= 0) ? a : b; 615 } 616 617 /** 618 * Returns the least of the specified values according to this ordering. If there are multiple 619 * least values, the first of those is returned. 620 * 621 * <p><b>Java 8+ users:</b> Use {@code Collections.min(Arrays.asList(a, b, c...), thisComparator)} 622 * instead (but note that it does not guarantee which tied minimum element is returned). 623 * 624 * @param a value to compare, returned if less than or equal to the rest. 625 * @param b value to compare 626 * @param c value to compare 627 * @param rest values to compare 628 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this 629 * ordering. 630 */ 631 @ParametricNullness 632 public <E extends T> E min( 633 @ParametricNullness E a, @ParametricNullness E b, @ParametricNullness E c, E... rest) { 634 E minSoFar = min(min(a, b), c); 635 636 for (E r : rest) { 637 minSoFar = min(minSoFar, r); 638 } 639 640 return minSoFar; 641 } 642 643 /** 644 * Returns the greatest of the specified values according to this ordering. If there are multiple 645 * greatest values, the first of those is returned. The iterator will be left exhausted: its 646 * {@code hasNext()} method will return {@code false}. 647 * 648 * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterator).max(thisComparator).get()} instead 649 * (but note that it does not guarantee which tied maximum element is returned). 650 * 651 * @param iterator the iterator whose maximum element is to be determined 652 * @throws NoSuchElementException if {@code iterator} is empty 653 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this 654 * ordering. 655 * @since 11.0 656 */ 657 @ParametricNullness 658 public <E extends T> E max(Iterator<E> iterator) { 659 // let this throw NoSuchElementException as necessary 660 E maxSoFar = iterator.next(); 661 662 while (iterator.hasNext()) { 663 maxSoFar = max(maxSoFar, iterator.next()); 664 } 665 666 return maxSoFar; 667 } 668 669 /** 670 * Returns the greatest of the specified values according to this ordering. If there are multiple 671 * greatest values, the first of those is returned. 672 * 673 * <p><b>Java 8+ users:</b> If {@code iterable} is a {@link Collection}, use {@code 674 * Collections.max(collection, thisComparator)} instead. Otherwise, use {@code 675 * Streams.stream(iterable).max(thisComparator).get()} instead. Note that these alternatives do 676 * not guarantee which tied maximum element is returned. 677 * 678 * @param iterable the iterable whose maximum element is to be determined 679 * @throws NoSuchElementException if {@code iterable} is empty 680 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this 681 * ordering. 682 */ 683 @ParametricNullness 684 public <E extends T> E max(Iterable<E> iterable) { 685 return max(iterable.iterator()); 686 } 687 688 /** 689 * Returns the greater of the two values according to this ordering. If the values compare as 0, 690 * the first is returned. 691 * 692 * <p><b>Implementation note:</b> this method is invoked by the default implementations of the 693 * other {@code max} overloads, so overriding it will affect their behavior. 694 * 695 * <p><b>Note:</b> Consider using {@code Comparators.max(a, b, thisComparator)} instead. If {@code 696 * thisComparator} is {@link Ordering#natural}, then use {@code Comparators.max(a, b)}. 697 * 698 * @param a value to compare, returned if greater than or equal to b. 699 * @param b value to compare. 700 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this 701 * ordering. 702 */ 703 @ParametricNullness 704 public <E extends T> E max(@ParametricNullness E a, @ParametricNullness E b) { 705 return (compare(a, b) >= 0) ? a : b; 706 } 707 708 /** 709 * Returns the greatest of the specified values according to this ordering. If there are multiple 710 * greatest values, the first of those is returned. 711 * 712 * <p><b>Java 8+ users:</b> Use {@code Collections.max(Arrays.asList(a, b, c...), thisComparator)} 713 * instead (but note that it does not guarantee which tied maximum element is returned). 714 * 715 * @param a value to compare, returned if greater than or equal to the rest. 716 * @param b value to compare 717 * @param c value to compare 718 * @param rest values to compare 719 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> under this 720 * ordering. 721 */ 722 @ParametricNullness 723 public <E extends T> E max( 724 @ParametricNullness E a, @ParametricNullness E b, @ParametricNullness E c, E... rest) { 725 E maxSoFar = max(max(a, b), c); 726 727 for (E r : rest) { 728 maxSoFar = max(maxSoFar, r); 729 } 730 731 return maxSoFar; 732 } 733 734 /** 735 * Returns the {@code k} least elements of the given iterable according to this ordering, in order 736 * from least to greatest. If there are fewer than {@code k} elements present, all will be 737 * included. 738 * 739 * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple 740 * elements are equivalent, it is undefined which will come first. 741 * 742 * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterable).collect(Comparators.least(k, 743 * thisComparator))} instead. 744 * 745 * @return an immutable {@code RandomAccess} list of the {@code k} least elements in ascending 746 * order 747 * @throws IllegalArgumentException if {@code k} is negative 748 * @since 8.0 749 */ 750 @SuppressWarnings("nullness") // TODO: b/316358623 - Remove after checker fix. 751 public <E extends T> List<E> leastOf(Iterable<E> iterable, int k) { 752 if (iterable instanceof Collection) { 753 Collection<E> collection = (Collection<E>) iterable; 754 if (collection.size() <= 2L * k) { 755 // In this case, just dumping the collection to an array and sorting is 756 // faster than using the implementation for Iterator, which is 757 // specialized for k much smaller than n. 758 759 @SuppressWarnings("unchecked") // c only contains E's and doesn't escape 760 E[] array = (E[]) collection.toArray(); 761 Arrays.sort(array, this); 762 if (array.length > k) { 763 array = Arrays.copyOf(array, k); 764 } 765 return Collections.unmodifiableList(Arrays.asList(array)); 766 } 767 } 768 return leastOf(iterable.iterator(), k); 769 } 770 771 /** 772 * Returns the {@code k} least elements from the given iterator according to this ordering, in 773 * order from least to greatest. If there are fewer than {@code k} elements present, all will be 774 * included. 775 * 776 * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple 777 * elements are equivalent, it is undefined which will come first. 778 * 779 * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterator).collect(Comparators.least(k, 780 * thisComparator))} instead. 781 * 782 * @return an immutable {@code RandomAccess} list of the {@code k} least elements in ascending 783 * order 784 * @throws IllegalArgumentException if {@code k} is negative 785 * @since 14.0 786 */ 787 public <E extends T> List<E> leastOf(Iterator<E> iterator, int k) { 788 checkNotNull(iterator); 789 checkNonnegative(k, "k"); 790 791 if (k == 0 || !iterator.hasNext()) { 792 return Collections.emptyList(); 793 } else if (k >= Integer.MAX_VALUE / 2) { 794 // k is really large; just do a straightforward sorted-copy-and-sublist 795 ArrayList<E> list = Lists.newArrayList(iterator); 796 Collections.sort(list, this); 797 if (list.size() > k) { 798 list.subList(k, list.size()).clear(); 799 } 800 list.trimToSize(); 801 return Collections.unmodifiableList(list); 802 } else { 803 TopKSelector<E> selector = TopKSelector.least(k, this); 804 selector.offerAll(iterator); 805 return selector.topK(); 806 } 807 } 808 809 /** 810 * Returns the {@code k} greatest elements of the given iterable according to this ordering, in 811 * order from greatest to least. If there are fewer than {@code k} elements present, all will be 812 * included. 813 * 814 * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple 815 * elements are equivalent, it is undefined which will come first. 816 * 817 * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterable).collect(Comparators.greatest(k, 818 * thisComparator))} instead. 819 * 820 * @return an immutable {@code RandomAccess} list of the {@code k} greatest elements in 821 * <i>descending order</i> 822 * @throws IllegalArgumentException if {@code k} is negative 823 * @since 8.0 824 */ 825 public <E extends T> List<E> greatestOf(Iterable<E> iterable, int k) { 826 // TODO(kevinb): see if delegation is hurting performance noticeably 827 // TODO(kevinb): if we change this implementation, add full unit tests. 828 return this.<E>reverse().leastOf(iterable, k); 829 } 830 831 /** 832 * Returns the {@code k} greatest elements from the given iterator according to this ordering, in 833 * order from greatest to least. If there are fewer than {@code k} elements present, all will be 834 * included. 835 * 836 * <p>The implementation does not necessarily use a <i>stable</i> sorting algorithm; when multiple 837 * elements are equivalent, it is undefined which will come first. 838 * 839 * <p><b>Java 8+ users:</b> Use {@code Streams.stream(iterator).collect(Comparators.greatest(k, 840 * thisComparator))} instead. 841 * 842 * @return an immutable {@code RandomAccess} list of the {@code k} greatest elements in 843 * <i>descending order</i> 844 * @throws IllegalArgumentException if {@code k} is negative 845 * @since 14.0 846 */ 847 public <E extends T> List<E> greatestOf(Iterator<E> iterator, int k) { 848 return this.<E>reverse().leastOf(iterator, k); 849 } 850 851 /** 852 * Returns a <b>mutable</b> list containing {@code elements} sorted by this ordering; use this 853 * only when the resulting list may need further modification, or may contain {@code null}. The 854 * input is not modified. The returned list is serializable and has random access. 855 * 856 * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard elements that are 857 * duplicates according to the comparator. The sort performed is <i>stable</i>, meaning that such 858 * elements will appear in the returned list in the same order they appeared in {@code elements}. 859 * 860 * <p><b>Performance note:</b> According to our 861 * benchmarking 862 * on Open JDK 7, {@link #immutableSortedCopy} generally performs better (in both time and space) 863 * than this method, and this method in turn generally performs better than copying the list and 864 * calling {@link Collections#sort(List)}. 865 */ 866 // TODO(kevinb): rerun benchmarks including new options 867 @SuppressWarnings("nullness") // TODO: b/316358623 - Remove after checker fix. 868 public <E extends T> List<E> sortedCopy(Iterable<E> elements) { 869 @SuppressWarnings("unchecked") // does not escape, and contains only E's 870 E[] array = (E[]) Iterables.toArray(elements); 871 Arrays.sort(array, this); 872 return Lists.newArrayList(Arrays.asList(array)); 873 } 874 875 /** 876 * Returns an <b>immutable</b> list containing {@code elements} sorted by this ordering. The input 877 * is not modified. 878 * 879 * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard elements that are 880 * duplicates according to the comparator. The sort performed is <i>stable</i>, meaning that such 881 * elements will appear in the returned list in the same order they appeared in {@code elements}. 882 * 883 * <p><b>Performance note:</b> According to our 884 * benchmarking 885 * on Open JDK 7, this method is the most efficient way to make a sorted copy of a collection. 886 * 887 * @throws NullPointerException if any element of {@code elements} is {@code null} 888 * @since 3.0 889 */ 890 // TODO(kevinb): rerun benchmarks including new options 891 public <E extends @NonNull T> ImmutableList<E> immutableSortedCopy(Iterable<E> elements) { 892 return ImmutableList.sortedCopyOf(this, elements); 893 } 894 895 /** 896 * Returns {@code true} if each element in {@code iterable} after the first is greater than or 897 * equal to the element that preceded it, according to this ordering. Note that this is always 898 * true when the iterable has fewer than two elements. 899 * 900 * <p><b>Java 8+ users:</b> Use the equivalent {@link Comparators#isInOrder(Iterable, Comparator)} 901 * instead, since the rest of {@code Ordering} is mostly obsolete (as explained in the class 902 * documentation). 903 */ 904 public boolean isOrdered(Iterable<? extends T> iterable) { 905 Iterator<? extends T> it = iterable.iterator(); 906 if (it.hasNext()) { 907 T prev = it.next(); 908 while (it.hasNext()) { 909 T next = it.next(); 910 if (compare(prev, next) > 0) { 911 return false; 912 } 913 prev = next; 914 } 915 } 916 return true; 917 } 918 919 /** 920 * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i> 921 * greater than the element that preceded it, according to this ordering. Note that this is always 922 * true when the iterable has fewer than two elements. 923 * 924 * <p><b>Java 8+ users:</b> Use the equivalent {@link Comparators#isInStrictOrder(Iterable, 925 * Comparator)} instead, since the rest of {@code Ordering} is mostly obsolete (as explained in 926 * the class documentation). 927 */ 928 public boolean isStrictlyOrdered(Iterable<? extends T> iterable) { 929 Iterator<? extends T> it = iterable.iterator(); 930 if (it.hasNext()) { 931 T prev = it.next(); 932 while (it.hasNext()) { 933 T next = it.next(); 934 if (compare(prev, next) >= 0) { 935 return false; 936 } 937 prev = next; 938 } 939 } 940 return true; 941 } 942 943 /** 944 * {@link Collections#binarySearch(List, Object, Comparator) Searches} {@code sortedList} for 945 * {@code key} using the binary search algorithm. The list must be sorted using this ordering. 946 * 947 * @param sortedList the list to be searched 948 * @param key the key to be searched for 949 * @deprecated Use {@link Collections#binarySearch(List, Object, Comparator)} directly. 950 */ 951 @Deprecated 952 public int binarySearch( 953 List<? extends T> sortedList, @ParametricNullness T key) { 954 return Collections.binarySearch(sortedList, key, this); 955 } 956 957 /** 958 * Exception thrown by a {@link Ordering#explicit(List)} or {@link Ordering#explicit(Object, 959 * Object[])} comparator when comparing a value outside the set of values it can compare. 960 * Extending {@link ClassCastException} may seem odd, but it is required. 961 */ 962 @VisibleForTesting 963 static class IncomparableValueException extends ClassCastException { 964 final Object value; 965 966 IncomparableValueException(Object value) { 967 super("Cannot compare value: " + value); 968 this.value = value; 969 } 970 971 private static final long serialVersionUID = 0; 972 } 973 974 // Never make these public 975 static final int LEFT_IS_GREATER = 1; 976 static final int RIGHT_IS_GREATER = -1; 977}