Map that could be iterated in the order of values

Question

I need a Map that could be iterated in the decreasing order of its values. Does any of the standard libraries like Apache Commons or Guava provide this kind of map ?

Solution 1

I would do this with Guava as follows:

Ordering<Map.Entry<Key, Value>> entryOrdering = Ordering.from(valueComparator)
  .onResultOf(new Function<Entry<Key, Value>, Value>() {
    public Value apply(Entry<Key, Value> entry) {
      return entry.getValue();
    }
  }).reverse();
// Desired entries in desired order.  Put them in an ImmutableMap in this order.
ImmutableMap.Builder<Key, Value> builder = ImmutableMap.builder();
for (Entry<Key, Value> entry : 
    entryOrdering.sortedCopy(map.entrySet())) {
  builder.put(entry.getKey(), entry.getValue());
}
return builder.build();
// ImmutableMap iterates over the entries in the desired order

Solution 2

With guava, there is even cleaner way than @LoisWasserman's anwer - using Ordering combined with Functions.forMap:

Ordering.natural().reverse().nullsLast().onResultOf(Functions.forMap(map, null))

or if values aren't Comparable:

Ordering.fromComparator(yourComparator).reverse().nullsLast().onResultOf(Functions.forMap(map, null))

An example (with first option - natural ordering):

final Map<String, String> map = ImmutableMap.of(
    "key 1", "value 1",
    "key 2", "value 2",
    "key 3", "another value",
    "key 4", "zero value");

final Ordering<String> naturalReverseValueOrdering =
    Ordering.natural().reverse().nullsLast().onResultOf(Functions.forMap(map, null));

System.out.println(ImmutableSortedMap.copyOf(map, naturalReverseValueOrdering));

outputs:

{key 4=zero value, key 2=value 2, key 1=value 1, key 3=another value}

(I use ImmutableSortedMap here, but TreeMap can also be used if mutability is required.)

EDIT:

If there are identical values (more exactly if there are two values for which Comparator.compare(String v1, String v2) returns 0) ImmutableSortedMap throws an exception. Ordering must not return, so i.e. you should order map by values first and keys next if both values are equal (keys aren't supposed to be equal) by using Ordering.compound:

final Map<String, String> map = ImmutableMap.of(
    "key 1", "value 1",
    "key 2", "value 2",
    "key 3", "zero value",
    "key 4", "zero value");

final Ordering<String> reverseValuesAndNaturalKeysOrdering =
    Ordering.natural().reverse().nullsLast().onResultOf(Functions.forMap(map, null)) // natural for values
        .compound(Ordering.natural()); // secondary - natural ordering of keys

System.out.println(ImmutableSortedMap.copyOf(map, reverseValuesAndNaturalKeysOrdering));

prints:

{key 3=zero value, key 4=zero value, key 2=value 2, key 1=value 1}

Solution 3

This can now be done in a single line using Java 8 Streams:

map.entrySet().stream()
    .sorted(Comparator.comparing(Map.Entry::getValue))
    .forEach(...);

Solution 4

Simple method to get an immutable copy of your map sorted by descending value. Remove the call to reverse() if you want ascending order. Requires Google Guava.

private Map<String, String> mapSortedByValues(Map<String, String> theMap) {
    final Ordering<String> ordering =
            Ordering.natural().reverse().nullsLast().onResultOf(Functions.forMap(theMap, null));

    return ImmutableSortedMap.copyOf(theMap, ordering);
}

View more solutions

Comments

[yshavit]

You don't need two trees. You could have one Map for the key-values, and an ordered List of values (or of Map.Entrys if you need that).

[Michael Borgwardt]

@yshavit: you could, if you have a list structure that is both auto-ordered and allows efficient insertion and deletion, which is not simple (I think it can be done with a skip list). Why the extra complexity if you already have one tree?

[Piotr Gwiazda]

What to do with duplicated values?

[yshavit]

because, as you point out, it doesn't allow for duplicate values. If that's a requirement, the two-Map approach is disqualified. And you don't need a List that manages the order for you, you can just manually ensure the ordering on inserts as an invariant. But anyway, I agree it's more complexity, and should only be done if you need those duplicate values.

[Rajat Gupta]

could you clarify how do I define this valueComparator ?

[Xaerxess]

@user it's Comparator<V> you want to use in first place. If values implement Comparable, then you can use Ordering.natural() instead of custom valueComparator.

[Rajat Gupta]

this leads to illegal argument exception incase two keys are set with same value...

[Xaerxess]

@user that's because comparing them returns 0 (suggesting equality, what's correct) and ImmutableSortedMap treats that as exceptional case (what should it do? entry: key1=same_value first or rather key2=same_value first?). Comparator must not return 0 in this case, edited my answer and example (but remember - it's for Strings!).

[Louis Wasserman]

I'm really fundamentally uncomfortable with this solution, specifically because your ImmutableSortedMap won't just return null on keys that aren't in the map: it'll fail completely, because the comparator doesn't apply.

[Rajat Gupta]

Ordering.from(Ordering.natural())... leads to a deprecated function call, there is a alternative method which asks for a comparator type argument instead. My values are actually of type Integer. Could you suggest what comparator should I pass for integer values sorting? Thanks a lot

[Louis Wasserman]

Don't use Ordering.from(Ordering.natural()), just use Ordering.natural() directly.

[Xaerxess]

@LouisWasserman isn't this enough when same map is used in Functions.forMap and ImmutableSortedMap.copyOf constructor?

[Louis Wasserman]

It's enough to make the ImmutableSortedMap creation work fine, yes. And then it'll explode in your face when you try to query the ImmutableSortedMap later on and have no idea why it's throwing weird exceptions. That is, map.get(keyNotInTheMap) will throw an exception. Ew.

[Xaerxess]

@LouisWasserman ah, that's your point! Functions.forMap(map, null) should be used then.

[Louis Wasserman]

That's still iffy and bug-prone, since then you need your comparator to be able to deal with nulls. And that's all setting aside the potential cost of calling map.get every time you do a comparison. This approach as a whole is just much more prone to things going wrong in subtle and unexpected ways. =/

[Xaerxess]

@LouisWasserman I added .nullsLast() to comparator and now I surrender :) Treat this answer as narrow (works quite fine in ImmutableSortedMap) unconventional use of Functions.forMap (it must have some purpose in library) for getting values of map for keys while using comparator.

[Louis Wasserman]

I think the modified answer is correct, but as a general rule, if you can avoid writing code that can go wrong in many subtle ways, you should always do so.