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 { 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 lexicographical(Comparator<T> comparator)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 isInOrder(Iterable<? extends T> iterable, Comparator<T> comparator)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 isInStrictOrder( Iterable<? extends T> iterable, Comparator<T> comparator)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 */ least(int k, Comparator<? super T> comparator)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 */ greatest(int k, Comparator<? super T> comparator)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 emptiesFirst(Comparator<? super T> valueComparator)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 emptiesLast(Comparator<? super T> valueComparator)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 min(T a, T b)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 min(@ullable T a, @Nullable T b, Comparator<T> comparator)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 max(T a, T b)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 max(@ullable T a, @Nullable T b, Comparator<T> comparator)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 } 271