Ordered Objects

Ordering objects

When it comes to numbers, we have a perfect natural ordering, for instance:

When it comes to text, there is also a general consensus of how text should be ordered, such as:

"0123" - "20" - "9" - "app" - "apple" - "programming"

But for new classes, things are usually not so clear. For instance, considering the following class that models a mobile phone subscription with a price per month and an data limit per month:

public class Subscription {

    private double price;
    private int dataLimit;

    public Subscription(double price, int limit) {
        this.price = price;
        this.dataLimit = limit;
    }

    public double getPrice() { return this.price; }
    public int getDataLimit() { return this.dataLimit; }
}

For the following examples, is there a natural order?

new Subscription(30, 1000);
new Subscription(15, 250);
new Subscription(5, 20);
new Subscription(10, 15);

You could give preference to either the price or the dataLimit, or even come up with weighted sums that intend to combine both of them. In general, this is a problem when we have more than one attribute that we might consider to determine an order.

Java has two important interfaces that make it easy to make objects of our classes ordered. The Comparable interface can be used for natural orders that serve as a default order for objects of a class, whereas the Comparator interface can be used to define an ad-hoc order by creating objects that can determine the order of objects of another class.

The Comparable interface

If we want to define a natural ordering (or an ordering that is at least more natural than others), we can implement the Comparable interface. Before, we have already looked at interfaces in general. The Comparable interface is another one of Java's ready-made interfaces. For example: public class Subscription implements Comparable<Subscription>.

The Comparable interface defines the compareTo method used to compare objects: public int compareTo(E other);. If a class implements the Comparable interface, objects created from that class can be sorted using Java's sorting algorithms. The compareTo method required by the Comparable interface receives as its parameter the object to which the this object is compared. If the this object comes before the object received as a parameter in terms of sorting order, the method should return a negative number. If, on the other hand, the this object comes after the object received as a parameter, the method should return a positive number. Otherwise, 0 is returned. The sorting resulting from the compareTo method is called natural ordering.

The Comparable interface has the following rules in its contract:

• If we have x.compareTo(y) > 0 then we must have y.compareTo(x) < 0.
• It is transitive: if we have x.compareTo(y) > 0 and y.compareTo(z) > 0, then we must have x.compareTo(z) > 0.
• Finally, if we have x.compareTo(y) == 0, then the sign of x.compareTo(z) must be equal to the sign of y.compareTo(z).

For consistency, it is recommended that x.compareTo(y) == 0 is equal to x.equals(y), but this is not strictly required. If this is not the case, you should state this in the commentary of the class, for instance as follows: "Note: this class has a natural ordering that is inconsistent with equals.".

Although the previous rules can be a bit daunting, implementing Comparable<E> is often straightforward. For instance, see the following examples:

public class MyInt implements Comparable<MyInt> {
    private final int value;
    public MyInt(int i) {
        value = i;
    }

    @Override
    public int compareTo(MyInt o) {
        return value - o.value;
    }
}

public class MyDouble implements Comparable<MyDouble> {
    private double value;
    public MyDouble(Double val) {
        value = val;
    }

    @Override
    public int compareTo(MyDouble other) {
        return Double.compare(value, other.value);
    }
}

With a String, you can even delegate the comparison to the compareTo function of the String class! For instance, like this:

public class MyText implements Comparable<MyText> {
    private final String text;
    public MyText(String text) {
        this.text = text;
    }

    @Override
    public int compareTo(MyText other) {
        return text.compareTo(other.text);
    }
}

Let us also take a look at this with the help of a Member class that represents a child or youth who belongs to a club. Each club member has a name and height. The club members should go to eat in order of height, so the Member class should implement the Comparable interface. The Comparable interface takes as its type parameter the class that is the subject of the comparison. We'll use the same Member class as the type parameter.

public class Member implements Comparable<Member> {
    private String name;
    private int height;

    public Member(String name, int height) {
        this.name = name;
        this.height = height;
    }

    public String getName() {
        return this.name;
    }

    public int getHeight() {
        return this.height;
    }

    @Override
    public String toString() {
        return this.getName() + " (" + this.getHeight() + ")";
    }

    @Override
    public int compareTo(Member member) {
        if (this.height == member.getHeight()) {
            return 0;
        } else if (this.height > member.getHeight()) {
            return 1;
        } else {
            return -1;
        }
    }
}

As returning a negative number from compareTo() is enough if the this object is smaller than the parameter object, and returning zero is sufficient when the heights are the same, the compareTo method described above can also be implemented as follows.

@Override
public int compareTo(Member member) {
    return this.height - member.getHeight();
}

Since the Member class implements the Comparable interface, it is possible to sort the list by using the sort method. In fact, objects of any class that implement the Comparable interface can be sorted using the sort method. If a programmer wants to organize the original list, the sort method of the Collections class should be used. This, of course, assumes that the objects on the list implement the Comparable interface.

Sorting club members is straightforward now.

List<Member> members = new ArrayList<>();
members.add(new Member("mikael", 182));
members.add(new Member("matti", 187));
members.add(new Member("ada", 184));

for (Member m : members) {
    System.out.println(m);
}
System.out.println();
// sorting the stream that is to be printed using the sorted method
Collections.sort(members);
for (Member m : members) {
    System.out.println(m);
}

Returning to the example of the Subscription class for the mobile phone subscripts, we can observe that a user may want to choose how to sort the different subscriptions. For an implementation of the compareTo methods it is difficult to choose which one of the following two implementations is the most natural:

@Override
public int compareTo(Subscription other) {
    if (price != other.price) {
        // A lower price is better than a higher one
        return (int)Math.signum(price - other.price);
    }
    // A higher data limit is better than a lower one
    return other.dataLimit - dataLimit;
}

or this one:

@Override
public int compareTo(Subscription other) {
    if (dataLimit != other.dataLimit) {
        // A higher data limit is better than a lower one
        return other.dataLimit - dataLimit;
    }
    // A lower price is better than a higher one
    return (int)Math.signum(price - other.price);
}

Fortunately, there is another interface for situations as this one.

Comparator interface

Now, we will have a look at the Comparator interface, which is obviously slightly different from the Comparable and defines the following method: public int compare(E left, E right);. It should also behave very similar to compareTo, but now you are comparing left with right. The big difference between the two is the following: The compareTo() method of the Comparable interface defines a natural order, while the compare() method of the Comparator interface defines an ad-hoc order!

Here is an extensive example of an implementation of the compare method:

public class PriceComparator implements Comparator<Subscription> {
    @Override
    public int compare(Subscription left, Subscription right) {
        return (int)Math.signum(left.getPrice() - right.getPrice());
    }
}

or

public class DataLimitComparator implements Comparator<Subscription> {
    @Override
    public int compare(Subscription left, Subscription right) {
        return right.getDataLimit() - left.getDataLimit();
    }
}

and if we assign the following tasks to the compiler:

ArrayList<Subscription> subs = new ArrayList<>();
subs.add(new Subscription(5, 20));
subs.add(new Subscription(30, 1000));
subs.add(new Subscription(10, 15));
subs.add(new Subscription(15, 250));
System.out.println(subs);
Collections.sort(subs, new PriceComparator());
System.out.println(subs);
Collections.sort(subs, new DataLimitComparator());
System.out.println(subs);

it would print the following:

public class Employee {
    private int yearsOfService;
    private String surName;

    public Employee(String surName, int yearsOfService) {
        this.yearsOfService = yearsOfService;
        this.surName = surname;
    }

    public int getYearsOfService() { return this.yearsOfService; }
    public String getSurName() { return this.surName; }
}