Sorting/Comparator Problem

Newbie & Debugging Questions
#1

I have now gotten two crash reports from players that have me puzzled:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.ComparableTimSort.mergeLo(ComparableTimSort.java:744)
at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:481)
at java.util.ComparableTimSort.mergeForceCollapse(ComparableTimSort.java:422)
at java.util.ComparableTimSort.sort(ComparableTimSort.java:222)
at java.util.Arrays.sort(Arrays.java:1312)
at java.util.Arrays.sort(Arrays.java:1506)
at java.util.ArrayList.sort(ArrayList.java:1462)
at java.util.Collections.sort(Collections.java:143)

This is the place in my code that the crash has occurred:

public Unit chooseDropUnit(ArrayList<Unit> units) {
    ArrayList<Unit> temp = new ArrayList<Unit>(units.size());
    temp.addAll(units);

    // This is where the crash occurs
    Collections.sort(temp);

    // The rest of the code takes the lowest ranking unit that
    // isn't artillery. If none, it takes the lowest ranking unit.
}

The CompareTo method of my class Unit is involved here:

public int compareTo(Unit u) {
	int cr_one = u.getCombatRating();
	int cr_two = this.getCombatRating();
	
	// Make allowance for rifled musket or artillery.
	boolean b = u.isInfantry();
	b &= this.isInfantry();
	if (b && u.isRifledInfantry())
		cr_one++;
	if (b && this.isRifledInfantry())
		cr_two++;
	
	// Same for repeating rifles.
	if (b && u.hasRepeatingRifles())
		cr_one++;
	if (b && this.hasRepeatingRifles())
		cr_two++;
	
	// Artillery.
	b = u.isArtillery();
	b &= this.isArtillery();
	if (b && u.isRifledArtillery())
		cr_one++;
	if (b && this.isRifledArtillery())
		cr_two++;
	
	return (cr_one - cr_two);
}

I don’t see any possible violation of transitivity. Could I be getting this error because one of the elements in the ArrayList is null? I assume NO, and it must be an error in the CompareTo method. But I am suspicious because both crashes occurred in “chooseDropUnit” and that is NOT the only place that sorts objects of the Unit class.

I tested this empirically by sorting every army in the game 100,000 times, and I could not duplicate this error. Of course the game state when I happened to chose to do this is not exactly the same as the player’s when this crash occurred. I shuffled the units before each sort, of course. But this error never came up.

I just don’t see what could be wrong.

#2

Because you can have a situation where if you have three units, A, B, and C, such that A > B and B > C but in your logic it is possible A == C.

Cas :slight_smile:

#3

Thanks for the quick reply, Cas. I looked for exactly that, but I didn’t see at first how it was possible. Now I understand what the problem is. Pretty obvious, really.

As usual, when I post something on the forum, I am wrong. >:(

I don’t know if it is better to amend my code, or to be a little cheesy and use this

System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

Which tells the JVM to ignore this kind of error, of course.

#4

Using “java.util.Arrays.useLegacyMergeSort” maybe wont fix the problem :

Your “compareTo” method is just not an order relation. You must think of an algorithm that does not use a sort.

#5

Well, it seems at first glance that the post you cited is referring to a different problem.

I need to sort because the logic in question is sorting an array of objects in order to choose one or more of them.

Thinking about it, I just decided to change my compareTo method in my class Unit. Just choosing to ignore the problem when sorting does seem a little silly.

Also - isn’t using sorting a basic part of algorithms?

#6

OK, if you really want to make a sorting, your “Unit” class should have a method:

“float getProbabilityToWin()” returning a function of:

  • getCombatRating()
  • isInfantry()
  • isRifledInfantry()
  • hasRepeatingRifles()
  • isArtillery()
  • isRifledArtillery()

And then the compareTo compares only the two results of this method
This way, your sort() will always succeed :slight_smile:

#7

[quote]Your “compareTo” method is just not an order relation.
[/quote]
You are right of course.

I have effectively done that by amending my compareTo method. Truthfully, now that I have my head on straight about this particular sorting problem, I am not 100% what results I want anyway. That has to do with the game’s subject matter, and it won’t interest anyone here.

Thanks for the help! :slight_smile: