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

Data Structures in Java: Part 13, The Comparator Interface, Part 5

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

Java Programming, Lecture Notes #1374


Preface

A miniseries

This is the thirteenth 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 12, The Comparator Interface, Part 4.

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 fifth 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 the sort method of the Collections class along with a Comparator object to sort the contents of a List into reverse natural order.

The methodology that I will teach you is completely general, and can be used to sort a list in a wide variety of ways, depending on how you define the compare method of a Comparator object.

Furthermore, the same sort method and the same Comparator object can be used to sort any implementation of a list, so long as the list properly implements the List interface.

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 Comparator06.java
//Copyright 2001, R.G.Baldwin
import java.util.*;
import java.io.Serializable;

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

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

    ref = new LinkedList();
    Populator.fillIt(ref);
    Collections.sort(
       (List)ref, new TheComparator());
    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();

    //Do an upper-case comparison
    int result = ((String)o1).
               compareTo(((String)o2));
    return result*(-1);
  }//end compare()
}//end class TheComparator

Listing 1

The correct answer to the above question is shown below:

D.  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 LinkedList object

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

    ref = new LinkedList();
    Populator.fillIt(ref);

Listing 2

The LinkedList class is one of the concrete implementation classes of the Collections Framework.  This class implements the Collection interface and the List interface.  Here is part of what Sun has to say about the LinkedList class:

"Linked list implementation of the List interface. Implements all optional list operations, and permits all elements (including null). In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue (deque)."
Populating the List

The code in Listing 3 shows the fillIt method that is used to populate the list with references to six different String objects.

The add method is used to add each new element to the end of the list.  As you can see, the elements are added to the list in no particular order with respect to their values.
 

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

Displaying the list

Although I didn't bother to do so in this program, if an iterator were to be used to access and display the elements in the list following the invocation of the fillIt method, the result would be as shown below:

Joe Bill Tom JOE BILL TOM

As you can see, this is the same as the order in which the elements are added to the list.  The first element is added to the list at index value 0 and the sixth element is added to the list at index value 6.

Sort the list

The code shown in Listing 4 is new to this lesson.  This code uses the sort method of the Collections class, along with a Comparator object to sort the contents of the list.

A very important point

Note that unlike the programs in previous lessons that simply extracted the contents of the collection into an array and sorted the array, this code actually rearranges the contents of the list according to the sorting rules.  (The programs in previous lessons that sorted the arrays did not rearrange the contents of the list.  Only the contents of the arrays were rearranged.)

Thus, the relationship between an element in the list and the index associated with that element can change as a result of the sorting operation shown in Listing 4.

Following the sort, when an iterator is used to access the elements, the elements will be returned by the iterator in the newly-sorted order.
 

    Collections.sort(
       (List)ref, new TheComparator());

Listing 4

The Collections class

Note that despite the similarity of the names, the Collections class is different from the Collection interface.  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."
The sort method

The Collections class provides a large number of very interesting and useful methods, such as binarySearch, copy, reverse, and reverseOrder(The reverseOrder method will be examined in the next lesson.)

One of the static methods of the Collections class is the sort method.  One version of the sort method can be used to sort a list into the natural ordering of its elements.  Another version sorts a list according to the order induced by a comparator.

Here is part of what Sun has to say about this second version of the sort method that uses a Comparator:

public static void sort(
     List list, Comparator c)
"Sorts the specified list according to the order induced by the specified comparator. All elements in the list must be mutually comparable using the specified comparator (that is ...

The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the  n2 log(n) performance that would result from attempting to sort a linked list in place."

Also uses an array

I find it interesting that the sort method uses an array as an intermediary in the sorting process.  However, the difference between this approach and the approach involving arrays shown in previous lessons is given by the following excerpt from the above quotation:

"iterates over the list resetting each element from the corresponding position in the array"
In other words, after sorting the array, the sort method uses the sorted results in the array to rearrange the positions of the elements in the list, resulting in a sorted list.

A flexible approach to sorting

Thus, the sort method of the Collections class can be used to sort the elements in a list using whatever set of comparison rules you program into the compare method of the Comparator object.  Furthermore, it doesn't matter how the list is actually implemented so long as it properly implements the List interface.

The Comparator

The code in Listing 5 shows the class from which the Comparator object was instantiated.
 

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()
}//end class TheComparator

Listing 5

I have presented and discussed this class in previous lessons, so I won't discuss it in detail again here. Suffice it for now to say that an object instantiated from this class will induce the list to be sorted into reverse natural order.

Display the sorted list

The code in Listing 6 gets and uses an iterator to display the contents of the sorted list.
 

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

Listing 6

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

Tom TOM Joe JOE Bill BILL

As you can see, this is reverse natural order as induced by the Comparator object.

Summary

In this lesson, I have taught you how to use the sort method of the Collections class along with a Comparator object to sort the contents of a list.

By using this approach, you can sort the contents of list according to any set of comparison rules that you can program into the compare method of the Comparator object.

Furthermore, the ability to sort the list is independent of the actual implementation of the list, so long as the list properly implements the List interface.  For example, the same Comparator object (and the same code) can be used to sort an ArrayList, a LinkedList, or a Vector, producing the same results regardless of which class the list object is instantiated from.

What's Next?

In the next lesson, I will show 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 show you how to use the reverse method of the Collections class to reverse the order of the elements in a list.

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