A Miniseries
This is the eleventh 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 10, The Comparator 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 third 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
In this lesson, I will teach you how to use a Comparator to cause a TreeSet collection to be sorted in descending order while preserving the impact of differences in case.
We might refer to this as reverse natural order. In other words, the sorting order is the same as the natural order except that the order is descending instead of ascending.
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 Comparator04.java //Copyright 2001, R.G.Baldwin import java.util.*; import java.io.Serializable; public class Comparator04{ public static void main( String args[]){ new Worker().doIt(); }//end main() }//end class Comparator04 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("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(); int result = ((String)o1). compareTo(((String)o2)); return result*(-1); }//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 you selected the following, you are correct:
D. Tom TOM Joe JOE Bill BILL
Similar To Previous Programs
The overall structure of this program is very 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 TreeSet Object With A Comparator
The code in Listing 2 instantiates a new TreeSet object, by providing a reference to an anonymous object that implements the Comparator interface.
That object is instantiated from the class named TheComparator. It is the Comparator object that will be of most interest to us in this lesson.
Collection ref; ref = new TreeSet( new TheComparator()); Populator.fillIt(ref); iter = ref.iterator(); while(iter.hasNext()){ System.out.print( iter.next() + " "); }//end while loop Listing 2
Populating The TreeSet Collection
After the TreeSet object is instantiated, it is passed to a method named fillIt where the TreeSet collection is populated with the names of several people.
Display The Contents Of The Treeset Collection
As shown by the code in Listing 2, after the TreeSet collection is populated, an Iterator is obtained for that collection and used to display the contents of the collection. The output produced by the program is shown below:
Tom TOM Joe JOE Bill BILL
Analyzing The Contents Of The Treeset Collection
We will need to compare this output with the names used to populate the collection to appreciate the true significance of the use of the Comparator object.
At this point, it is worth pointing out that the six names contained in the collection are returned by the iterator in descending order, taking the significance of upper and lower case into account.
In other words, names beginning with letters that are high in the alphabet occur before names beginning with letters that are lower in the alphabet.
In addition, names containing lower case characters appear before the same names containing only upper case characters.
Method Used To Populate The Collection
Listing 3 shows the method named fillIt that was used to populate the collection with references to six String objects. As you can see, the names weren’t added in any particular order.
As you can also see by comparing Listing 3 with the output shown above, all six names that were added to the collection were displayed in the output, but in a different order from the order in which they were added. (Names with the same spelling but different case were not considered to be duplicates insofar as the contract for the set was concerned.)
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() Listing 3
Implementing The Comparator Interface
That brings us to the class from which the Comparator object was instantiated. The beginning portion of that class is shown in Listing 4.
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(); Listing 4
The code in Listing 4 isn’t particularly interesting. That code simply throws an exception if either of the references passed to the compare method refer to an object of some type other than String.
The Interesting Code
The interesting code is shown in Listing 5. The first statement in Listing 5 uses the compareTo method of the string class to compare the two objects in an ascending natural ordering sense. The behavior of this method is more formally described as follows:
“Returns: the value 0 if the argument is a string lexicographically equal to this string; a value less than 0 if the argument is a string lexicographically greater than this string; and a value greater than 0 if the argument is a string lexicographically less than this string.”
int result = ((String)o1). compareTo(((String)o2)); return result*(-1); Listing 5
Converting To Reverse Natural Order
The most interesting line of code in this entire program is the return statement shown in Listing 5.
This line of code changes the sign on the value returned by the compareTo method before returning it as the return value for the compare method.
The effect of changing the sign is to return a value that causes the TreeSet collection to arrange the elements in reverse natural order instead of the normal ascending natural order.
As a result, the use of an iterator to access and display the contents of the collection is as follows:
Tom TOM Joe JOE Bill BILL
For comparison, if the names were arranged in ascending natural order, the output would be as shown below:
Summary
In this lesson, I taught you how to use a Comparator to cause a TreeSet collection to be sorted in reverse natural order. In other words, the sorting order is the same as the natural order except that the order is descending instead of ascending.
What’s Next?
In the next lesson, I will show you how to use a Comparator object to sort the contents of an array.