Return to Answer

• 1

• 13.6k
• 1
• 35
• 74

For now, I comment on one part only, which is IMHO dangerous enough to deserve it:

##ScoreTools

public static <K, V extends Comparable<? super V>> SortedSet<Map.Entry<K, V>> entriesSortedByValues(Map<K, V> map, final boolean descending) {
 SortedSet<Map.Entry<K, V>> sortedEntries = new TreeSet<Map.Entry<K, V>>(
 new Comparator<Map.Entry<K, V>>() {
 @Override
 public int compare(Map.Entry<K, V> e1, Map.Entry<K, V> e2) {
 int res;
 if (descending) res = e1.getValue().compareTo(e2.getValue());
 else res = e2.getValue().compareTo(e1.getValue());
 return res != 0 ? -res : 1; // Special fix to preserve items with equal values
 }
 }
 );
 sortedEntries.addAll(map.entrySet());
 return sortedEntries;
}

Your special fix can easily lead to a map unable to find anything. As rolfl already noted, your Comparator is non-transitive. But it's not antisymmetric and it's not reflexive either. So you're violating every single point of the contract.

Assuming it works now, it can break anytime. Without e.compare(e) returning non zero, there's no way to find an entry, except by using ==, which is an optimization probably included in the current TreeMap version.

When you want such a preserving Comparator, you can do better:

int res;
if (descending) res = e1.getValue().compareTo(e2.getValue());
else res = e2.getValue().compareTo(e1.getValue());
if (res != 0 || e1.equals(e2)) {
 return res;
}

This ensures reflexivity. Now, we don't care about the result, but need something like transitivity and antisymmetry. We use what we have

res = Integer.compare(e1.getKey().hashCode(), e2.getKey().hashCode());
if (res != 0 || e1.equals(e2)) {
 return res;
}

The chances we come that far are low, but non-zero.

res = Integer.compare(e1.getValue().hashCode(), e2.getValue().hashCode());
if (res != 0 || e1.equals(e2)) {
 return res;
}

Now, we have nothing more to compare. Bad luck. You could decide that it's improbable enough and losing some entries is allowed. You could use your ugly hack now. You could also go the hard route like

if (!uniqueIdMap.contains(e1)) {
 uniqueIdMap.put(e1, uniqueIdMap.size());
}
if (!uniqueIdMap.contains(e2)) {
 uniqueIdMap.put(e2, uniqueIdMap.size());
}
return uniqueIdMap.get(e1) - uniqueIdMap.get(e2);

using a

private Map<Map.Entry<K, V>, Integer> uniqueIdMap;

You don't need to be concerned with performance here, as the chances of double hash collision are pretty low. You may want to use a WeakHashMap to avoid memory leaks or ConcurentHashMap with putIfAbsent. You may want to create it lazily as chances it gets needed are low.

In case your objects don't care about equals, you can use Guava Ordering#arbitrary which is such a tie-breaker (and replaces all my lengthy code above).