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