Sorting an ArrayList of Object X

[David Dickinson]

Hi,

I've had a quick search in the forum archive but it didn't find anything and google results seem to centre around sorting lists of doubles/floats etc.

I have an ArrayList (multiple infact) of objects I have defined myself. I need to sort in DESCENDING (the highest value in index 0) based upon the double value of a field in my objects.

The ArrayLists are very small only containing approx 10 objects each.

Thanks for any advice.

[Paul Sturrock]

You need to add an implementation of the java.util.Comparator interface to impose this orderin and use it with Collections.sort(List list, Comparator comparator)

[Peter Chase]

Look at java.util.Collections class.

There is a method to sort a Collection, using a Comparator. There is also reverseOrder(), which gives a Comparator to give the reverse of natural ordering.

[David Dickinson]

Thanks for your quick replies guys.

Is it better to use these implementations or write my own code? I have wrote sorting algortithms before for C++ but would rather avoid it if possible.

Thanks

[Stan James]

You'll have to write your own Comparator for your own class. It doesn't implement a sort algorithm, tho. It's much simpler, thank goodness. It just has to compare two objects and tell which one should come first in sort order.

If you're in JDK 1.5 try the "generics" feature to specify the type of object in your collection. It makes the comparator a little simpler because the compiler can guarantee you're getting objects of the right type. I just did that for the first time last night.

Oh, another choice is to have your custom object implement Comparable and put the compare code right in the class. Then you can compare any two objects at any time without using the Comparator. You should also implement equals() which means you really ought to implement hashcode(), so it can get a little long winded just to sort some simple thing.

[David Dickinson]

I've started reading about the comparable interface and since this will be the first interface i've ever implemented im having a bit of a play with the functionality.

I like the idea of implementing comparable within the existing class but am slightly confused as to how this would compare two objects?

Would ObjectA.Compare(ObjectA,ObjectB) do the job?

Also why should I overide equals? If I don't override it will it never return a 0 from the compare method?

[Layne Lund]

Originally posted by David Dickinson:
I've started reading about the comparable interface and since this will be the first interface i've ever implemented im having a bit of a play with the functionality.

I like the idea of implementing comparable within the existing class but am slightly confused as to how this would compare two objects?

Would ObjectA.Compare(ObjectA,ObjectB) do the job?

Also why should I overide equals? If I don't override it will it never return a 0 from the compare method?

Notice that there are two possible interfaces to use: Comparator or Comparable. Comparator defines the method compare(Object o1, Object o2). Notice that this takes two objects to compare. Comparable on the other hand defines the method compareTo(Object o). Notice this only takes a single object to compare. "So what do I compare it with?" you may ask. You should compare it with "this" (i.e. the "current" object that the method is called on) by calling objA.compare(objB).

Since you want to implement this within the existing class, I think Comparable makes more sense than Comparator. Typically I think of Comparator when you want to implement separate classes for different types of comparisons (e.g. reverse order, case-insensitive String comparisions, etc.).

Finally, you should probably also override equals() in order to define what it means for two objects to be equal. If you don't, it *is* still possible for compare() to return 0, since Object provides a default implementation of the equals() method. However, this will only happen if the two references being compared point to the exact same object.

Several people here have suggested that you "take a look at the Xxx class." In case you don't know where to look, probably the best reference is

(As a side note classes and interfaces names start with upper case while variable and method names start with lower case.)the Java API docs. While these docs are not a tutorial, they are very helpful when you need to know how to use a particular class or interface. All of the methods that are available are listed, as well as detailed descriptions. For example, you can easily find the details about Object's default implementation of the equals() method.

I hope this helps. Please come back with more questions.

Keep Coding!

Layne

p.s. Note that convention dictates that class and interface names start start with upper case while variable and method names start in lower case.

[David Dickinson]

I have created a class CarValueComparator which extends Comparator

public abstract class CarValueComparator implements Comparator {
 
/**
 * 
 */
public CarValueComparator() {
super();
}
 
/* (non-Javadoc)
 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
 */
public static final Comparator CarValueComparator = new Comparator() {
public int compare(Car a, Car b) {
if (a.getValue() < b.getValue()) { return -1; }
else if (a.getValue() > b.getValue()) { return 1; }
else return 0;
}
 
public int compare(Object a, Object b) {
return 0;
}
};
}

Eclipse insists I must have the default line

public int compare(Object a, Object b) {

But when I use the following code

Collection.sort(ArrayList, CarValueComparator.compare(carA, carB)

It always used the default compare method which obviously doesn't do correct comparisons. How do I get around this? The idea of interfaces has be quite confused.


Thanks
[ December 02, 2004: Message edited by: David Dickinson ]

[David Dickinson]

Layne,

I've just seen your post so i'm going to make an attempt to incorporate the compareTo() method and i'll get back in touch.

Thank you so far!

[David Dickinson]

Hi,

I've altered my code as follows:

public abstract class Car implements Comparable {
 
public int compareTo(Loan a) {
if (this.Value < a.Value) { return -1; }
else if (this.Value > a.Value) { return 1; }
else { return 0; }
}
}

Now how do I call sort on my ArrayList (presume its called CarList)?

Collections.sort(CarList, ???? );

I don't know what to put in the ??? Thanks!

[Joel McNary]

I myself prefer the Comparatrr approach instead of the Comparable one; I made a slight change to your posted code.

public abstract class CarValueComparator implements Comparator {
/**
 * 
 */
public CarValueComparator() {
super();
}
 
/* (non-Javadoc)
 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
 */
public static final Comparator CarValueComparator = new Comparator() {
public int compare(Car a, Car b) {
if (a.getValue() < b.getValue()) { return -1; }
else if (a.getValue() > b.getValue()) { return 1; }
else return 0;
}
 
public int compare(Object a, Object b) {
Car carA = (Car)a;
Car carB = (Car)b;
return this.compare(carA, carB);
}
};
}

>Eclipse insists I must have the default line

public int compare(Object a, Object b) {

That's true, because the Comparator interface identifies that the two parameters are Objects -- you made them Cars.
This is because when the Collections calls the compare method, it calls the one with the Object, Object parameters.

>But when I use the following code

Collection.sort(ArrayList, CarValueComparator.compare(carA, carB)

try:

Collection.sort(myArrayList, new CarValueComparator())

You want to pass the Comparator, not the results of a comparison

[David Dickinson]

I tried exactly what you suggested but the following error occured...

Class must implement the inherited abstract method Comparator.compare
(Object, Object)

It still insists I need a method with the following code:

public int compare(Object arg0, Object arg1) {
// TODO Auto-generated method stub
return 0;
}

Otherwise I have to make my class abstract which I can't do as I instantiate instances of this class later in my package.

Any suggestions?

[Stan James]

The methods defined in the interfaces Comparable and Comparator call for methods with Object arguments. Sun had to do that because when they wrote the interface they had no idea what classes you'd write to compare. And now you have to have Object arguments because they did.

So, first thing, cast them into your real class.

public int compare(Object one, Object two)
{
   MyClass myOne = (MyClass)one;
   MyClass myTwo = (MyClass)two;
   now do comparisons ...
}

You may want to add null checking or instanceof checking or just let the exceptions fly. I have some comparators that look like this ... I assume this is common when equality can involve several fields.

int result = this.field1.compareTo(other.field1);
if ( result == 0 )
    result = this.field2.compareTo(other.field2);
if ( result == 0 )
    result = this.field3.compareTo( other.field3 );
return result;

Hope that helps!