0

I have this generic method to sort a Map by value:

public static <K, V extends Comparable<? super V>> Map<K, V>
        sortByValue(Map<K, V> map) {
    Map<K, V> result = new LinkedHashMap<>();
    Stream<Map.Entry<K, V>> st = map.entrySet().stream();

    st.sorted(Map.Entry.comparingByValue())
            .forEachOrdered(e -> result.put(e.getKey(), e.getValue()));

    return result;
}

And sometimes I'm getting java.lang.IllegalArgumentException: Comparison method violates its general contract!. Is there any particular reason this code might behave like this?

I am aware of the duplicate question, but this example involves generics, lambdas and built-in methods, which makes it more complex and I would appreciate some explanation.

Community
  • 1
  • 1
alex
  • 10,900
  • 15
  • 70
  • 100
  • This strongly depends on the comparator for `V`. Basically, your code should be good as long as the `Comparable` contract is held. Meaning, there is probably a Comparable instance out there that has an incorrect comparator. Try catching the IllegalArgumentException for debug purposes and printing out the suspect class. – Piotr Wilkin Jul 29 '16 at 15:18
  • So what if the duplicate question is simpler than yours, the cause of your error is still the same: **Your comparator is not transitive.** Read the [accepted answer](http://stackoverflow.com/a/8327575/5221149) if you don't know what that means. – Andreas Jul 29 '16 at 15:18
  • 1
    He probably knows what it means, he was asking why it happens here. It's like saying an explanation of what is a `NullPointerException` is akin to explaning why a particular piece of code throws one. – Piotr Wilkin Jul 29 '16 at 15:19
  • Also, intransitivity is not the only potential cause of this problem. Another reason might be irreflexivity - the comparator returning something other than 0 when x.equals(y). – Piotr Wilkin Jul 29 '16 at 15:21
  • Ok, the problem is that the `compareTo()` method of `V` is not transitive, i.e. the ordering is not *consistent*. Without knowing what `V` is, or how it's `compareTo()` method is implemented, we can't help identify the error. – Andreas Jul 29 '16 at 15:22
  • @PiotrWilkin When sorting, the `equals()` method is not called, so that can't be the cause of it. Besides, there is no requirement that a `Comparator` be consistent with `equals()` of the object it is comparing. – Andreas Jul 29 '16 at 15:25
  • @Andreas, please show some understanding. Also, thanks for clarification Piotr. – alex Jul 29 '16 at 15:53
  • @alex I'm understanding. Are you? I mean, do you understand that your problem is a "transitive" issue with the `compareTo()` method of `V`? A method you haven't shown, so we can't help you identify why it is not transitive. You do understand why the issue is there, right? It's because you use `comparingByValue()`, which means that it will sort values by their *natural ordering*, i.e. using the `compareTo()` method of the value class (`V`). Whether that method "involves generics, lambdas and built-in methods" is unclear, but duplicate question is right on point. – Andreas Jul 29 '16 at 15:57
  • @Andreas I did understand the transitivity issue. I didn't know how to apply it to my code. – alex Jul 29 '16 at 16:02
  • @Andreas what I mean is not that equals() is called within the sorting code (are you sure, btw? there are two implementations of the sort in the standard library, I haven't looked through them), but that this is the _semantics_ of what the contract is about. A total ordering function is one that is reflexive, antisymmetric, transitive and total. – Piotr Wilkin Jul 29 '16 at 17:40
  • 1
    @PiotrWilkin Why bring up *total* ordering? There is no requirement for *total* ordering when sorting. Values that are equal according to the `Comparator` will retain their original ordering, as the [javadoc](https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html#sorted-java.util.Comparator-) says: *For ordered streams, the sort is stable.* --- I did search the `TimSort` implementation, and it doesn't call `equals()`. Why would it, since object equality is *not* part of the sort contract (or semantics as you call it)? – Andreas Jul 29 '16 at 17:47
  • You're right, it doesn't have to be total. I have a hard time believing it can be irreflexive, though - can you really have a comparator on integers that can for example have (5, 5) -> 1 and not 0? I believe that might break the contract after all (haven't tried). – Piotr Wilkin Jul 29 '16 at 17:51

0 Answers0