# "Compress" the entry set of Integers in a Map<String, Integer> to values incrementing by 1

What I'm trying to achieve is the following:

Given a Map, where the values may contain duplicates, I want to change the values so that they are incrementing by 1, starting from 1.

Example:

{"One"=1, "Three"=3, "Another three"=3, "Seven"=7} should result in:
{"One"=1, "Three"=2, "Another three"=2, "Seven"=3}

I do this now by:

1. "Inverting" the map into a com.google.common.collect.Multimap
2. Build a sorted list of unique values from the original map values (via Java 8 Stream API)
3. Iterate with ++-increments from 0 until size of unique values, and in the process get(i) the unique value from the sorted list, then map the original string to the value of the incrementing integer into a new map.

I'd be happy to learn if there is a better a.k.a. more elegant or more performant way of doing this!

The relevant JUnit test looks as follows, and passes.

import com.google.common.collect.HashMultimap;
import com.google.common.collect.Multimap;

...

@Test
public void mappingTest() {
Map<String, Integer> map = new HashMap<>();
map.put("One", 1);
map.put("Two", 2);
map.put("AnotherTwo", 2);
map.put("Three", 3);
map.put("Seven", 7);
map.put("AnotherSeven", 7);
map.put("Ten", 10);

// Build the "inverted" Multimap
Multimap<Integer, String> mMap = HashMultimap.create();
for (Entry<String, Integer> entry : map.entrySet()) {
mMap.put(entry.getValue(), entry.getKey());
}

// Get a list of unique integers compiled from the original map's values
List<Integer> uniques = map.values().stream().distinct().sorted().collect(Collectors.toList());

// Map the original keys to the new incrementing values
Map<String, Integer> fMap = new HashMap<>();
for (int i = 0; i < uniques.size(); i++) {
for (String string : mMap.get(uniques.get(i))) {
fMap.put(string, i+1);
}
}

// Asserts
assertEquals(fMap.get("One"), Integer.valueOf(1));
assertEquals(fMap.get("Two"), Integer.valueOf(2));
assertEquals(fMap.get("AnotherTwo"), Integer.valueOf(2));
assertEquals(fMap.get("Three"), Integer.valueOf(3));
assertEquals(fMap.get("Seven"), Integer.valueOf(4));
assertEquals(fMap.get("AnotherSeven"), Integer.valueOf(4));
assertEquals(fMap.get("Ten"), Integer.valueOf(5));
}


## 2 Answers

When you are collecting the unique integer values to a sorted list from the values of the original Map<String, Integer>, you are doing work that has already been done, namely the elimination of duplicates by calling distinct() on the stream. You have already filtered out the duplicates when you populated the Multimap<Integer, String>, so instead of collecting the values of the Map<String, Integer>, you could instead collect the keys of the Multimap<Integer, String>.

Also, you are creating a HashMultimap, which stores its values in HashSets (so it's like a HashMap<Integer, HashSet<String>>). This creates unneeded overhead, because the HashSet<String>s containing the values of the multimap eliminate duplicates. But in this case, the multimap can never contain duplicate values in the first place, since its values are obtained from the key set of the original Map<String, Integer>. It would therefore suffice to configure the multimap to store its values in ArrayLists instead of HashSets. By the way, the documentation says that the create methods of the individual Multimap implementations will be deprecated in the future, and that MultimapBuilder should be used instead.

Apart from that, you can omit the List<Integer> entirely by configuring the multimap to behave like a TreeMap instead of a HashMap. This might also save a bit of performance, because you have two functionalities implemented in one data structure, as opposed to using a Multimap for associating each integer with one or more Strings, and an additional List for sorting the integers. Of course, a TreeMap does not index its keys, so you would have to maintain a counter yourself when you iterate over the keys of the multimap.

Finally, the overall structure of your code sample is strange. Unit tests are meant to test whether some code works correctly. But your method mappingTest() not only performs the tests, it also contains the code to be tested. Of course, there's nothing wrong with placing assertions in code to test it. But what you wrote is not a unit test, because it doesn't test any defined unit (for example a method). It just executes some code and then uses assertions to check whether the code did what you thought it would do.

Instead, I suggest that you first write a method that accepts a Map<K, Integer> (or any Map<K, V> where <V extends Comparable<? super V>>) as a parameter and returns a "compressed" version of this map:

public static <K, V extends Comparable<? super V>> Map<K, Integer> compress(Map<K, V> map) {
//...
}


Then, you write a separate method that tests that method by constructing a map like you did in mappingTest(), passing this map to compress(Map) and then inspecting the returned Map. This would be a unit test, because you are testing the functionality of a unit, i.e. the method compress(Map).

"I'd be happy to learn if there is a better a.k.a. more elegant or more performant way of doing this!"

The following is at least a more performant way.

Keeping procedural-style state variables on the entries sorted by value seems the most natural, as most direct.

    final AtomicInteger oldValue = new AtomicInteger();
final AtomicInteger distinctCount = new AtomicInteger();
map.entrySet().stream()
.sorted(Comparator.comparing(Map.Entry<String, Integer>::getValue))
.forEachOrdered(e -> {
int newValue = e.getValue().intValue() == oldValue.intValue()
? distinctCount.get()
: distinctCount.incrementAndGet();
oldValue.set(e.getValue().intValue());
e.setValue(newValue);
});


Admittedly AtomicInteger is abused just to have a final reference.

Though in real functional languages the two state variables would become as collectors of the stream, it seems in java the API is still too cumbersome to create just for that an accumulator (like summing).

Also one can immediately "correct" the map in-situ, not needing to create a new collection. As the entries are backed by the original map.

In short this seems the most sensible solution, though somehow not very elegant.

One could make a class DistinctCounter<T> with two fields (T/Integer and int), if this would be a reusable piece of code: numbering distinct fields.