Java Enterprise Java Data Structures in Java: Part 12, The Comparator Interface, Part 4

Data Structures in Java: Part 12, The Comparator Interface, Part 4

Java Programming, Lecture Notes #1372


Preface


A miniseries

This is the twelfth 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 11, The
Comparator Interface, Part 3
.

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 primary purpose of the lessons in this sub-series
is to teach you about the interactions between the Comparator interface
and the Collections Framework.

However, this lesson departs somewhat from that primary purpose and
teaches you how to use a Comparator object to sort the contents
of an array containing references to objects.  Technically speaking,
an array is not part of the core Collections Framework.  However,
it is definitely a first cousin to the Framework.

An array is a container

As you should already be aware, an array is a container that can be
used to store a collection of primitive values or references to objects. 
Furthermore, the Collection interface declares a method named toArray,
which can be invoked on a Collection object to “return an array
containing all of the elements in this collection whose runtime type is
that of the specified array”
.

An opportune time to …

Since you are studying this sub-series of lessons to learn about the
uses of the Comparator interface, this seems like an opportune time
to teach you how to get an array from a collection, and how to use the
Comparator
interface to sort the contents of the array.  (While I’m at it,
I will also teach you how to sort the elements in an array of object references
into natural order without the use of a Comparator object.)

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 extract
the contents of a collection into an array, and how to use a Comparator
object to sort the contents of the array into reverse natural order
I will also teach you how to sort the contents of the array into natural
order
without the use of a Comparator object.

Discussion
and Sample Program


Beginning with a quiz

Take a pencil and a piece of paper and see if you can write down the
output produced by the program shown in Listing 1.

 

//File Comparator05.java
//Copyright 2001, R.G.Baldwin
import java.util.*;
import java.io.Serializable;

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

class Worker{
  public void doIt(){
    Iterator iter;
    Collection ref;
    Object[] array;

    ref = new Vector();
    Populator.fillIt(ref);
    iter = ref.iterator();
    System.out.println(
                    "Collection data");
    while(iter.hasNext()){
      System.out.print(
                    iter.next() + " ");
    }//end while loop
    System.out.println();
    
    array = ref.toArray();
    System.out.println(
                     "Raw array data");
    display(array);

    //Sort the array into natural order
    // and display it.
    Arrays.sort(array);
    System.out.println(
              "Natural order sorted " +
                         "array data");
    display(array);

    //Sort the array into custom order
    // and display it.
    Arrays.sort(
           array, new TheComparator());
    System.out.println(
              "Custom order sorted " + 
                         "array data");
    display(array);

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

  }//end doIt()
    
  static void display(Object[] array){
    for(int i = 0; i < array.length;
                                  i++){
      System.out.print(array[i] + " ");
    }//end for loop
    System.out.println();
  }//end display()
}// 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()
}//end class TheComparator

Listing 1

If you wrote down the following for the program output, you already
understand most of the material covered in this lesson and you can probably
skip this lesson and move on to the next lesson.

Collection data

Joe Bill Tom JOE BILL TOM

Raw array data

Joe Bill Tom JOE BILL TOM

Natural order sorted array data

BILL Bill JOE Joe TOM Tom

Custom order sorted array data

Tom TOM Joe JOE Bill BILL

Collection data

Joe Bill Tom JOE BILL TOM

If you didn’t write down the correct output for the program in Listing
1, you should probably continue with your study of this lesson.

Similar to previous programs

Although this program is somewhat more complex, the overall structure
of this program 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 Vector object

The code in Listing 2 instantiates a new object of the Vector
class and stores a reference to that object in the variable named ref.

 

    ref = new Vector();

Listing 2

The Vector class was part of Java long before the Collections
Framework was released.  However, with the release of the Collections
Framework, the Vector class was upgraded to implement the Collection
interface
and the List interface.

A Vector is a List

Therefore, a Vector is a List, and adheres to the various
contracts of the List interface.  For example, since it is
not a Set, it doesn’t prohibit duplicate elements.  Because
it is a List, it is an ordered collection.  The position
of each element in the collection is determined by a numeric index associated
with the element and is independent of the value of the element.

The fillIt method

As has been the case in several of the programs in previous lessons,
the code in Listing 3 passes the Vector object’s reference to a
method named fillIt where the Vector is populated with the
names of several people.

 

    Populator.fillIt(ref);

Listing 3

The code for the fillIt method is shown in Listing 4.  As
you can see, the names were added to the collection in no particular order
relative to their values.  (The add method for the Vector class
simply adds each new element to the end of the list.)


 

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 4

Iteration on a Vector

When an iterator is used to traverse the elements in a Vector
collection, the elements are delivered by the iterator in ascending index
order, beginning with the element stored at index 0.

The code in Listing 5 gets and uses an iterator to display the contents
of the populated collection.

 

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

Listing 5

The output

The code in Listing 5 produces the following output:

Collection data

Joe Bill Tom JOE BILL TOM

As you can see, this is the same order in which the names were added
to the collection by the fillIt method.

The toArray method

The code in Listing 6 is new to this lesson.  This code extracts
the contents of the collection and stores the elements in an array of type
Object.

 

    array = ref.toArray();

Listing 6

The contract

According to the documentation for the Vector class, this version
of the toArray method:

“Returns an array containing all of the elements in this
Vector in the correct order.”

The documentation for the toArray method of the Collection
interface is a little more verbose, reading partially as follows:

“Returns an array containing all of the elements in this
collection. If the collection makes any guarantees as to what order its
elements are returned by its iterator, this method must return the elements
in the same order.

Elements are returned in ascending index order

The iterator for a Vector returns its elements in ascending index
order.  Therefore, the toArray method for a Vector object
must return the elements in the same order.

A “safe” array

Also, according to Sun:

“The returned array will be “safe” in that no references
to it are maintained by this collection. … The caller is thus free to
modify the returned array.”

In the code in Listing 6 above, the returned reference to an array object
is assigned to a reference variable that previously contained null. 
Following the execution of the toArray method, that reference variable
refers to an array object of type Object containing the same elements
as the Vector collection, in ascending index order.

(Regarding the concept of a “safe” array, it is easy to demonstrate
that the elements in the array refer to the same objects referred to by
the elements in the Vector.  Thus, using the references stored in
the array to modify the objects to which they refer also modifies the objects
referred to by the elements stored in the Vector.  In other words,
the elements in the array are copies of the elements in the Vector. 
The elements in the array refer to the original objects, and do no refer
to copies of those objects.  As usual when dealing with multiple references
to objects, care should be taken to avoid inadventently corrupting those
objects.)

Displaying the contents of the array

The code in Listing 7 passes the array object’s reference to a method
named display that displays the contents of the array in ascending
index order.

 

    System.out.println(
                     "Raw array data");
    display(array);

Listing 7

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

Raw array data

Joe Bill Tom JOE BILL TOM

As you can see, this is the same data, in the same order, as the contents
of the collection displayed earlier.  (The method named display
is a simple utility method, which I won’t discuss here because of its simplicity. 
You can view the display method in its entirety in Listing 1.)

Sorting the array into natural order

The code in Listing 8 is also new to this lesson.  This code uses
one of the overloaded sort methods of the Arrays class to
sort the contents of the array into natural order.

 

    Arrays.sort(array);

Listing 8

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

“This class contains various methods for manipulating arrays
(such as sorting and searching).”

The class contains many overloaded versions of the sort method. 
Here is part of what Sun has to say about the version of the sort
method used in Listing 8 above:

“Sorts the specified array of objects into ascending order,
according to the natural ordering of its elements. All elements in the
array must implement the Comparable interface.”

The Comparable interface and polymorphic behavior

Although the declared type of the array is Object, the array
actually contains references to String objects.

The String class implements the Comparable interface. 
Therefore, it is not necessary to cast the array to type String
before passing it to the Sort method.

Rather, the sort method treats the array as type Comparable
and uses the compareTo method declared in that interface to perform
any necessary comparisons required to carry out the sorting operation.

This is another example of the usefulness of polymorphism as implemented
through the use of the Java interface.  (The Comparable interface
and the compareTo method declared in that interface were discussed in detail
in an earlier lesson.)

Display the sorted array data

The code in Listing 9 displays the contents of the array after those
contents are sorted into natural order by the sort
method in Listing 8 above.

 

    System.out.println(
              "Natural order sorted " +
                         "array data");
    display(array);

Listing 9

The output produced by Listing 9 above was:

Natural order sorted array data

BILL Bill JOE Joe TOM Tom

The natural order for String objects

I discussed the concept of natural ordering in a previous lesson
with particular emphasis of the natural order for strings. 
You will recognize that the strings shown in the above output have been
sorted into natural order according to the definition of the compareTo
method of the String class.

Sort the array with a Comparator

The code in Listing 10 is also new to this lesson.  This code uses
a different version of the overloaded sort method of the Arrays
class to sort the array using the rules defined in the compare method
of a Comparator object (passed as a parameter to the sort method).

 

    Arrays.sort(
           array, new TheComparator());

Listing 10

What does Sun have to say about this?

Here is part of what Sun has to say about this version of the sort
method of the Arrays class:

“Sorts the specified array of objects according to the order
induced by the specified comparator. All elements in the array must be
mutually comparable by the specified comparator (that is, c.compare(e1,
e2) must not throw a ClassCastException for any elements e1 and e2 in the
array).”

TheComparator class

Listing 11 shows the class from which the Comparator object was
instantiated.

This is essentially the same class that was used to instantiate a Comparator
object in an earlier lesson.  I discussed the compare method in detail
in that lesson and won’t repeat that discussion here.

 

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 11

Suffice it to say at this point that this Comparator object causes
the elements in the array to be sorted into reverse natural order
That term was also explained in the previous lesson, so I won’t discuss
it further here.

Display the array contents again

The code in Listing 12 was used to display the newly-sorted contents
of the array.

 

    System.out.println(
              "Custom order sorted " + 
                         "array data");
    display(array);

Listing 12

The output produced by this code was:

Custom order sorted array data

Tom TOM Joe JOE Bill BILL

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

Could have sorted differently

It is important to note that I could have caused the sorting order to
be different from reverse natural order simply by defining the rules
used for comparison in the compare method shown in Listing 11 above. 
This makes it possible for you to sort array data into any order that you
choose as long as you can write the sorting rules into the compare
method of a class that implements the Comparator interface.

Display the collection data again

Finally, in order to show that none of this has disturbed the contents
of the original collection, the code in Listing 13 gets and uses an iterator
to display the contents of the Vector collection.

 

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

Listing 13

The output produced by the code in Listing 13 was:

Collection data

Joe Bill Tom JOE BILL TOM

If you compare this with the output produced by the code at the beginning
of the program, you will see that the iterator still returns the elements
in the Vector in the same order that they were added.  Thus,
modifications to the array did not disturb the contents of the Vector
collection.

The bottom line

The toArray method of the Collection interface makes it
possible to extract a copy of the elements in a collection into an array
and to manipulate those elements in whatever way you wish.  As mentioned
earlier, however, care should be exercised to make certain that the copies
of the references to the original objects are not used to corrupt the objects.

The various versions of the sort method in the Arrays
class make it possible to sort the contents of arrays in a variety of different
ways.

Summary


In this lesson, I have taught you how to extract
the contents of a collection into an array and how to use a Comparator
to sort the contents of the array into reverse natural order.

Although I elected to use reverse natural order
for purposes of illustration, I could have sorted the array into some other
order simply by defining the comparison rules in the compare method
of the Comparator class differently.

In order to further expand your knowledge of array
sorting, I also sorted the array into natural order without the
use of a Comparator.

Sorting the contents of the array did not disturb
the contents of the Vector collection from which the contents of
the array were derived.

What’s Next?


In the next lesson, I will show you how to use the sort method of
the Collections class along with a Comparator object to sort
the contents of 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.

[email protected]

Latest Posts

Related Stories