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 047public final class Comparators { 048 private Comparators() {} 049 050 /** 051 * Returns a new comparator which sorts iterables by comparing corresponding elements pairwise 052 * until a nonzero result is found; imposes "dictionary order." If the end of one iterable is 053 * reached, but not the other, the shorter iterable is considered to be less than the longer one. 054 * For example, a lexicographical natural ordering over integers considers {@code [] < [1] < [1, 055 * 1] < [1, 2] < [2]}. 056 * 057 * <p>Note that {@code Collections.reverseOrder(lexicographical(comparator))} is not equivalent to 058 * {@code lexicographical(Collections.reverseOrder(comparator))} (consider how each would order 059 * {@code [1]} and {@code [1, 1]}). 060 */ 061 // Note: 90% of the time we don't add type parameters or wildcards that serve only to "tweak" the 062 // desired return type. However, *nested* generics introduce a special class of problems that we 063 // think tip it over into being worthwhile. 064 @Beta 065 public static <T, S extends T> Comparator<Iterable<S>> lexicographical(Comparator<T> comparator) { 066 return new LexicographicalOrdering<S>(checkNotNull(comparator)); 067 } 068 069 /** 070 * Returns {@code true} if each element in {@code iterable} after the first is greater than or 071 * equal to the element that preceded it, according to the specified comparator. Note that this is 072 * always true when the iterable has fewer than two elements. 073 */ 074 @Beta 075 public static <T> boolean isInOrder(Iterable<? extends T> iterable, Comparator<T> comparator) { 076 checkNotNull(comparator); 077 Iterator<? extends T> it = iterable.iterator(); 078 if (it.hasNext()) { 079 T prev = it.next(); 080 while (it.hasNext()) { 081 T next = it.next(); 082 if (comparator.compare(prev, next) > 0) { 083 return false; 084 } 085 prev = next; 086 } 087 } 088 return true; 089 } 090 091 /** 092 * Returns {@code true} if each element in {@code iterable} after the first is <i>strictly</i> 093 * greater than the element that preceded it, according to the specified comparator. Note that 094 * this is always true when the iterable has fewer than two elements. 095 */ 096 @Beta 097 public static <T> 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 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}