Java Enterprise Java Data Structures in Java: Part 14, The Comparator Interface, Part 6

Data Structures in Java: Part 14, The Comparator Interface, Part 6

Java Programming, Lecture Notes #1376


Preface


A miniseries

This is the fourteenth 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 13, The
Comparator Interface, Part 5
.

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 sixth 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
a Comparator created by the reverseOrder method of the Collections
class to sort a list into
reverse natural order.  I will also
teach you how to use the reverse method of the Collections
class to reverse the order of the elements in a list.

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 (select
one or more answers)
?

  • A.  Compiler Error
  • B.  Runtime Error
  • C.  Joe Bill Tom JOE BILL TOM
  • D.  BILL Bill JOE Joe TOM Tom
  • E.  TOM BILL JOE Tom Bill Joe
  • F.  Joe Bill Tom JOE TOM BILL
  • G.  Tom TOM Joe JOE Bill BILL
  • H.  Joe Bill Tom
  • I.  None of the above.
//File Comparator07.java
//Copyright 2001, R.G.Baldwin
import java.util.*;

public class Comparator07{
  public static void main(
                        String args[]){
    new Worker().doIt();
  }//end main()
}//end class Comparator07

class Worker{
  public void doIt(){
    Iterator iter;
    Collection ref;

    ref = new ArrayList();
    Populator.fillIt(ref);
    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(
                    iter.next() + " ");
    }//end while loop
    System.out.println();
    
    Collections.reverse((List)ref);
    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(
                    iter.next() + " ");
    }//end while loop
    System.out.println();
    
    Comparator aComparator 
          = Collections.reverseOrder();
    Collections.sort(
               (List)ref, aComparator);
    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

Listing 1

And the answer is …

The correct answer to the above question is C, E, and G.  The output
from the program is shown below:

Joe Bill Tom JOE BILL TOM

TOM BILL JOE Tom Bill Joe

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 ArrayList object

The code in Listing 2 instantiates a new ArrayList object and
passes that object’s reference to a method named fillIt where it
is populated with the names of several people.

 

    ref = new ArrayList();
    Populator.fillIt(ref);
    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(
                    iter.next() + " ");
    }//end while loop

Listing 2

Displays the list contents

The code in Listing 2 also gets an iterator on the list and uses that
iterator to display the contents of the populated list.  At that point
in the program, the list contains the following elements in the order shown:

Joe Bill Tom JOE BILL TOM

You will recognize this as matching the order in which the elements
were added to the list by the fillIt method shown in Listing 3.

 

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

The ArrayList class

The ArrayList class is one of the concrete class implementations
of the Collections Framework.  This class implements both the Collection
interface and the List interface.  Thus, it is both a collection
and a list, and adheres to the contracts and stipulations of those interfaces.

Here is part of what Sun has to say about the ArrayList class:

“Resizable-array implementation of the List interface. Implements
all optional list operations, and permits all elements, including null.
… (This class is roughly equivalent to Vector, except that it is unsynchronized.)”

The reverse method of the Collections class

The invocation of the reverse method shown in Listing 4 is new
to this lesson.

 

    
    Collections.reverse((List)ref);

    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(
                    iter.next() + " ");
    }//end while loop

Listing 4

The Collections class

A previous lesson discussed the Collections class, indicating
that the class provides a number of static methods that can be used to
manipulate collections.  As a refresher, 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.”

You should recall that the Collections class is not the same as
the Collection interface.  Don’t confuse the two.

The reverse method

One of the static methods in the Collections class is the method
named reverse.  Here is part of what Sun has to say about the
reverse
method:

“Reverses the order of the elements in the specified list.”

Pretty simple, huh?  But also very useful in some cases.

Contents of the list

After invoking the reverse method on the list, the code in Listing 4
above used an iterator to get and display the contents of the list. 
The contents of the list at that point in the program were as shown below:

TOM BILL JOE Tom Bill Joe

If you compare this with the previous output, you will see that the
locations of the elements in the list are reversed.  The element at
index 0 was moved to index 5, the element at index 5 was moved to index
0, and the elements in between were moved accordingly.

The reverseOrder method

The code in Listing 5 is also new to this lesson.  This code invokes
the static reverseOrder method of the Collections class and
stores the returned value in a reference variable of type Comparator.

 

    Comparator aComparator 
          = Collections.reverseOrder();

Listing 5

What does Sun have to say about this?

Here is part of what Sun has to say about the reverseOrder method:

“Returns a comparator that imposes the reverse of the natural
ordering on a collection of objects that implement the Comparable interface.
(The natural ordering is the ordering imposed by the objects’ own compareTo
method.) This enables a simple idiom for sorting (or maintaining) collections
(or arrays) of objects that implement the Comparable interface in reverse-natural-order.”

Reverse natural order

You will recall that in several previous lessons, I have written a class
from which I instantiated a Comparator object that was used to sort
elements into reverse natural order.  I chose that sorting
order simply because I needed to illustrate how to define such a class,
and in my specific cases, reverse natural order was relatively easy
to implement.  (With a little more effort, I could have implemented
a variety of different sorting orders.)

In my design of those classes, I made no attempt to write a generic
class that could do the job independent of the type of the elements to
be sorted.  Rather, my Comparator objects tended to be very
type specific.

A type-independent Comparator

What we see here is much more general and sophisticated.  The Comparator
object returned by the reverseOrder method can be used to impose
a reverse natural order on any collection of objects that implement
the Comparable interface.  Thus, the class from which the objects
are instantiated doesn’t matter, as long as those classes implement the
Comparable
interface.   (I also discussed the Comparable interface in
some detail in an earlier lesson.  You may want to refer back to that
lesson to learn more about it.)

The wonderful world of the Java interface

Here again, we see a manifestation of the benefits of polymorphism as
implemented using the Java interface.  (I tell my students at least
once each week that if they don’t understand interfaces, they can’t possibly
understand Java.)

Sorting the list

The code in Listing 6 is not new to this lesson.  An earlier lesson
discussed the use of the sort method of the Collections class,
along with a Comparator object to sort a list.

 

    Collections.sort(
               (List)ref, aComparator);

Listing 6

Source of Comparator object is new

The thing that is new to this lesson is the source of the Comparator
object provided to the sort method in Listing 6.

In the previous lessons, the Comparator object was obtained by
instantiating an object from a class of my own design.  Those classes
implemented the Comparator interface.

In this case, a reference to a Comparator object was returned
by the invocation of the reverseOrder method of the Collections
class, and that reference was passed as a parameter to the sort
method.

Don’t know, don’t care …

The sort method doesn’t care where the Comparator object
comes from, as long as it properly implements the Comparator interface.

Regardless of the source of the Comparator object, the sort
method will use that object to impose the sorting rules imposed by the
compare
method of the object.  In this case, the sorting rules cause the list
to be sorted into reverse natural order.

The output

The code in Listing 7 gets and uses an iterator to display the contents
of the list following the invocation of the sort method.

 

    iter = ref.iterator();
    while(iter.hasNext()){
      System.out.print(
                    iter.next() + " ");
    }//end while loop

Listing 7

The output produced by the code in Listing 7 is shown below:

Tom TOM Joe JOE Bill BILL

You will recognize this as reverse natural order for the
elements in the list.

Summary


In this lesson, I taught you how to use a
Comparator
created by the reverseOrder method of the Collections class
to sort a list into
reverse natural order.  The Comparator
object is generic, and can be used to sort any list of objects that implement
the Comparable interface.

I also taught you how to use the reverse method of the Collections
class to reverse the order of the elements in a list.

What’s Next?


In the next lesson, I am going to dig a little deeper into the implications
of using the toArray method declared in the Collection interface.

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