Comparable vs. Comparator

Today a story about a design decision whether or not to implement the Comparable interface. We will start with the following code snippet – a simplified version of a UI widget that holds info about a person and can be selected by the user:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
public static class SelectablePerson {
    private final String name;
    private boolean selected;

    public SelectablePerson(String name) {
        this.name = name;
        this.selected = false;
    }

    public boolean isSelected() {
        return selected;
    }

    public void setSelected(boolean selected) {
        this.selected = selected;
    }
}

A quick notice: the code above is just to show my point in this post, not to be taken seriously when implementing similar functionality :) As you can see this class is fairly simple: just with a name and ’selected’ variable that can be switched on and off. We use those objects in our application to show a list of persons (maybe employees?) and allow the user to select a subset of them (to give a raise or fire?).

All is working fine, but then we get a new requirement: since it is hard to find an employee on the list we want to have it now sorted alphabetically. No biggy, right? We can sort all our objects with Collections.sort() and display them sorted. There is only one decision to make: either we will have ‘SelectablePerson’ implementing Comparable interface or write a separate comparator and use it in sort. So which one is the best option? Is it even important? Let’s check that!

Assume we go with the first possibility and implement additional interface. This means that we have to add one new method to the class – compareTo()… right? Well, close but not really. If we have compareTo() we also need to implement equals(). If we have this one we also need hashCode(). After all the class will look like this:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
public class SelectablePerson implements Comparable<SelectablePerson> {

    // ...

    public int compareTo(SelectablePerson other) {
        return this.name.compareTo(other.name);
    }

    @Override
    public int hashCode() {
        return name.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof SelectablePerson)) return false;
        SelectablePerson other = (SelectablePerson) obj;
        return this.compareTo(other) == 0;
    }
}

It is a pain that we had to go with equals() and hashCode() – I mean why do you need a hash code to sort out widgets? This is an indication that something is going wrong… but besides that all is fine and we can do the sorting. Mission accomplished!

Next requirement: we need our widget to react on the changes in other widgets of UI. This is done in a standard way with Observer-Observable pattern. What’s awesome is that in Java implementing that is really easy. Let’s be more specific with the new requirement: we need to have a reset button that will unselect all of the SelectablePerson widgets. This is the code of the button:

1:
2:
3:
4:
5:
6:
public class ResetButton extends Observable {
    public void press() {
        setChanged();
        notifyObservers();
    }
}

Now a simple change in SelectablePerson – implement Observer and as a reaction on (any) change of an observed object clear the selection. The code is following:

1:
2:
3:
4:
5:
6:
7:
8:
9:
public class SelectablePerson implements Comparable<SelectablePerson>,
        Observer {

    // ...

    public void update(Observable observable, Object value) {
        selected = false;
    }
}

Now when an reset() method of a reset button is invoked all SelectablePerson objects observing it will be unselected. Nice, huh?

Now we are back to the main question: was the decision of implementing Comparable good? You can use the code above, compile it and test it… all is working, right? Well, no… I really suggest trying to implement it as the bug is not that obvious and its good to see it on your own. One of the use cases making the bug appear is when you will instantiate the widgets with the following names: “Smith”, “Brown”, “Smith”, “Jackson”. You will notice that sorting is working fine, but the reset button does not work correctly – it resets all except one of the “Smith” widgets. Strange, huh? Even more bizarre: why only one of the same widgets is affected??

The explanation is quite simple: the reset button extends Observable (as it should). The Observable class internals handle the keeping and managing of all the objects that observe it. More specifically it keeps a list (Vector) of all observing objects and (when appropriate) notifies them about change in observed object. Every time you add another observer the Observable.addObserver() code checks whether or not the provided object is already in the list. How does it check? By comparing with equals() function, the one that we had to override… So because the name “Smith” appears twice in UI both of its widgets are considered by reset button equal and therefore only one is added to the list of observers. And the one that is not added is the one malfunctioning…

Now back to the main topic: would we encounter the same bug if we wrote a Comparator instead of implementing Comparable? No, we would not. You might argue that there are ways of keeping the Comparable and removing the bug… true, but that would just mask the design error we made. The reason we run into trouble is that the SelectablePerson instances are not suppose to have equals() or compareTo() methods as they are in fact unique and representing UI entities rather than values they carry. This comes to an additional lesson: if you do not really need to implement Comparable, do not do it… especially if you can get by with a Comparator :D

FindBugs plugin for Eclipse

Some time ago I wrote a post about FindBugs – a powerful tool for static code analysis in Java. Today I want to tell you about an Eclipse plugin that allows you to integrate FindBugs into your favorite IDE and automatically use it on your code.

The plugin works only with Eclipse 3.3+. The install instructions are quite simple, although depending on your Eclipse version some details like button names may vary. Do not worry though – the installation shouldn’t take you more than 5 minutes (yes, I did check it :D ).

After you have it installed you can configure its settings for every project you have in your workspace. You can choose what kind of bugs you want FindBugs to look for, how are they reported and when is FindBugs run. The nice thing is that you really do not have to do that as the default settings are pretty reasonable. To get to the settings menu you have to right click on the project and then choose Properties > FindBugs. It looks like this:

For every project you can set custom preferences of what kind of bugs are you interested in.

After all is configured it is time to run the FindBugs. If you have not set it to run automatically you can start it by right clicking on your project and choosing FindBugs > FindBugs. Below is an example of a code that has been analyzed by FindBugs. Can you see what is wrong with it?

Code of the analyzed program. Notice the 'bug' symbols on the left.

Notice the little bug markers on the left side of the code – they point to the places where errors have been found. If you move your cursor over them you will get a list of all issues detected – exactly like with regular Eclipse Java warnings. All those errors can also be seen in a ‘Bug Explorer’ window with additional description. To see this window go to Window > Show View > Other > FindBugs > Bug Explorer. For our code sample the list of errors is as following:

A view of Bug Explorer tab with all the bugs found in the code.

As you can see FindBugs found 7 problems with the code. Have you managed to find them all by yourself? Even if you did you probably see that it is much easier and safer to have FindBugs to detect those for you. And now with this plugin it is also much easier! :D

Few words on how to compare integers

Before I say anything I want to share with you a code snippet that is a simplified version of something I have recently wrote in my work. There is a small, yet painful bug in this code… can you see it?

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
public static class Point implements Comparable<Point> {
    private int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Point other) {
        if (this.x != other.x) {
            return this.x - other.x;
        } else {
            return this.y - other.y;
        }
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof Point)) return false;
        Point other = (Point) obj;
        return (this.x == other.x && this.y == other.y);
    }

    @Override
    public int hashCode() {
        return 31 * x + y;
    }
}

This is a simple value class represanting a point. At first glance everything is good with it: the hash function is not sophisticated, but it is correct and legal. The equals() method is written ‘by the book’ so it is probably OK. The class implements Comparable interface and defines a lexicographic order of the points – the code of compareTo() is standard and fulfills the contract of the interface. All three methods are compatible with each other: hash codes of equal points are equal, comparisons are transitive, if A.compareTo(B) == 0 then A.equals(B)… Basically all is fine, so where is the bug? Is there any bug at all?

Unfortunatelly there is a bug in this code. What is worse you probably read about it many times (’Effective Java’ item 11, ‘Java Puzzlers’ puzzle 65, the list goes on an on…). The problem with this code is that substraction based comparators are BAD as they often exposes you to danger of an overflow. This is what happens in this case – see the following:

1:
2:
3:
4:
5:
6:
7:
8:
9:
public static void main(String[] args) {
    Point pZero  = new Point(0, 0);
    Point pPlus  = new Point(2000000000, 0);
    Point pMinus = new Point(-2000000000, 0);

    System.out.println( pPlus.compareTo(pZero) > 0 );
    System.out.println( pZero.compareTo(pMinus) > 0 );
    System.out.println( pPlus.compareTo(pMinus) > 0 );
  }

We are comparing in this code three points. When you look at the declaration of those object you can already see the order of them: pPlus > pZero > pMinus. Just to be sure we check it by printing to console the result of compareTo() function. If you execute this code you’ll get that as expected ‘true’ for pPlus > pZero and ‘true’ for pZero > pMinus. The suprizing thing is the last comparison that evaluates to false. This is because of the integer overflow: in pPlus.compareTo(pMinus) the result value is 2000000000 – (-2000000000) == -294967296! Scary, right? :)

Cialis Online Pharmacy