Page History

Objects of a class can be ordered relative to one another. One way to do this is for the class to implement the Comparable interfaceChoosing to implement the Comparable interface represents a commitment that the implementation of the compareTo() method adheres to the general contract for that method regarding how the method is to be called. Library classes such as TreeSet and TreeMap} accept {{Comparable objects and use their the associated compareTo() methods to sort themthe objects. However, a class that implements the compareTo() method in an unexpected way can cause undesirable results.unmigrated-wiki-markup

The general usage contract for {{compareTo()}} from Java SE 6 API \[[API 06|AA. Java References#API 06]\] states that:8 API [API 2014] states that

1. The implementor

The implementpr

1. 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.

Do not Implementations must never violate any of the first three conditions when implementing the compareTo() method. Implementing Implementations should conform to the fourth condition is strongly recommended but is not necessarywhenever possible.

Noncompliant Code Example

...

(Rock-Paper-Scissors)

This program implements the classic game of rock-paper-scissors, using the compareTo() operator to determine the winner of a game:This noncompliant code example violates the third condition (transitivity) in the contract. This requirement states that the objects that compareTo() considers equal (returns 0) must be ordered the same with respect to other objects. For example, a card is to be compared against any other card to check whether both belong to the same suit or have the same rank. If none of these conditions is true, the compareTo() is expected to order the objects based on rank alone. 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 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;
  this.value = value;
  }

  public booleanint equalscompareTo(Object othat) {
    if (o!(that instanceof CardGameEntry)) {
      Cardthrow cnew = ClassCastException(Card)o;
    }
  return suit.equals(c.suit) || (rank GameEntry t == c.rank); // bad
    }(GameEntry) that;
    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;
(value == t.value) ? 0
      : if((c.rank >= rank + Integer.MIN_VALUE)value == Roshambo.ROCK && 
      (c.rank <= rank + Integer.MAX_VALUE))
        // check for integer underflow/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, the comparison between (a,c) yields that c is larger. However, the comparison (b,c) yields b as larger. This means b must be larger than a. However, comparing (a,b) results in the value 0 (same).

Compliant Solution

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 that the compareTo() contract is satisfied, and the corresponding equals() method is consistent with compareTo().

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 = rthis.value = value;
  }

  public booleanint equalsbeats(Object othat) {
    if (o!(that instanceof CardGameEntry)) {
      Card c=(Card)o;
      return suit.equals(c.suit) && (rank == c.rank); // goodthrow new ClassCastException();
    }
    returnGameEntry false;
  }

  //this method fulfills its contract
  public int compareTo(Object o){t = (GameEntry) that;
    ifreturn (ovalue instanceof Card){
      Card c=(Card)o;== t.value) ? 0
      if(suit.equals(c.suit) && (c.rank >= rank + Integer.MIN_VALUE): (value == Roshambo.ROCK && (ct.rankvalue <== rank + Integer.MAX_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 contract.

Exceptions

MET34-EX1: In some situations it may be necessary to violate the condition that (x.compareTo(y) == 0) == (x.equals(y) ). However, as this will make an object Comparable, it should not be used in most data structures (like TreeSet and TreeMap) that deal with Comparable objects. It would be better to use a separate method entirely. If compatibility issues demand the use of this non-standard compareTo() method, care should be taken through comments or other means that the object is not used in data structures that expect a standard Comparable.

Risk Assessment

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

Automated Detection

TODO

Related Vulnerabilities

Search for vulnerabilities resulting from the violation Automated detections of violations of this rule on the CERT website.

Other Languages

This rule appears in the C++ Secure Coding Standard as ARR40-CPP. Use a Valid Ordering Rule.

References

is infeasible in the general case.

Related Guidelines

Bibliography

...

Image Added Image Added Image Added Wiki Markup\[[API 06|AA. Java References#API 06]\] [method compareTo()|http://java.sun.com/javase/6/docs/api/java/lang/Comparable.html#compareTo(java.lang.Object)] \[[JLS 05|AA. Java References#JLS 05]\]