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 import org.checkerframework.checker.nullness.qual.Nullable;
30
31 /**
32 * Provides static methods for working with {@link Comparator} instances. For many other helpful
33 * comparator utilities, see either {@code Comparator} itself (for Java 8 or later), or {@code
34 * com.google.common.collect.Ordering} (otherwise).
35 *
36 * <h3>Relationship to {@code Ordering}</h3>
37 *
38 * <p>In light of the significant enhancements to {@code Comparator} in Java 8, the overwhelming
39 * majority of usages of {@code Ordering} can be written using only built-in JDK APIs. This class is
40 * intended to "fill the gap" and provide those features of {@code Ordering} not already provided by
41 * the JDK.
42 *
43 * @since 21.0
44 * @author Louis Wasserman
45 */
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 [] < [1] < [1,
55 * 1] < [1, 2] < [2]}.
56 *
57 * <p>Note that {@code Collections.reverseOrder(lexicographical(comparator))} is not equivalent to
58 * {@code lexicographical(Collections.reverseOrder(comparator))} (consider how each would order
59 * {@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 @Beta
65 public static <T, S extends T> Comparator<Iterable<S>> lexicographical(Comparator<T> comparator) {
66 return new LexicographicalOrdering<S>(checkNotNull(comparator));
67 }
68
69 /**
70 * Returns {@code true} if each element in {@code iterable} after the first is greater than or
71 * equal to the element that preceded it, according to the specified comparator. Note that this is
72 * always true when the iterable has fewer than two elements.
73 */
74 @Beta
75 public static <T> boolean isInOrder(Iterable<? extends T> iterable, Comparator<T> comparator) {
76 checkNotNull(comparator);
77 Iterator<? extends T> it = iterable.iterator();
78 if (it.hasNext()) {
79 T prev = it.next();
80 while (it.hasNext()) {
81 T next = it.next();
82 if (comparator.compare(prev, next) > 0) {
83 return false;
84 }
85 prev = next;
86 }
87 }
88 return true;
89 }
90
91 /**
92 * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i>
93 * greater than the element that preceded it, according to the specified comparator. Note that
94 * this is always true when the iterable has fewer than two elements.
95 */
96 @Beta
97 public static <T> boolean isInStrictOrder(
98 Iterable<? extends T> iterable, Comparator<T> comparator) {
99 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 22.0
133 */
134 public static <T> Collector<T, ?, List<T>> least(int k, Comparator<? super T> comparator) {
135 checkNonnegative(k, "k");
136 checkNotNull(comparator);
137 return Collector.of(
138 () -> TopKSelector.<T>least(k, comparator),
139 TopKSelector::offer,
140 TopKSelector::combine,
141 TopKSelector::topK,
142 Collector.Characteristics.UNORDERED);
143 }
144
145 /**
146 * Returns a {@code Collector} that returns the {@code k} greatest (relative to the specified
147 * {@code Comparator}) input elements, in descending order, as an unmodifiable {@code List}. Ties
148 * are broken arbitrarily.
149 *
150 * <p>For example:
151 *
152 * <pre>{@code
153 * Stream.of("foo", "quux", "banana", "elephant")
154 * .collect(greatest(2, comparingInt(String::length)))
155 * // returns {"elephant", "banana"}
156 * }</pre>
157 *
158 * <p>This {@code Collector} uses O(k) memory and takes expected time O(n) (worst-case O(n log
159 * k)), as opposed to e.g. {@code Stream.sorted(comparator.reversed()).limit(k)}, which currently
160 * takes O(n log n) time and O(n) space.
161 *
162 * @throws IllegalArgumentException if {@code k < 0}
163 * @since 22.0
164 */
165 public static <T> Collector<T, ?, List<T>> greatest(int k, Comparator<? super T> comparator) {
166 return least(k, comparator.reversed());
167 }
168
169 /**
170 * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as less
171 * than all other values, and orders the rest using {@code valueComparator} on the contained
172 * value.
173 *
174 * @since 22.0
175 */
176 @Beta
177 public static <T> Comparator<Optional<T>> emptiesFirst(Comparator<? super T> valueComparator) {
178 checkNotNull(valueComparator);
179 return Comparator.comparing(o -> o.orElse(null), Comparator.nullsFirst(valueComparator));
180 }
181
182 /**
183 * Returns a comparator of {@link Optional} values which treats {@link Optional#empty} as greater
184 * than all other values, and orders the rest using {@code valueComparator} on the contained
185 * value.
186 *
187 * @since 22.0
188 */
189 @Beta
190 public static <T> Comparator<Optional<T>> emptiesLast(Comparator<? super T> valueComparator) {
191 checkNotNull(valueComparator);
192 return Comparator.comparing(o -> o.orElse(null), Comparator.nullsLast(valueComparator));
193 }
194
195 /**
196 * Returns the minimum of the two values. If the values compare as 0, the first is returned.
197 *
198 * <p>The recommended solution for finding the {@code minimum} of some values depends on the type
199 * of your data and the number of elements you have. Read more in the Guava User Guide article on
200 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
201 * Comparators}</a>.
202 *
203 * @param a first value to compare, returned if less than or equal to b.
204 * @param b second value to compare.
205 * @throws ClassCastException if the parameters are not <i>mutually comparable</i>.
206 * @since 30.0
207 */
208 @Beta
209 public static <T extends Comparable<? super T>> T min(T a, T b) {
210 return (a.compareTo(b) <= 0) ? a : b;
211 }
212
213 /**
214 * Returns the minimum of the two values, according to the given comparator. If the values compare
215 * as equal, the first is returned.
216 *
217 * <p>The recommended solution for finding the {@code minimum} of some values depends on the type
218 * of your data and the number of elements you have. Read more in the Guava User Guide article on
219 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
220 * Comparators}</a>.
221 *
222 * @param a first value to compare, returned if less than or equal to b
223 * @param b second value to compare.
224 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given
225 * comparator.
226 * @since 30.0
227 */
228 @Beta
229 public static <T> T min(@Nullable T a, @Nullable T b, Comparator<T> comparator) {
230 return (comparator.compare(a, b) <= 0) ? a : b;
231 }
232
233 /**
234 * Returns the maximum of the two values. If the values compare as 0, the first is returned.
235 *
236 * <p>The recommended solution for finding the {@code maximum} of some values depends on the type
237 * of your data and the number of elements you have. Read more in the Guava User Guide article on
238 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
239 * Comparators}</a>.
240 *
241 * @param a first value to compare, returned if greater than or equal to b.
242 * @param b second value to compare.
243 * @throws ClassCastException if the parameters are not <i>mutually comparable</i>.
244 * @since 30.0
245 */
246 @Beta
247 public static <T extends Comparable<? super T>> T max(T a, T b) {
248 return (a.compareTo(b) >= 0) ? a : b;
249 }
250
251 /**
252 * Returns the maximum of the two values, according to the given comparator. If the values compare
253 * as equal, the first is returned.
254 *
255 * <p>The recommended solution for finding the {@code maximum} of some values depends on the type
256 * of your data and the number of elements you have. Read more in the Guava User Guide article on
257 * <a href="https://github.com/google/guava/wiki/CollectionUtilitiesExplained#comparators">{@code
258 * Comparators}</a>.
259 *
260 * @param a first value to compare, returned if greater than or equal to b.
261 * @param b second value to compare.
262 * @throws ClassCastException if the parameters are not <i>mutually comparable</i> using the given
263 * comparator.
264 * @since 30.0
265 */
266 @Beta
267 public static <T> T max(@Nullable T a, @Nullable T b, Comparator<T> comparator) {
268 return (comparator.compare(a, b) >= 0) ? a : b;
269 }
270 }