CODEWITHSUNDEEP
java
ragingcorgi
ragingcorgi

Reputation: 3468

Comparison method violates its general contract- overlapping conditions

I'm stuck in a exception where java complains the comparison method is wrong.

Here's the rules: I defined a class called match. Imagine searching through 2 sequences to find identical substrings. If there exists 2 identical substrings, call it a match. The score is how long the substring is, and seq1/2 start/end marks where the 2 substrings begin and end. The goal is to pick the longest substring match. If the 2 matches have the same score, I'll pick a match that starts earlier in both sequences. Otherwise I ignore the rest by making them equal to each other.

Here's the code that's wrong:

public class CompareMatch implements Comparator<match>{
    @Override
    public int compare(match o1, match o2) {
    if(o1.score>o2.score)   return -1;
    if ((o1.score==o2.score)&&((o1.seq1start<o2.seq1start)&&(o1.seq2start<o2.seq2start))) 
        return -1;
    if((o1.score==o2.score)&&!((o1.seq1start<o2.seq1start)&&(o1.seq2start<o2.seq2start)))
        return 0;
    return 1;
    }
}

Also the match class is defined as follows:

public class match {
    public int seq1start;
    public int seq1end;
    public int seq2start;
    public int seq2end;
    public int score;
    }

Can someone help me pick out which part of the comparison logic is wrong? I must have overlapped one of the conditions. Thanks

Upvotes: 0

Views: 103

Answers (2)

thejh
thejh

Reputation: 45578

How about rewriting it like this? Should be more clear this way – first compare the more significant components, then the less significant ones.

Also, I think that, in order to make the function contract-abiding, you need to have a transitive sorting condition, and I think that your idea does not behave that way.

Try this:

// first compare scores
if (o1.score>o2.score) return -1; /* higher score for o1 -> o1 */
if (o1.score<o2.score) return 1; /* higher score for o2 -> o2 */

// scores are equal, go on with the position
if (o1.seq1start+o1.seq2start < o2.seq1start+o2.seq2start) return -1; /* o1 is farther left */
if (o1.seq1start+o1.seq2start > o2.seq1start+o2.seq2start) return 1; /* o2 is farther left */

// they're equally good
return 0;

Upvotes: 1

SKi
SKi

Reputation: 8476

Your code is breaking the following rule of API:

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y

If compare(a,b) returns -1 in here:

if ((o1.score==o2.score) &&((o1.seq1start<o2.seq1start)&&(o1.seq2start<o2.seq2start))) 
    return -1;

then compare(b,a) will return 0 in here:

if((o1.score==o2.score)&&!((o1.seq1start<o2.seq1start)&&(o1.seq2start<o2.seq2start)))
    return 0;

And that is against the rule.

Upvotes: 0

Related Questions