Comparators - java.util

Comparators

Both TreeSet and TreeMap store elements in sorted order. However, it is the comparator that defines precisely what “sorted order” means. By default, these classes store their elements by using what Java refers to as “natural ordering,” which is usually the ordering that you would expect (A before B, 1 before 2, and so forth). If you want to order elements a different way, then specify a Comparator when you construct the set or map. Doing so gives you the ability to govern precisely how elements are stored within sorted collections and maps.

Comparator is a generic interface that has this declaration: interface Comparator<T>

Here, T specifies the type of objects being compared.

Prior to JDK 8, the Comparator interface defined only two methods: compare( ) and equals( ). The compare( ) method, shown here, compares two elements for order:

int compare(T obj1, T obj2)

obj1 and obj2 are the objects to be compared. Normally, this method returns zero if the objects are equal. It returns a positive value if obj1 is greater than obj2. Otherwise, a negative value is returned. The method can throw a ClassCastException if the types of the objects are not compatible for comparison. By implementing compare( ), you can alter the way that objects are ordered. For example, to sort in reverse order, you can create a comparator that reverses the outcome of a comparison.

The equals( ) method, shown here, tests whether an object equals the invoking comparator:

boolean equals(object obj)

Here, obj is the object to be tested for equality. The method returns true if obj and the invoking object are both Comparator objects and use the same ordering. Otherwise, it returns false. Overriding equals( ) is not necessary, and most simple comparators will not do so.

For many years, the preceding two methods were the only methods defined by Comparator. With the release of JDK 8, the situation has dramatically changed. JDK 8 adds significant new functionality to Comparator through the use of default and static interface methods. Each is described here.

You can obtain a comparator that reverses the ordering of the comparator on which it is called by using reversed( ), shown here:

default Comparator<T> reversed( )

It returns the reverse comparator. For example, assuming a comparator that uses natural ordering for the characters A through Z, a reverse order comparator would put B before A, C before B, and so on.

A method related to reversed( ) is reverseOrder( ), shown next:

static <T extends Comparable<? super T>> Comparator<T> reverseOrder( )

It returns a comparator that reverses the natural order of the elements. Conversely, you can obtain a comparator that uses natural ordering by calling the static method

naturalOrder( ), shown next:

static <T extends Comparable<? super T>> Comparator<T> naturalOrder( )

If you want a comparator that can handle null values, use nullsFirst( ) or nullsLast( ), shown here:

static <T> Comparator<T> nullsFirst(Comparator<? super T> comp) static <T> Comparator<T> nullsLast(Comparator<? super T> comp)

The nullsFirst( ) method returns a comparator that views null values as less than other values. The nullsLast( ) method returns a comparator that views null values as greater than other values. In both cases, if the two values being compared are non-null, comp performs the comparison. If comp is passed null, then all non-null values are viewed as equivalent.

Another default method added by JDK 8 is thenComparing( ). It returns a comparator that performs a second comparison when the outcome of the first comparison indicates that the objects being compared are equal. Thus, it can be used to create a “compare by X then compare by Y” sequence. For example, when comparing cities, the first comparison might compare names, with the second comparison comparing states. (Therefore, Springfield, Illinois, would come before Springfield, Missouri, assuming normal, alphabetical order.) The thenComparing( ) method has three forms. The first, shown here, lets you specify the second comparator by passing an instance of Comparator:

default Comparator<T> thenComparing(Comparator<? super T> thenByComp)

Here, thenByComp specifies the comparator that is called if the first comparison returns equal.

The next versions of thenComparing( ) let you specify the standard functional interface Function (defined by java.util.function). They are shown here:

default <U extends Comparable<? super U> Comparator<T> thenComparing(Function<? super T, ? extends U> getKey)

default <U> Comparator<T>

thenComparing(Function<? super T, ? extends U> getKey,

                                     Comparator<? super U> keyComp)

In both, getKey refers to function that obtains the next comparison key, which is used if the first comparison returns equal. In the second version, keyComp specifies the comparator used to compare keys. (Here, and in subsequent uses, U specifies the type of the key.)

Comparator also adds the following specialized versions of “then comparing” methods for the primitive types:

default Comparator<T> thenComparingDouble(ToDoubleFunction<? super T> getKey)

default Comparator<T> thenComparingInt(ToIntFunction<? super T> getKey)

default Comparator<T> thenComparingLong(ToLongFunction<? super T> getKey)

In all methods, getKey refers to a function that obtains the next comparison key. Finally, JDK 8 adds to Comparator a method called comparing( ). It returns a

comparator that obtains its comparison key from a function passed to the method. There are two versions of comparing( ), shown here:

static <T, U extends Comparable<? super U>> Comparator<T> comparing(Function<? super T, ? extends U> getKey)

static <T, U> Comparator<T>

comparing(Function<? super T, ? extends U> getKey, Comparator<? super U> keyComp)

In both, getKey refers to a function that obtains the next comparison key. In the second version, keyComp specifies the comparator used to compare keys. Comparator also adds the following specialized versions of these methods for the primitive types:

static <T> Comparator<T> ComparingDouble(ToDoubleFunction<? super T> getKey)

static <T> Comparator<T> ComparingInt(ToIntFunction<? super T> getKey)

static <T> Comparator<T> ComparingLong(ToLongFunction<? super T> getKey)

In all methods, getKey refers to a function that obtains the next comparison key.

Using a Comparator

The following is an example that demonstrates the power of a custom comparator. It implements the compare( ) method for strings that operates in reverse of normal. Thus, it causes a tree set to be sorted in reverse order.

     //Use a custom comparator.

     import java.util.*;

     //A reverse comparator for strings.

class MyComp implements Comparator<String> {

public int compare(String aStr, String bStr) {

// Reverse the comparison.

return bStr.compareTo(aStr);

}

// No need to override equals or the default methods.

}

class CompDemo {

public static void main(String args[]) { // Create a tree set.

TreeSet<String> ts = new TreeSet<String>(new MyComp());

     //Add elements to the tree set.

     ts.add("C");

ts.add("A");

ts.add("B");

ts.add("E");

ts.add("F");

ts.add("D");

     Display the elements. for(String element : ts)

System.out.print(element + " ");

System.out.println();

}

}

As the following output shows, the tree is now sorted in reverse order:

F E D C B A

Look closely at the MyComp class, which implements Comparator by implementing compare( ). (As explained earlier, overriding equals( ) is neither necessary nor common. It is also not necessary to override the default methods added by JDK 8.) Inside compare( ), the String method compareTo( ) compares the two strings. However, bStr—not aStr— invokes compareTo( ). This causes the outcome of the comparison to be reversed.

Although the way in which the reverse order comparator is implemented by the preceding program is perfectly adequate, beginning with JDK 8, there is another way to approach a solution. It is now possible to simply call reversed( ) on a natural-order comparator. It will return an equivalent comparator, except that it runs in reverse. For example, assuming the preceding program, you can rewrite MyComp as a natural-order comparator, as shown here:

class MyComp implements Comparator<String> { public int compare(String aStr, String bStr) {

return aStr.compareTo(bStr);

}

Next, you can use the following sequence to create a TreeSet that orders its string elements in reverse:

MyComp mc = new MyComp(); // Create a comparator

// Pass a reverse order version of MyComp to TreeSet.

TreeSet<String> ts = new TreeSet<String>(mc.reversed());

If you plug this new code into the preceding program, it will produce the same results as before. In this case, there is no advantage gained by using reversed( ). However, in cases in which you need to create both a natural-order comparator and a reversed comparator, then using reversed( ) gives you an easy way to obtain the reverse-order comparator without having to code it explicitly.

Beginning with JDK 8, it is not actually necessary to create the MyComp class in the preceding examples because a lambda expression can be easily used instead. For example, you can remove the MyComp class entirely and create the string comparator by using this statement:

// Use a lambda expression to implement Comparator<String>.

 Comparator<String> mc = (aStr, bStr) -> aStr.compareTo(bStr);

One other point: in this simple example, it would also be possible to specify a reverse comparator via a lambda expression directly in the call to the TreeSet( ) constructor, as shown here:

     //Pass a reversed comparator to TreeSet() via a

     //lambda expression.

TreeSet<String> ts = new TreeSet<String>(

(aStr, bStr) -> bStr.compareTo(aStr));

By making these changes, the program is substantially shortened, as its final version shown here illustrates:

// Use a lambda expression to create a reverse comparator.

import java.util.*;

class CompDemo2 {

public static void main(String args[]) {

     //Pass a reverse comparator to TreeSet() via a

     //lambda expression.

TreeSet<String> ts = new TreeSet<String>(

(aStr, bStr) -> bStr.compareTo(aStr));

// Add elements to the tree set.

ts.add("C");

ts.add("A");

ts.add("B");

ts.add("E");

ts.add("F");

ts.add("D");

// Display the elements.

for(String element : ts)

System.out.print(element + " ");

System.out.println();

}

}

For a more practical example that uses a custom comparator, the following program is an updated version of the TreeMap program shown earlier that stores account balances. In the previous version, the accounts were sorted by name, but the sorting began with the first name. The following program sorts the accounts by last name. To do so, it uses a comparator that compares the last name of each account. This results in the map being sorted by last name.

    //Use a comparator to sort accounts by last name.

    import java.util.*;

    //Compare last whole words in two strings.

class TComp implements Comparator<String> {

public int compare(String aStr, String bStr) {

int i, j, k;

// Find index of beginning of last name.

i = aStr.lastIndexOf(' ');

j = bStr.lastIndexOf(' ');

k = aStr.substring(i).compareToIgnoreCase (bStr.substring(j));

 if(k==0) // last names match, check entire name

return aStr.compareToIgnoreCase (bStr); else

return k;

}

// No need to override equals.

}

class TreeMapDemo2 {

public static void main(String args[]) { // Create a tree map.

TreeMap<String, Double> tm = new TreeMap<String, Double>(new TComp());

     Put elements to the map. tm.put("John Doe", new Double(3434.34)); tm.put("Tom Smith", new Double(123.22));

tm.put("Jane Baker", new Double(1378.00)); tm.put("Tod Hall", new Double(99.22)); tm.put("Ralph Smith", new Double(-19.08));

     Get a set of the entries.

Set<Map.Entry<String, Double>> set = tm.entrySet();

     Display the elements. for(Map.Entry<String, Double> me : set) {

System.out.print(me.getKey() + ": "); System.out.println(me.getValue());

}

System.out.println();

     Deposit 1000 into John Doe's account. double balance = tm.get("John Doe"); tm.put("John Doe", balance + 1000);

System.out.println("John Doe's new balance: " + tm.get("John Doe"));

}

}

Here is the output; notice that the accounts are now sorted by last name:

Jane Baker: 1378.0

John Doe: 3434.34

Todd Hall: 99.22

Ralph Smith: -19.08

Tom Smith: 123.22

John Doe's new balance: 4434.34

The comparator class TComp compares two strings that hold first and last names. It does so by first comparing last names. To do this, it finds the index of the last space in each string and then compares the substrings of each element that begin at that point. In cases where last names are equivalent, the first names are then compared. This yields a tree map that is sorted by last name, and within last name by first name. You can see this because Ralph Smith comes before Tom Smith in the output.

If you are using JDK 8 or later, then there is another way that you could code the preceding program so the map is sorted by last name and then by first name. This approach uses the thenComparing( ) method. Recall that thenComparing( ) lets you specify a second comparator that will be used if the invoking comparator returns equal. This approach is put into action by the following program, which reworks the preceding example to use thenComparing( ):

     //Use thenComparing() to sort by last, then first name.

     import java.util.*;

     //A comparator that compares last names.

class CompLastNames implements Comparator<String> { public int compare(String aStr, String bStr) {

int i, j;

// Find index of beginning of last name. i = aStr.lastIndexOf(' ');

j = bStr.lastIndexOf(' ');

return aStr.substring(i).compareToIgnoreCase(bStr.substring(j));

}

}

// Sort by entire name when last names are equal.

class CompThenByFirstName implements Comparator<String> { public int compare(String aStr, String bStr) {

int i, j;

return aStr.compareToIgnoreCase(bStr);

}

}

class TreeMapDemo2A {

public static void main(String args[]) {

     //Use thenComparing() to create a comparator that compares

     //last names, then compares entire name when last names match.

     CompLastNames compLN = new CompLastNames();

Comparator<String> compLastThenFirst =

compLN.thenComparing(new CompThenByFirstName());

// Create a tree map.

TreeMap<String, Double> tm = new TreeMap<String, Double>(compLastThenFirst);

     //Put elements to the map.

     tm.put("John Doe", new Double(3434.34));

     tm.put("Tom Smith", new Double(123.22));

tm.put("Jane Baker", new Double(1378.00));

tm.put("Tod Hall", new Double(99.22));

tm.put("Ralph Smith", new Double(-19.08));

     //Get a set of the entries.

Set<Map.Entry<String, Double>> set = tm.entrySet();

     //Display the elements.

     for(Map.Entry<String, Double> me : set) {

System.out.print(me.getKey() + ": ");

System.out.println(me.getValue());

}

System.out.println();

     Deposit 1000 into John Doe's account. double balance = tm.get("John Doe"); tm.put("John Doe", balance + 1000);

System.out.println("John Doe's new balance: " + tm.get("John Doe"));

}

}

compares only the last names. A second comparator, called CompThenByFirstName, compares the entire name, starting with the first name. Next, the TreeMap is then created by the following sequence:

CompLastNames compLN = new CompLastNames(); Comparator<String>

compLastThenFirst = compLN.thenComparing(new CompThenByFirstName());

Here, the primary comparator is compLN. It is an instance of CompLastNames. On it is called thenComparing( ), passing in an instance of CompThenByFirstName. The result is assigned to the comparator called compLastThenFirst. This comparator is used to construct the TreeMap, as shown here:

TreeMap<String, Double> tm = new TreeMap<String, Double>(compLastThenFirst);

Now, whenever the last names of the items being compared are equal, the entire name, beginning with the first name, is used to order the two. This means that names are ordered based on last name, and within last names, by first names.

One last point: in the interest of clarity, this example explicitly creates two comparator classes called CompLastNames and ThenByFirstNames, but lambda expressions could have been used instead. You might want to try this on your own. Just follow the same general approach described for the CompDemo2 example shown earlier.