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