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