Page History

Choosing to implement the Comparable interface represents a commitment that the implementation of the compareTo() method adheres to the general usage contract for that method regarding how the method is to be called. Library classes such as TreeSet and TreeMap accept Comparable objects and use the associated compareTo() methods to sort the objects. However, a class that implements the compareTo() method in an unexpected way can cause undesirable results.

Wiki MarkupThe general usage contract for {{compareTo()}} from Java SE 6 API \[[API 2006|AA. Bibliography#API 06]\] states 8 API [API 2014] states that

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

iff

1. if y.compareTo(x) throws an exception.)
2. The implementor must also ensure that the relation is transitive: (x.compareTo(y)

>0

1. > 0 && y.compareTo(z)

>0

1. > 0) implies x.compareTo(z)

>0

1. > 0.
2. Finally, the implementor must ensure that x.compareTo(y) == 0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z))

,

1. for all z.
2. It is strongly recommended, but not strictly required, that (x.compareTo(y) == 0) ==

(

1. x.equals(y

)

1. ). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is

"

1. 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 either -1, 0, or 1 depending on whether the value of the expression is negative, zero or positive.

Never Implementations must never violate any of the first three conditions when implementing the compareTo() method. Implementations should conform to the fourth condition whenever possible.

Noncompliant Code Example (Rock-Paper-Scissors)

This noncompliant code example violates the third condition in the contract. This requirement states that the objects that compareTo() considers equal (by returning 0) must be ordered identically when compared to other objects. For example, it may be necessary to compare a card with any other card to check whether both belong to the same suit or have the same rank. When neither of these conditions is true, compareTo() is expected to order the cards based on rank alone. This situation may arise in a game like Uno or Crazy Eights, where one can place a card on the pile only when it shares a suit or rank with the topmost card on the pile.program implements the classic game of rock-paper-scissors, using the compareTo() operator to determine the winner of a game:

public final class CardGameEntry implements Comparable {
  public enum Roshambo private String suit;{ROCK, PAPER, SCISSORS}
  private intRoshambo rankvalue;

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

  public boolean equals(Object othis.value = value;
  }

  public int compareTo(Object that) {
    if (o!(that instanceof CardGameEntry)) {
      Cardthrow cnew = ClassCastException(Card)o;
      return suit.equals(c.suit) || (rank == c.rank); // Bad
    }
    returnGameEntry false;
  }

  // This method violates its contract
  public int compareTo(Object o) {t = (GameEntry) that;
    ifreturn (o instanceof Card) {
      Card c = (Card)o;
      if (suit.equals(c.suit) ) 
        return 0;value == t.value) ? 0
      if: ((c.rank >= rank + Integer.MIN_VALUE)value == Roshambo.ROCK && 
          (c.rank <= rank + Integer.MAX_VALUE) )
        // Check for integer overflowt.value == Roshambo.PAPER) ? -1
      : (value return== cRoshambo.rankPAPER - rank; // Order based on rank&& t.value == Roshambo.SCISSORS) ? -1
    }
    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 numbervalue == Roshambo.SCISSORS && t.value == Roshambo.ROCK) ? -1
      : 1;
  }
}

Here, comparing a with c} indicates that {{c is larger, and comparing b with c indicates that b is larger. Consequently, b must be larger than a. However, comparing a with b reports that a and b are equal. Therefore, the compareTo() implementation violates the general contract.

Compliant Solution

However, this game violates the required transitivity property because rock beats scissors, scissors beats paper, but rock does not beat paper.

Compliant Solution (Rock-Paper-Scissors)

This compliant solution implements the same game without using the Comparable interface:This compliant solution ensures both that the compareTo() contract is satisfied and also that the corresponding equals() method is consistent with the compareTo() method.

publicclass finalGameEntry class{
 Card implementspublic Comparable{
enum Roshambo private String suit;{ROCK, PAPER, SCISSORS}
  private intRoshambo rankvalue;

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

  public boolean equals(Object othis.value = value;
  }

  public int beats(Object that) {
    if (o!(that instanceof CardGameEntry)) {
      Card c=(Card)o;
      return suit.equals(c.suit) && (rank == c.rank); // Goodthrow new ClassCastException();
    }
    returnGameEntry false;
t  }

  // This method fulfills its contract
  public int compareTo(Object o) {= (GameEntry) that;
    ifreturn (o instanceof Card) {
      Card c=(Card)o;
      if (suit.equals(c.suit) &&value == t.value) ? 0
       :   (c.rankvalue >== rank + Integer.MIN_VALUE)Roshambo.ROCK &&
          (c.rank <= rank + Integer.MAX_VALUE) )  t.value == Roshambo.PAPER) ? -1
      : (value return== cRoshambo.rankPAPER - rank;
      return suit.compareTo(c.suit);
    }&& t.value == Roshambo.SCISSORS) ? -1
    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 negative number : (value == Roshambo.SCISSORS && t.value == Roshambo.ROCK) ? -1
      : 1;
  }
}

As required by the ordering, c is larger than both a and b and the comparison (a,b) produces an equal result. This maintains the compareTo() method's contract.

Risk Assessment

Violating the general contract when implementing the compareTo() method can result in cause unexpected results, possibly leading to invalid comparisons and information disclosure.

Automated Detection

...

Automated detections of violations of this rule is infeasible in the general case.

Tool	Version	Checker	Description
CodeSonar	Include Page CodeSonar_V CodeSonar_V	JAVA.CLASS.MCS	Missing Call to super (Java)
Coverity	7.5	FB.RU_INVOKE_RUN	Implemented

Related Guidelines

Bibliography

...

Image Added Image Added Image Added

The Coverity Prevent Version 5.0 MUTABLE_COMPARISON checker can detect the instances where compareTo method is reading from a non constant field. If the non-constant field is modified, the value of compareTo might change, which may break program invariants.

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this guideline on the CERT website.

Other Languages

This guideline appears in the C++ Secure Coding Standard as ARR40-CPP. Use a valid ordering rule.

Bibliography

\[[API 2006|AA. Bibliography#API 06]\] method [compareTo()|http://java.sun.com/javase/6/docs/api/java/lang/Comparable.html#compareTo(java.lang.Object)]
\[[JLS 2005|AA. Bibliography#JLS 05]\]

MET13-J. Classes that define an equals() method must also define a hashCode() method      05. Methods (MET)      MET15-J. Do not use deprecated or obsolete classes or methods