Friday, February 7, 2014

Java Comparable Example for Natural Order Sorting

Java allows you to sort your object in natural order by implementing Comparable interface. It's one of the fundamental interface of Java API and defined in java.lang package, which means you don't need to implement this unlike its counterpart Comparator, which is defined in java.util package.  Comparable is used to provide natural order of sorting to objects e.g. numeric order is natural order for numbers, alphabetic order is natural order for String and chronological order is natural for dates. Similarly when you define your own objects e.g. Person, sorting it on name sounds natural. Similarly for teams, ranking seems their natural orders. It all depends how object is looked in their domain. By the way, you are not limited to just one order, you can sort objects in any order by using java.util.Comparator, as we have seen in our last article custom sorting in Java. Comparable interface defines abstract method compareTo(), you need to override this method to implement natural order sorting of objects in Java. This method returns positive if the object, on which you are calling this method is greater than other object, return negative, if this object is less than other and returns zero if both object are equal. Several or other classes from Java API relies on this interface for their behaviour, for example Arrays.sort(), Collections.sort() uses this method to sort objects contained in Array and Collection in their natural order. Similarly SortedSet and SortedMap implementation e.g. TreeSet and TreeMap also uses compareTo() method to keep their elements sorted. I have earlier shared some tips to override compareTo() method, which is also worth looking if you are implementing Comparable interface. In this article, we will see a simple example of Java Comparable interface, to sort objects in their natural order.



Comparable and compareTo Method

Comparable has only one method compareTo(), which is where we define logic to compare objects. As I said in previous paragraph that this method returns positive, negative and zero depending upon result of comparison, but most important thing, there is no restriction on return 1, 0 or -1 for greater, equal and lesser results, you can return any positive or negative number, this property is utilized in this example, but it comes with caveat that difference between them should not exceed, Integer.MAX_VALUE, well explained in my favourite book Effective Java. There are few more things, you need to consider while implementing Comparable interface. Before Java 5, its compareTo() method accepts java.lang.Object, but after introduction of Generics, this class can be written in standard type T. This makes it type-safe with compiler helping you by flagging error, when you pass different object to compareTo(). So always use generic version. Second thing, make sure your compareTo() is consistent with equals() method. Though this is not a requirement mandated by compiler or Java API, and there are examples of violating this principle in Java API itself e.g. BigDecimal, you should make them consistent if you are going to store object in SortedSet or SortedMap. Failing to do so, will result in classes like Set breaking their invariants and allowing duplicates. One more important thing to remember is order of comparison, if your object contains multiple value fields then the order on which you compare is important, compare them from most useful to least useful. This is where it differs with equals, in that you don't need to put attention on order of comparison, though comparing primitives earlier is preferred due to performance reason, but here it affects your sorting order. If you are comparing objects, then call their respective compareTo() methods, don't reinvent comparison. Last but not the least Prefer relational operator over arithmetic operator for comparing numeric fields. I also recommend to read corresponding item on Effective Java for more deeper understanding of this useful concept and don't forget to read about difference between Comparable and Comparator interface before going to any Java interview


Java Comparable Example

Java Comparable Example - Natural Order Sorting Objects
Here is our code example of how to implement Comparable interface in Java.  This code is saved in a Java file called HelloComparable.java, but it contains two classes, first HelloComparable, which is a test class to demonstrate example, and second class named Bank, which is our domain object. Banks has just two fields, name and ranking. In this example, I have taken their ranking as natural order, but in  some cases it may well be their name as well.  Point here is whatever logic you put on compareTo() method, that becomes your natural order, so you should put the logic which is most common in your application e.g. sorting Employee objects on id is most common, and sorting Event object on date is most common. If you look at code of compareTo() method it just does an integer arithmetic and return result its possible because ranking are small positive number. It makes your code clean, but only if you are 100% sure that difference will not exceed maximum value of integer in product's life time, because it it happens it will create subtle bugs due to integer overflow, giving impression that your natural order sorting is working in many cases but suddenly fails. By the way, I would like to share debugging tips with such condition, if you ever face an issue, which is intermittent, focus on data and concurrency. Repeat test with same data and if you are not able to reproduce than focus on concurrency characteristic of application. Coming bank to our Comparable example, we have stored all six banks in random order in a List and using Collections.sort() method to sort them on their natural order. This is an overloaded method, where other version also expect Comparator for custom order sorting. You can also use Arrays.sort() method, if you prefer to store your object in array. Both Collections.sort() and Arrays.sort() sort objects in their natural order, defined by compareTo() method of java.lang.Comaprable interface.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class HelloComparable {

    public static void main(String args[]) {
        Bank citibank = new Bank("Citibank", 1);
        Bank icici = new Bank("ICICI", 5);
        Bank bankOfAmerica = new Bank("BankOfAmerica", 2);
        Bank dbs = new Bank("DBS", 6);
        Bank hsbc = new Bank("HSBC", 3);
        Bank scb = new Bank("Standard Charted", 4);

        List<Bank> banks = new ArrayList<Bank>();
        banks.add(citibank);
        banks.add(icici);
        banks.add(bankOfAmerica);
        banks.add(dbs);
        banks.add(hsbc);
        banks.add(scb);

        // print banks in unsorted order
        System.out.println("List of Banks in unsorted order" + banks);

        // Sort bank on their natural order, which is ranking
        Collections.sort(banks);

        // print banks in their natural order, sorted
        System.out.println("List of Banks in sorted order" + banks);
    }
}

class Bank implements Comparable<Bank> {

    private String name;
    private int ranking;

    public Bank(String name, int ranking) {
        this.name = name;
        this.ranking = ranking;
    }

    @Override
    public int compareTo(Bank bank) {
        return this.ranking - bank.ranking; // possible because ranking is small
        // positive integer
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + ranking;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        Bank other = (Bank) obj;
        if (name == null) {
            if (other.name != null) {
                return false;
            }
        } else if (!name.equals(other.name)) {
            return false;
        }
        if (ranking != other.ranking) {
            return false;
        }
        return true;
    }

    @Override
    public String toString() {
        return String.format("%s: %d", name, ranking);
    }

}

Output:
List of Banks in unsorted order[Citibank: 1, ICICI: 5, BankOfAmerica: 2, DBS: 6, HSBC: 3, Standard Charted: 4]
List of Banks in sorted order[Citibank: 1, BankOfAmerica: 2, HSBC: 3, Standard Charted: 4, ICICI: 5, DBS: 6]


That's all in this Java Comparable example. Always remember to make your compareTo() method consistent with equals, only use integer arithmetic operation in compareTo if you know numbers are positive and small, and their difference will not exceed maximum value of integer in Java. You should implement Comparable interface for all value or domain classes e.g. Order, Trade, Instrument, Security, Counterparty etc . 

1 comment :

Eric Jablow said...

Why not use the Java 7 Objects.hash(Object...values) method in your Bank.hashCode method? Use Objects.equals(Object a, Object b) in Bank.equalTo() also. I would never use subtraction for comparing numbers for the same reason that I always wear my seatbelt when driving. The one time I forget, I will probably crash.

Post a Comment