Thursday, November 3, 2011

How to override compareTo method in Java - Example Tutorial

compareTo in Java is in the same league of equals() and hashcode() and used to implement natural order of object, compareTo is slightly different to compare() method of Comparator interface which is used to implement custom sorting order. I have seen during java interviews that many Java programmers not able to correctly write or implement equals(), hashCode() and compareTo() method for common business objects like Order or Employee. Simple reason behind this is that they either not understand the concept well enough or doesn't write this stuff at all. I will try to fill that gap in this Java tutorial and will see What is compareTo() method in java, how to write compareTo in Java and things to remember while implementing compareTo in Java.

What is compareTo() method in Java

compareTo() method is defined in interface java.lang.Comparable and it is used to implement natural sorting on java classes. natural sorting means the the sort order which naturally applies on object e.g. lexical order for String, numeric order for Integer or Sorting employee by there ID etc. most of the java core classes including String and Integer implements CompareTo() method and provide natural sorting.

Why do you need CompareTo()

How to write compareTo method in Object - Java ExampleSorting is an essential part of application development, which you often required to implement in your system. in Java sorting is implemented using Comparator and Comparable in Java. Since we store java objects in Collection there are also certain Set and Map which provides automating sorting when you insert element on that e.g. TreeSet and TreeMap. to implement sorting you need to override either compareTo(Object o) method or Comparable class or compare(Object o1, Object o2) method of Comparator class. Most of the classes implement Comparable to implement natural order. for example if you are writing Employee object you probably want to implement Comparable interface and override compareTo() method to compare current employee with other employee based on ID. So essentially you need to override compareTo() because you need to sort elements in ArrayList or any other Collection.

How to implement compareTo in Java

There are certain rules and important points to remember while overriding compareTo method:

1) CompareTo method must return negative number if current object is less than other object, positive number if current object is greater than other object and zero if both objects are equal to each other.

2) CompareTo must be in consistent with equals method e.g. if two objects are equal via equals() , there compareTo() must return zero otherwise if those objects are stored in SortedSet or SortedMap they will not behave properly. Since SortedSet or SortedMap use compareTo() to check the object if two unequal object are returned equal by compareTo those will not be added into Set or Map if they are not using external Comparator.  One example where compareTo is not consistent with equals in JDK is BigDecimal class. two BigDecimal number for which compareTo returns zero, equals returns false as clear from following BigDecimal comparison example:

BigDecimal bd1 = new BigDecimal("2.0");
BigDecimal bd2 = new BigDecimal("2.00");
     
System.out.println("comparing BigDecimal using equals: " + bd1.equals(bd2));
System.out.println("comparing BigDecimal using compareTo: " + bd1.compareTo(bd2));

Output:
comparing BigDecimal using equals: false
comparing BigDecimal using compareTo: 0
 
How does it affect BigDecimal ? well if you store these two BigDecimal in HashSet you will end up with duplicates (violation of Set Contract) i.e. two elements while if you store them in TreeSet you will end up with just 1 element because HashSet uses equals to check duplicates while TreeSet uses compareTo to check duplicates. That's why its suggested to keep compareTo consistent with equals method in java.

3) CompareTo() must throw NullPointerException if current object get compared to null object as opposed to equals() which return false on such scenario.

4) Another important point to note is don't use subtraction for comparing integral values because result of subtraction can overflow as every int operation in Java is modulo 2^32. use either Integer.compareTo()  or logical operators for comparison. There is one scenario where you can use subtraction to reduce clutter and improve performance. As we know compareTo doesn't care magnitude, it just care whether result is positive or negative. While comparing two integral fields you can use subtraction if you are absolutely sure that both operands are positive integer or more precisely there different must be less than Integer.MAX_VALUE. In this case there will be no overflow and your compareTo will be concise and faster.

5. Use relational operator to compare integral numeric value i.e. < or > but use Float.compareTo() or Double.compareTo() to compare floating point number as relational operator doesn't obey contract of compareTo for floating point numbers.

6. CompareTo() method is for comparison so order in which you compare two object matters. If you have more than one significant field to compare than always start comparing from most significant field to least significant field. here compareTo is different with equals because in case of equality check order doesn't matter. like in above example of compareTo if we don't consider Id and compare two student by its name and age than name should be first compare and than age, so if two student have same name one that has higher age should result in greater.

Student john12 = new Student(1001, "John", 12);
Student john13 = new Student(1002, "John", 13);
     
//compareTo will return -1 as age of john12 is less than john13
System.out.println("comparing John, 12 and John, 13 with compareTo :" + john12.compareTo(john13));

Output:
comparing John, 12 and John, 13 with compareTo :-1

7. Another important point while comparing String using compareTo is to consider case. just like equals() doesn't consider case, compareTo also do not consider case, if you want to compare regardless of case than use String.compareToIgnoreCase() as we have used in above example.



Where compareTo() method used in Java
---------------------------------------------------
In Java API compareTo() method is used in SortedSet e.g. TreeSet and SortedMap e.g. TreeMap for sorting elements on natural order if no explicit Comparator is passed to Collections.sort() method e.g.

List stocks = getListOfStocks();
Collections.
sort(stocks);

as mentioned earlier if compareTo is not consistent with equals then it could produce strange result. let took another example you put Stock A and Stock B on StockSet which is a TreeSet. Both Stock A and Stock B are equal by equals() method but compareTo return non zero values for it which makes that StockB will also be landed into TreeSet which was voilation of Set itself because it is not supposed to allow duplicates.

Example of compareTo() in Java
--------------------------------------

Let’s see an example of how to override compareTo method in Java. This method is very similar to equals and hashcode, key thing is compareTo should provide natural ordering e.g. in this example order of object based on Student ID.


public class Student implements Comparable {
   
private int id;
   
private String name;
   
private int age;
 
   
/*
     *Compare a given Student with current(this) object.
     *If current Student id is greater than the received object,
     *then current object is greater than the other.
     */
 
   
public int compareTo(Student otherStudent) {
       
// return this.id - otherStudent.id ; //result of this operation can overflow
       
return (this.id &lt; otherStudent.id ) ? -1: (this.id &gt; otherStudent.id) ? 1:0 ;

   
}
}

here is another example of compareTo method in Java on which compareTo uses two significant field to compare objects:

public class Student implements Comparable<Student> {
   .....   
    /**
     * Compare a given Student with current(this) object.
     * first compare name and than age
     */

    @Override
    public int compareTo(Student otherStudent) {      
        //compare name
        int nameDiff = name.compareToIgnoreCase(otherStudent.name);
        if(nameDiff != 0){
            return nameDiff;
        }
        //names are equals compare age
        return age - otherStudent.age;
    }
 
}


That’s all on implementing compareTo method in Java. Please add any other fact which you think important to note while overriding compareTo. In summary compareTo should provide natural ordering and compareTo must be consistent with equals() method in Java.

Related Java Tutorial

18 comments :

Eric Jablow said...

It's dangerous to use subtraction for comparing int variables. Remember, all arithmetic on integers is module 2^32. Let l = Integer.MIN_VALUE. Let r = Integer.MAX_VALUE. Then, l - r == -2^31 - (2^31 - 1) == -2^32 + 1. But this overflows, and so in Java, l - r ==2, and so this comparison has l > r.

In ordinary cases where the integers are reasonable measurements--human ages, number of wins in a sports season, chapters in a book--this won't matter. But ids can and should be arbitrary so people aren't tempted to use them for business purposes. Americans would be much better served if the Social Security Number were not used as a universal identifier. In fact, because ids should be immutable, the id variable would best be an Integer instead of an int, and probably final (though that will take extra work in database mappings), And then Integer.compareTo(Integer) works fine, not falling into the subtraction trap. It's logic is that of (l < r) ? -1 : (l > r) ? 1 : 0.

Javin @ outofmemory in Java said...

Hi Eric, You are absolutely correct. Thanks for bringing this important point while overriding compareTo. I think using logical operator for comparison makes lot of sense here.

Eric Jablow said...

One computing mistake in my post: l - r == -2^32 +1 == 1. Two grammar mistakes in my post: modulo, not module, and its logic, not it's.

Joshi said...

I too made the mistake of using subtraction for comparing integers inside compareTo() in Java luckily it never failed and I just realized this after reading this post. I think its very common mistake while overriding compareTo in Java.

Anonymous said...

String [] arrayA = {"Rene","Andrei","Xena"};
String [] arrayB = {"Diana","Tana","Madonna"};

compareTo and get alphabetical order?

ViraSundar said...

well compareTo is entirely different than equals() and hashCode. CompareTo is all about order rather than equality and that's why comparison in CompareTo is much trickier than in equals even for equal object.

Anonymous said...

String [] arrayA = {"Andrei","Rene""Xena"};
String [] arrayB = {"Diana","Madonna","Tana"};
String [] arrayC = {arrayA.length+arrayB.length}

What i am trying to do is to compare first Anderei and Dianathen Andrei comes first.Diana and Rene Diana comes first.then Rene and Madonna Madonna comes first and so on?

Anonymous said...

Good article, although worth noting that neither of the code examples override compareTo (in Object).

i.e.
compareTo (Student OtherStudent)
does not override
compareTo (Object o) in the Object class.

Both Object and Student implement the Comparable interface.

srinivas jalappagari said...

Hi Experts,
I want to know how to eliminate duplicate strings in an array and print unique values
example:String[] s=new String[]{"india","america","japan","america","china","india"}
Output should be:india,america,japan,china

Anonymous said...

Tell me the follow of compareTo(object obj) which object is acts as current object is that first element in the array list & second element acts as specified object.

Gorbachau said...

isn't it in above code, compareTo() method is not consistent with equals(). Since compareTo() only using id, while equals() using all three properties, it may be possible that two student with same id, but different name. Which means compareTo() will return zero, but equals will return false, i.e. compareTo is not consistent with equals

Prakash Gupta said...

@srinivas jalappagari :try this

String[] s = new String[] { "india", "america", "japan", "america",
"china", "india" };
// HashMap hs=new HashMap();
List hs = new ArrayList();
for (String aa : s) {
if (!hs.contains(aa)) {
hs.add(aa);
}
}
System.out.println("Lsit=="+hs);

David Nicoll said...

@srinivas jalappagari : Another possible solution

Set set = new HashSet();
for (String a : s) {
set.add(a);
}
System.out.println(set);

kammiti krishna said...

who is calling compareTo() method in our program

Anonymous said...

How can I compare double values inside compareTo method for sorting purpose?

Javin Paul said...

You can use Double.CompareTo() method, also you can use relational operator with double values e.g.

return this.doubleValue > o.doubleValue? 1 : this.doubleValue< o.doubleValue? -1 : 0;

p saikumar said...

in implementation of compareTo(),
in this line
return (this.id < otherStudent.id ) ? -1: (this.id > otherStudent.id) ? 1:0 ;

what is lt and gt

Anonymous said...

@p saikumar - Its less than and great than

Post a Comment