|
Data Structures in Java: Part 13, The Comparator Interface, Part 5
By Richard G. Baldwin
Java Programming, Lecture Notes #1374
Preface
A miniseries
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.
Preview
In this lesson, I will teach you how to use the sort
method of the Collections class along with a Comparator object
to sort the contents of a List into reverse natural order.
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.
Discussion
and Sample Program
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. BILL Bill JOE Joe TOM Tom
-
D. Tom TOM Joe JOE Bill BILL
-
E. Joe Bill Tom
F. None of the above.
//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(
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."
Also uses an array
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.
Summary
In this lesson, I have taught you how to use the
sort method of the Collections class along with a Comparator
object to sort the contents of a list.
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.
What's Next?
In the next lesson, I will show you how to use a Comparator created
by the reverseOrder method of the Collections class to sort
a list into
reverse natural order. I will also show you how
to use the reverse method of the Collections class to reverse
the order of the elements in a list.
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.
baldwin.richard@iname.com
|
IE 7
Firefox 2.0
