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 ?

Answer 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

Answer 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}