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

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

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.

[email protected]

Latest Posts

Related Stories