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