CODEWITHSUNDEEP
javacollectionsdictionaryguavaapache-commons
Rajat Gupta
Rajat Gupta

Reputation: 26597

Map that could be iterated in the order of values

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 ?

Upvotes: 16

Views: 10940

Answers (8)

ejain
ejain

Reputation: 3614

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

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

Upvotes: 2

matt burns
matt burns

Reputation: 25390

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

Upvotes: 1

Louis Wasserman
Louis Wasserman

Reputation: 198163

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

Upvotes: 13

Grzegorz Rożniecki
Grzegorz Rożniecki

Reputation: 28005

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}

Upvotes: 12

nd.
nd.

Reputation: 8932

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.

Upvotes: 0

Piotr Gwiazda
Piotr Gwiazda

Reputation: 12222

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

    }

Upvotes: 0

Rostislav Matl
Rostislav Matl

Reputation: 4543

What about putting the values also in TreeSet ?

for(;;) { yourMap.put(key,value); }
SortedSet sortedValues = new TreeSet(yourMap.values());

or

SortedSet sortedValues = new TreeSet();
for(;;) 
{
yourMap.put(key,value);
sortedValued.add(value);
}

Upvotes: 0

Michael Borgwardt
Michael Borgwardt

Reputation: 346327

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.

Upvotes: 0

Related Questions