JAVA Comparator throws error (multithreaded execution)

Question

I've been trying to get my head around the problem, but haven't managed to do so.

In short, I have written a bee hive algorithm, where one of it's premutations is sorting block of points, by distance to a point preceding the block sorted.

This permutation uses a Comparator

public class PointDistanceComparator implements Comparator {

    @Override
    public int compare(Object arg0, Object arg1) {
        double resultDouble = ((Point) arg1).getSortUsageDistance()-((Point) arg0).getSortUsageDistance(); 
        if(resultDouble>0){
            return 1;
        }
        else if(resultDouble==0){
            return 0;
        }
        else{
            return -1;
        }
    }

}

I calculate distances to preceding point for every point in block:

List<Point> pointsVector = new ArrayList<Point>();
double distance = 0;
Point point2 = pointsToVisit.get(visitedPoints.get(visitedPointsPossibleInputStartingIndex));
for(int k = visitedPointsPossibleInputStartingIndex+1; k < visitedPointsPossibleInputEndingIndex; k++){
    Point point = pointsToVisit.get(visitedPoints.get(k));
    distance = Utils.getDistanceKm(point2, point);
    point.setSortUsageDistance(distance);
    pointsVector.add(point);
}

And I try to sort it:

try{
    PointDistanceComparator pdComparator = new PointDistanceComparator();
    pointsVector.sort(pdComparator);
    int pointsVectorIndex = 0;
    for(int k = visitedPointsPossibleInputStartingIndex+1; k < visitedPointsPossibleInputEndingIndex; k++){
        visitedPoints.set(k, pointsVector.get(pointsVectorIndex).getIndex());
        pointsVectorIndex++;
    }
}
catch(Exception e){
    System.out.println("Unsortable route: ");
    for(Point point : pointsVector){
        System.out.println(point.getSortUsageDistance());
    }
    e.printStackTrace();
}

And the result I get (for high amount of points) is:

Unsortable route: 
2.409437209114269
4.195074884990501
0.9691536825922977
1.1818593906071124
3.7959341231055044
1.344833460712328
2.7808472396551256
2.3341362332820377
3.0826195327369685
5.981871507031457
4.096491609253349
2.6730445628945447
3.6026805136626736
5.070192970603796
6.525798962460061
2.437658869598336
2.3249264696009666
2.22717482314044
1.3205919751367337
1.4326093612218957
5.032187900596256
2.6186056819000028
3.715867402052429
2.905908208286016
1.25868451375791
1.5362377319604628
3.4961506217046376
2.961495413336175
1.9345437912998407
4.49333274460376
3.2997943500252442
4.5252963191878175
5.336224710120464

Which even excel can sort just fine (needs swapping . for ,).

Stack trace:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
    at java.util.TimSort.mergeHi(Unknown Source)
    at java.util.TimSort.mergeAt(Unknown Source)
    at java.util.TimSort.mergeCollapse(Unknown Source)
    at java.util.TimSort.sort(Unknown Source)
    at java.util.Arrays.sort(Unknown Source)
    at java.util.ArrayList.sort(Unknown Source)
    at beeAlgorithm.BeeHive.sortBlockByDistanceToPrecedingPoint(BeeHive.java:334)
    at beeAlgorithm.BeeHive.permuteRoute(BeeHive.java:172)
    at beeAlgorithm.BeeHive.searchRouteNeighbourhood(BeeHive.java:144)
    at beeAlgorithm.BeeHive.iterateOverRoute(BeeHive.java:130)
    at beeAlgorithm.BeeHive.iterateOverAllRoutes(BeeHive.java:123)
    at beeAlgorithmAgents.BeeHiveAgent$1.action(BeeHiveAgent.java:114)
    at jade.core.behaviours.Behaviour.actionWrapper(Behaviour.java:344)
    at jade.core.Agent$ActiveLifeCycle.execute(Agent.java:1552)
    at jade.core.Agent.run(Agent.java:1491)
    at java.lang.Thread.run(Unknown Source)

This is run on a multithreaded environment (JADE agents).

Seems like my compare method has a hole, but I just can't find it. Any clues?

Edit (fixed):

Seems like generating my points list was the issue. I don't have a single clue as to why it didn't work with:

    List<Point> points = new ArrayList<Point>();
    for(int l = 0; l < algInputParameters.getPointsAmount(); l++){
        Point point = null;
        if(l == 0){
            point = new Point(0, 24*1024, 0, 0, 0, 0, 0);
            if(algInputParameters.isCityCiechanow()){
                point.generatePositionForCiechanow(random);
            }
            else if(algInputParameters.isCityTorun()){
                point.generatePositionForTorun(random);
            }
            else{
                point.generatePositionForWarsaw(random);
            }
        }
        else{
            point = new Point(0, 0, l, visitTime, 0, 0, 0);
            point.generateHours(random, startHour, endHour, duration);
            if(algInputParameters.isCityCiechanow()){
                point.generatePositionForCiechanow(random);
            }
            else if(algInputParameters.isCityTorun()){
                point.generatePositionForTorun(random);
            }
            else{
                point.generatePositionForWarsaw(random);
            }
        }
        points.add(point);
    }

But worked with:

    List<Point> points = new ArrayList<Point>();
    for(int l = 0; l <algInputParameters.getBeeAmount(); l++){
        if(l == 0){
            Point point = new Point(0, 24*1024, 0, 0, 0, 0, 0);
            if(algInputParameters.isCityCiechanow()){
                point.generatePositionForCiechanow(random);
            }
            else if(algInputParameters.isCityTorun()){
                point.generatePositionForTorun(random);
            }
            else if(algInputParameters.isCityWarszawa()){
                point.generatePositionForWarsaw(random);
            }
            points.add(point);
        }
        else{
            Point point = new Point(0, 0, l, visitTime, 0, 0, 0);
            point.generateHours(random, startHour, endHour, duration);
            if(algInputParameters.isCityCiechanow()){
                point.generatePositionForCiechanow(random);
            }
            else if(algInputParameters.isCityTorun()){
                point.generatePositionForTorun(random);
            }
            else if(algInputParameters.isCityWarszawa()){
                point.generatePositionForWarsaw(random);
            }
            points.add(point);
        }
    }

Honestly, no single idea . There is no concurrency when creating the pool of Points, though even if a Point stayed as "null", I'd get a null pointer exception sooner. Perhaps some people will encounter the same problem, just leaving it here.

Accepted the answer with BigDecimal usage, as it is most likely to answer any of the possible future searches

http://stackoverflow.com/questions/8327514/comparison-method-violates-its-general-contract — nano_nano, Aug 28 '15 at 12:41
I didn't runt your code but I suspect floating point arithmetic problem caused by subtraction. This may cause problems when you are comparing with `0`. Try to `return Double.compare(p2.getSortUsageDistance, p1.getSortUsageDistance());` in your `Comparator`. Since Java 8 you can also use it like `list.sort(Comparator.comparingDouble(Person::getSortUsageDistance));` or `list.sort(Comparator.comparingDouble(Person::getSortUsageDistance).reversed());` depending on order you want to achieve. — Pshemo, Aug 28 '15 at 12:43
What values can `getSortUsageDistance()` return? Based on that there could be **overflows**, **precision losses** or something else which causes this exception. — Codebender, Aug 28 '15 at 12:51
StefanBeike, I wouldn't have asked a question if I didn't read that first, my issue is that all those values that are put out show no tendency to be like that. Even when it comes to precision, there are too big differences (like 0.01 minimum) between the numbers. Pshemo, I didn't know about these methods, (sadly) they don't help my predicament, but it's good to know they exist, thanks. Codebender, it's a double similar to those shown in the question. The fact that even after using Double.compare as Pshemo advised I still get this error leads me to think that problem might be hidden elsewhere. — Stranko, Aug 28 '15 at 13:44
You have "multithreaded execution" in the title. Could you be changing the "sortUsageDistance" from another thread while the sorting is going on? — fishinear, Aug 28 '15 at 14:07
Could some of the "sortUsageDistance" values be NaN? That would also invalidate the comparator. — fishinear, Aug 28 '15 at 14:09

score 1 · Accepted Answer · edited May 23 '17 at 12:22

From the Javadoc of java.util.Comparator, The general contract of a comparator is as follow :

It follows immediately from the contract for compare that the quotient is an equivalence relation on S, and that the imposed ordering is a total order on S. When we say that the ordering imposed by c on S is consistent with equals, we mean that the quotient for the ordering is the equivalence relation defined by the objects' equals(Object) method(s)

Means that if x.compare(y) == 0 then it must be x.equals(y) == true

It seems from your comparator, you do a double datatype substraction and compare the value with 0, while it is known weakness of double with its limited precision. Math operation on double can cause loss of precision, makes two double that seems equals is actually not. This link shows exactly what I mean.

Another good excerpt is as follow,

System.out.println( 0.1f + 0.1f + 0.1f + 0.1f + 0.1f + 0.1f + 0.1f + 0.1f + 0.1f + 0.1f );
System.out.println( 0.1d + 0.1d + 0.1d + 0.1d + 0.1d + 0.1d + 0.1d + 0.1d + 0.1d + 0.1d );

1.0000001
0.9999999999999999

Adding 0.1 ten times, you expect an exact 1 (one). But you are not.

I suggest you to use BigDecimal when you want proper comparison.

Well, my problem lied in generating points (no idea why, seriously, if I manage to figure it out, I'll update the question with explanation) :/. Will accept your answer as one, since it does have information for others interested in this topic, or for those who will find it in the future. — Stranko, Aug 28 '15 at 14:22

JAVA Comparator throws error (multithreaded execution)

Edit (fixed):

1 Answers1