Sorting/Comparator Problem

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(
at java.util.ComparableTimSort.mergeAt(
at java.util.ComparableTimSort.mergeForceCollapse(
at java.util.ComparableTimSort.sort(
at java.util.Arrays.sort(
at java.util.Arrays.sort(
at java.util.ArrayList.sort(
at java.util.Collections.sort(

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());

    // This is where the crash occurs

    // 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())
	if (b && this.isRifledInfantry())
	// Same for repeating rifles.
	if (b && u.hasRepeatingRifles())
	if (b && this.hasRepeatingRifles())
	// Artillery.
	b = u.isArtillery();
	b &= this.isArtillery();
	if (b && u.isRifledArtillery())
	if (b && this.isRifledArtillery())
	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.

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:

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.

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.

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?

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:

[quote]Your “compareTo” method is just not an order relation.
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: