001 /*
002 * Copyright (C) 2007 Google Inc.
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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkNotNull;
020
021 import com.google.common.annotations.GwtCompatible;
022 import com.google.common.annotations.VisibleForTesting;
023 import com.google.common.base.Function;
024
025 import java.util.Collections;
026 import java.util.Comparator;
027 import java.util.HashSet;
028 import java.util.Iterator;
029 import java.util.List;
030 import java.util.Map;
031 import java.util.NoSuchElementException;
032 import java.util.SortedMap;
033 import java.util.SortedSet;
034 import java.util.concurrent.atomic.AtomicInteger;
035
036 /**
037 * A comparator with added methods to support common functions. For example:
038 * <pre> {@code
039 *
040 * if (Ordering.from(comparator).reverse().isOrdered(list)) { ... }}</pre>
041 *
042 * <p>The {@link #from(Comparator)} method returns the equivalent {@code
043 * Ordering} instance for a pre-existing comparator. You can also skip the
044 * comparator step and extend {@code Ordering} directly: <pre> {@code
045 *
046 * Ordering<String> byLengthOrdering = new Ordering<String>() {
047 * public int compare(String left, String right) {
048 * return Ints.compare(left.length(), right.length());
049 * }
050 * };}</pre>
051 *
052 * Except as noted, the orderings returned by the factory methods of this
053 * class are serializable if and only if the provided instances that back them
054 * are. For example, if {@code ordering} and {@code function} can themselves be
055 * serialized, then {@code ordering.onResultOf(function)} can as well.
056 *
057 * @author Jesse Wilson
058 * @author Kevin Bourrillion
059 * @since 2 (imported from Google Collections Library)
060 */
061 @GwtCompatible
062 public abstract class Ordering<T> implements Comparator<T> {
063 // Static factories
064
065 /**
066 * Returns a serializable ordering that uses the natural order of the values.
067 * The ordering throws a {@link NullPointerException} when passed a null
068 * parameter.
069 *
070 * <p>The type specification is {@code <C extends Comparable>}, instead of
071 * the technically correct {@code <C extends Comparable<? super C>>}, to
072 * support legacy types from before Java 5.
073 */
074 @GwtCompatible(serializable = true)
075 @SuppressWarnings("unchecked") // TODO: the right way to explain this??
076 public static <C extends Comparable> Ordering<C> natural() {
077 return (Ordering) NaturalOrdering.INSTANCE;
078 }
079
080 /**
081 * Returns an ordering for a pre-existing {@code comparator}. Note
082 * that if the comparator is not pre-existing, and you don't require
083 * serialization, you can subclass {@code Ordering} and implement its
084 * {@link #compare(Object, Object) compare} method instead.
085 *
086 * @param comparator the comparator that defines the order
087 */
088 @GwtCompatible(serializable = true)
089 public static <T> Ordering<T> from(Comparator<T> comparator) {
090 return (comparator instanceof Ordering)
091 ? (Ordering<T>) comparator
092 : new ComparatorOrdering<T>(comparator);
093 }
094
095 /**
096 * Simply returns its argument.
097 *
098 * @deprecated no need to use this
099 */
100 @GwtCompatible(serializable = true)
101 @Deprecated public static <T> Ordering<T> from(Ordering<T> ordering) {
102 return checkNotNull(ordering);
103 }
104
105 /**
106 * Returns an ordering that compares objects according to the order in
107 * which they appear in the given list. Only objects present in the list
108 * (according to {@link Object#equals}) may be compared. This comparator
109 * imposes a "partial ordering" over the type {@code T}. Subsequent changes
110 * to the {@code valuesInOrder} list will have no effect on the returned
111 * comparator. Null values in the list are not supported.
112 *
113 * <p>The returned comparator throws an {@link ClassCastException} when it
114 * receives an input parameter that isn't among the provided values.
115 *
116 * <p>The generated comparator is serializable if all the provided values are
117 * serializable.
118 *
119 * @param valuesInOrder the values that the returned comparator will be able
120 * to compare, in the order the comparator should induce
121 * @return the comparator described above
122 * @throws NullPointerException if any of the provided values is null
123 * @throws IllegalArgumentException if {@code valuesInOrder} contains any
124 * duplicate values (according to {@link Object#equals})
125 */
126 @GwtCompatible(serializable = true)
127 public static <T> Ordering<T> explicit(List<T> valuesInOrder) {
128 return new ExplicitOrdering<T>(valuesInOrder);
129 }
130
131 /**
132 * Returns an ordering that compares objects according to the order in
133 * which they are given to this method. Only objects present in the argument
134 * list (according to {@link Object#equals}) may be compared. This comparator
135 * imposes a "partial ordering" over the type {@code T}. Null values in the
136 * argument list are not supported.
137 *
138 * <p>The returned comparator throws a {@link ClassCastException} when it
139 * receives an input parameter that isn't among the provided values.
140 *
141 * <p>The generated comparator is serializable if all the provided values are
142 * serializable.
143 *
144 * @param leastValue the value which the returned comparator should consider
145 * the "least" of all values
146 * @param remainingValuesInOrder the rest of the values that the returned
147 * comparator will be able to compare, in the order the comparator should
148 * follow
149 * @return the comparator described above
150 * @throws NullPointerException if any of the provided values is null
151 * @throws IllegalArgumentException if any duplicate values (according to
152 * {@link Object#equals(Object)}) are present among the method arguments
153 */
154 @GwtCompatible(serializable = true)
155 public static <T> Ordering<T> explicit(
156 T leastValue, T... remainingValuesInOrder) {
157 return explicit(Lists.asList(leastValue, remainingValuesInOrder));
158 }
159
160 /**
161 * Exception thrown by a {@link Ordering#explicit(List)} or {@link
162 * Ordering#explicit(Object, Object[])} comparator when comparing a value
163 * outside the set of values it can compare. Extending {@link
164 * ClassCastException} may seem odd, but it is required.
165 */
166 // TODO: consider making this exception type public. or consider getting rid
167 // of it.
168 @VisibleForTesting
169 static class IncomparableValueException extends ClassCastException {
170 final Object value;
171
172 IncomparableValueException(Object value) {
173 super("Cannot compare value: " + value);
174 this.value = value;
175 }
176
177 private static final long serialVersionUID = 0;
178 }
179
180 /**
181 * Returns an arbitrary ordering over all objects, for which {@code compare(a,
182 * b) == 0} implies {@code a == b} (identity equality). There is no meaning
183 * whatsoever to the order imposed, but it is constant for the life of the VM.
184 *
185 * <p>Because the ordering is identity-based, it is not "consistent with
186 * {@link Object#equals(Object)}" as defined by {@link Comparator}. Use
187 * caution when building a {@link SortedSet} or {@link SortedMap} from it, as
188 * the resulting collection will not behave exactly according to spec.
189 *
190 * <p>This ordering is not serializable, as its implementation relies on
191 * {@link System#identityHashCode(Object)}, so its behavior cannot be
192 * preserved across serialization.
193 *
194 * @since 2
195 */
196 public static Ordering<Object> arbitrary() {
197 return ArbitraryOrderingHolder.ARBITRARY_ORDERING;
198 }
199
200 private static class ArbitraryOrderingHolder {
201 static final Ordering<Object> ARBITRARY_ORDERING = new ArbitraryOrdering();
202 }
203
204 @VisibleForTesting static class ArbitraryOrdering extends Ordering<Object> {
205 private Map<Object, Integer> uids =
206 Platform.tryWeakKeys(new MapMaker()).makeComputingMap(
207 new Function<Object, Integer>() {
208 final AtomicInteger counter = new AtomicInteger(0);
209 public Integer apply(Object from) {
210 return counter.getAndIncrement();
211 }
212 });
213
214 @Override public int compare(Object left, Object right) {
215 if (left == right) {
216 return 0;
217 }
218 int leftCode = identityHashCode(left);
219 int rightCode = identityHashCode(right);
220 if (leftCode != rightCode) {
221 return leftCode < rightCode ? -1 : 1;
222 }
223
224 // identityHashCode collision (rare, but not as rare as you'd think)
225 int result = uids.get(left).compareTo(uids.get(right));
226 if (result == 0) {
227 throw new AssertionError(); // extremely, extremely unlikely.
228 }
229 return result;
230 }
231
232 @Override public String toString() {
233 return "Ordering.arbitrary()";
234 }
235
236 /*
237 * We need to be able to mock identityHashCode() calls for tests, because it
238 * can take 1-10 seconds to find colliding objects. Mocking frameworks that
239 * can do magic to mock static method calls still can't do so for a system
240 * class, so we need the indirection. In production, Hotspot should still
241 * recognize that the call is 1-morphic and should still be willing to
242 * inline it if necessary.
243 */
244 int identityHashCode(Object object) {
245 return System.identityHashCode(object);
246 }
247 }
248
249 /**
250 * Returns an ordering that compares objects by the natural ordering of their
251 * string representations as returned by {@code toString()}. It does not
252 * support null values.
253 *
254 * <p>The comparator is serializable.
255 */
256 @GwtCompatible(serializable = true)
257 public static Ordering<Object> usingToString() {
258 return UsingToStringOrdering.INSTANCE;
259 }
260
261 /**
262 * Returns an ordering which tries each given comparator in order until a
263 * non-zero result is found, returning that result, and returning zero only if
264 * all comparators return zero. The returned ordering is based on the state of
265 * the {@code comparators} iterable at the time it was provided to this
266 * method.
267 *
268 * <p>The returned ordering is equivalent to that produced using {@code
269 * Ordering.from(comp1).compound(comp2).compound(comp3) . . .}.
270 *
271 * <p><b>Warning:</b> Supplying an argument with undefined iteration order,
272 * such as a {@link HashSet}, will produce non-deterministic results.
273 *
274 * @param comparators the comparators to try in order
275 */
276 @GwtCompatible(serializable = true)
277 public static <T> Ordering<T> compound(
278 Iterable<? extends Comparator<? super T>> comparators) {
279 return new CompoundOrdering<T>(comparators);
280 }
281
282 /**
283 * Constructs a new instance of this class (only invokable by the subclass
284 * constructor, typically implicit).
285 */
286 protected Ordering() {}
287
288 // Non-static factories
289
290 /**
291 * Returns an ordering which first uses the ordering {@code this}, but which
292 * in the event of a "tie", then delegates to {@code secondaryComparator}.
293 * For example, to sort a bug list first by status and second by priority, you
294 * might use {@code byStatus.compound(byPriority)}. For a compound ordering
295 * with three or more components, simply chain multiple calls to this method.
296 *
297 * <p>An ordering produced by this method, or a chain of calls to this method,
298 * is equivalent to one created using {@link Ordering#compound(Iterable)} on
299 * the same component comparators.
300 */
301 @GwtCompatible(serializable = true)
302 public <U extends T> Ordering<U> compound(
303 Comparator<? super U> secondaryComparator) {
304 return new CompoundOrdering<U>(this, checkNotNull(secondaryComparator));
305 }
306
307 /**
308 * Returns the reverse of this ordering; the {@code Ordering} equivalent to
309 * {@link Collections#reverseOrder(Comparator)}.
310 */
311 // type parameter <S> lets us avoid the extra <String> in statements like:
312 // Ordering<String> o = Ordering.<String>natural().reverse();
313 @GwtCompatible(serializable = true)
314 public <S extends T> Ordering<S> reverse() {
315 return new ReverseOrdering<S>(this);
316 }
317
318 /**
319 * Returns a new ordering on {@code F} which orders elements by first applying
320 * a function to them, then comparing those results using {@code this}. For
321 * example, to compare objects by their string forms, in a case-insensitive
322 * manner, use: <pre> {@code
323 *
324 * Ordering.from(String.CASE_INSENSITIVE_ORDER)
325 * .onResultOf(Functions.toStringFunction())}</pre>
326 */
327 @GwtCompatible(serializable = true)
328 public <F> Ordering<F> onResultOf(Function<F, ? extends T> function) {
329 return new ByFunctionOrdering<F, T>(function, this);
330 }
331
332 /**
333 * Returns a new ordering which sorts iterables by comparing corresponding
334 * elements pairwise until a nonzero result is found; imposes "dictionary
335 * order". If the end of one iterable is reached, but not the other, the
336 * shorter iterable is considered to be less than the longer one. For example,
337 * a lexicographical natural ordering over integers considers {@code
338 * [] < [1] < [1, 1] < [1, 2] < [2]}.
339 *
340 * <p>Note that {@code ordering.lexicographical().reverse()} is not
341 * equivalent to {@code ordering.reverse().lexicographical()} (consider how
342 * each would order {@code [1]} and {@code [1, 1]}).
343 *
344 * @since 2
345 */
346 @GwtCompatible(serializable = true)
347 // type parameter <S> lets us avoid the extra <String> in statements like:
348 // Ordering<Iterable<String>> o =
349 // Ordering.<String>natural().lexicographical();
350 public <S extends T> Ordering<Iterable<S>> lexicographical() {
351 /*
352 * Note that technically the returned ordering should be capable of
353 * handling not just {@code Iterable<S>} instances, but also any {@code
354 * Iterable<? extends S>}. However, the need for this comes up so rarely
355 * that it doesn't justify making everyone else deal with the very ugly
356 * wildcard.
357 */
358 return new LexicographicalOrdering<S>(this);
359 }
360
361 /**
362 * Returns an ordering that treats {@code null} as less than all other values
363 * and uses {@code this} to compare non-null values.
364 */
365 // type parameter <S> lets us avoid the extra <String> in statements like:
366 // Ordering<String> o = Ordering.<String>natural().nullsFirst();
367 @GwtCompatible(serializable = true)
368 public <S extends T> Ordering<S> nullsFirst() {
369 return new NullsFirstOrdering<S>(this);
370 }
371
372 /**
373 * Returns an ordering that treats {@code null} as greater than all other
374 * values and uses this ordering to compare non-null values.
375 */
376 // type parameter <S> lets us avoid the extra <String> in statements like:
377 // Ordering<String> o = Ordering.<String>natural().nullsLast();
378 @GwtCompatible(serializable = true)
379 public <S extends T> Ordering<S> nullsLast() {
380 return new NullsLastOrdering<S>(this);
381 }
382
383 // Regular instance methods
384
385 /**
386 * {@link Collections#binarySearch(List, Object, Comparator) Searches}
387 * {@code sortedList} for {@code key} using the binary search algorithm. The
388 * list must be sorted using this ordering.
389 *
390 * @param sortedList the list to be searched
391 * @param key the key to be searched for
392 */
393 public int binarySearch(List<? extends T> sortedList, T key) {
394 return Collections.binarySearch(sortedList, key, this);
395 }
396
397 /**
398 * Returns a copy of the given iterable sorted by this ordering. The input is
399 * not modified. The returned list is modifiable, serializable, and has random
400 * access.
401 *
402 * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard
403 * elements that are duplicates according to the comparator. The sort
404 * performed is <i>stable</i>, meaning that such elements will appear in the
405 * resulting list in the same order they appeared in the input.
406 *
407 * @param iterable the elements to be copied and sorted
408 * @return a new list containing the given elements in sorted order
409 */
410 public <E extends T> List<E> sortedCopy(Iterable<E> iterable) {
411 List<E> list = Lists.newArrayList(iterable);
412 Collections.sort(list, this);
413 return list;
414 }
415
416 /**
417 * Returns an <i>immutable</i> copy of the given iterable sorted by this
418 * ordering. The input is not modified.
419 *
420 * <p>Unlike {@link Sets#newTreeSet(Iterable)}, this method does not discard
421 * elements that are duplicates according to the comparator. The sort
422 * performed is <i>stable</i>, meaning that such elements will appear in the
423 * resulting list in the same order they appeared in the input.
424 *
425 * @param iterable the elements to be copied and sorted
426 * @return a new immutable list containing the given elements in sorted order
427 * @throws NullPointerException if {@code iterable} or any of its elements is
428 * null
429 * @since 3
430 */
431 public <E extends T> ImmutableList<E> immutableSortedCopy(
432 Iterable<E> iterable) {
433 return ImmutableList.copyOf(sortedCopy(iterable));
434 }
435
436 /**
437 * Returns {@code true} if each element in {@code iterable} after the first is
438 * greater than or equal to the element that preceded it, according to this
439 * ordering. Note that this is always true when the iterable has fewer than
440 * two elements.
441 */
442 public boolean isOrdered(Iterable<? extends T> iterable) {
443 Iterator<? extends T> it = iterable.iterator();
444 if (it.hasNext()) {
445 T prev = it.next();
446 while (it.hasNext()) {
447 T next = it.next();
448 if (compare(prev, next) > 0) {
449 return false;
450 }
451 prev = next;
452 }
453 }
454 return true;
455 }
456
457 /**
458 * Returns {@code true} if each element in {@code iterable} after the first is
459 * <i>strictly</i> greater than the element that preceded it, according to
460 * this ordering. Note that this is always true when the iterable has fewer
461 * than two elements.
462 */
463 public boolean isStrictlyOrdered(Iterable<? extends T> iterable) {
464 Iterator<? extends T> it = iterable.iterator();
465 if (it.hasNext()) {
466 T prev = it.next();
467 while (it.hasNext()) {
468 T next = it.next();
469 if (compare(prev, next) >= 0) {
470 return false;
471 }
472 prev = next;
473 }
474 }
475 return true;
476 }
477
478 /**
479 * Returns the largest of the specified values according to this ordering. If
480 * there are multiple largest values, the first of those is returned.
481 *
482 * @param iterable the iterable whose maximum element is to be determined
483 * @throws NoSuchElementException if {@code iterable} is empty
484 * @throws ClassCastException if the parameters are not <i>mutually
485 * comparable</i> under this ordering.
486 */
487 public <E extends T> E max(Iterable<E> iterable) {
488 Iterator<E> iterator = iterable.iterator();
489
490 // let this throw NoSuchElementException as necessary
491 E maxSoFar = iterator.next();
492
493 while (iterator.hasNext()) {
494 maxSoFar = max(maxSoFar, iterator.next());
495 }
496
497 return maxSoFar;
498 }
499
500 /**
501 * Returns the largest of the specified values according to this ordering. If
502 * there are multiple largest values, the first of those is returned.
503 *
504 * @param a value to compare, returned if greater than or equal to the rest.
505 * @param b value to compare
506 * @param c value to compare
507 * @param rest values to compare
508 * @throws ClassCastException if the parameters are not <i>mutually
509 * comparable</i> under this ordering.
510 */
511 public <E extends T> E max(E a, E b, E c, E... rest) {
512 E maxSoFar = max(max(a, b), c);
513
514 for (E r : rest) {
515 maxSoFar = max(maxSoFar, r);
516 }
517
518 return maxSoFar;
519 }
520
521 /**
522 * Returns the larger of the two values according to this ordering. If the
523 * values compare as 0, the first is returned.
524 *
525 * <p><b>Implementation note:</b> this method is invoked by the default
526 * implementations of the other {@code max} overloads, so overriding it will
527 * affect their behavior.
528 *
529 * @param a value to compare, returned if greater than or equal to b.
530 * @param b value to compare.
531 * @throws ClassCastException if the parameters are not <i>mutually
532 * comparable</i> under this ordering.
533 */
534 public <E extends T> E max(E a, E b) {
535 return compare(a, b) >= 0 ? a : b;
536 }
537
538 /**
539 * Returns the smallest of the specified values according to this ordering. If
540 * there are multiple smallest values, the first of those is returned.
541 *
542 * @param iterable the iterable whose minimum element is to be determined
543 * @throws NoSuchElementException if {@code iterable} is empty
544 * @throws ClassCastException if the parameters are not <i>mutually
545 * comparable</i> under this ordering.
546 */
547 public <E extends T> E min(Iterable<E> iterable) {
548 Iterator<E> iterator = iterable.iterator();
549
550 // let this throw NoSuchElementException as necessary
551 E minSoFar = iterator.next();
552
553 while (iterator.hasNext()) {
554 minSoFar = min(minSoFar, iterator.next());
555 }
556
557 return minSoFar;
558 }
559
560 /**
561 * Returns the smallest of the specified values according to this ordering. If
562 * there are multiple smallest values, the first of those is returned.
563 *
564 * @param a value to compare, returned if less than or equal to the rest.
565 * @param b value to compare
566 * @param c value to compare
567 * @param rest values to compare
568 * @throws ClassCastException if the parameters are not <i>mutually
569 * comparable</i> under this ordering.
570 */
571 public <E extends T> E min(E a, E b, E c, E... rest) {
572 E minSoFar = min(min(a, b), c);
573
574 for (E r : rest) {
575 minSoFar = min(minSoFar, r);
576 }
577
578 return minSoFar;
579 }
580
581 /**
582 * Returns the smaller of the two values according to this ordering. If the
583 * values compare as 0, the first is returned.
584 *
585 * <p><b>Implementation note:</b> this method is invoked by the default
586 * implementations of the other {@code min} overloads, so overriding it will
587 * affect their behavior.
588 *
589 * @param a value to compare, returned if less than or equal to b.
590 * @param b value to compare.
591 * @throws ClassCastException if the parameters are not <i>mutually
592 * comparable</i> under this ordering.
593 */
594 public <E extends T> E min(E a, E b) {
595 return compare(a, b) <= 0 ? a : b;
596 }
597
598 // Never make these public
599 static final int LEFT_IS_GREATER = 1;
600 static final int RIGHT_IS_GREATER = -1;
601 }