Java Programming, Lecture Notes # 1374
This is the thirteenth 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 12, The Comparator Interface, Part 4.
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 fifth lesson in a sub-series on the Comparator interface. The primary purpose of the lessons in this sub-series is to teach you about the interactions between the Comparator interface and 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 methodology that I will teach you is completely general, and can be used to sort a list in a wide variety of ways, depending on how you define the compare method of a Comparator object.
Furthermore, the same sort method and the same Comparator object can be used to sort any implementation of a list, so long as the list properly implements the List interface.
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 Comparator06.java
//Copyright 2001, R.G.Baldwin
import java.util.*;
import java.io.Serializable;
public class Comparator06{
public static void main(
String args[]){
new Worker().doIt();
}//end main()
}//end class Comparator06
class Worker{
public void doIt(){
Iterator iter;
Collection ref;
ref = new LinkedList();
Populator.fillIt(ref);
Collections.sort(
(List)ref, new TheComparator());
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("Joe");
ref.add("Bill");
ref.add("Tom");
ref.add("JOE");
ref.add("BILL");
ref.add("TOM");
}//end fillIt()
}//end class Populator
class TheComparator
implements Comparator,Serializable{
public int compare(
Object o1,Object o2){
if(!(o1 instanceof String))
throw new ClassCastException();
if(!(o2 instanceof String))
throw new ClassCastException();
//Do an upper-case comparison
int result = ((String)o1).
compareTo(((String)o2));
return result*(-1);
}//end compare()
}//end class TheComparator
Listing 1
|
The correct answer to the above question is shown below:
D. Tom TOM Joe JOE Bill BILL
If that was your answer, you probably already understand most of the material covered in this lesson. In that case, you might consider skipping this lesson and moving on to the next lesson. If that wasn't your answer, you should probably continue with your study of this lesson.
Similar to previous programs
The overall structure of this program in Listing 1 is similar to programs that I have discussed in previous lessons. Therefore, I will concentrate on those aspects of this program that differentiate it from the programs in previous lessons.
A new LinkedList object
The code in Listing 2 instantiates a new LinkedList object and
passes that object's reference to a method named fillIt where it
is populated with the names of several people.
ref = new LinkedList(); Populator.fillIt(ref); Listing 2 |
The LinkedList class is one of the concrete implementation classes of the Collections Framework. This class implements the Collection interface and the List interface. Here is part of what Sun has to say about the LinkedList class:
"Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque)."Populating the List
The code in Listing 3 shows the fillIt method that is used to populate the list with references to six different String objects.
The add method is used to add each new element to the end of
the list. As you can see, the elements are added to the list in no
particular order with respect to their values.
class Populator{
public static void fillIt(
Collection ref){
ref.add("Joe");
ref.add("Bill");
ref.add("Tom");
ref.add("JOE");
ref.add("BILL");
ref.add("TOM");
}//end fillIt()
}//end class Populator
Listing 3
|
Displaying the list
Although I didn't bother to do so in this program, if an iterator were to be used to access and display the elements in the list following the invocation of the fillIt method, the result would be as shown below:
Joe Bill Tom JOE BILL TOM
As you can see, this is the same as the order in which the elements are added to the list. The first element is added to the list at index value 0 and the sixth element is added to the list at index value 6.
Sort the list
The code shown in Listing 4 is new to this lesson. This code uses the sort method of the Collections class, along with a Comparator object to sort the contents of the list.
A very important point
Note that unlike the programs in previous lessons that simply extracted the contents of the collection into an array and sorted the array, this code actually rearranges the contents of the list according to the sorting rules. (The programs in previous lessons that sorted the arrays did not rearrange the contents of the list. Only the contents of the arrays were rearranged.)
Thus, the relationship between an element in the list and the index associated with that element can change as a result of the sorting operation shown in Listing 4.
Following the sort, when an iterator is used to access the elements,
the elements will be returned by the iterator in the newly-sorted order.
Collections.sort( (List)ref, new TheComparator()); Listing 4 |
The Collections class
Note that despite the similarity of the names, the Collections class is different from the Collection interface. Here is part of what Sun has to say about the Collections class:
"This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends."The sort method
The Collections class provides a large number of very interesting and useful methods, such as binarySearch, copy, reverse, and reverseOrder. (The reverseOrder method will be examined in the next lesson.)
One of the static methods of the Collections class is the sort method. One version of the sort method can be used to sort a list into the natural ordering of its elements. Another version sorts a list according to the order induced by a comparator.
Here is part of what Sun has to say about this second version of the sort method that uses a Comparator:
public static void sort(Also uses an array
List list, Comparator c)
"Sorts the specified list according to the order induced by the specified comparator. All elements in the list must be mutually comparable using the specified comparator (that is ...The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place."
I find it interesting that the sort method uses an array as an intermediary in the sorting process. However, the difference between this approach and the approach involving arrays shown in previous lessons is given by the following excerpt from the above quotation:
"iterates over the list resetting each element from the corresponding position in the array"In other words, after sorting the array, the sort method uses the sorted results in the array to rearrange the positions of the elements in the list, resulting in a sorted list.
A flexible approach to sorting
Thus, the sort method of the Collections class can be used to sort the elements in a list using whatever set of comparison rules you program into the compare method of the Comparator object. Furthermore, it doesn't matter how the list is actually implemented so long as it properly implements the List interface.
The Comparator
The code in Listing 5 shows the class from which the Comparator
object was instantiated.
class TheComparator
implements Comparator,Serializable{
public int compare(
Object o1,Object o2){
if(!(o1 instanceof String))
throw new ClassCastException();
if(!(o2 instanceof String))
throw new ClassCastException();
int result = ((String)o1).
compareTo(((String)o2));
return result*(-1);
}//end compare()
}//end class TheComparator
Listing 5
|
I have presented and discussed this class in previous lessons, so I won't discuss it in detail again here. Suffice it for now to say that an object instantiated from this class will induce the list to be sorted into reverse natural order.
Display the sorted list
The code in Listing 6 gets and uses an iterator to display the contents
of the sorted list.
iter = ref.iterator();
while(iter.hasNext()){
System.out.print(
iter.next() + " ");
}//end while loop
Listing 6
|
The output produced by the code in Listing 6 is shown below:
Tom TOM Joe JOE Bill BILL
As you can see, this is reverse natural order as induced by the Comparator object.
By using this approach, you can sort the contents of list according to any set of comparison rules that you can program into the compare method of the Comparator object.
Furthermore, the ability to sort the list is independent of the actual implementation of the list, so long as the list properly implements the List interface. For example, the same Comparator object (and the same code) can be used to sort an ArrayList, a LinkedList, or a Vector, producing the same results regardless of which class the list object is instantiated from.
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-