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