Java Programming, Lecture Notes # 1366
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.
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.
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?
//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
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.
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.
Copyright 2001, Richard G. Baldwin. Reproduction in whole or in part in any form or medium without express written permission from Richard Baldwin is prohibited.
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.
-end-