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