30 Sep 2016

Map Inversion

Recently, I had occasion to invert a map, i. e. exchange its keys and values. Having read several discussions on Stackoverflow (see here, here, and here), I decided to create my own utility, internally using Java streams. Besides simple maps, I wanted to be able to convert multimaps, both of the Google Guava and "standard Java" kind, the difference being that the entry set of a Guava multimap contains only elements with single values, whereas the entry set of a standard multimap contains an element with a Collection value.

As an example, here's the code for the latter (and most complicated) case:

 * Inverts a map. The map may also be a non-Guava multimap (i. e. the entrySet elements may have collections as values).
 * @param map the map to inverted
 * @param valueStreamer a function that converts an original map value to a stream. (In case of a multimap, may stream the original
 *            value collection.) Can also perform any other transformation on the original values to make them suitable as keys.
 * @param mapFactory a factory which returns a new empty Map into which the results will be inserted
 * @param collectionFactory a factory for the value type of the inverted map
 * @return the inverted map, where all keys that map to the same value are now mapped from that value
public static <K, V, V1, C extends Collection<K>> Map<V, C> invertMultiMap(Map<K, V1> map, Function<V1, Stream<V>> valueStreamer,
  Supplier<Map<V, C>> mapFactory, Supplier<C> collectionFactory) {
    Map<V, C> inverted = map.entrySet().stream().flatMap(e ->
       valueStreamer.apply(e.getValue()).map(v -> new SimpleEntry<>(v, newCollection(e.getKey(), collectionFactory))))
      .collect(toMap(Entry::getKey, Entry::getValue, (a, b) -> {a.addAll(b);  return a;}, mapFactory));
    return inverted;

private static <T, E extends T, C extends Collection<T>> C newCollection(E elem, Supplier<C> s) {
    C collection = s.get();
    return collection;

You can find the complete code, covering some more cases and with some tests, in this Gist. The tests depend on Guava.

No comments:

Post a Comment