Collections.binarySearch Question

[Clay Chow]

Can a list be sorted & searched if the array elements implement Comparable only ? The below code creates an ArrayList of "Sheep" objects (which implement Comparable). However, I get the below error when I compile. The code compiles when I substitute Integer in for Sheep; which leads me to think it works because Integers have a natural order. But would implementing Comparable make any object have a natural order?

Thanks!


C:\SCJP\del>javac Jav.java
Jav.java:55: cannot find symbol
symbol : method binarySearch(java.util.List<Sheep>,Sheep)
location: class java.util.Collections
int a = Collections.binarySearch(pq, new Sheep("Rack"));
^
1 error

import java.util.*;
 
interface Hungry<E> { void munch ( E e); }
 
interface Herbivore<E extends Plant> extends Hungry<E>{}
interface Carnivore<E extends Animal> extends Hungry<E>{}
abstract class Animal{}
abstract class Plant{}
class Grass extends Plant{}
class Sheep extends Animal implements Herbivore<Plant> , Comparable{
public void munch( Plant e) {}
String name;
public int compareTo(Object a) {
return name.length() - ((Sheep)a).name.length();
}
public int compare(Object a, Object b) {
return ((Sheep)a).name.length() - ((Sheep)b).name.length();
}

public boolean equals(Object a) {
return true;
//return ((Sheep)a).name == name;
}
Sheep(String s) { name = s;}

public String toString() { return name;}

 
public static void main(String... e) {
 
List<Sheep> pq = new ArrayList<Sheep>();
pq.add(new Sheep("Bad"));
pq.add(new Sheep("Bill"));
 
Collections.sort(pq);

int a = Collections.binarySearch(pq, new Sheep("Rack"));
System.out.println(a);
System.out.println(pq);
}
}

[Harvinder Thakur]

Originally posted by Clay Chow:

However, I get the below error when I compile.

The code that you have given compiles & runs fine.
May be you've given the wrong code and also do mention the source of your code.

[Clay Chow]

curious.
I am definitely getting an error (using 1.6.0_07).
I would agree that there should be no error, but am curious as to what the result would be. I wrote this to see how the binarySearch method works: since the Sheep.equals method always returns true, I assume that it will return the index of any element that matches.




Source:
Extended code from Osbourne McGraw SCJP 6 Study Guide. Although the question I'm asking is not the same.

[Campbell Ritchie]

It ought to be implements Comparable<Sheep> . . .
Then you can have Sheep as the type of the parameter to the compareTo method. You can then forget about the class casting, too.
Telling the compiler to implement Comparable<T> will lead the compiler to "believe" that this class has a "natural order."

You realise that two Sheep with the same name length will be left alone by the sort algorithm?
And imagine what will happen if you have a flock of 976 sheep, all with 6 letters in their name. The sort method will leave them all in the same order and the binary search will have no chance of finding them.

Suggest that, if you are comparing by the name field, and name is a String, and String already implements Comparable<String>, you could try changing the compareTo method to read

return name.compareTo(other.name);

You ought to have a look at the Object class and read about equals.
You will be in a situation where woolly.equals(obj) and !obj.equals(woolly). The sort and search methods are dependent on the compare, equals (and maybe hashCode) methods being implemented correctly.

The way binary search works is that it finds the middle element by taking myArray.length / 2; if that is equal, then eureka!
If it is "less" (compareTo returns negative) it tries middle / 2, otherwise it tries (middle + length) / 2 and keeps going until it runs out of options or finds something.
What happens if compareTo() returns 0 and equals returns false, I am not sure. Maybe it returns a negative result.

[Clay Chow]

Thanks for your help!

But your answer begs one more question: why does implementing Comparable<T> but not just Comparable, lead the compiler to "believe" that this class has a "natural order." ?


This would lead me to believe any object that implements Comparable<Sheep> would be accepted in that binarySearch argument. But that is not the case.
So I guess the compiler is looking for a Sheep object as well.

[Harvinder Thakur]

Originally posted by Campbell Ritchie:

What happens if compareTo() returns 0 and equals returns false, I am not sure. Maybe it returns a negative result.

In the code snippet in the OP, if i make the equals() method to return "false" then the result is still the same even if compareTo() returns *0* which it will because of the way compareTo() logic has been written.
I believe the reason is that the equals() method is not used in the binarySearch or sort. It's only the compareTo() method that is used.
Please correct me if i'm wrong.

Originally posted by Campbell Ritchie:

Telling the compiler to implement Comparable<T> will lead the compiler to "believe" that this class has a "natural order."

Can you please elaborate on the above statement regarding "natural order"?

I agree with the rest of the explanation given by Campbell regarding how one should correctly implement the compareTo() method.

@Clay: I am using java version "1.5.0_05" and the code compiles and gives the output:

1
[Bad, Bill]

[Campbell Ritchie]

Read the API for Comparable<T> which used to be called Comparable. It there tells you that Comparable (or Comparable<T> is used for classes which have a "natural order." Whoever wrote the sort method which takes Comparable<...> as a parameter wrote it on the assumption that its parameters have a natural order, so when it is compiled and executed, that is on the assumption that it has a natural order.
Whoever wrote the compiler did so on the assumption that Comparable<T> represents a natural order. The same applied to Comparable when it was called Comparable rather than Comparable<T>.

If you put implements Comparable<...> on something which doesn't have a natural order, you needn't expect the correct results back.

I think the nearest you have to a natural order for sheep (do real sheep have a natural order) is in order of name.

[Harvinder Thakur]

@Campbell:
Thanks for the explanation on natural order.
Can you please elaborate if and how the equals() method is used in the sort() and binarySearch() methods? Because as per my understanding equals() is not used in either of sort() or binarySearch()?

[Campbell Ritchie]

I don't think equals() is used in sort().
I think (but I am not sure) that methods which identify an object in a Collection use the equals() method to signal that they have found it. You look in the Collection for an object called obj, and when your collection element returns true from obj.equals(element) or element.equals(obj), the method is programmed to assume it has "found it."

Find a file called src.zip in your Java installation folders, unzip it to a convenient location, find the java folder, then the util folder, then the Collections class, and you can read the code of the binarySearch method. That will confirm how the method works.

[Harvinder Thakur]

Thanks a lot for the explanation Campbell. In fact, i did check up the Collections class source code and found that neither sort() nor binarySearch() use the equals() method. They both use the compareTo() method.

[Campbell Ritchie]

Aha. I never knew about it using compareTo. Thank you