MET34-J. Follow the general contract when implementing the compareTo method

Objects of a class can be ordered relative to one another. One way to do this is for the class to implement the Comparable interface. Library classes like TreeSet or TreeMap will accept Comparable objects and use their compareTo() methods to sort them. However, a class that implements the compareTo() method in an unexpected way could cause unexpected results, like a TreeSet reporting it does not contain an object that it really does contain, that could lead to exploitable behavior.

The general usage contract for compareTo() has been put forth verbatim from the Java specification:

The implementor must ensure sgn(x.compareTo ) == -sgn(y.compareTo ) for all x and y. (This implies that x.compareTo must throw an exception iff y.compareTo throws an exception.)

The implementor must also ensure that the relation is transitive: (x.compareTo >0 && y.compareTo(z)>0) implies x.compareTo(z)>0.

Finally, the implementor must ensure that x.compareTo ==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z.

It is strongly recommended, but not strictly required that (x.compareTo ==0) == (x.equals ). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is "Note: this class has a natural ordering that is inconsistent with equals."

In the foregoing description, the notation sgn(expression) designates the mathematical signum function, which is defined to return one of -1, 0, or 1 according to whether the value of expression is negative, zero or positive.

Do not violate any of these four conditions when implementing the compareTo() method.

Noncompliant Code Example

This noncompliant code example violates the third condition in the contract. This requirement states objects that compareTo() considers equal (returns 0) must be ordered the same with respect to other objects. Consider a Card that considers itself equal to any card of the same suit or same rank; otherwise it orders based on rank. This might arise in a game like Uno or Crazy Eights, where you can only place a card on the pile that shares a suit or rank with the top card on the pile.

public final class Card implements Comparable{
  private String suit;
  private int rank;

  public Card(String s, int r) {
    if (s == null)
      throw new NullPointerException();
    suit = s;
    rank = r;
  }

  public boolean equals(Object o) {
    if (o instanceof Card){
      Card c=(Card)o;
      return suit.equals(c.suit) || (rank == c.rank);
    }
    return false;
  }

//This method violates its contract
  public int compareTo(Object o){
    if (o instanceof Card){
      Card c=(Card)o;
      if(suit.equals(c.suit)) return 0;
      return c.rank - rank;
    }
    throw new ClassCastException();
  }

  public static void main(String[] args) {
    Card a = new Card("Clubs", 2);
    Card b = new Card("Clubs", 10);
    Card c = new Card("Hearts", 7);
    System.out.println(a.compareTo(b)); //returns 0
    System.out.println(a.compareTo(c)); //returns a negative number
    System.out.println(b.compareTo(c)); //returns a positive number
  }
}

Compliant Solution

Make sure you fulfill the compareTo() contract, and don't forget to make sure your corresponding equals() method matches with compareTo().

public final class Card implements Comparable{
  private String suit;
  private int rank;

  public Card(String s, int r) {
    if (s == null)
      throw new NullPointerException();
    suit = s;
    rank = r;
  }

  public boolean equals(Object o) {
    if (o instanceof Card){
      Card c=(Card)o;
      return suit.equals(c.suit) && (rank == c.rank);
    }
    return false;
  }

  //this method fulfills its contract
  public int compareTo(Object o){
    if (o instanceof Card){
      Card c=(Card)o;
      if(suit.equals(c.suit)) return c.rank - rank;
      return suit.compareTo(c.suit);
    }
    throw new ClassCastException();
  }

  public static void main(String[] args) {
    Card a = new Card("Clubs", 2);
    Card b = new Card("Clubs", 2);
    Card c = new Card("Hearts", 7);
    System.out.println(a.compareTo(b)); //returns 0
    System.out.println(a.compareTo(c)); //returns a negative number
    System.out.println(b.compareTo(c)); //returns a negative number
  }
}

Risk Assessment

Violating the general contract when overriding the compareTo() method can lead to unexpected results.

Automated Detection

TODO

References

Java API