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.
