1 /*
2  * Copyright (c) 1997, 2021, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.  Oracle designates this
8  * particular file as subject to the "Classpath" exception as provided
9  * by Oracle in the LICENSE file that accompanied this code.
10  *
11  * This code is distributed in the hope that it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14  * version 2 for more details (a copy is included in the LICENSE file that
15  * accompanied this code).
16  *
17  * You should have received a copy of the GNU General Public License version
18  * 2 along with this work; if not, write to the Free Software Foundation,
19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20  *
21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22  * or visit www.oracle.com if you need additional information or have any
23  * questions.
24  */
25 
26 package java.util;
27 
28 import java.io.Serializable;
29 import java.util.function.Function;
30 import java.util.function.ToIntFunction;
31 import java.util.function.ToLongFunction;
32 import java.util.function.ToDoubleFunction;
33 import java.util.Comparators;
34 
35 /**
36  * A comparison function, which imposes a <i>total ordering</i> on
37  * some collection of objects.  Comparators can be passed to a sort
38  * method (such as {@link Collections#sort(List,Comparator)
39  * Collections.sort} or {@link Arrays#sort(Object[],Comparator)
40  * Arrays.sort}) to allow precise control over the sort order.
41  * Comparators can also be used to control the order of certain data
42  * structures (such as {@linkplain SortedSet sorted sets} or
43  * {@linkplain SortedMap sorted maps}), or to provide an ordering for
44  * collections of objects that don't have a {@linkplain Comparable
45  * natural ordering}.<p>
46  *
47  * The ordering imposed by a comparator {@code c} on a set of elements
48  * {@code S} is said to be <i>consistent with equals</i> if and only if
49  * {@code c.compare(e1, e2)==0} has the same boolean value as
50  * {@code e1.equals(e2)} for every {@code e1} and {@code e2} in
51  * {@code S}.<p>
52  *
53  * Caution should be exercised when using a comparator capable of imposing an
54  * ordering inconsistent with equals to order a sorted set (or sorted map).
55  * Suppose a sorted set (or sorted map) with an explicit comparator {@code c}
56  * is used with elements (or keys) drawn from a set {@code S}.  If the
57  * ordering imposed by {@code c} on {@code S} is inconsistent with equals,
58  * the sorted set (or sorted map) will behave "strangely."  In particular the
59  * sorted set (or sorted map) will violate the general contract for set (or
60  * map), which is defined in terms of {@code equals}.<p>
61  *
62  * For example, suppose one adds two elements {@code a} and {@code b} such that
63  * {@code (a.equals(b) && c.compare(a, b) != 0)}
64  * to an empty {@code TreeSet} with comparator {@code c}.
65  * The second {@code add} operation will return
66  * true (and the size of the tree set will increase) because {@code a} and
67  * {@code b} are not equivalent from the tree set's perspective, even though
68  * this is contrary to the specification of the
69  * {@link Set#add Set.add} method.<p>
70  *
71  * Note: It is generally a good idea for comparators to also implement
72  * {@code java.io.Serializable}, as they may be used as ordering methods in
73  * serializable data structures (like {@link TreeSet}, {@link TreeMap}).  In
74  * order for the data structure to serialize successfully, the comparator (if
75  * provided) must implement {@code Serializable}.<p>
76  *
77  * For the mathematically inclined, the <i>relation</i> that defines the
78  * <i>imposed ordering</i> that a given comparator {@code c} imposes on a
79  * given set of objects {@code S} is:<pre>
80  *       {(x, y) such that c.compare(x, y) &lt;= 0}.
81  * </pre> The <i>quotient</i> for this total order is:<pre>
82  *       {(x, y) such that c.compare(x, y) == 0}.
83  * </pre>
84  *
85  * It follows immediately from the contract for {@code compare} that the
86  * quotient is an <i>equivalence relation</i> on {@code S}, and that the
87  * imposed ordering is a <i>total order</i> on {@code S}.  When we say that
88  * the ordering imposed by {@code c} on {@code S} is <i>consistent with
89  * equals</i>, we mean that the quotient for the ordering is the equivalence
90  * relation defined by the objects' {@link Object#equals(Object)
91  * equals(Object)} method(s):<pre>
92  *     {(x, y) such that x.equals(y)}. </pre>
93  *
94  * In other words, when the imposed ordering is consistent with
95  * equals, the equivalence classes defined by the equivalence relation
96  * of the {@code equals} method and the equivalence classes defined by
97  * the quotient of the {@code compare} method are the same.
98 
99  * <p>Unlike {@code Comparable}, a comparator may optionally permit
100  * comparison of null arguments, while maintaining the requirements for
101  * an equivalence relation.
102  *
103  * <p>This interface is a member of the
104  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
105  * Java Collections Framework</a>.
106  *
107  * @param <T> the type of objects that may be compared by this comparator
108  *
109  * @author  Josh Bloch
110  * @author  Neal Gafter
111  * @see Comparable
112  * @see java.io.Serializable
113  * @since 1.2
114  */
115 @FunctionalInterface
116 public interface Comparator<T> {
117     /**
118      * Compares its two arguments for order.  Returns a negative integer,
119      * zero, or a positive integer as the first argument is less than, equal
120      * to, or greater than the second.<p>
121      *
122      * The implementor must ensure that {@link Integer#signum
123      * signum}{@code (compare(x, y)) == -signum(compare(y, x))} for
124      * all {@code x} and {@code y}.  (This implies that {@code
125      * compare(x, y)} must throw an exception if and only if {@code
126      * compare(y, x)} throws an exception.)<p>
127      *
128      * The implementor must also ensure that the relation is transitive:
129      * {@code ((compare(x, y)>0) && (compare(y, z)>0))} implies
130      * {@code compare(x, z)>0}.<p>
131      *
132      * Finally, the implementor must ensure that {@code compare(x,
133      * y)==0} implies that {@code signum(compare(x,
134      * z))==signum(compare(y, z))} for all {@code z}.
135      *
136      * @apiNote
137      * It is generally the case, but <i>not</i> strictly required that
138      * {@code (compare(x, y)==0) == (x.equals(y))}.  Generally speaking,
139      * any comparator that violates this condition should clearly indicate
140      * this fact.  The recommended language is "Note: this comparator
141      * imposes orderings that are inconsistent with equals."
142      *
143      * @param o1 the first object to be compared.
144      * @param o2 the second object to be compared.
145      * @return a negative integer, zero, or a positive integer as the
146      *         first argument is less than, equal to, or greater than the
147      *         second.
148      * @throws NullPointerException if an argument is null and this
149      *         comparator does not permit null arguments
150      * @throws ClassCastException if the arguments' types prevent them from
151      *         being compared by this comparator.
152      */
compare(T o1, T o2)153     int compare(T o1, T o2);
154 
155     /**
156      * Indicates whether some other object is &quot;equal to&quot;
157      * this comparator.  This method must obey the general contract of
158      * {@link Object#equals(Object)}.  Additionally, this method can
159      * return {@code true} <i>only</i> if the specified object is also
160      * a comparator and it imposes the same ordering as this
161      * comparator.  Thus, {@code comp1.equals(comp2)} implies that
162      * {@link Integer#signum signum}{@code (comp1.compare(o1,
163      * o2))==signum(comp2.compare(o1, o2))} for every object reference
164      * {@code o1} and {@code o2}.<p>
165      *
166      * Note that it is <i>always</i> safe <i>not</i> to override
167      * {@code Object.equals(Object)}.  However, overriding this method may,
168      * in some cases, improve performance by allowing programs to determine
169      * that two distinct comparators impose the same order.
170      *
171      * @param   obj   the reference object with which to compare.
172      * @return  {@code true} only if the specified object is also
173      *          a comparator and it imposes the same ordering as this
174      *          comparator.
175      * @see Object#equals(Object)
176      * @see Object#hashCode()
177      */
equals(Object obj)178     boolean equals(Object obj);
179 
180     /**
181      * Returns a comparator that imposes the reverse ordering of this
182      * comparator.
183      *
184      * @return a comparator that imposes the reverse ordering of this
185      *         comparator.
186      * @since 1.8
187      */
reversed()188     default Comparator<T> reversed() {
189         return Collections.reverseOrder(this);
190     }
191 
192     /**
193      * Returns a lexicographic-order comparator with another comparator.
194      * If this {@code Comparator} considers two elements equal, i.e.
195      * {@code compare(a, b) == 0}, {@code other} is used to determine the order.
196      *
197      * <p>The returned comparator is serializable if the specified comparator
198      * is also serializable.
199      *
200      * @apiNote
201      * For example, to sort a collection of {@code String} based on the length
202      * and then case-insensitive natural ordering, the comparator can be
203      * composed using following code,
204      *
205      * <pre>{@code
206      *     Comparator<String> cmp = Comparator.comparingInt(String::length)
207      *             .thenComparing(String.CASE_INSENSITIVE_ORDER);
208      * }</pre>
209      *
210      * @param  other the other comparator to be used when this comparator
211      *         compares two objects that are equal.
212      * @return a lexicographic-order comparator composed of this and then the
213      *         other comparator
214      * @throws NullPointerException if the argument is null.
215      * @since 1.8
216      */
thenComparing(Comparator<? super T> other)217     default Comparator<T> thenComparing(Comparator<? super T> other) {
218         Objects.requireNonNull(other);
219         return (Comparator<T> & Serializable) (c1, c2) -> {
220             int res = compare(c1, c2);
221             return (res != 0) ? res : other.compare(c1, c2);
222         };
223     }
224 
225     /**
226      * Returns a lexicographic-order comparator with a function that
227      * extracts a key to be compared with the given {@code Comparator}.
228      *
229      * @implSpec This default implementation behaves as if {@code
230      *           thenComparing(comparing(keyExtractor, cmp))}.
231      *
232      * @param  <U>  the type of the sort key
233      * @param  keyExtractor the function used to extract the sort key
234      * @param  keyComparator the {@code Comparator} used to compare the sort key
235      * @return a lexicographic-order comparator composed of this comparator
236      *         and then comparing on the key extracted by the keyExtractor function
237      * @throws NullPointerException if either argument is null.
238      * @see #comparing(Function, Comparator)
239      * @see #thenComparing(Comparator)
240      * @since 1.8
241      */
thenComparing( Function<? super T, ? extends U> keyExtractor, Comparator<? super U> keyComparator)242     default <U> Comparator<T> thenComparing(
243             Function<? super T, ? extends U> keyExtractor,
244             Comparator<? super U> keyComparator)
245     {
246         return thenComparing(comparing(keyExtractor, keyComparator));
247     }
248 
249     /**
250      * Returns a lexicographic-order comparator with a function that
251      * extracts a {@code Comparable} sort key.
252      *
253      * @implSpec This default implementation behaves as if {@code
254      *           thenComparing(comparing(keyExtractor))}.
255      *
256      * @param  <U>  the type of the {@link Comparable} sort key
257      * @param  keyExtractor the function used to extract the {@link
258      *         Comparable} sort key
259      * @return a lexicographic-order comparator composed of this and then the
260      *         {@link Comparable} sort key.
261      * @throws NullPointerException if the argument is null.
262      * @see #comparing(Function)
263      * @see #thenComparing(Comparator)
264      * @since 1.8
265      */
thenComparing( Function<? super T, ? extends U> keyExtractor)266     default <U extends Comparable<? super U>> Comparator<T> thenComparing(
267             Function<? super T, ? extends U> keyExtractor)
268     {
269         return thenComparing(comparing(keyExtractor));
270     }
271 
272     /**
273      * Returns a lexicographic-order comparator with a function that
274      * extracts an {@code int} sort key.
275      *
276      * @implSpec This default implementation behaves as if {@code
277      *           thenComparing(comparingInt(keyExtractor))}.
278      *
279      * @param  keyExtractor the function used to extract the integer sort key
280      * @return a lexicographic-order comparator composed of this and then the
281      *         {@code int} sort key
282      * @throws NullPointerException if the argument is null.
283      * @see #comparingInt(ToIntFunction)
284      * @see #thenComparing(Comparator)
285      * @since 1.8
286      */
thenComparingInt(ToIntFunction<? super T> keyExtractor)287     default Comparator<T> thenComparingInt(ToIntFunction<? super T> keyExtractor) {
288         return thenComparing(comparingInt(keyExtractor));
289     }
290 
291     /**
292      * Returns a lexicographic-order comparator with a function that
293      * extracts a {@code long} sort key.
294      *
295      * @implSpec This default implementation behaves as if {@code
296      *           thenComparing(comparingLong(keyExtractor))}.
297      *
298      * @param  keyExtractor the function used to extract the long sort key
299      * @return a lexicographic-order comparator composed of this and then the
300      *         {@code long} sort key
301      * @throws NullPointerException if the argument is null.
302      * @see #comparingLong(ToLongFunction)
303      * @see #thenComparing(Comparator)
304      * @since 1.8
305      */
thenComparingLong(ToLongFunction<? super T> keyExtractor)306     default Comparator<T> thenComparingLong(ToLongFunction<? super T> keyExtractor) {
307         return thenComparing(comparingLong(keyExtractor));
308     }
309 
310     /**
311      * Returns a lexicographic-order comparator with a function that
312      * extracts a {@code double} sort key.
313      *
314      * @implSpec This default implementation behaves as if {@code
315      *           thenComparing(comparingDouble(keyExtractor))}.
316      *
317      * @param  keyExtractor the function used to extract the double sort key
318      * @return a lexicographic-order comparator composed of this and then the
319      *         {@code double} sort key
320      * @throws NullPointerException if the argument is null.
321      * @see #comparingDouble(ToDoubleFunction)
322      * @see #thenComparing(Comparator)
323      * @since 1.8
324      */
thenComparingDouble(ToDoubleFunction<? super T> keyExtractor)325     default Comparator<T> thenComparingDouble(ToDoubleFunction<? super T> keyExtractor) {
326         return thenComparing(comparingDouble(keyExtractor));
327     }
328 
329     /**
330      * Returns a comparator that imposes the reverse of the <em>natural
331      * ordering</em>.
332      *
333      * <p>The returned comparator is serializable and throws {@link
334      * NullPointerException} when comparing {@code null}.
335      *
336      * @param  <T> the {@link Comparable} type of element to be compared
337      * @return a comparator that imposes the reverse of the <i>natural
338      *         ordering</i> on {@code Comparable} objects.
339      * @see Comparable
340      * @since 1.8
341      */
reverseOrder()342     public static <T extends Comparable<? super T>> Comparator<T> reverseOrder() {
343         return Collections.reverseOrder();
344     }
345 
346     /**
347      * Returns a comparator that compares {@link Comparable} objects in natural
348      * order.
349      *
350      * <p>The returned comparator is serializable and throws {@link
351      * NullPointerException} when comparing {@code null}.
352      *
353      * @param  <T> the {@link Comparable} type of element to be compared
354      * @return a comparator that imposes the <i>natural ordering</i> on {@code
355      *         Comparable} objects.
356      * @see Comparable
357      * @since 1.8
358      */
359     @SuppressWarnings("unchecked")
naturalOrder()360     public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
361         return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;
362     }
363 
364     /**
365      * Returns a null-friendly comparator that considers {@code null} to be
366      * less than non-null. When both are {@code null}, they are considered
367      * equal. If both are non-null, the specified {@code Comparator} is used
368      * to determine the order. If the specified comparator is {@code null},
369      * then the returned comparator considers all non-null values to be equal.
370      *
371      * <p>The returned comparator is serializable if the specified comparator
372      * is serializable.
373      *
374      * @param  <T> the type of the elements to be compared
375      * @param  comparator a {@code Comparator} for comparing non-null values
376      * @return a comparator that considers {@code null} to be less than
377      *         non-null, and compares non-null objects with the supplied
378      *         {@code Comparator}.
379      * @since 1.8
380      */
nullsFirst(Comparator<? super T> comparator)381     public static <T> Comparator<T> nullsFirst(Comparator<? super T> comparator) {
382         return new Comparators.NullComparator<>(true, comparator);
383     }
384 
385     /**
386      * Returns a null-friendly comparator that considers {@code null} to be
387      * greater than non-null. When both are {@code null}, they are considered
388      * equal. If both are non-null, the specified {@code Comparator} is used
389      * to determine the order. If the specified comparator is {@code null},
390      * then the returned comparator considers all non-null values to be equal.
391      *
392      * <p>The returned comparator is serializable if the specified comparator
393      * is serializable.
394      *
395      * @param  <T> the type of the elements to be compared
396      * @param  comparator a {@code Comparator} for comparing non-null values
397      * @return a comparator that considers {@code null} to be greater than
398      *         non-null, and compares non-null objects with the supplied
399      *         {@code Comparator}.
400      * @since 1.8
401      */
nullsLast(Comparator<? super T> comparator)402     public static <T> Comparator<T> nullsLast(Comparator<? super T> comparator) {
403         return new Comparators.NullComparator<>(false, comparator);
404     }
405 
406     /**
407      * Accepts a function that extracts a sort key from a type {@code T}, and
408      * returns a {@code Comparator<T>} that compares by that sort key using
409      * the specified {@link Comparator}.
410      *
411      * <p>The returned comparator is serializable if the specified function
412      * and comparator are both serializable.
413      *
414      * @apiNote
415      * For example, to obtain a {@code Comparator} that compares {@code
416      * Person} objects by their last name ignoring case differences,
417      *
418      * <pre>{@code
419      *     Comparator<Person> cmp = Comparator.comparing(
420      *             Person::getLastName,
421      *             String.CASE_INSENSITIVE_ORDER);
422      * }</pre>
423      *
424      * @param  <T> the type of element to be compared
425      * @param  <U> the type of the sort key
426      * @param  keyExtractor the function used to extract the sort key
427      * @param  keyComparator the {@code Comparator} used to compare the sort key
428      * @return a comparator that compares by an extracted key using the
429      *         specified {@code Comparator}
430      * @throws NullPointerException if either argument is null
431      * @since 1.8
432      */
comparing( Function<? super T, ? extends U> keyExtractor, Comparator<? super U> keyComparator)433     public static <T, U> Comparator<T> comparing(
434             Function<? super T, ? extends U> keyExtractor,
435             Comparator<? super U> keyComparator)
436     {
437         Objects.requireNonNull(keyExtractor);
438         Objects.requireNonNull(keyComparator);
439         return (Comparator<T> & Serializable)
440             (c1, c2) -> keyComparator.compare(keyExtractor.apply(c1),
441                                               keyExtractor.apply(c2));
442     }
443 
444     /**
445      * Accepts a function that extracts a {@link java.lang.Comparable
446      * Comparable} sort key from a type {@code T}, and returns a {@code
447      * Comparator<T>} that compares by that sort key.
448      *
449      * <p>The returned comparator is serializable if the specified function
450      * is also serializable.
451      *
452      * @apiNote
453      * For example, to obtain a {@code Comparator} that compares {@code
454      * Person} objects by their last name,
455      *
456      * <pre>{@code
457      *     Comparator<Person> byLastName = Comparator.comparing(Person::getLastName);
458      * }</pre>
459      *
460      * @param  <T> the type of element to be compared
461      * @param  <U> the type of the {@code Comparable} sort key
462      * @param  keyExtractor the function used to extract the {@link
463      *         Comparable} sort key
464      * @return a comparator that compares by an extracted key
465      * @throws NullPointerException if the argument is null
466      * @since 1.8
467      */
comparing( Function<? super T, ? extends U> keyExtractor)468     public static <T, U extends Comparable<? super U>> Comparator<T> comparing(
469             Function<? super T, ? extends U> keyExtractor)
470     {
471         Objects.requireNonNull(keyExtractor);
472         return (Comparator<T> & Serializable)
473             (c1, c2) -> keyExtractor.apply(c1).compareTo(keyExtractor.apply(c2));
474     }
475 
476     /**
477      * Accepts a function that extracts an {@code int} sort key from a type
478      * {@code T}, and returns a {@code Comparator<T>} that compares by that
479      * sort key.
480      *
481      * <p>The returned comparator is serializable if the specified function
482      * is also serializable.
483      *
484      * @param  <T> the type of element to be compared
485      * @param  keyExtractor the function used to extract the integer sort key
486      * @return a comparator that compares by an extracted key
487      * @see #comparing(Function)
488      * @throws NullPointerException if the argument is null
489      * @since 1.8
490      */
comparingInt(ToIntFunction<? super T> keyExtractor)491     public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
492         Objects.requireNonNull(keyExtractor);
493         return (Comparator<T> & Serializable)
494             (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
495     }
496 
497     /**
498      * Accepts a function that extracts a {@code long} sort key from a type
499      * {@code T}, and returns a {@code Comparator<T>} that compares by that
500      * sort key.
501      *
502      * <p>The returned comparator is serializable if the specified function is
503      * also serializable.
504      *
505      * @param  <T> the type of element to be compared
506      * @param  keyExtractor the function used to extract the long sort key
507      * @return a comparator that compares by an extracted key
508      * @see #comparing(Function)
509      * @throws NullPointerException if the argument is null
510      * @since 1.8
511      */
comparingLong(ToLongFunction<? super T> keyExtractor)512     public static <T> Comparator<T> comparingLong(ToLongFunction<? super T> keyExtractor) {
513         Objects.requireNonNull(keyExtractor);
514         return (Comparator<T> & Serializable)
515             (c1, c2) -> Long.compare(keyExtractor.applyAsLong(c1), keyExtractor.applyAsLong(c2));
516     }
517 
518     /**
519      * Accepts a function that extracts a {@code double} sort key from a type
520      * {@code T}, and returns a {@code Comparator<T>} that compares by that
521      * sort key.
522      *
523      * <p>The returned comparator is serializable if the specified function
524      * is also serializable.
525      *
526      * @param  <T> the type of element to be compared
527      * @param  keyExtractor the function used to extract the double sort key
528      * @return a comparator that compares by an extracted key
529      * @see #comparing(Function)
530      * @throws NullPointerException if the argument is null
531      * @since 1.8
532      */
comparingDouble(ToDoubleFunction<? super T> keyExtractor)533     public static<T> Comparator<T> comparingDouble(ToDoubleFunction<? super T> keyExtractor) {
534         Objects.requireNonNull(keyExtractor);
535         return (Comparator<T> & Serializable)
536             (c1, c2) -> Double.compare(keyExtractor.applyAsDouble(c1), keyExtractor.applyAsDouble(c2));
537     }
538 }
539