Search code examples
javakey-valuecomparatortreeset

Java TreeSet<Pair<Integer, Integer>> sorted by the value of the Pair element, how to insert a new pair that has the same value as an existing pair?

I currently have a TreeSet that contains elements of type Pair, and I'm sorting them by their value in descending order.

Here is the link to the original Pair class documentation: https://docs.oracle.com/javase/9/docs/api/javafx/util/Pair.html

This is the declaration:

TreeSet<Pair<Integer, Integer>> sortedSet = new TreeSet<Pair<Integer, Integer>>((a,b) -> b.getValue() - a.getValue());

My issue is that if I try to insert a few pairs into the set, for example: Pair(4, 51), Pair(8, 85), Pair(1, 16), Pair(2,51), the Pair(2,51) doesn't get inserted.

Code for inserting the pairs:

sortedSet.add(new Pair<Integer, Integer>(4, 51));
sortedSet.add(new Pair<Integer, Integer>(8, 85));
sortedSet.add(new Pair<Integer, Integer>(1, 16));
sortedSet.add(new Pair<Integer, Integer>(2, 51));

I managed to figure out that the reason is because there already exists a pair element with the same value - P(4,51), however, they have different keys so they are different elements, and I expected the Pair(2,51) to be inserted before or after P(4,51).

Is there a way I can solve this issue?

Solution

  • The issue is caused by the definition of the Comparator:

    (a,b) -> b.getValue() - a.getValue()

    According to this Comparator, two Pairs with the same value are "equal". As to the contract of Set, this means that an add(...) adds an element to the Set if and only if no element that is "equal" (with respect to the Comparator) exists in the Set.

    If we want to store two Pairs with the same value, but different keys, we need to extend the Comparator, such that it returns a non-0 value for Pairs with equal value, but different keys.

    One possibility is to:

    • first sort by value (descending - as in the original code), and
    • then by key (either ascending or descending)

    The following code accomplishes exactly this. The .reversed() is for the descending sort order for value, and I chose an ascending sort order for key:

    final TreeSet<Pair<Integer, Integer>> sortedSet = new TreeSet<>(Comparator
    .comparingInt(Pair<Integer, Integer>::getValue).reversed()
    .thenComparing(Pair::getKey));

    Ideone demo