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    
017    package com.google.common.collect;
018    
019    import static com.google.common.base.Preconditions.checkArgument;
020    import static com.google.common.base.Preconditions.checkNotNull;
021    
022    import com.google.common.annotations.Beta;
023    import com.google.common.annotations.GwtCompatible;
024    import com.google.common.annotations.VisibleForTesting;
025    import com.google.common.base.Function;
026    
027    import java.util.Arrays;
028    import java.util.Collections;
029    import java.util.Comparator;
030    import java.util.HashSet;
031    import java.util.Iterator;
032    import java.util.List;
033    import java.util.Map;
034    import java.util.NoSuchElementException;
035    import java.util.SortedMap;
036    import java.util.SortedSet;
037    import java.util.concurrent.atomic.AtomicInteger;
038    
039    import 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.0 (imported from Google Collections Library)
065     */
066    @GwtCompatible
067    public 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): 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.0
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        @SuppressWarnings("deprecation") // TODO(kevinb): ?
210        private Map<Object, Integer> uids =
211            Platform.tryWeakKeys(new MapMaker()).makeComputingMap(
212                new Function<Object, Integer>() {
213                  final AtomicInteger counter = new AtomicInteger(0);
214                  @Override
215                  public Integer apply(Object from) {
216                    return counter.getAndIncrement();
217                  }
218                });
219    
220        @Override public int compare(Object left, Object right) {
221          if (left == right) {
222            return 0;
223          }
224          int leftCode = identityHashCode(left);
225          int rightCode = identityHashCode(right);
226          if (leftCode != rightCode) {
227            return leftCode < rightCode ? -1 : 1;
228          }
229    
230          // identityHashCode collision (rare, but not as rare as you'd think)
231          int result = uids.get(left).compareTo(uids.get(right));
232          if (result == 0) {
233            throw new AssertionError(); // extremely, extremely unlikely.
234          }
235          return result;
236        }
237    
238        @Override public String toString() {
239          return "Ordering.arbitrary()";
240        }
241    
242        /*
243         * We need to be able to mock identityHashCode() calls for tests, because it
244         * can take 1-10 seconds to find colliding objects. Mocking frameworks that
245         * can do magic to mock static method calls still can't do so for a system
246         * class, so we need the indirection. In production, Hotspot should still
247         * recognize that the call is 1-morphic and should still be willing to
248         * inline it if necessary.
249         */
250        int identityHashCode(Object object) {
251          return System.identityHashCode(object);
252        }
253      }
254    
255      /**
256       * Returns an ordering that compares objects by the natural ordering of their
257       * string representations as returned by {@code toString()}. It does not
258       * support null values.
259       *
260       * <p>The comparator is serializable.
261       */
262      @GwtCompatible(serializable = true)
263      public static Ordering<Object> usingToString() {
264        return UsingToStringOrdering.INSTANCE;
265      }
266    
267      /**
268       * Returns an ordering which tries each given comparator in order until a
269       * non-zero result is found, returning that result, and returning zero only if
270       * all comparators return zero. The returned ordering is based on the state of
271       * the {@code comparators} iterable at the time it was provided to this
272       * method.
273       *
274       * <p>The returned ordering is equivalent to that produced using {@code
275       * Ordering.from(comp1).compound(comp2).compound(comp3) . . .}.
276       *
277       * <p><b>Warning:</b> Supplying an argument with undefined iteration order,
278       * such as a {@link HashSet}, will produce non-deterministic results.
279       *
280       * @param comparators the comparators to try in order
281       */
282      @GwtCompatible(serializable = true)
283      public static <T> Ordering<T> compound(
284          Iterable<? extends Comparator<? super T>> comparators) {
285        return new CompoundOrdering<T>(comparators);
286      }
287    
288      /**
289       * Constructs a new instance of this class (only invokable by the subclass
290       * constructor, typically implicit).
291       */
292      protected Ordering() {}
293    
294      // Non-static factories
295    
296      /**
297       * Returns an ordering which first uses the ordering {@code this}, but which
298       * in the event of a "tie", then delegates to {@code secondaryComparator}.
299       * For example, to sort a bug list first by status and second by priority, you
300       * might use {@code byStatus.compound(byPriority)}. For a compound ordering
301       * with three or more components, simply chain multiple calls to this method.
302       *
303       * <p>An ordering produced by this method, or a chain of calls to this method,
304       * is equivalent to one created using {@link Ordering#compound(Iterable)} on
305       * the same component comparators.
306       */
307      @GwtCompatible(serializable = true)
308      public <U extends T> Ordering<U> compound(
309          Comparator<? super U> secondaryComparator) {
310        return new CompoundOrdering<U>(this, checkNotNull(secondaryComparator));
311      }
312    
313      /**
314       * Returns the reverse of this ordering; the {@code Ordering} equivalent to
315       * {@link Collections#reverseOrder(Comparator)}.
316       */
317      // type parameter <S> lets us avoid the extra <String> in statements like:
318      // Ordering<String> o = Ordering.<String>natural().reverse();
319      @GwtCompatible(serializable = true)
320      public <S extends T> Ordering<S> reverse() {
321        return new ReverseOrdering<S>(this);
322      }
323    
324      /**
325       * Returns a new ordering on {@code F} which orders elements by first applying
326       * a function to them, then comparing those results using {@code this}. For
327       * example, to compare objects by their string forms, in a case-insensitive
328       * manner, use: <pre>   {@code
329       *
330       *   Ordering.from(String.CASE_INSENSITIVE_ORDER)
331       *       .onResultOf(Functions.toStringFunction())}</pre>
332       */
333      @GwtCompatible(serializable = true)
334      public <F> Ordering<F> onResultOf(Function<F, ? extends T> function) {
335        return new ByFunctionOrdering<F, T>(function, this);
336      }
337    
338      /**
339       * Returns a new ordering which sorts iterables by comparing corresponding
340       * elements pairwise until a nonzero result is found; imposes "dictionary
341       * order". If the end of one iterable is reached, but not the other, the
342       * shorter iterable is considered to be less than the longer one. For example,
343       * a lexicographical natural ordering over integers considers {@code
344       * [] < [1] < [1, 1] < [1, 2] < [2]}.
345       *
346       * <p>Note that {@code ordering.lexicographical().reverse()} is not
347       * equivalent to {@code ordering.reverse().lexicographical()} (consider how
348       * each would order {@code [1]} and {@code [1, 1]}).
349       *
350       * @since 2.0
351       */
352      @GwtCompatible(serializable = true)
353      // type parameter <S> lets us avoid the extra <String> in statements like:
354      // Ordering<Iterable<String>> o =
355      //     Ordering.<String>natural().lexicographical();
356      public <S extends T> Ordering<Iterable<S>> lexicographical() {
357        /*
358         * Note that technically the returned ordering should be capable of
359         * handling not just {@code Iterable<S>} instances, but also any {@code
360         * Iterable<? extends S>}. However, the need for this comes up so rarely
361         * that it doesn't justify making everyone else deal with the very ugly
362         * wildcard.
363         */
364        return new LexicographicalOrdering<S>(this);
365      }
366    
367      /**
368       * Returns an ordering that treats {@code null} as less than all other values
369       * and uses {@code this} to compare non-null values.
370       */
371      // type parameter <S> lets us avoid the extra <String> in statements like:
372      // Ordering<String> o = Ordering.<String>natural().nullsFirst();
373      @GwtCompatible(serializable = true)
374      public <S extends T> Ordering<S> nullsFirst() {
375        return new NullsFirstOrdering<S>(this);
376      }
377    
378      /**
379       * Returns an ordering that treats {@code null} as greater than all other
380       * values and uses this ordering to compare non-null values.
381       */
382      // type parameter <S> lets us avoid the extra <String> in statements like:
383      // Ordering<String> o = Ordering.<String>natural().nullsLast();
384      @GwtCompatible(serializable = true)
385      public <S extends T> Ordering<S> nullsLast() {
386        return new NullsLastOrdering<S>(this);
387      }
388    
389      // Regular instance methods
390      
391      // Override to add @Nullable
392      @Override public abstract int compare(@Nullable T left, @Nullable T right);
393    
394      /**
395       * Returns the {@code k} least elements of the given iterable according to
396       * this ordering, in order from least to greatest.  If there are fewer than
397       * {@code k} elements present, all will be included.
398       *
399       * <p>The implementation does not necessarily use a <i>stable</i> sorting
400       * algorithm; when multiple elements are equivalent, it is undefined which
401       * will come first.
402       * 
403       * @return an immutable {@code RandomAccess} list of the {@code k} least
404       *     elements in ascending order
405       * @throws IllegalArgumentException if {@code k} is negative
406       * @since 8.0
407       */
408      @Beta
409      public <E extends T> List<E> leastOf(Iterable<E> iterable, int k) {
410        checkArgument(k >= 0, "%d is negative", k);
411        
412        // values is not an E[], but we use it as such for readability. Hack.
413        @SuppressWarnings("unchecked")
414        E[] values = (E[]) Iterables.toArray(iterable);
415        
416        // TODO(nshupe): also sort whole list if k is *near* values.length?
417        // TODO(kevinb): benchmark this impl against hand-coded heap
418        E[] resultArray;
419        if (values.length <= k) {
420          Arrays.sort(values, this);
421          resultArray = values;
422        } else {
423          quicksortLeastK(values, 0, values.length - 1, k);
424    
425          // this is not an E[], but we use it as such for readability. Hack.
426          @SuppressWarnings("unchecked")
427          E[] tmp = (E[]) new Object[k];
428          resultArray = tmp;
429          System.arraycopy(values, 0, resultArray, 0, k);
430        }
431    
432        return Collections.unmodifiableList(Arrays.asList(resultArray));
433      }
434      
435      /**
436       * Returns the {@code k} greatest elements of the given iterable according to
437       * this ordering, in order from greatest to least. If there are fewer than
438       * {@code k} elements present, all will be included.
439       *
440       * <p>The implementation does not necessarily use a <i>stable</i> sorting
441       * algorithm; when multiple elements are equivalent, it is undefined which
442       * will come first.
443       * 
444       * @return an immutable {@code RandomAccess} list of the {@code k} greatest
445       *     elements in <i>descending order</i>
446       * @throws IllegalArgumentException if {@code k} is negative
447       * @since 8.0
448       */
449      @Beta
450      public <E extends T> List<E> greatestOf(Iterable<E> iterable, int k) {
451        // TODO(kevinb): see if delegation is hurting performance noticeably
452        // TODO(kevinb): if we change this implementation, add full unit tests.
453        return reverse().leastOf(iterable, k);
454      }
455    
456      private <E extends T> void quicksortLeastK(
457          E[] values, int left, int right, int k) {
458        if (right > left) {
459          int pivotIndex = (left + right) >>> 1; // left + ((right - left) / 2)
460          int pivotNewIndex = partition(values, left, right, pivotIndex);
461          quicksortLeastK(values, left, pivotNewIndex - 1, k);
462          if (pivotNewIndex < k) {
463            quicksortLeastK(values, pivotNewIndex + 1, right, k);
464          }
465        }
466      }
467      
468      private <E extends T> int partition(
469          E[] values, int left, int right, int pivotIndex) {
470        E pivotValue = values[pivotIndex];
471    
472        values[pivotIndex] = values[right];
473        values[right] = pivotValue;
474     
475        int storeIndex = left;
476        for (int i = left; i < right; i++) {
477          if (compare(values[i], pivotValue) < 0) {
478            ObjectArrays.swap(values, storeIndex, i);
479            storeIndex++;
480          }
481        }
482        ObjectArrays.swap(values, right, storeIndex);
483        return storeIndex;
484      }
485    
486      /**
487       * {@link Collections#binarySearch(List, Object, Comparator) Searches}
488       * {@code sortedList} for {@code key} using the binary search algorithm. The
489       * list must be sorted using this ordering.
490       *
491       * @param sortedList the list to be searched
492       * @param key the key to be searched for
493       */
494      public int binarySearch(List<? extends T> sortedList, @Nullable T key) {
495        return Collections.binarySearch(sortedList, key, this);
496      }
497    
498      /**
499       * Returns a copy of the given iterable sorted by this ordering. The input is
500       * not modified. The returned list is modifiable, serializable, and has random
501       * access.
502       *
503       * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard
504       * elements that are duplicates according to the comparator. The sort
505       * performed is <i>stable</i>, meaning that such elements will appear in the
506       * resulting list in the same order they appeared in the input.
507       *
508       * @param iterable the elements to be copied and sorted
509       * @return a new list containing the given elements in sorted order
510       */
511      public <E extends T> List<E> sortedCopy(Iterable<E> iterable) {
512        List<E> list = Lists.newArrayList(iterable);
513        Collections.sort(list, this);
514        return list;
515      }
516    
517      /**
518       * Returns an <i>immutable</i> copy of the given iterable sorted by this
519       * ordering. The input is not modified.
520       *
521       * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard
522       * elements that are duplicates according to the comparator. The sort
523       * performed is <i>stable</i>, meaning that such elements will appear in the
524       * resulting list in the same order they appeared in the input.
525       *
526       * @param iterable the elements to be copied and sorted
527       * @return a new immutable list containing the given elements in sorted order
528       * @throws NullPointerException if {@code iterable} or any of its elements is
529       *     null
530       * @since 3.0
531       */
532      public <E extends T> ImmutableList<E> immutableSortedCopy(
533          Iterable<E> iterable) {
534        return ImmutableList.copyOf(sortedCopy(iterable));
535      }
536    
537      /**
538       * Returns {@code true} if each element in {@code iterable} after the first is
539       * greater than or equal to the element that preceded it, according to this
540       * ordering. Note that this is always true when the iterable has fewer than
541       * two elements.
542       */
543      public boolean isOrdered(Iterable<? extends T> iterable) {
544        Iterator<? extends T> it = iterable.iterator();
545        if (it.hasNext()) {
546          T prev = it.next();
547          while (it.hasNext()) {
548            T next = it.next();
549            if (compare(prev, next) > 0) {
550              return false;
551            }
552            prev = next;
553          }
554        }
555        return true;
556      }
557    
558      /**
559       * Returns {@code true} if each element in {@code iterable} after the first is
560       * <i>strictly</i> greater than the element that preceded it, according to
561       * this ordering. Note that this is always true when the iterable has fewer
562       * than two elements.
563       */
564      public boolean isStrictlyOrdered(Iterable<? extends T> iterable) {
565        Iterator<? extends T> it = iterable.iterator();
566        if (it.hasNext()) {
567          T prev = it.next();
568          while (it.hasNext()) {
569            T next = it.next();
570            if (compare(prev, next) >= 0) {
571              return false;
572            }
573            prev = next;
574          }
575        }
576        return true;
577      }
578    
579      /**
580       * Returns the greatest of the specified values according to this ordering. If
581       * there are multiple greatest values, the first of those is returned.
582       *
583       * @param iterable the iterable whose maximum element is to be determined
584       * @throws NoSuchElementException if {@code iterable} is empty
585       * @throws ClassCastException if the parameters are not <i>mutually
586       *     comparable</i> under this ordering.
587       */
588      public <E extends T> E max(Iterable<E> iterable) {
589        Iterator<E> iterator = iterable.iterator();
590    
591        // let this throw NoSuchElementException as necessary
592        E maxSoFar = iterator.next();
593    
594        while (iterator.hasNext()) {
595          maxSoFar = max(maxSoFar, iterator.next());
596        }
597    
598        return maxSoFar;
599      }
600    
601      /**
602       * Returns the greatest of the specified values according to this ordering. If
603       * there are multiple greatest values, the first of those is returned.
604       *
605       * @param a value to compare, returned if greater than or equal to the rest.
606       * @param b value to compare
607       * @param c value to compare
608       * @param rest values to compare
609       * @throws ClassCastException if the parameters are not <i>mutually
610       *     comparable</i> under this ordering.
611       */
612      public <E extends T> E max(
613          @Nullable E a, @Nullable E b, @Nullable E c, E... rest) {
614        E maxSoFar = max(max(a, b), c);
615    
616        for (E r : rest) {
617          maxSoFar = max(maxSoFar, r);
618        }
619    
620        return maxSoFar;
621      }
622    
623      /**
624       * Returns the greater of the two values according to this ordering. If the
625       * values compare as 0, the first is returned.
626       *
627       * <p><b>Implementation note:</b> this method is invoked by the default
628       * implementations of the other {@code max} overloads, so overriding it will
629       * affect their behavior.
630       *
631       * @param a value to compare, returned if greater than or equal to b.
632       * @param b value to compare.
633       * @throws ClassCastException if the parameters are not <i>mutually
634       *     comparable</i> under this ordering.
635       */
636      public <E extends T> E max(@Nullable E a, @Nullable E b) {
637        return compare(a, b) >= 0 ? a : b;
638      }
639    
640      /**
641       * Returns the least of the specified values according to this ordering. If
642       * there are multiple least values, the first of those is returned.
643       *
644       * @param iterable the iterable whose minimum element is to be determined
645       * @throws NoSuchElementException if {@code iterable} is empty
646       * @throws ClassCastException if the parameters are not <i>mutually
647       *     comparable</i> under this ordering.
648       */
649      public <E extends T> E min(Iterable<E> iterable) {
650        Iterator<E> iterator = iterable.iterator();
651    
652        // let this throw NoSuchElementException as necessary
653        E minSoFar = iterator.next();
654    
655        while (iterator.hasNext()) {
656          minSoFar = min(minSoFar, iterator.next());
657        }
658    
659        return minSoFar;
660      }
661    
662      /**
663       * Returns the least of the specified values according to this ordering. If
664       * there are multiple least values, the first of those is returned.
665       *
666       * @param a value to compare, returned if less than or equal to the rest.
667       * @param b value to compare
668       * @param c value to compare
669       * @param rest values to compare
670       * @throws ClassCastException if the parameters are not <i>mutually
671       *     comparable</i> under this ordering.
672       */
673      public <E extends T> E min(
674          @Nullable E a, @Nullable E b, @Nullable E c, E... rest) {
675        E minSoFar = min(min(a, b), c);
676    
677        for (E r : rest) {
678          minSoFar = min(minSoFar, r);
679        }
680    
681        return minSoFar;
682      }
683    
684      /**
685       * Returns the lesser of the two values according to this ordering. If the
686       * values compare as 0, the first is returned.
687       *
688       * <p><b>Implementation note:</b> this method is invoked by the default
689       * implementations of the other {@code min} overloads, so overriding it will
690       * affect their behavior.
691       *
692       * @param a value to compare, returned if less than or equal to b.
693       * @param b value to compare.
694       * @throws ClassCastException if the parameters are not <i>mutually
695       *     comparable</i> under this ordering.
696       */
697      public <E extends T> E min(@Nullable E a, @Nullable E b) {
698        return compare(a, b) <= 0 ? a : b;
699      }
700    
701      // Never make these public
702      static final int LEFT_IS_GREATER = 1;
703      static final int RIGHT_IS_GREATER = -1;
704    }