Published: July 16, 2001
By Richard G. Baldwin
Java Programming, Lecture Notes # 1362
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 first 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.
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 index on my site provides links to the lessons at Gamelan.com.
Specialization
I will provide a concrete example of the specialization that occurs while moving down the interface hierarchy from Collection to List. I will show an example of using two different overloaded versions of the add method to add new elements to an ArrayList object. One version is declared in the Collection interface and both versions are declared in the List interface.
To cast, or not to cast
I will illustrate the use of a cast to change the type of a reference from Collection to List, in order to invoke a version of the add method that is declared only in the List interface. This version, (which actually does an insert) makes it possible for the user to control the location of each individual element added to a List. The fact that the location of each element can be controlled in a List is what causes a List to be an ordered collection.
I will illustrate that a cast is not required on a reference being treated as type Collection in order to invoke the version of the add method that is declared in the Collection interface. This version of the add method supports the addition of new elements only at the end of the List.
Comparable not required for a List
Finally, I will show that it is not necessary for objects to implement the Comparable interface to make them eligible for inclusion in a List. I will tell you that it is necessary for objects to implement the Comparable interface to make them eligible for inclusion in a SortedSet, although I won't demonstrate that until the next lesson.
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 Comparable01.java
import java.util.*;
public class Comparable01{
public static void main(
String args[]){
new Worker().doIt();
}//end main()
}//end class Comparable01
class Worker{
public void doIt(){
Iterator iter;
Collection ref;
ref = new ArrayList();
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(0,new MyClass(4));
ref.add(1,new MyClass(4));
ref.add(2,new MyClass(3));
ref.add(3,new MyClass(2));
ref.add(4,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 A. Compiler Error, you were correct.
What caused the compiler error?
The compiler error was caused by the code shown in Listing 2.
public static void fillIt(
Collection ref){
ref.add(0,new MyClass(4));
Listing 2
|
The problem here is that the method named fillIt() receives a reference to an object of the ArrayList class as the interface type Collection, and attempts to invoke the following overloaded method on that reference:
add(int index, Object element)
Implements Collection and List
The ArrayList class implements both the Collection interface and the List interface. As you will probably recall from earlier lessons in this series, List is a subinterface of Collection. The List interface declares the following overloaded versions of the add method:
add(Object o)
add(int index, Object element)
The second of these two methods is unknown to the Collection interface. The Collection interface declares only the first version of the add method shown above.
Specialization
This is the result of specialization. A List object is a more-specialized collection than a Collection object. (In fact, Collection is a generic interface type and it is not possible to instantiate an object of type Collection using the standard classes in JDK 1.3.)
Therefore, the version of the add method that requires two parameter cannot be invoked on a reference to an ArrayList object when that object is treated as the generic type Collection.
Modified program
Now, take a look at the modified version of the program as shown in Listing 3.
What output is produced by the program shown in Listing 3?
//File Comparable02.java
import java.util.*;
public class Comparable02{
public static void main(
String args[]){
new Worker().doIt();
}//end main()
}//end class Comparable02
class Worker{
public void doIt(){
Iterator iter;
Collection ref;
ref = new ArrayList();
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){
((List)ref).add(0,new MyClass(4));
((List)ref).add(1,new MyClass(4));
((List)ref).add(2,new MyClass(3));
((List)ref).add(3,new MyClass(2));
((List)ref).add(4,new MyClass(1));
((List)ref).add(3,new MyClass(5));
}//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 3
|
If your answer was G. 443521, you are correct.
The corrected code
This version of the program illustrates the standard mechanism for correcting
the problem in the earlier program shown in Listing 1. The updated
code that corrected the problem is shown in Listing 4.
class Populator{
public static void fillIt(
Collection ref){
((List)ref).add(0,new MyClass(4));
((List)ref).add(1,new MyClass(4));
((List)ref).add(2,new MyClass(3));
((List)ref).add(3,new MyClass(2));
((List)ref).add(4,new MyClass(1));
((List)ref).add(3,new MyClass(5));
}//end fillIt()
}//end class populator
Listing 4
|
The incoming parameter to the fillIt method in Listing 4 is a reference to an object instantiated from the ArrayList class. That reference is passed as type Collection, which is legal because the ArrayList class implements both the Collection interface and the List interface.
Casting to type List
The code in Listing 4 uses a cast to convert the incoming reference from type Collection to type List. Because the version of the add method that is used in Listing 4 is declared in the List interface, and because the ArrayList class correctly implements the List interface, that version of the add method can be invoked on the reference to the ArrayList object when it is treated as the interface type List. Hopefully this is review material for you at this point. If not, you may need to go back and study some of my earlier lessons.
The List contract for the add method
Listing 4 also illustrates part of the contract for this version of the add method in the List interface. This version of the add method makes it possible to specify the position of each element added to the ArrayList object. (A List is an ordered collection because the user has control over the location of each element in the collection relative to the other elements in the collection.)
Controlling the locations of the elements
In Listing 4 above, the elements are added to the ArrayList object in increasing element order during the first five invocations of the add method. However, the sixth invocation of the add method adds a new element at index position 3.
Add method actually does an insert
A portion of the contract for this version of the add method in the List interface is as follows:
"Inserts the specified element at the specified position in this list (optional operation). Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices)."Thus, the new element is inserted at that position, and the other elements are pushed up, as required, toward higher index values to make room for the new element.
An aside regarding the Vector class
Here is an interesting aside. The Java Vector class has been around longer than the Collection Framework. Somewhere along the way, the Vector class was upgraded to cause it to become a concrete implementation of the Collection interface and the List interface.
As a result of the upgrade, the Vector class now provides an implementation of the add method described above. Except for the order of the parameters, that add method appears to have the same behavior as the older method named:
insertElementAt(Object elem, int index)
You can insert elements into a Vector object by invoking the add method on that object while treating it as type List. However, since the older insertElementAt method is not declared in the List interface, you cannot insert an element into the Vector object by invoking the insertElementAt method while treating it as a List. In order to invoke that method, you must treat it as type Vector.
More on the List contract
Another portion of the contract for a List object is that the iterator method
"Returns an iterator over the elements in this list in proper sequence."As a result, the code shown in Listing 5, along with the overridden toString method of the MyClass class causes the program to display the elements in the following order: 443521.
iter = ref.iterator();
while(iter.hasNext()){
System.out.print(iter.next());
}//end while loop
Listing 5
|
Duplicates are allowed in a List
One final thing that is worthy of note in this program is that a List objects allows duplicates. Hence, the populated collection contains two separate objects that are equal to one another in the sense that they both contain the same values in their instance variables.
One more sample program
Let's take a look at one more sample program. What output is produced by the program shown in Listing 6?
//File Comparable03.java
import java.util.*;
public class Comparable03{
public static void main(
String args[]){
new Worker().doIt();
}//end main()
}//end class Comparable03
class Worker{
public void doIt(){
Iterator iter;
Collection ref;
ref = new ArrayList();
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 6
|
If you selected C. 44321, you are correct.
No need to cast to type List
As shown in Listing 7, this program takes a different approach to solving
the problem originally exposed in the program shown in Listing 1.
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 7
|
This program does not change the type of the incoming reference to the ArrayList object in the fillIt method. Rather, it continues to treat the incoming reference as type Collection, and invokes the version of the add method that is declared in the Collection interface. This avoids the requirement to cast the incoming reference to type List.
The contract for this version of the add method in the List interface is
"Appends the specified element to the end of this list (optional operation)."As a result, the new elements are added to the collection in increasing index order. Since an iterator on a List returns the elements in increasing index order, this program displays the elements in the same order that they are added.
What happened to the Comparable interface?
By now, you are probably wondering what all of this has to do with the Comparable interface, because I haven't mentioned that interface since the introductory comments at the beginning of the lesson.
Comparable interface is not required for a List
Actually, the purpose of this lesson is to illustrate the lack of any requirement to make use of the Comparable interface with List objects. In particular, the purpose is to illustrate that this is one of the features that differentiates between a List object and a Set or SortedSet object.
A List can be used as a container for other objects regardless of whether or not those objects implement the Comparable interface. However, in the next lesson, we will see that objects must implement the Comparable interface in order to be eligible for inclusion in collections that implement the SortedSet interface.
This and the next several lessons are intended to provide you with an understanding of the interaction between the Comparable and Comparator interfaces and the Collections Framework.
No requirement to compare
Because a List makes no attempt to eliminate duplicate elements, or to sort the elements on the basis of their values, there is no requirement to compare objects when placing them in a List. Therefore, objects whose references are stored in a List are not required to implement the Comparable interface (but they may implement the Comparable interface without causing any harm).
Comparison is required
Because a SortedSet does eliminate duplicates and does sort the elements on the basis of their values, there is a requirement to compare each new element with the existing elements in a SortedSet whenever a new element is added to the collection. Therefore, objects whose references are stored in a SortedSet are required to implement the Comparable interface.
I provided a concrete example of the specialization that occurs while moving down the interface hierarchy from Collection to List. I showed an example of using two different overloaded versions of the add method to add new elements to an ArrayList object. One version is declared in the Collection interface and both versions are declared in the List interface.
I illustrated the use of a cast to change the type of a reference from Collection to List, in order to invoke a version of the add method that is declared only in the List interface. This version makes it possible for the user to control the location of each individual element added to a List.
I illustrated that a cast is not required on a reference being treated as type Collection in order to invoke the version of the add method that is declared in the Collection interface. This version of the add method supports the addition of new elements only at the end of the List.
Finally, I showed that it is not necessary for objects to implement the Comparable interface to make them eligible for inclusion in a List.
Although I didn't demonstrate it, I told you that it is necessary for objects to implement the Comparable interface to make them eligible for inclusion in a SortedSet.
Copyright 2000, 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-