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