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.