Java Programming, Lecture Notes # 1372
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.
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.
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.
Copyright 2001, Richard G. Baldwin. Reproduction in whole or in part in any form or medium without express written permission from Richard Baldwin is prohibited.
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.
-end-