[ Data Structures with Java ] Section 22.2 : The Comparator Interface

Preface : 
Up to this point, we have been able to order an array of objects by using the compareTo() method when the objects in the array implement the Comparableinterface. This ordering is referred to as the class's natural ordering, and the class's compareTo() method is referred to as its natural comparison method. TheComparator interface defines objects containing a comparison method which imposes a total ordering on some collection of objects. Comparators can be passed to a sort method (such as the select sort) to allow precise control over the sort order. Comparators can also be used to control the order of certain data structures such as a heap. 
The Comparator interface specifies two comparison methods, compare() and equals(). A class that implements the interface defines an ordering between objects. 
The method compare() is similar to the Comparable method compareTo(), except that is takes two arguments. As an example, we create a class CircleLess that we can use to determine if one Circle object is less than another based on the relative size of their radius. Note that the Circle class does not implement the Comparable interface and so there is no preferred ordering among instances of the class. Our CircleLess class and the compare() method create an ordering : 

- class CircleLess :

view plaincopy to clipboardprint?

1. public class CircleLess implements Comparator{  
2.     @Override  
3.     public int compare(Circle x, Circle y) {  
4.         double radX = x.getRadius(), radY = y.getRadius();  
5.         return (int)(radX - radY);  
6.     }  
7. }  

CircleLess is external to the Circle class and so does not have access to the private instance variable radius. The compare() method must access the radius using the public method getRadius(). That said, we can compute two Circle objects by using an instance of the CircleLess class : 

- Demo on class CircleLess :

view plaincopy to clipboardprint?

1. public static void main(String args[]) {  
2.     Circle cirA = new Circle(5), cirB = new Circle(7.5);  
3.     CircleLess circComp = new CircleLess();  // comparing object  
4.     if(circComp.compare(cirA, cirB)<0)  
5.         System.out.println("Circle A is less than circle B");  
6. }  

Output : 

Circle A is less than circle B

General Comparison Objects : 
If we assume that objects implement the Comparable interface, we can develop generic Comparator classes that compare two objects for either the < or the > relation. The classes implement compare() by using the compareTo() ordering between objects. We will define and then extensively use the generic Comparator classes Less and Greater. Their implementation of compare() casts one of the arguments to a Comparable object and makes the comparison using compareTo(). The class Less compares two objects for "less than" : 

- class Less :

view plaincopy to clipboardprint?

1. public class Less implements Comparator{  
2.   
3.     @Override  
4.     public int compare(T x, T y) {        
5.         return ((Comparable)x).compareTo(y);  
6.     }  
7. }  

A Less object can be used to determine if one object has a lesser value than another. The underlying assumption is that the objects implement the Comparable interface. In general, for any Comparator object comp, the expression comp.compare(x,y) < 0 is used to evaluate success for the comparison (x < y). This is an important fact that we exploit in the design of the Comparator class Greater. We want compare() to be negative (<0) when the first object is greater than the second object : 

- class Greater :

view plaincopy to clipboardprint?

1. public class Greater implements Comparator{  
2.   
3.     @Override  
4.     public int compare(T x, T y) {  
5.         return -((Comparable)x).compareTo(y); // Just put a minus sign to reverse the order  
6.     }  
7. }  

Generalized Array Sorts : 
We have developed methods for a variety of array sorting algorithms. In each case, the method uses compareTo() for comparisons and the array is sorted in ascending order. This approach has a series limitation. If we want to use a method to sort the array in descending order, we would need a alternative version that simply changes the order of comparison to "greater than." 
We can cut through this needless duplication by defining sorting methods that include a Comparator parameter. Using a Less or Greater object as argument that calls compare(), the same sorting method can be used to order an array in ascending or descending order. Let us illustrate the idea with a new version of selectionSort(). The implementation is showing below. 
The following code is essentially a copy of the selectionSort() method in Chapter 5. The expression Comparator indicates that comp is an object that implements the Comparator interface in T itself or in some supperclass of T. We continue to use the identifier smallIndex : 

- Selection Sort with Comparator :

view plaincopy to clipboardprint?

1. public static void selectionSort(T[] arr, Comparatorsuper T> comp) {  
2.     int smallIndex;   
3.     int n = arr.length;  
4.     T temp;  
5.     for(int i=0; i1; i++) {  
6.         smallIndex = i;  
7.         for(int j=i+1; j
8.             if(comp.compare(arr[smallIndex], arr[j])>0) smallIndex = j;   
9.         temp = arr[i];  
10.         arr[i] = arr[smallIndex];  
11.         arr[smallIndex] = temp;  
12.     }  
13. }  

- Example 22.2 : 
This example uses a Less comparator and selectionSort() introduced previously to sort an array of strings in ascending order. A second call to selectionSort() with a Greater comparator orders the array in descending order. In each case, the resulting sorted list is output : 

- Demo on method selectionSort() with different Comparator (Less/Greater) :

view plaincopy to clipboardprint?

1. public static void main(String args[]) {  
2.     String[] arr = {"red", "green", "blue", "yellow", "tea", "orange"};  
3.     Less less = new Less();  
4.     Greater greater = new Greater();  
5.     selectionSort(arr, less);  
6.     System.out.println("Sort with less: "+Arrays.toString(arr));  
7.     selectionSort(arr, greater);  
8.     System.out.println("Sort with greater: "+Arrays.toString(arr));  
9. }  

Output : 

Sort with less: [blue, green, orange, red, tea, yellow]
Sort with greater: [yellow, tea, red, orange, green, blue]

Supplement : 
* [ Data Structures with Java ] Section 4.1 : Selection Sort