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