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.Beta;
023import com.google.common.annotations.GwtCompatible;
024import java.util.Comparator;
025import java.util.Iterator;
026import java.util.List;
027import java.util.Optional;
028import java.util.stream.Collector;
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 later), 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  @Beta
066  public static <T extends @Nullable Object, S extends T> Comparator<Iterable<S>> lexicographical(
067      Comparator<T> comparator) {
068    return new LexicographicalOrdering<S>(checkNotNull(comparator));
069  }
070
071  /**
072   * Returns {@code true} if each element in {@code iterable} after the first is greater than or
073   * equal to the element that preceded it, according to the specified comparator. Note that this is
074   * always true when the iterable has fewer than two elements.
075   */
076  @Beta
077  public static <T extends @Nullable Object> boolean isInOrder(
078      Iterable<? extends T> iterable, Comparator<T> comparator) {
079    checkNotNull(comparator);
080    Iterator<? extends T> it = iterable.iterator();
081    if (it.hasNext()) {
082      T prev = it.next();
083      while (it.hasNext()) {
084        T next = it.next();
085        if (comparator.compare(prev, next) > 0) {
086          return false;
087        }
088        prev = next;
089      }
090    }
091    return true;
092  }
093
094  /**
095   * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i>
096   * greater than the element that preceded it, according to the specified comparator. Note that
097   * this is always true when the iterable has fewer than two elements.
098   */
099  @Beta
100  public static <T extends @Nullable Object> boolean isInStrictOrder(
101      Iterable<? extends T> iterable, Comparator<T> comparator) {
102    checkNotNull(comparator);
103    Iterator<? extends T> it = iterable.iterator();
104    if (it.hasNext()) {
105      T prev = it.next();
106      while (it.hasNext()) {
107        T next = it.next();
108        if (comparator.compare(prev, next) >= 0) {
109          return false;
110        }
111        prev = next;
112      }
113    }
114    return true;
115  }
116
117  /**
118   * Returns a {@code Collector} that returns the {@code k} smallest (relative to the specified
119   * {@code Comparator}) input elements, in ascending order, as an unmodifiable {@code List}. Ties
120   * are broken arbitrarily.
121   *
122   * <p>For example:
123   *
124   * <pre>{@code
125   * Stream.of("foo", "quux", "banana", "elephant")
126   *     .collect(least(2, comparingInt(String::length)))
127   * // returns {"foo", "quux"}
128   * }</pre>
129   *
130   * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
131   * k)), as opposed to e.g. {@code Stream.sorted(comparator).limit(k)}, which currently takes O(n
132   * log n) time and O(n) space.
133   *
134   * @throws IllegalArgumentException if {@code k < 0}
135   * @since 22.0
136   */
137  public static <T extends @Nullable Object> Collector<T, ?, List<T>> least(
138      int k, Comparator<? super T> comparator) {
139    checkNonnegative(k, "k");
140    checkNotNull(comparator);
141    return Collector.of(
142        () -> TopKSelector.<T>least(k, comparator),
143        TopKSelector::offer,
144        TopKSelector::combine,
145        TopKSelector::topK,
146        Collector.Characteristics.UNORDERED);
147  }
148
149  /**
150   * Returns a {@code Collector} that returns the {@code k} greatest (relative to the specified
151   * {@code Comparator}) input elements, in descending order, as an unmodifiable {@code List}. Ties
152   * are broken arbitrarily.
153   *
154   * <p>For example:
155   *
156   * <pre>{@code
157   * Stream.of("foo", "quux", "banana", "elephant")
158   *     .collect(greatest(2, comparingInt(String::length)))
159   * // returns {"elephant", "banana"}
160   * }</pre>
161   *
162   * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
163   * k)), as opposed to e.g. {@code Stream.sorted(comparator.reversed()).limit(k)}, which currently
164   * takes O(n log n) time and O(n) space.
165   *
166   * @throws IllegalArgumentException if {@code k < 0}
167   * @since 22.0
168   */
169  public static <T extends @Nullable Object> Collector<T, ?, List<T>> greatest(
170      int k, Comparator<? super T> comparator) {
171    return least(k, comparator.reversed());
172  }
173
174  /**
175   * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as less
176   * than all other values, and orders the rest using {@code valueComparator} on the contained
177   * value.
178   *
179   * @since 22.0
180   */
181  @Beta
182  public static <T> Comparator<Optional<T>> emptiesFirst(Comparator<? super T> valueComparator) {
183    checkNotNull(valueComparator);
184    return Comparator.<Optional<T>, @Nullable T>comparing(
185        o -> o.orElse(null), Comparator.nullsFirst(valueComparator));
186  }
187
188  /**
189   * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as greater
190   * than all other values, and orders the rest using {@code valueComparator} on the contained
191   * value.
192   *
193   * @since 22.0
194   */
195  @Beta
196  public static <T> Comparator<Optional<T>> emptiesLast(Comparator<? super T> valueComparator) {
197    checkNotNull(valueComparator);
198    return Comparator.<Optional<T>, @Nullable T>comparing(
199        o -> o.orElse(null), Comparator.nullsLast(valueComparator));
200  }
201
202  /**
203   * Returns the minimum of the two values. If the values compare as 0, the first is returned.
204   *
205   * <p>The recommended solution for finding the {@code minimum} of some values depends on the type
206   * of your data and the number of elements you have. Read more in the Guava User Guide article on
207   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
208   * Comparators}</a>.
209   *
210   * @param a first value to compare, returned if less than or equal to b.
211   * @param b second value to compare.
212   * @throws ClassCastException if the parameters are not <i>mutually comparable</i>.
213   * @since 30.0
214   */
215  @Beta
216  public static <T extends Comparable<? super T>> T min(T a, T b) {
217    return (a.compareTo(b) <= 0) ? a : b;
218  }
219
220  /**
221   * Returns the minimum of the two values, according to the given comparator. If the values compare
222   * as equal, the first is returned.
223   *
224   * <p>The recommended solution for finding the {@code minimum} of some values depends on the type
225   * of your data and the number of elements you have. Read more in the Guava User Guide article on
226   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
227   * Comparators}</a>.
228   *
229   * @param a first value to compare, returned if less than or equal to b
230   * @param b second value to compare.
231   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given
232   *     comparator.
233   * @since 30.0
234   */
235  @Beta
236  @ParametricNullness
237  public static <T extends @Nullable Object> T min(
238      @ParametricNullness T a, @ParametricNullness T b, Comparator<T> comparator) {
239    return (comparator.compare(a, b) <= 0) ? a : b;
240  }
241
242  /**
243   * Returns the maximum of the two values. If the values compare as 0, the first is returned.
244   *
245   * <p>The recommended solution for finding the {@code maximum} of some values depends on the type
246   * of your data and the number of elements you have. Read more in the Guava User Guide article on
247   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
248   * Comparators}</a>.
249   *
250   * @param a first value to compare, returned if greater than or equal to b.
251   * @param b second value to compare.
252   * @throws ClassCastException if the parameters are not <i>mutually comparable</i>.
253   * @since 30.0
254   */
255  @Beta
256  public static <T extends Comparable<? super T>> T max(T a, T b) {
257    return (a.compareTo(b) >= 0) ? a : b;
258  }
259
260  /**
261   * Returns the maximum of the two values, according to the given comparator. If the values compare
262   * as equal, the first is returned.
263   *
264   * <p>The recommended solution for finding the {@code maximum} of some values depends on the type
265   * of your data and the number of elements you have. Read more in the Guava User Guide article on
266   * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
267   * Comparators}</a>.
268   *
269   * @param a first value to compare, returned if greater than or equal to b.
270   * @param b second value to compare.
271   * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given
272   *     comparator.
273   * @since 30.0
274   */
275  @Beta
276  @ParametricNullness
277  public static <T extends @Nullable Object> T max(
278      @ParametricNullness T a, @ParametricNullness T b, Comparator<T> comparator) {
279    return (comparator.compare(a, b) >= 0) ? a : b;
280  }
281}