001/*
002 * Copyright (C) 2016 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkNonnegative;
021
022import com.google.common.annotations.GwtCompatible;
023import java.util.Comparator;
024import java.util.Iterator;
025import java.util.List;
026import java.util.Optional;
027import java.util.stream.Collector;
028import javax.annotation.CheckForNull;
029import org.checkerframework.checker.nullness.qual.Nullable;
030
031/**
032 * Provides static methods for working with {@link Comparator} instances. For many other helpful
033 * comparator utilities, see either {@code Comparator} itself (for Java 8+), or {@code
034 * com.google.common.collect.Ordering} (otherwise).
035 *
036 * <h3>Relationship to {@code Ordering}</h3>
037 *
038 * <p>In light of the significant enhancements to {@code Comparator} in Java 8, the overwhelming
039 * majority of usages of {@code Ordering} can be written using only built-in JDK APIs. This class is
040 * intended to "fill the gap" and provide those features of {@code Ordering} not already provided by
041 * the JDK.
042 *
043 * @since 21.0
044 * @author Louis Wasserman
045 */
046@GwtCompatible
047@ElementTypesAreNonnullByDefault
048public final class Comparators {
049  private Comparators() {}
050
051  /**
052   * Returns a new comparator which sorts iterables by comparing corresponding elements pairwise
053   * until a nonzero result is found; imposes "dictionary order." If the end of one iterable is
054   * reached, but not the other, the shorter iterable is considered to be less than the longer one.
055   * For example, a lexicographical natural ordering over integers considers {@code [] < [1] < [1,
056   * 1] < [1, 2] < [2]}.
057   *
058   * <p>Note that {@code Collections.reverseOrder(lexicographical(comparator))} is not equivalent to
059   * {@code lexicographical(Collections.reverseOrder(comparator))} (consider how each would order
060   * {@code [1]} and {@code [1, 1]}).
061   */
062  // Note: 90% of the time we don't add type parameters or wildcards that serve only to "tweak" the
063  // desired return type. However, *nested* generics introduce a special class of problems that we
064  // think tip it over into being worthwhile.
065  public static <T extends @Nullable Object, S extends T> Comparator<Iterable<S>> lexicographical(
066      Comparator<T> comparator) {
067    return new LexicographicalOrdering<S>(checkNotNull(comparator));
068  }
069
070  /**
071   * Returns {@code true} if each element in {@code iterable} after the first is greater than or
072   * equal to the element that preceded it, according to the specified comparator. Note that this is
073   * always true when the iterable has fewer than two elements.
074   */
075  public static <T extends @Nullable Object> boolean isInOrder(
076      Iterable<? extends T> iterable, Comparator<T> comparator) {
077    checkNotNull(comparator);
078    Iterator<? extends T> it = iterable.iterator();
079    if (it.hasNext()) {
080      T prev = it.next();
081      while (it.hasNext()) {
082        T next = it.next();
083        if (comparator.compare(prev, next) > 0) {
084          return false;
085        }
086        prev = next;
087      }
088    }
089    return true;
090  }
091
092  /**
093   * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i>
094   * greater than the element that preceded it, according to the specified comparator. Note that
095   * this is always true when the iterable has fewer than two elements.
096   */
097  public static <T extends @Nullable Object> boolean isInStrictOrder(
098      Iterable<? extends T> iterable, Comparator<T> comparator) {
099    checkNotNull(comparator);
100    Iterator<? extends T> it = iterable.iterator();
101    if (it.hasNext()) {
102      T prev = it.next();
103      while (it.hasNext()) {
104        T next = it.next();
105        if (comparator.compare(prev, next) >= 0) {
106          return false;
107        }
108        prev = next;
109      }
110    }
111    return true;
112  }
113
114  /**
115   * Returns a {@code Collector} that returns the {@code k} smallest (relative to the specified
116   * {@code Comparator}) input elements, in ascending order, as an unmodifiable {@code List}. Ties
117   * are broken arbitrarily.
118   *
119   * <p>For example:
120   *
121   * <pre>{@code
122   * Stream.of("foo", "quux", "banana", "elephant")
123   *     .collect(least(2, comparingInt(String::length)))
124   * // returns {"foo", "quux"}
125   * }</pre>
126   *
127   * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
128   * k)), as opposed to e.g. {@code Stream.sorted(comparator).limit(k)}, which currently takes O(n
129   * log n) time and O(n) space.
130   *
131   * @throws IllegalArgumentException if {@code k < 0}
132   * @since 33.2.0 (available since 22.0 in guava-jre)
133   */
134  @SuppressWarnings("Java7ApiChecker")
135  @IgnoreJRERequirement // Users will use this only if they're already using streams.
136  public static <T extends @Nullable Object> Collector<T, ?, List<T>> least(
137      int k, Comparator<? super T> comparator) {
138    checkNonnegative(k, "k");
139    checkNotNull(comparator);
140    return Collector.of(
141        () -> TopKSelector.<T>least(k, comparator),
142        TopKSelector::offer,
143        TopKSelector::combine,
144        TopKSelector::topK,
145        Collector.Characteristics.UNORDERED);
146  }
147
148  /**
149   * Returns a {@code Collector} that returns the {@code k} greatest (relative to the specified
150   * {@code Comparator}) input elements, in descending order, as an unmodifiable {@code List}. Ties
151   * are broken arbitrarily.
152   *
153   * <p>For example:
154   *
155   * <pre>{@code
156   * Stream.of("foo", "quux", "banana", "elephant")
157   *     .collect(greatest(2, comparingInt(String::length)))
158   * // returns {"elephant", "banana"}
159   * }</pre>
160   *
161   * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
162   * k)), as opposed to e.g. {@code Stream.sorted(comparator.reversed()).limit(k)}, which currently
163   * takes O(n log n) time and O(n) space.
164   *
165   * @throws IllegalArgumentException if {@code k < 0}
166   * @since 33.2.0 (available since 22.0 in guava-jre)
167   */
168  @SuppressWarnings("Java7ApiChecker")
169  @IgnoreJRERequirement // Users will use this only if they're already using streams.
170  public static <T extends @Nullable Object> Collector<T, ?, List<T>> greatest(
171      int k, Comparator<? super T> comparator) {
172    return least(k, comparator.reversed());
173  }
174
175  /**
176   * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as less
177   * than all other values, and orders the rest using {@code valueComparator} on the contained
178   * value.
179   *
180   * @since 33.4.0 (but since 22.0 in the JRE flavor)
181   */
182  @SuppressWarnings("Java7ApiChecker")
183  @IgnoreJRERequirement // Users will use this only if they're already using Optional.
184  public static <T> Comparator<Optional<T>> emptiesFirst(Comparator<? super T> valueComparator) {
185    checkNotNull(valueComparator);
186    return Comparator.<Optional<T>, @Nullable T>comparing(
187        o -> orElseNull(o), Comparator.nullsFirst(valueComparator));
188  }
189
190  /**
191   * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as greater
192   * than all other values, and orders the rest using {@code valueComparator} on the contained
193   * value.
194   *
195   * @since 33.4.0 (but since 22.0 in the JRE flavor)
196   */
197  @SuppressWarnings("Java7ApiChecker")
198  @IgnoreJRERequirement // Users will use this only if they're already using Optional.
199  public static <T> Comparator<Optional<T>> emptiesLast(Comparator<? super T> valueComparator) {
200    checkNotNull(valueComparator);
201    return Comparator.<Optional<T>, @Nullable T>comparing(
202        o -> orElseNull(o), Comparator.nullsLast(valueComparator));
203  }
204
205  @SuppressWarnings("Java7ApiChecker")
206  @IgnoreJRERequirement // helper for emptiesFirst+emptiesLast
207  /*
208   * If we make these calls inline inside the lambda inside emptiesFirst()/emptiesLast(), we get an
209   * Animal Sniffer error, despite the @IgnoreJRERequirement annotation there. For details, see
210   * ImmutableSortedMultiset.
211   */
212  @CheckForNull
213  private static <T> T orElseNull(Optional<T> optional) {
214    return optional.orElse(null);
215  }
216
217  /**
218   * Returns the minimum of the two values. If the values compare as 0, the first is returned.
219   *
220   * <p>The recommended solution for finding the {@code minimum} of some values depends on the type
221   * of your data and the number of elements you have. Read more in the Guava User Guide article on
222   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
223   * Comparators}</a>.
224   *
225   * @param a first value to compare, returned if less than or equal to b.
226   * @param b second value to compare.
227   * @throws ClassCastException if the parameters are not <i>mutually comparable</i>.
228   * @since 30.0
229   */
230  public static <T extends Comparable<? super T>> T min(T a, T b) {
231    return (a.compareTo(b) <= 0) ? a : b;
232  }
233
234  /**
235   * Returns the minimum of the two values, according to the given comparator. If the values compare
236   * as equal, the first is returned.
237   *
238   * <p>The recommended solution for finding the {@code minimum} of some values depends on the type
239   * of your data and the number of elements you have. Read more in the Guava User Guide article on
240   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
241   * Comparators}</a>.
242   *
243   * @param a first value to compare, returned if less than or equal to b
244   * @param b second value to compare.
245   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given
246   *     comparator.
247   * @since 30.0
248   */
249  @ParametricNullness
250  public static <T extends @Nullable Object> T min(
251      @ParametricNullness T a, @ParametricNullness T b, Comparator<? super T> comparator) {
252    return (comparator.compare(a, b) <= 0) ? a : b;
253  }
254
255  /**
256   * Returns the maximum of the two values. If the values compare as 0, the first is returned.
257   *
258   * <p>The recommended solution for finding the {@code maximum} of some values depends on the type
259   * of your data and the number of elements you have. Read more in the Guava User Guide article on
260   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
261   * Comparators}</a>.
262   *
263   * @param a first value to compare, returned if greater than or equal to b.
264   * @param b second value to compare.
265   * @throws ClassCastException if the parameters are not <i>mutually comparable</i>.
266   * @since 30.0
267   */
268  public static <T extends Comparable<? super T>> T max(T a, T b) {
269    return (a.compareTo(b) >= 0) ? a : b;
270  }
271
272  /**
273   * Returns the maximum of the two values, according to the given comparator. If the values compare
274   * as equal, the first is returned.
275   *
276   * <p>The recommended solution for finding the {@code maximum} of some values depends on the type
277   * of your data and the number of elements you have. Read more in the Guava User Guide article on
278   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
279   * Comparators}</a>.
280   *
281   * @param a first value to compare, returned if greater than or equal to b.
282   * @param b second value to compare.
283   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given
284   *     comparator.
285   * @since 30.0
286   */
287  @ParametricNullness
288  public static <T extends @Nullable Object> T max(
289      @ParametricNullness T a, @ParametricNullness T b, Comparator<? super T> comparator) {
290    return (comparator.compare(a, b) >= 0) ? a : b;
291  }
292}