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'd put entries on the list and sort it. I don't recall any map that can be ordered by values, only by keys. You could use BiMap from Guava, but it requires values uniqueness.

Example:

    public static void main(String[] args) {
        Map<String, String> map = new HashMap<String, String>() {{
            put("key1", "value1");
            put("key2", "value3");
            put("key3", "value4");
            put("key4", "value2");
        }};

        List<Map.Entry<String, String>> entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries, new Comparator<Map.Entry<String, String>>() {

            @Override
            public int compare(Entry<String, String> o1,
                    Entry<String, String> o2) {
                if (o1.getValue() == null && o2.getValue() == null) return 0;
                if (o1.getValue() == null) return -1; //Nulls last
                return - o1.getValue().compareTo(o2.getValue());
            }
        });

    }

Answer 2

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);
}

Answer 3

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 4

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}

Answer 5

I think the DualTreeBidiMap of Apache Commons Collections should make this possible, probably by iterating over the return from inverseBidiMap().

But I don't think this allows for duplicate values - as the name says, the structure is simply based on keeping two trees, which is really the only thing that makes sense, since values in a map have no meaning to the map structure.

Answer 6

I think you have to roll your own implementation of such a map. Fortunately, it shouldn't be much of an issue with Guava:

public class SortedValueMap<K, V> extends ForwardingMap<K, V> {

  private Map<K, V> delegate = newHashMap();
  private Comparator<V> valueComparator;

  public static <K, V extends Comparable<V>> SortedValueMap<K, V> reverse() {
    return new SortedValueMap<K, V>(Ordering.<V> natural().reverse());
  }

  public static <K, V> SortedValueMap<K, V> create(Comparator<V> valueComparator) {
    return new SortedValueMap<K, V>(valueComparator);
  }

  protected SortedValueMap(Comparator<V> valueComparator) {
    this.valueComparator = checkNotNull(valueComparator);

  }

  @Override
  protected Map<K, V> delegate() {
    return delegate;
  }

  @Override
  public Set<K> keySet() {
    return new StandardKeySet();
  }

  @Override
  public Set<Map.Entry<K, V>> entrySet() {
    TreeSet<Map.Entry<K, V>> result = newTreeSet(new Comparator<Map.Entry<K, V>>() {
      @Override
      public int compare(Map.Entry<K, V> o1, Map.Entry<K, V> o2) {
        return ComparisonChain.start()
            .compare(o1.getValue(), o2.getValue(), valueComparator)
            .compare(o1.getKey(), o2.getKey(), Ordering.arbitrary())
            .result();
      }

    });
    result.addAll(Collections.unmodifiableMap(delegate).entrySet());
    return result;
  }

  @Override
  public Collection<V> values() {
    return new StandardValues();
  }

  public static void main(String[] args) {
    SortedValueMap<String, String> svm = SortedValueMap.reverse();
    svm.put("foo", "1");
    svm.put("bar", "3");
    svm.put("baz", "2");

    System.out.println(Joiner.on(", ").withKeyValueSeparator("=").join(svm));
    System.out.println(Joiner.on(", ").join(svm.values()));
    System.out.println(Joiner.on(", ").join(svm.keySet()));
  }
}

Fail-fast iterators are not present in this implementation; please add them for yourself if required. Please also note that setting a value via Map.Entry.setValue would cause havoc with the sort order, which is why I used unmodifyableMap in entry set.