Tuesday, February 22, 2011

Chapter 41: Sorting Collections and Arrays

In the previous chapter, we said that the java creators created the arraylist to help the programmers who use that language to efficiently insert/update and delete stuff in an array. There is one more thing we may want to do with a collection of objects. That is “Sorting”. In this chapter we are going to look at that feature.

Sorting and searching topics have been added to the exam for Java 5. Both collections and arrays can be sorted and searched using methods in the API.

So, lets get started!!!

Sorting Collections

Let’s start with something simple like sorting an ArrayList of Strings alphabetically. What could be easier? ArrayList doesn’t give you any way to sort its contents, but the
java.util.Collections class does

import java.util.*;
class SortingExample {
public static void main(String[] args) {
ArrayList stuff = new ArrayList(); // #1
stuff.add("Ferrari");
stuff.add("BMW");
stuff.add("Porsche");
stuff.add("Aston Martin");
stuff.add("Lamborghini");
System.out.println("unsorted " + stuff);
Collections.sort(stuff); // #2
System.out.println("sorted " + stuff);
}
}

This produces something like this:
unsorted [Ferrari, BMW, Porsche, Aston Martin, Lamborghini]
sorted [Aston Martin, BMW, Ferrari, Lamborghini, Porsche]

Line 1 is declaring an ArrayList of Strings, and line 2 is sorting the ArrayList alphabetically.

We’ll talk more about the Collections class, along with the Arrays class in a later chapter, for now let’s keep sorting stuff.

Let’s imagine we’re building the ultimate home-automation application. Today we’re focused on the home entertainment center, and more specifically the DVD control center. We’ve already got the file I/O software in place to read and write data between the MovideDVDInfo.txt file and instances of class MovideDVDInfo. Here are the key aspects of the class:

class MovideDVDInfo {
String movieName;
String movieType;
String hero;
MovideDVDInfo(String t, String g, String a) {
movieName = t; movieType = g; hero = a;
}
public String toString() {
return movieName + " " + movieType + " " + hero + "\n";
}
// getters and setter go here
}

Here’s the DVD data that’s in the MovideDVDInfo.txt file:
Fast & Furious/Action/Vin Diesel
The Little Man/Comedy/Calvin
Ice Age/Animation/Sid The Sloth


In our home-automation application, we want to create an instance of MovideDVDInfo for each line of data we read in from the MovideDVDInfo.txt file. For each instance, we will parse the line of data (remember String.split()?) and populate MovideDVDInfo’s three instance variables. Finally, we want to put all of the MovideDVDInfo instances into an ArrayList. Imagine that the populateList() method (below) does all of this. Here is a small piece of code from our application:

ArrayList dvdList = new ArrayList();
populateList(); // adds the file data to the ArrayList
System.out.println(dvdList);

You might get output like this:
[Fast & Furious Action Vin Diesel
, The Little Man Comedy Calvin
, Ice Age Animation Sid The Sloth
]

Note: We overrode MovideDVDInfo’s toString() method, so when we invoked println() on the ArrayList it invoked toString() for each instance.

Now that we’ve got a populated ArrayList, let’s sort it:

Collections.sort(dvdlist);

Oops!, you get something like this:
TestDVD.java:13: cannot find symbol
symbol : method sort(java.util.ArrayList)
location: class java.util.Collections
Collections.sort(dvdlist);

What’s happened here? We know that the Collections class has a sort() method, yet this error implies that Collections does NOT have a sort() method that can take a dvdlist. That means there must be something wrong with the argument we’re passing (dvdlist).

If you’ve already figured out the problem, our guess is that you did it without the help of the obscure error message shown above...How do you sort instances of MovideDVDInfo? Why were we able to sort instances of String? When you look up Collections.sort() in the API your first reaction might be to panic. Don't worry, once again the generics section will help you read that weird looking method signature. If you read the description of the one-arg sort() method, you’ll see that the sort() method takes a List argument, and that the objects in the List must implement an interface called Comparable. It turns out that String implements Comparable, and that’s why we were able to sort a list of Strings using the Collections.sort() method.

The Comparable Interface

The Comparable interface is used by the Collections.sort() method and the java.util.Arrays.sort() method to sort Lists and arrays of objects, respectively. To implement Comparable, a class must implement a single method, compareTo(). Here’s an invocation of compareTo():

int x = thisObject.compareTo(anotherObject);

The compareTo() method returns an int with the following characteristics:
1. negative – if thisObject < anotherObhect 2. zero – if the objects are equal 3. positive – if thisObject > anotherObject

The sort() method uses compareTo() to determine how the List or object array should be sorted. Since you get to implement compareTo() for your own classes, you can use whatever criteria you prefer, to sort instances of your classes. Returning to our earlier example for class MovideDVDInfo, we can take the easy way out and use the String class’s implementation of compareTo():

class MovideDVDInfo implements Comparable { // #1
// existing code
public int compareTo(MovideDVDInfo d) {
return movieName.compareTo(d.getTitle()); // #2
} }

In line 1 we declare that class MovideDVDInfo implements Comparable in such a way that MovideDVDInfo objects can be compared to other MovideDVDInfo objects. In line 2 we implement compareTo() by comparing the two MovideDVDInfo object’s titles. Since we know that the titles are Strings, and that String implements Comparable, this is an easy way to sort our MovideDVDInfo objects, by movieName. Before generics came along in Java 5, you would have had to implement Comparable something like this:

class MovideDVDInfo implements Comparable {
// existing code
public int compareTo(Object o) { // takes an Object rather
// than a specific type
MovideDVDInfo d = (MovideDVDInfo)o;
return movieName.compareTo(d.getTitle());
} }

This is still legal, but you can see that it’s both painful and risky, because you have to do a cast, and you need to verify that the cast will not fail before you try it.

Exam Tip: It’s important to remember that when you override equals() you MUST take an argument of type Object, but that when you override compareTo() you should take an argument of the type you’re sorting.

Putting it all together, our MovideDVDInfo class should now look like this:

class MovideDVDInfo implements Comparable {
String movieName;
String movieType;
String hero;
MovideDVDInfo(String t, String g, String a) {
movieName = t; movieType = g; hero = a;
}
public String toString() {
return movieName + " " + movieType + " " + hero + "\n";
}
public int compareTo(MovideDVDInfo d) {
return movieName.compareTo(d.getTitle());
}
public String getTitle() {
return movieName;
}
// other getters and setters
}

Now, when we invoke Collections.sort(dvdList); we get
[Fast & Furious Action Vin Diesel
, Ice Age Animation Sid The Sloth
, The Little Man Comedy Calvin
]

Wow! Our ArrayList has been sorted by movieName. Of course, if we want our home automation system to really rock, we’ll probably want to sort DVD collections in lots of different ways. Since we sorted our ArrayList by implementing the compareTo() method, we seem to be stuck. We can only implement compareTo() once in a class, so how do we go about sorting our classes in an order different than what we specify in our compareTo() method? Good question. As luck would have it, the answer is coming up next.

Sorting with Comparator

While you were looking up the Collections.sort() method you might have noticed that there is an overloaded version of sort() that takes both a List AND something called a Comparator. The Comparator interface gives you the capability to sort a given collection any number of different ways. The other handy thing about the Comparator interface is that you can use it to sort instances of any class—even classes you can’t modify—unlike the Comparable interface, which forces you to change the class whose instances you want to sort. The Comparator interface is also very easy to implement, having only one method, compare(). Here’s a small class that can be used to sort a List of MovideDVDInfo instances, by movieType.

import java.util.*;
class GenreSort implements Comparator {
public int compare(MovideDVDInfo one, MovideDVDInfo two) {
return one.getGenre().compareTo(two.getGenre());
}
}

The Comparator.compare() method returns an int whose meaning is the same as the Comparable.compareTo() method’s return value. In this case we’re taking advantage of that by asking compareTo() to do the actual comparison work for us. Here’s a test program that lets us test both our Comparable code and our new Comparator code:

import java.util.*;
import java.io.*;
public class TestDVD {
ArrayList dvdlist = new ArrayList();
public static void main(String[] args) {
new TestDVD().go();
}
public void go() {
populateList();
System.out.println(dvdlist); // output as read from file
Collections.sort(dvdlist);
System.out.println(dvdlist); // output sorted by movieName

GenreSort gs = new GenreSort();
Collections.sort(dvdlist, gs);
System.out.println(dvdlist); // output sorted by movieType
}
public void populateList() {
// read the file, create MovideDVDInfo instances, and
// populate the ArrayList dvdlist with these instances
}
}

You’ve already seen the first two output lists, here’s the third:
[Fast & Furious Action Vin Diesel
, Ice Age Animation Sid The Sloth
, The Little Man Comedy Calvin
]

Because the Comparable and Comparator interfaces are so similar, expect the exam to try to confuse you. For instance you might be asked to implement the compareTo() method in the Comparator interface.

Difference Between Comparable and Comparator

Though both the Comparable and Comparator classes serve the same purposes, the way they work and the way they are used are different. Lets take a look at how they are different:
Comparable Comparator
int objOne.compareTo(objTwo) int compare(objOne, objTwo)
You must modify the class whose instances you want to sort. You build a class separate from the class whose instances you want to sort.
Only one sort sequence can be created Many sort sequences can be created
Implemented frequently in the API by: String, Wrapper classes, Date, Calendar... Meant to be implemented to sort instances of third-party classes.

Sorting with the Arrays Class

We’ve been using the java.util.Collections class to sort collections; now let’s look at using the java.util.Arrays class to sort arrays. The good news is that sorting arrays of objects is just like sorting collections of objects. The Arrays.sort() method is overridden in the same way the Collections.sort() method is.

• Arrays.sort(arrayToSort)
• Arrays.sort(arrayToSort, Comparator)

In addition, the Arrays.sort() method is overloaded numerous times to provide a couple of sort methods for every type of primitive. The Arrays.sort() methods that sort primitives always sort based on natural order. Don’t be fooled by an exam question that tries to sort a primitive array using a Comparator.

Finally, remember that the sort() methods for both the Collections class and the Arrays class are static methods, and that they alter the objects they are sorting, instead of returning a different sorted object.

Exam Tip: We’ve talked a lot about sorting by natural order and using Comparators to sort. The last rule you’ll need to burn in is that, whenever you want to sort an array or a collection, the elements inside must all be mutually comparable. In other words, if you have an Object[] and you put Cat and Dog objects into it, you won’t be able to sort it. In general, objects of different types should be considered NOT mutually comparable, unless specifically stated otherwise.

Previous Chapter: Chapter 40 - ArrayList Basics

Next Chapter: Chapter 42 - Searching Arrays & Collections

No comments:

Post a Comment

© 2013 by www.inheritingjava.blogspot.com. All rights reserved. No part of this blog or its contents may be reproduced or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without prior written permission of the Author.

ShareThis

Google+ Followers

Followers