September 2, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

Data Structures in Java: Part 11, The Comparator Interface, Part 3

  • August 16, 2001
  • By Richard G. Baldwin
  • Send Email »
  • More Articles »

Java Programming, Lecture Notes #1370


Preface

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:

BILL Bill JOE Joe TOM Tom
 

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.

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






Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Sitemap | Contact Us

Rocket Fuel