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