Tuesday, February 7, 2017

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 interfaces 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 a natural order for numbers, alphabetic order is a 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 order. It all depends on how the object is looked into 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 objects, return negative if this object is less than other and returns zero if both object are equal.

Several other classes from Java API rely on this interface for their behavior, 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 use 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 a Java Comparable interface, to sort objects in their natural order.

And, If you are new to Java world then I also recommend you go through The Complete Java MasterClass on Udemy to learn Java in a better and more structured way. This is one of the best and up-to-date courses to learn Java online.







Comparable and compareTo Method

Comparable has only one method compareTo(), which is where we define logic to compare objects. As I said in the previous paragraph that this method returns positive, negative and zero depending upon the result of the 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 the caveat that difference between them should not exceed, Integer.MAX_VALUE, well explained in my favorite book Effective Java.

There are few more things, you need to consider while implementing a Comparable interface. Before Java 5, its compareTo() method accepts java.lang.Object, but after the 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 a different object to compareTo().

So always use the generic version. Second thing, make sure your compareTo() is consistent with equals() method. Though this is not a requirement mandated by the 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 invariant and allowing duplicates.

Java Comparable Example How to

One more important thing to remember is the 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 the order of comparison, though comparing primitives earlier is preferred due to performance reason, here it affects your sorting order. If you are comparing objects, then call their respective compareTo() methods, don't reinvent comparison.

Last but not least Prefer relational operator over arithmetic operator for comparing numeric fields. I also recommend reading the corresponding item on Effective Java for a deeper understanding of this useful concept and don't forget to read about the difference between Comparable and Comparator interface before going to any Java interview.



Java Comparable Example

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 an example, and a 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 the natural order, but in some cases it may well be their name as well.  The 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 a date is most common.

If you look at the code of compareTo() method it just does integer arithmetic and returns result it's possible because ranking is a small positive number. It makes your code clean, but only if you are 100% sure that difference will not exceed the maximum value of an integer in product's lifetime, because it happens it will create subtle bugs due to integer overflow, giving the impression that your natural order sorting is working in many cases but suddenly fails.

Java Comparable Example - Natural Order Sorting Objects


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 the test with the same data and if you are not able to reproduce than focus on concurrency characteristic of the 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 versions also expect a Comparator for custom order sorting. You can also use Arrays.sort() method, if you prefer to store your object in the 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 the maximum value of an integer in Java. You should implement a Comparable interface for all value or domain classes e.g. Order, Trade, Instrument, Security, Counterparty, etc.

Further Learning
Java In-Depth: Become a Complete Java Engineer
Java Fundamentals: Collections
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz


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