October 22, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Data Structures in Java: Part 9, The Comparator Interface, Part 1

  • August 1, 2001
  • By Richard G. Baldwin
  • Send Email »
  • More Articles »

Java Programming, Lecture Notes #1366


Preface

A miniseries

This is the ninth lesson in a miniseries on Java data structures and the Java Collections Framework.  The first lesson in the miniseries was entitled Data Structures in Java: Part 1, Getting Started.  The previous lesson was entitled Data Structures in Java: Part 8, The Comparable Interface, Part 2.

The purpose of this miniseries is to help you learn the essential features of Object-Oriented data structures in Java using the Collections Framework.

A sub-series

This is also the first lesson in a sub-series on the Comparator interface.  The purpose of the lessons in this sub-series is to teach you about the interactions between the Comparator interface and the Collections Framework, particularly with respect to the Set, SortedSet, and SortedMap interfaces of the Collections Framework.  This lesson discusses Set and SortedSet.  A discussion of SortedMap will be deferred for inclusion in a subsequent lesson.

Viewing tip

You may find it useful to open another copy of this lesson in a separate browser window.  That will make it easier for you to scroll back and forth among the different listings while you are reading about them.

Supplementary material

I recommend that you also study the other lessons in my extensive collection of online Java tutorials.  You will find those lessons published at Gamelan.com.  However, as of the date of this writing, Gamelan doesn't maintain a consolidated index of my Java tutorial lessons, and sometimes they are difficult to locate there.  You will find a consolidated index at Baldwin's Java Programming Tutorials.

Preview

Previous lessons have discussed the use of the Comparable interface.  This lesson discusses and illustrates the use of the Comparator interface.

The Comparable interface establishes natural ordering.  The sorting order established by a Comparator may be different or may be the same as the natural order.

A Comparator can be used to establish a sorting order for objects that don't have a natural ordering.

The use of a Comparator is an alternative to the implementation of the Comparable interface.  A TreeSet object instantiated with the benefit of a Comparator object doesn't require the objects in its collection to implement Comparable.

Discussion and Sample Program

The Comparable interface

Several previous lessons have discussed the use of the Comparable interface to establish the natural ordering of elements in a sorted set.  Although the name of the Comparable interface is similar to the name of the Comparator interface, they are different interfaces.  Don't be confused by the similarity of the names.

The Comparator interface

This lesson will begin the discussion of an alternative approach to sorting, using the Comparator interface to establish sorting order.

The sorting order established by a Comparator may be different from the natural ordering.  The Comparator interface can also be used to establish sorting order for objects that do not implement the Comparable interface and therefore do not have a natural ordering.

Beginning with a quiz

Let's begin with a little quiz to test your prior knowledge of the Collections Framework.

What output is produced by the program shown in Listing 1?

  • A.  Compiler Error
  • B.  Runtime Error
  • C.  44321
  • D.  4321
  • E.  1234
  • F.  12344
  • G.  None of the above.
//File Comparator02.java
//Copyright 2001, R.G.Baldwin
import java.util.*;
import java.io.Serializable;

public class Comparator02{
  public static void main(
                        String args[]){
    new Worker().doIt();
  }//end main()
}//end class Comparator02

class Worker{
  public void doIt(){
    Iterator iter;
    Collection ref;
   
    ref = new TreeSet(
                  new TheComparator());
    Populator.fillIt(ref);
    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(iter.next());
    }//end while loop
    System.out.println();

  }//end doIt()
}// end class Worker

class Populator{
  public static void fillIt(
                       Collection ref){
    ref.add(new MyClass(4));
    ref.add(new MyClass(4));
    ref.add(new MyClass(3));
    ref.add(new MyClass(2));
    ref.add(new MyClass(1));
  }//end fillIt()
}//end class Populator

class MyClass{
  int data;
  
  MyClass(){
    data = 0;
  }//end noarg constructor
  
  MyClass(int data){
    this.data = data;
  }//end parameterized constructor
  
  public String toString(){
    return "" + data;
  }//end overridden toString()

}//end MyClass

class TheComparator  
    implements Comparator,Serializable{
      
  public int compare(
                  Object o1,Object o2){
    if(!(o1 instanceof MyClass))
        throw new ClassCastException();
    if(!(o2 instanceof MyClass))
        throw new ClassCastException();
    if(((MyClass)o1).data 
                  < ((MyClass)o2).data) 
      return -1;
    if(((MyClass)o1).data 
                  > ((MyClass)o2).data) 
      return 1;
    else return 0;
  }//end compare()
    
  public boolean equals(Object o){
    if(!(o instanceof TheComparator))
        return false;
    else return true;
  }//end overridden equals()
}//end class TheComparator

Listing 1

If your answer was E.  1234, then you are correct.

Eligibility for inclusion in a TreeSet

The TreeSet class implements the SortedSet interface.

In an earlier lesson, I told you that in order to be eligible for inclusion in a TreeSet collection, an object must be instantiated from a class that implements the Comparable interface.

At that time, I also told you that it is possible to instantiate a new TreeSet object using a constructor that receives an incoming reference to a Comparator object, in which case it is not necessary for the objects in the collection to implement the Comparable interface.

Using a Comparator object

The program in Listing 1 takes this latter approach.  The main purpose of this program is to illustrate the use of a Comparator object as an alternative to implementation of the Comparable interface.

Passing Comparator to TreeSet constructor

The code fragment in Listing 2 shows the instantiation of a new TreeSet object, passing an anonymous object of type TheComparator as a parameter to the constructor for TreeSet.  Shortly, we will see that the class named TheComparator implements the Comparator interface.  Therefore, an object instantiated from that class is a Comparator object.
 

    Collection ref;
    ref = new TreeSet(
                  new TheComparator());
    Populator.fillIt(ref);

Listing 2

Passing the TreeSet to a populator method

The code fragment in Listing 2 also shows the reference to the TreeSet object being stored in a reference variable of the interface type Collection. The reference to the TreeSet object is passed as type Collection to a method named fillIt.

The purpose of the fillIt method is to instantiate some objects of type MyClass, and to store those object references in the TreeSet collection.

The fillIt method

The code fragment in Listing 3 shows the entire method named fillIt.  This method instantiates five objects from the class named MyClass and adds the references to those objects to the TreeSet collection.
 

class Populator{
  public static void fillIt(
                       Collection ref){
    ref.add(new MyClass(4));
    ref.add(new MyClass(4));
    ref.add(new MyClass(3));
    ref.add(new MyClass(2));
    ref.add(new MyClass(1));
  }//end fillIt()
}//end class populator

Listing 3

Similar to previous program

This is essentially the same code that we saw in a sample program in a previous lesson.  In that lesson, we saw that it was necessary for the class named MyClass to implement the Comparable interface.  Otherwise, the add method would throw a runtime exception.

MyClass does not implement Comparable

In that program, however, the TreeSet object was instantiated without benefit of a Comparator object.

As you can see in the code fragment in Listing 4, the class named MyClass does not implement the Comparable interface.

Comparator eliminates requirement for Comparable

Furthermore, the add method in Listing 3 does not throw a runtime exception.  That is because the TreeSet object was instantiated with the benefit of a Comparator object.

The use of a Comparator object in the instantiation of the TreeSet object eliminates the requirement for objects stored in the TreeSet collection to implement the Comparable interface.
 

class MyClass{
  int data;
  
  MyClass(){
    data = 0;
  }//end noarg constructor
  
  MyClass(int data){
    this.data = data;
  }//end parameterized constructor
  
  public String toString(){
    return "" + data;
  }//end overridden toString()
}//end MyClass

Listing 4

The class named TheComparator

That brings us to the class named TheComparator from which the Comparator object was instantiated and passed to the constructor for the TreeSet object.  The declaration for the class is shown in Listing 5.
 

class TheComparator  
    implements Comparator,Serializable{

Listing 5

As you can see, the class named TheComparator implements both the Comparator interface and the Serializable interface.

Implementing the Comparator interface

By implementing the Comparator interface, an object instantiated from the class is eligible for being passed to the constructor for a TreeSet object, which requires an incoming parameter of type Comparator.

Implementing the Serializable interface

Here is what Sun has to say about implementing the Serializable interface:

"Note: It is generally a good idea for comparators to implement java.io.Serializable, as they may be used as ordering methods in serializable data structures (like TreeSet, TreeMap). In order for the data structure to serialize successfully, the comparator (if provided) must implement Serializable."
Since the Serializable interface doesn't declare any methods, implementing the interface simply requires a declaration that the interface is being implemented.

Methods of the Comparator interface

The Comparator interface declares the two methods listed below:

public int compare(Object o1, Object o2)
public boolean equals(Object obj)

As is always the case when implementing interfaces, a class that implements the Comparator interface must provide concrete definitions for both of these methods.

The compare method

The code fragment in Listing 6 shows the beginning of the compare method.
 

      
  public int compare(
                  Object o1,Object o2){
    if(!(o1 instanceof MyClass))
        throw new ClassCastException();
    if(!(o2 instanceof MyClass))
        throw new ClassCastException();

Listing 6

The purpose of a Comparator is to compare the values stored in the instance variables of two objects and to return a value indicating which object is greater.

Specialization is required

Generally speaking, therefore, a Comparator object must be specialized to deal with a particular type of object.  That type could be

  • A specific class from which the object is instantiated,
  • A specific interface implemented by the class from which the object is instantiated, or perhaps
  • A specific superclass of the class from which the object is instantiated.
Must gain access to instance variables

Regardless of how the type is established, the code in the compare method of the Comparator object must gain access to the instance variables of the two objects passed to the compare method as type Object.  This normally requires that a downcast be performed on the incoming object references.

Specialized for type MyClass

This Comparator is specialized to compare two objects of the class named MyClass.  The first two statements in Listing 6 above confirm that both of the incoming objects are of type MyClass.  If either object is not of that type, an exception is thrown.

General behavior of compare method

The general description of the behavior of the compare method as provided by Sun is shown below:

"Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second."
Implementation of required behavior

This behavior is accomplished by the code shown in Listing 7.  In this case, the comparison is based solely on the values of the instance variable named data in each of the two objects.

Depending on which object contains the larger value in its instance variable, a value of 1 or -1 is returned.  If the two values are equal, a value of 0 is returned.  (Note that it is up to the author of the compare method to decide what constitutes larger.  This gives the author of the method a great deal of control over the results of a sorting operation.)
 

    if(((MyClass)o1).data 
                  < ((MyClass)o2).data) 
      return -1;
    if(((MyClass)o1).data 

                  > ((MyClass)o2).data) 
      return 1;
    else return 0;
  }//end compare()

Listing 7

Other stipulations

The documentation for the compare method contains several other stipulations regarding the behavior of the method.  While I believe that this version of the compare method meets all of those stipulations, I haven't taken the time to test it fully.  Therefore, it is possible that it may not meet all of the stipulations in terms of its behavior.

The equals method

Every new class inherits a default version of the equals method from the class named Object.  Therefore, a new class that implements the Comparator interface already has such a method.  The new class is free to override the inherited version, or to simply make use of the inherited version.  Here is what Sun has to say on the subject:

"Note that it is always safe not to override Object.equals(Object). However, overriding this method may, in some cases, improve performance by allowing programs to determine that two distinct Comparators impose the same order."
Overridden equals method

I decided, for purposes of illustration, to go ahead and override the equals method.  However, my overridden version, as shown in Listing 8 isn't very significant.  It simply confirms that an object being compared for equality to a Comparator object is instantiated from the same class.

Since the Comparator object doesn't contain any instance variables, there isn't much more to be tested for equality.
 

    
  public boolean equals(Object o){
    if(!(o instanceof TheComparator))
        return false;
    else return true;
  }//end overridden equals()
}//end class TheComparator

Listing 8

The program output

Finally, the code shown in Listing 9 is used with an Iterator to display the contents of the populated TreeSet object.
 

    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(iter.next());
    }//end while loop

Listing 9

The output produced by this code fragment is shown below.

1234

As you can see, the duplicate elements having the value 4 were eliminated as would be expected for a Set object.  In addition, the Comparator was used to accomplish the following contract of a SortedSet object:

"A set that further guarantees that its iterator will traverse the set in ascending element order, sorted according to the natural ordering of its elements (see Comparable), or by a Comparator provided at sorted set creation time."
In this case, the sorted order was controlled by the Comparator object, and not by the natural ordering of the elements.  The natural ordering is controlled by implementation of the Comparable interface, and the elements in this collection did not implement the Comparable interface.

Summary

This lesson has discussed and illustrated the use of the Comparator interface.

The sorting order established by a Comparator may be different or may be the same as the natural ordering for a collection of objects.

A Comparator can be used to establish a sorting order for objects that don't have a natural ordering.

The use of a Comparator is an alternative to the implementation of the Comparable interface.

A TreeSet object instantiated with the benefit of a Comparator object doesn't require the objects in its collection to implement Comparable.

What's Next?

In the next lesson, I will illustrate the use of a Comparator to eliminate the effect of case when sorting String objects.

About the author

Richard Baldwin is a college professor and private consultant whose primary focus is a combination of Java and XML. In addition to the many platform-independent benefits of Java applications, he believes that a combination of Java and XML will become the primary driving force in the delivery of structured information on the Web.

Richard has participated in numerous consulting projects involving Java, XML, or a combination of the two.  He frequently provides onsite Java and/or XML training at the high-tech companies located in and around Austin, Texas.  He is the author of Baldwin's Java Programming Tutorials, which has gained a worldwide following among experienced and aspiring Java programmers. He has also published articles on Java Programming in Java Pro magazine.

Richard holds an MSEE degree from Southern Methodist University and has many years of experience in the application of computer technology to real-world problems.

baldwin.richard@iname.com






Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel