View Javadoc
1   /*
2    * Copyright (C) 2016 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkNotNull;
20  import static com.google.common.collect.CollectPreconditions.checkNonnegative;
21  
22  import com.google.common.annotations.Beta;
23  import com.google.common.annotations.GwtCompatible;
24  import java.util.Comparator;
25  import java.util.Iterator;
26  import java.util.List;
27  import java.util.Optional;
28  import java.util.stream.Collector;
29  
30  /**
31   * Provides static methods for working with {@link Comparator} instances. For many other helpful
32   * comparator utilities, see either {@code Comparator} itself (for Java 8 or later), or {@code
33   * com.google.common.collect.Ordering} (otherwise).
34   *
35   * <h3>Relationship to {@code Ordering}</h3>
36   *
37   * <p>In light of the significant enhancements to {@code Comparator} in Java 8, the overwhelming
38   * majority of usages of {@code Ordering} can be written using only built-in JDK APIs. This class is
39   * intended to "fill the gap" and provide those features of {@code Ordering} not already provided by
40   * the JDK.
41   *
42   * @since 21.0
43   * @author Louis Wasserman
44   */
45  @Beta
46  @GwtCompatible
47  public final class Comparators {
48    private Comparators() {}
49  
50    /**
51     * Returns a new comparator which sorts iterables by comparing corresponding elements pairwise
52     * until a nonzero result is found; imposes "dictionary order." If the end of one iterable is
53     * reached, but not the other, the shorter iterable is considered to be less than the longer one.
54     * For example, a lexicographical natural ordering over integers considers {@code
55     * [] < [1] < [1, 1] < [1, 2] < [2]}.
56     *
57     * <p>Note that {@code Collections.reverseOrder(lexicographical(comparator))} is not
58     * equivalent to {@code lexicographical(Collections.reverseOrder(comparator))} (consider how each
59     * would order {@code [1]} and {@code [1, 1]}).
60     */
61    // Note: 90% of the time we don't add type parameters or wildcards that serve only to "tweak" the
62    // desired return type. However, *nested* generics introduce a special class of problems that we
63    // think tip it over into being worthwhile.
64    public static <T, S extends T> Comparator<Iterable<S>> lexicographical(Comparator<T> comparator) {
65      return new LexicographicalOrdering<S>(checkNotNull(comparator));
66    }
67  
68    /**
69     * Returns {@code true} if each element in {@code iterable} after the first is greater than or
70     * equal to the element that preceded it, according to the specified comparator. Note that this
71     * is always true when the iterable has fewer than two elements.
72     */
73    public static <T> boolean isInOrder(Iterable<? extends T> iterable, Comparator<T> comparator) {
74      checkNotNull(comparator);
75      Iterator<? extends T> it = iterable.iterator();
76      if (it.hasNext()) {
77        T prev = it.next();
78        while (it.hasNext()) {
79          T next = it.next();
80          if (comparator.compare(prev, next) > 0) {
81            return false;
82          }
83          prev = next;
84        }
85      }
86      return true;
87    }
88  
89    /**
90     * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i>
91     * greater than the element that preceded it, according to the specified comparator. Note that
92     * this is always true when the iterable has fewer than two elements.
93     */
94    public static <T> boolean isInStrictOrder(
95        Iterable<? extends T> iterable, Comparator<T> comparator) {
96      checkNotNull(comparator);
97      Iterator<? extends T> it = iterable.iterator();
98      if (it.hasNext()) {
99        T prev = it.next();
100       while (it.hasNext()) {
101         T next = it.next();
102         if (comparator.compare(prev, next) >= 0) {
103           return false;
104         }
105         prev = next;
106       }
107     }
108     return true;
109   }
110 
111   /**
112    * Returns a {@code Collector} that returns the {@code k} smallest (relative to the specified
113    * {@code Comparator}) input elements, in ascending order, as an unmodifiable {@code List}.
114    * Ties are broken arbitrarily.
115    *
116    * For example:
117    *  <pre>   {@code
118    *
119    *   Stream.of("foo", "quux", "banana", "elephant")
120    *       .collect(least(2, comparingInt(String::length)))
121    *   // returns {"foo", "quux"}}</pre>
122    *
123    * <p>This {@code Collector} uses O(k) memory and takes expected time O(n)
124    * (worst-case O(n log k)), as opposed to e.g. {@code Stream.sorted(comparator).limit(k)}, which
125    * currently takes O(n log n) time and O(n) space.
126    *
127    * @throws IllegalArgumentException if {@code k < 0}
128    * @since 22.0
129    */
130   public static <T> Collector<T, ?, List<T>> least(int k, Comparator<? super T> comparator) {
131     checkNonnegative(k, "k");
132     checkNotNull(comparator);
133     return Collector.of(
134         () -> TopKSelector.<T>least(k, comparator),
135         TopKSelector::offer,
136         TopKSelector::combine,
137         TopKSelector::topK,
138         Collector.Characteristics.UNORDERED);
139   }
140 
141   /**
142    * Returns a {@code Collector} that returns the {@code k} greatest (relative to the specified
143    * {@code Comparator}) input elements, in descending order, as an unmodifiable {@code List}.
144    * Ties are broken arbitrarily.
145    *
146    * For example:
147    *  <pre>   {@code
148    *
149    *   Stream.of("foo", "quux", "banana", "elephant")
150    *       .collect(greatest(2, comparingInt(String::length)))
151    *   // returns {"elephant", "banana"}}</pre>
152    *
153    * <p>This {@code Collector} uses O(k) memory and takes expected time O(n)
154    * (worst-case O(n log k)), as opposed to e.g.
155    * {@code Stream.sorted(comparator.reversed()).limit(k)}, which currently takes O(n log n) time
156    * and O(n) space.
157    *
158    * @throws IllegalArgumentException if {@code k < 0}
159    * @since 22.0
160    */
161   public static <T> Collector<T, ?, List<T>> greatest(int k, Comparator<? super T> comparator) {
162     return least(k, comparator.reversed());
163   }
164 
165   /**
166    * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as less
167    * than all other values, and orders the rest using {@code valueComparator} on the contained
168    * value.
169    *
170    * @since 22.0
171    */
172   @Beta
173   public static <T> Comparator<Optional<T>> emptiesFirst(Comparator<T> valueComparator) {
174     checkNotNull(valueComparator);
175     return Comparator.comparing(o -> o.orElse(null), Comparator.nullsFirst(valueComparator));
176   }
177 
178   /**
179    * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as greater
180    * than all other values, and orders the rest using {@code valueComparator} on the contained
181    * value.
182    *
183    * @since 22.0
184    */
185   @Beta
186   public static <T> Comparator<Optional<T>> emptiesLast(Comparator<T> valueComparator) {
187     checkNotNull(valueComparator);
188     return Comparator.comparing(o -> o.orElse(null), Comparator.nullsLast(valueComparator));
189   }
190 }