October 1, 2014
Hot Topics:
RSS RSS feed Download our iPhone app

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

  • September 6, 2001
  • By Richard G. Baldwin
  • Send Email »
  • More Articles »

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.

baldwin.richard@iname.com






Comment and Contribute

 


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

 

 


Sitemap | Contact Us

Rocket Fuel