Published: July 23, 2001
By Richard G. Baldwin
Java Programming, Lecture Notes # 1364
The purpose of this miniseries is to help you learn the essential features of Object-Oriented data structures in Java using the Collections Framework.
This is also the second and final lesson in a sub-series on the Comparable interface. The purpose of the lessons in the sub-series is to teach you about the interactions between the Comparable 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.
I will provide an example of implementing the Comparable interface for a new class definition, and will teach you about the natural ordering of the elements for a class.
I will teach you the meaning of the consistent with equals requirement and show you how to satisfy that requirement for a new class definition.
Finally, I will show you how to define a new class whose objects are eligible for inclusion in a TreeSet collection.
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 Comparable04.java
import java.util.*;
public class Comparable04{
public static void main(
String args[]){
new Worker().doIt();
}//end main()
}//end class Comparable04
class Worker{
public void doIt(){
Iterator iter;
Collection ref;
ref = new TreeSet();
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
Listing 1
|
If your answer was B. Runtime Error, you were correct.
What caused the runtime error?
The runtime error was caused by the code shown in Listing 2.
class Populator{
public static void fillIt(
Collection ref){
ref.add(new MyClass(4));
Listing 2
|
Why did this code produce a runtime error?
This code produced a runtime error for the reasons described in the following paragraphs.
The incoming parameter of the fillIt method is a reference to an object of type TreeSet. The TreeSet class implements the Collection, Set, and SortedSet interfaces. In this lesson, we will be primarily interested in the Set and SortedSet interfaces.
The contract for the add method of the Set interface reads partially as follows:
"Adds the specified element to this set if it is not already present ... If this set already contains the specified element, the call leaves this set unchanged and returns false. ... this ensures that sets never contain duplicate elements."What does this mean?
This means that whenever the add method is invoked on a Set object, the add method must have a way of determining if the element being added is a duplicate of an element that already exists in the collection. This means that it must be possible for the add method to compare the new element with all of the existing elements to determine if the new element is a duplicate of any of the existing elements.
The compareTo method
The documentation for the TreeSet class states the following:
"... the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all key comparisons using its compareTo (or compare) method ..."What this means is that insofar as the handling of duplicate elements is concerned, (with the possible exception given below involving a Comparator), in order for a reference to an object to be included in a TreeSet collection, the class from which that object is instantiated must implement the Comparable interface.
A possible exception
Note that one of the constructors for the TreeSet class makes it possible to instantiate a new object by passing a parameter that is a reference to an object that implements the Comparator interface.
The Comparator interface declares a method named compare, which compares its two arguments for order. The text in the above excerpt from the Sun documentation suggests that when this parameterized constructor is used, it may not be necessary for the objects included in the TreeSet collection to implement the Comparable interface.
I won't discuss that possibility in this lesson, but I will discuss it in a subsequent lesson that discusses the use of the Comparator interface. For purposes of this lesson, I will concentrate on the use of a TreeSet collection that does not receive a reference to a Comparator object when it is instantiated.
The SortedSet interface
The TreeSet class also implements the SortedSet interface. The documentation for the SortedSet interface states the following:
"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."Natural ordering of the elements
The key term to note in the above quotation is the term natural ordering of its elements. This takes us back to the Comparable interface, for which the documentation states:
"This interface imposes a total ordering on the objects of each class that implements it. 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."Conclusion
The conclusion is, in order for the iterator to be able to traverse the set according to the natural ordering of its elements, the elements stored in an object that implements the SortedSet interface must be instantiated from a class that implements the Comparable interface (unless a Comparator is provided when the SortedSet object is instantiated.)
The bottom line
The bottom line is, because the class named MyClass in Listing 1 does not implement the Comparable interface, objects of that class are not eligible for use with a TreeSet collection (unless a Comparator is provided when the TreeSet object is instantiated).
A Comparator was not provided when the TreeSet object was instantiated in Listing 1.
Therefore, the attempt in Listing 2, to add a MyClass object to the TreeSet collection resulted in a ClassCastException being thrown at runtime.
The solution
To solve this problem, we must modify the definition of the class named MyClass to make it implement the Comparable interface (assuming that we don't provide a Comparator when the TreeSet object is instantiated).
This is accomplished in the modified version of the program shown in
Listing 3.
//File Comparable05.java
import java.util.*;
public class Comparable05{
public static void main(
String args[]){
new Worker().doIt();
}//end main()
}//end class Comparable05
class Worker{
public void doIt(){
Iterator iter;
Collection ref;
ref = new TreeSet();
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 implements Comparable{
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()
public int compareTo(Object o){
if(!(o instanceof MyClass))
throw new ClassCastException();
if(((MyClass)o).data < data)
return 1;
if(((MyClass)o).data > data)
return -1;
else return 0;
}//end compareTo()
public boolean equals(Object o){
if(!(o instanceof MyClass))
return false;
if(((MyClass)o).data == data)
return true;
else return false;
}//end overridden equals()
}//end MyClass
Listing 3
|
The corrected code
The important code to note in this modified version of the program is the new definition of the class named MyClass. The other code in the program is essentially the same as in the previous version of the program.
The beginning portion of the new definition for MyClass is shown
in Listing 4.
class MyClass implements Comparable{
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()
Listing 4
|
The code shown in Listing 4 is identical to the code in the previous version with one major exception. This version of the class definition implements the Comparable interface. That means that this class must provide a concrete definition for the following method, which is the only method declared in the Comparable interface:
public int compareTo(Object o)
The compareTo method
The description of the compareTo method in the Sun documentation begins as follows:
"Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object."
Beyond this, there are a number of additional stipulations that I won't repeat here. You can view them in the Sun documentation if you are interested in that level of detail.
Listing 5 shows my implementation of the compareTo method.
Although this implementation satisfies the general description given above,
I haven't taken the time to test it fully to confirm that it meets all
of the additional stipulations provided by Sun.
public int compareTo(Object o){
if(!(o instanceof MyClass))
throw new ClassCastException();
if(((MyClass)o).data < data)
return 1;
if(((MyClass)o).data > data)
return -1;
else return 0;
}//end compareTo()
Listing 5
|
Consistent with equals
The Sun documentation strongly emphasizes the need to make certain that a class' natural ordering is consistent with equals, and provides the rules for meeting that requirement.
Further, the documentation for the TreeSet class reads partially as follows:
"Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. ..."Meeting the consistent with equals requirement
In order to satisfy the rules and to cause the natural ordering
of the MyClass class to be consistent with equals, it was
necessary to override the equals method inherited from the Object
class. My overridden version of the equals method is shown
in Listing 6.
public boolean equals(Object o){
if(!(o instanceof MyClass))
return false;
if(((MyClass)o).data == data)
return true;
else return false;
}//end overridden equals()
}//end MyClass
Listing 6
|
As was the case in defining the compareTo method, there are also a large number of stipulations involved in properly overriding the equals method. I will simply refer you to the Sun documentation if you are interested in reading about those stipulations.
The program output
Given all of the above, this program compiles and executes correctly, producing the following output.
1234
Note that duplicate elements were eliminated, and the iterator traversed the set in ascending element order, sorted according to the natural ordering of the elements, as required for a SortedSet collection.
I provided an example of implementing the Comparable interface for a new class definition, and I taught you about the natural ordering of the elements for a class.
I taught you the meaning of the consistent with equals requirement and showed you how to satisfy that requirement for a new class definition.
I showed you how to define a new class whose objects are eligible for inclusion in a TreeSet collection.
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-