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