Monday, October 24, 2011

Guava's Bidirectional Maps

Google Guava has much to offer the Java developer working with J2SE 5, Java SE 6, or Java SE 7. The older the version of these being used, the more useful Guava can be. Although Java SE 7 brings select Guava-provided functionality to the Java programming language as a standard part of the language (such as the new Objects class), there are still numerous features of Guava that are not available even in JDK 7. In this post, I focus on Guava's support of bidirectional maps.

Guava's heritage is in the "ancient and unmaintained" Google Collections project and Guava's bidirectional map support comes from that Google Collections heritage. The API documentation for Guava's com.google.common.collect.BiMap interface provides a nice concise definition of a bidirectional map:

A bimap (or "bidirectional map") is a map that preserves the uniqueness of its values as well as that of its keys. This constraint enables bimaps to support an "inverse view", which is another bimap containing the same entries as this bimap but with reversed keys and values.

I have run into several situations during my career where bidirectional map support is helpful in making clearer and more readable code. I have even built custom implementations of bidirectional maps, but no longer do that thanks to the availability of Guava (and previously of Google Collections and Apache Commons's BidiMap). The next code listing shows a simple situation where a bidirectional map is useful. This example maps nations to their capital cities. The beauty of the bidirectional map is that I can look up a capital city by its nation's name or I can look up a nation's name by the name of the capital city. An important characteristic of the bidirectional map is that the "value" side of the bidirectional map requires unique values in addition to the more typical "key" side of the bidirectional map requiring unique values.

TwoMonoDirectionalMaps
package dustin.examples;

import static java.lang.System.out;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 * Demonstrate simplistic implementation of functionality equivalent to that
 * provided by bidirectional map via two monodirectional maps. This class has
 * some intentional problems to illustrate the maintenance disadvantages of this
 * approach. For example, there is a mismatch between the two single-direction
 * maps for "London" (UK in one case and England in the other case) and the
 * mapping for France/Paris was left off one of the single-direction maps.
 * 
 * @author Dustin
 */
public class TwoMonoDirectionalMaps
{
   private final static Map<String, String> nationsToCapitals;
   private final static Map<String, String> capitalsToNations;

   static
   {
      final Map<String, String> tempNationsToCapitals = new HashMap<String, String>();
      tempNationsToCapitals.put("Canada", "Ottawa");
      tempNationsToCapitals.put("England", "London");
      tempNationsToCapitals.put("France", "Paris");
      tempNationsToCapitals.put("Mexico", "Mexico City");
      tempNationsToCapitals.put("Portugal", "Lisbon");
      tempNationsToCapitals.put("Spain", "Madrid");
      tempNationsToCapitals.put("United States", "Washington");
      nationsToCapitals = Collections.unmodifiableMap(tempNationsToCapitals);

      final Map<String, String> tempCapitalsToNations = new HashMap<String, String>();
      tempCapitalsToNations.put("Lisbon", "Portugal");
      tempCapitalsToNations.put("London", "United Kingdom");
      tempCapitalsToNations.put("Madrid", "Spain");
      tempCapitalsToNations.put("Mexico City", "Mexico");
      tempCapitalsToNations.put("Ottawa", "Canada");
      tempCapitalsToNations.put("Washington", "United States");
      capitalsToNations = Collections.unmodifiableMap(tempCapitalsToNations);
   }

   /**
    * Print the capital city of the nation whose name is provided.
    * 
    * @param nationName Name of nation for which capital is decided.
    */
   public void printCapitalOfNation(final String nationName)
   {
      out.println(
           "The capital of " + nationName + " is "
         + (nationsToCapitals.containsKey(nationName) ? nationsToCapitals.get(nationName) : "unknown" )
         + ".");
   }

   /**
    * Print the name of the nation whose capital name is provided.
    * 
    * @param capitalName Name of capital city for which nation is desired.
    */
   public void printNationOfCapital(final String capitalName)
   {
      out.println(
           capitalName + " is the the capital of "
         + (capitalsToNations.containsKey(capitalName) ? capitalsToNations.get(capitalName) : "unknown" )
         + ".");
   }

   /**
    * Main function demonstrating this use of two mono-directional maps.
    * 
    * @param arguments Command-line arguments; none expected.
    */
   public static void main(final String[] arguments)
   {
      final TwoMonoDirectionalMaps me = new TwoMonoDirectionalMaps();
      me.printCapitalOfNation("United States");
      me.printCapitalOfNation("England");
      me.printCapitalOfNation("France");
      me.printNationOfCapital("Washington");
      me.printNationOfCapital("London");
      me.printNationOfCapital("Paris");
   }
}

When the above is run, the output looks like that shown in the next screen snapshot. The names for capital cities and nations that are provided in the example are intended to illustrate one of the problems with the approach of using two single-directional maps: they can get out of synch. This issue can be remedied with a bidirectional map as shown in the next code sample that employs the ImmutableBiMap implementation of the BiMap interface.

GuavaBiMapDemo
package dustin.examples;

import static java.lang.System.out;
import com.google.common.collect.BiMap;
import com.google.common.collect.ImmutableBiMap;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 * Simple demonstration of Google Guava's bidirectional map support.
 * 
 * @author Dustin
 */
public class GuavaBiMapDemo
{
   private final static BiMap<String, String> nationsToCapitals;

   static
   {
      final Map<String, String> tempNationsToCapitals = new HashMap<String, String>();
      tempNationsToCapitals.put("Canada", "Ottawa");
      tempNationsToCapitals.put("England", "London");
      tempNationsToCapitals.put("France", "Paris");
      tempNationsToCapitals.put("Mexico", "Mexico City");
      tempNationsToCapitals.put("Portugal", "Lisbon");
      tempNationsToCapitals.put("Spain", "Madrid");
      tempNationsToCapitals.put("United States", "Washington");
      nationsToCapitals = ImmutableBiMap.copyOf(Collections.unmodifiableMap(tempNationsToCapitals));
   }

   /**
    * Print the capital city of the nation whose name is provided.
    * 
    * @param nationName Name of nation for which capital is decided.
    */
   public void printCapitalOfNation(final String nationName)
   {
      out.println(
           "The capital of " + nationName + " is "
         + (nationsToCapitals.containsKey(nationName) ? nationsToCapitals.get(nationName) : "unknown" )
         + ".");
   }

   /**
    * Print the name of the nation whose capital name is provided.
    * 
    * @param capitalName Name of capital city for which nation is desired.
    */
   public void printNationOfCapital(final String capitalName)
   {
      out.println(
           capitalName + " is the the capital of "
         + (nationsToCapitals.containsValue(capitalName) ? nationsToCapitals.inverse().get(capitalName) : "unknown" )
         + ".");
   }

   /**
    * Main function demonstrating this use of two mono-directional maps.
    * 
    * @param arguments Command-line arguments; none expected.
    */
   public static void main(final String[] arguments)
   {
      final GuavaBiMapDemo me = new GuavaBiMapDemo();
      me.printCapitalOfNation("United States");
      me.printCapitalOfNation("England");
      me.printCapitalOfNation("France");
      me.printNationOfCapital("Washington");
      me.printNationOfCapital("London");
      me.printNationOfCapital("Paris");
   }
}

When the above is executed, the output shows more consistent mappings for London and for Paris/France because there was no need to maintain two separate maps.

Guava's bidirectional maps provide a safer and more readable approach to implementing data structures that map keys to values and values to key in such a way that one can be accessed via the other. Normal Java Maps only access use of a key to access a value directly, but both directions of access are supported by Guava's bidirectional maps.

Guava seems to be receiving more attention these days. Google's guava java: the easy parts was written about one year ago and is a nice introduction to the "easier" portions of Guava. Tom Jefferys's September 2011 post Multimaps - Google Guava also provides a nice overview of Guava's map support with focus on Multimaps followed by separate posts focusing on BiMaps and Multisets. Recent post 5 Reasons to use Guava includes Guava's map support as one of five reasons that Java developers should embrace Guava. Section 16.9. retrieving a key by value (working with bi-directional maps) of the Java Commons Cookbook (download) also covers Guava's support for bidirectional maps.