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