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