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