Understanding the Comparable Interface
I am a new programmer learning about interfaces, and I was wondering if someone could explain how exactly the Comparable interface works. For example, I have two classes, one which implements Comparable and the other which uses Collections.sort to sort a collection of items using the compareTo method overridden in my class which implements Comparable. First off, why does calling Collections.sort ultimately result in the compareTo method being called? And how does the compareTo method work with only one argument? More specifically, when comparing this.price to temp.price, what is "this" referring to (I know it refers to the current object, but where is the object coming from?), and how does this end up sorting all elements in the list?
Class 1: Defines characteristics of each Item
Code :
package Item;
import java.util.*;
public class Item implements Comparable {
private String id;
private String name;
private double retail;
private int quantity;
private double price;
Item(String idIn, String nameIn, String retailIn, String quanIn) {
id = idIn;
name = nameIn;
retail = Double.parseDouble(retailIn);
quantity = Integer.parseInt(quanIn);
if(quantity>400)
price = retail*.5D;
else if(quantity>200)
price = retail *.6D;
else
price = retail*.7D;
price = Math.floor(price*100+.5)/100;
}
public int compareTo(Object obj) {
Item temp = (Item)obj;
if(this.price < temp.price)
return 1;
else if(this.price > temp.price)
return -1;
return 0;
}
public String getId() { return id; }
public String getName() {return name; }
public double getRetail() {return retail;}
public int getQuantity() {return quantity;}
public double getPrice() {return price;}
}
Class 2: Catalogs each item in a LinkedList
Code :
package Item;
import java.util.*; //includes class Collections with method sort which implements Comparable
public class Storefront {
private LinkedList catalog = new LinkedList();
public void addItem(String id, String name, String price, String quant) {
Item it = new Item(id, name, price, quant);
catalog.add(it);
}
public Item getItem(int i) {return (Item)catalog.get(i);}
public int getSize() {return catalog.size();}
public void sort() {Collections.sort(catalog);}
}
I didn't include my main class which just adds a few items then calls the sort() method in Storefront
Re: Understanding the Comparable Interface
1. Collections.sort() results in the compareTo() method being called due to inheritance. The Collections.sort() method accepts a List of objects that implement the Comparable Interface (or extend classes that implement the Comparable Interface), and calls the Comparable.compareTo(Comparable) method on each object in the List. Due to the way inheritance works, it will use the implementation of the compareTo() method that the object being invoked upon has created, which is why an implementation of the compareTo() method is required when you implement the Comparable Interface.
2. The compareTo() method works with only one object because it is comparing the object you sent as an argument to the object you invoked the compareTo() method on.
3. "this" is a keyword that refers to an instance of the object. "this.price" refers to the global price variable for the object you invoked the compareTo() method on. If there are no problems with scope (you have not declared any other variables named "price"), you don't even need the keyword "this". "temp.price" refers to the global price variable for the object you sent as the argument.
Your confusions seem to be more about how Object Oriented Programming works, instead of how the compareTo() method works.
Re: Understanding the Comparable Interface
Quote:
First off, why does calling Collections.sort ultimately result in the compareTo method being called? And how does the compareTo method work with only one argument? More specifically, when comparing this.price to temp.price, what is "this" referring to (I know it refers to the current object, but where is the object coming from?), and how does this end up sorting all elements in the list?
Interfaces can hide how some behavior is implemented. In the case of sorting, imagine for a moment if you wrote a Sorting algorithm that sorted Integers....you'd then have to rewrite the algorithm for each class type (String, Double, etc...), and doing so doesn't provide any way to sort any other class type without re-implementing the algorithm. But all the sorting algorithm needs to know is whether an object is less than, equal to, or greater than another...it should not care what it's sorting (String, Double, Integer, etc...) Enter the Comparable interface, which defines the behavior for comparing one object to another. Written in this way, the sorting algorithm can be written once to compare objects, so long as the class types being sorted implement the appropriate interface (Comparable). From the standpoint of the class that implements the interface (Comparable) - it uses its available data to compare itself to another as appropriate (the sorting algorithm never directly sees this). IMO this is one of the major concept to understand about interfaces - it abstracts algorithms so you can write them once rather than several times for each type of input data.
Re: Understanding the Comparable Interface
Thanks, but I still don't totally understand how Collections.sort() results in compareTo() being called. Could you be more detailed than "due to inheritance"? I'm looking at the Oracle Docs and I just don't get how Collections.sort(list) "jumps" to compareTo() being called for each item in the list. I get that each item in the list must implement the Comparable interface, but how does that cause the compareTo() method being called? What is the exact process going on here?
Re: Understanding the Comparable Interface
A quick, dirty, and simple (and somewhat poor) example to demonstrate an interface in this context:
Code java:
/**
* Interface defining an object that contains a value
*/
public interface Value{
public int getValue();
}
/**
* Implementation of the Value interface that is based upon an Integer
*/
public class IntegerValue implements Value{
private final int value;
public IntegerValue(int val){
this.value = val;
}
@Override
public int getValue(){
return value;
}
}
/**
* Defines a value of 2, for demonstration
*/
public class TwoValue implements Value{
@Override
public int getValue(){
return 2;
}
}
public class AddUtil{
/**
* Adds all the values in the parameter List
*/
public static int addValues(List<Value> adders){
int added = 0;
for ( Value add : adders ){
added += add.getValue();
}
return added;
}
public static void main(String[] args){
List<Value> adders = new ArrayList<Value>();
adders.add(new TwoValue());
adders.add(new IntegerValue(1));
adders.add(new TwoValue());
adders.add(new IntegerValue(10));
System.out.println(AddUtil.addValues(adders));
}
}
Should compile (although I didn't test). The point is that a) the AddUtil.addValues method doesn't care about implementation b) You can implement the Value interface any way you want - so long as it abides by the contract of the interface. To make an analogy to Collections.sort - Collections.sort is to AdderUtil.addValues as the Comparable interface is to the Value interface.
Re: Understanding the Comparable Interface
Quote:
Thanks, but I still don't totally understand how Collections.sort() results in compareTo() being called.
Generally when some type of thing is comparable with others of its kind (say people by age, or beer glasses by volume) it is often the case that some outside agency does the comparing: the barman might decide that a customer is old enough to buy beer, the customer that they want a pint.
In Java code comparisons are done by calling the compareTo() method of an instance using a reference to some other instance as an argument. The interface definition ensures that compareTo() is there able to be used. So it is the Comparable instance that actually does the comparing. It is as if the barman doesn't compare the customer's age with some standard but, instead, asks "How does your age compare to 20?". An odd way of doing things, perhaps. But effective.
Sorting a collection involves a whole lot of comparisons. (You can test that by actually sorting a bunch of things and noticing how you do it. In any case, it *can* be done using a whole bunch of comparisons.) These comparisons are done not by putting the things alongside one another and comparing, but after the fashion of the barman, asking "are you bigger, lesser or equal to that?" to the various elements of the collection. Being instances of Comparable they all implement the compareTo() method and, so, can answer such questions.
If you look at the source code for Collections.sort() you will see that this method does actually call the compareTo() method of the collection elements.
Re: Understanding the Comparable Interface
Quote:
If you look at the source code for Collections.sort() you will see that this method does actually call the compareTo() method of the collection elements.
This is what I was trying to do before I replied, and I still can't find it. Here is the code for Collections.sort():
Code :
public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
i.next();
i.set((T)a[j]);
}
}
No compareTo() call here, but maybe it's called in Arrays.sort(a). Here's the code from java.util.Arrays:
Code :
public static void sort(Object[] a)
sort(a, 0, a.length, NATURAL_ORDER);
}
This is where I get stuck. NATURAL_ORDER seems to be a variable of type Comparator<Object>, but I can find no other sort method in Arrays that takes this set of arguments. While I understand the answers to my previous question, there is obviously something else going on here that I don't quite understand. If someone could find and describe the full path from Collections.sort() to compareTo() then that would be pretty awesome
Re: Understanding the Comparable Interface
See the mergeSort method of Arrays in the source: java.util: Arrays.java directly calling compareTo method, which provides you with the stack trace path to where compareTo can be called (I say can, because the source shows multiple sort methods that could be called). See post #5 (which you seem to have completely ignored) if you wish to understand the concept in a more simplified manner
Re: Understanding the Comparable Interface
I only have the 1.7 source on this machine. But, commented out, is the definition of NATURAL_ORDER:
Code :
private static final Comparator<Object> NATURAL_ORDER = new Comparator<Object>() {
@SuppressWarnings("unchecked")
public int compare(Object first, Object second) {
return ((Comparable<Object>)first).compareTo(second);
}
};
A Comparator instance is what I was referring to before as an "outside agency" that might do the comparing. It is declared to have compare() method that takes two arguments which it compares. The NATURAL_ORDER comparator is used to do the sorting with "sort(a, 0, a.length, NATURAL_ORDER);"
The array elements being sorted are actually instances of Comparable and, as that piece of code shows, the NATURAL_ORDER comparator indeed uses the comparable's compareTo() to implement its own compare() method.
Re: Understanding the Comparable Interface
Schematically compareTo() is used to sort a list of comparable things as follows:
(1) Sorting the list is turned into sorting an array of comparable things by the Collections method
Then, in Arrays:
(2) A suitable Comparator instance is created which will use compareTo() to implement compare()
(3) The comparator's compare() - and hence the comparables' compareTo() - is called lots of times to effect the array sort
Back in Collections:
(4) The sorted array is used to repopulate the list
