Java BiMap, BidiMap

After doing some research and trying to find just the right Java Bi-Map, I couldn't find any, so I had to roll my own :-( To my surprise, implementation of a Bi-Maps is not straight-forward, there's not such thing as the 'one Bi-Map functionality'.

The interesting case is this one: say there are mappings A->1 and B->2. What happens once you insert C->2 ?

Will you remove B->2 to ensure uniqueness of keys and values ? (resulting in A->1 and C->2)

or not, resulting in A->1, B->2 and C->2. Please note that in the latter case, there's no well-defined lookup for value "2". Is it B or is it C ?

So what I needed was uniqueness of both keys and values, in all cases, using generics. Here it goes:

import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/**
 * One possible implementation of a Bi-directional Map.
 * 
 * Note: there are several variations of BiMap, depending on the behaviour of put(k,v)... Is it allowed to have more
 * than one k for one value ?? Modify
 * 
 * @author apodehl
 * 
 * @param 
 * @param 
 */
public class BiMap implements Map
{
  Map keyVal; // maps key->value

  Map valKey; // maps value->key

  public BiMap()
  {
    keyVal = new LinkedHashMap();
    valKey = new LinkedHashMap();
  }

  @Override
  public V put(K key, V val)
  {
    // --- this implementation allows one-to-one ONLY !! ---
    if (valKey.containsKey(val)) {
      keyVal.remove(valKey.get(val));
    }
    if (keyVal.containsKey(key)) {
      valKey.remove(keyVal.get(key));
    }
    // --- remove above if that's not what you want ---

    // 
    valKey.put(val, key);
    return keyVal.put(key, val);
  }

  @Override
  public void putAll(Map< ? extends K, ? extends V> m)
  {
    for (Entry< ? extends K, ? extends V> e : m.entrySet()) {
      put(e.getKey(), e.getValue());
    }
  }

  /**
   * Type-safe get.
   * 
   * @param key
   * @return
   */
  public K getKey(V val)
  {
    return valKey.get(val);
  }

  /**
   * Type-safe get.
   * 
   * @param key
   * @return
   */
  public V getVal(K key)
  {
    return keyVal.get(key);
  }

  @Override
  // unfortunately Map interface isn't type-safe
  public V get(Object key)
  {
    return getVal((K) key);
  }

  /**
   * Type-safe contains.
   * 
   * @param key
   * @return
   */
  public boolean contains(K key)
  {
    if (keyVal == null) return false;
    return keyVal.containsKey(key);
  }

  /**
   * Type-safe containsValue.
   * 
   * @param key
   * @return
   */
  public boolean containsVal(V val)
  {
    if (valKey == null) return false;
    return valKey.containsKey(val);
  }

  // unfortunately Map interface isn't type safe here ..
  @Override
  public boolean containsKey(Object key)
  {
    return contains((K) key);
  }

  // unfortunately Map interface isn't type safe here ..
  @Override
  public boolean containsValue(Object value)
  {
    return containsVal((V) value);
  }

  @Override
  public Set< java.util.Map.Entry> entrySet()
  {
    return keyVal.entrySet();
  }

  @Override
  public boolean isEmpty()
  {
    return keyVal.isEmpty();
  }

  @Override
  public int size()
  {
    return keyVal.size();
  }

  @Override
  public Collection values()
  {
    return keyVal.values();
  }

  public V removeByKey(K key)
  {
    V val = keyVal.remove(key);
    valKey.remove(val);
    return val;
  }

  public K removeByVal(V val)
  {
    K key = valKey.remove(val);
    keyVal.remove(key);
    return key;
  }

  // unfortunately Map interface isn't type-safe
  @Override
  public V remove(Object key)
  {
    return removeByKey((K) key);
  }

  @Override
  public Set keySet()
  {
    return keyVal.keySet();
  }

  @Override
  public void clear()
  {
    keyVal.clear();
    valKey.clear();
  }

  public String toString()
  {
    String s = "BiMap:\n";
    s += "  key->value: " + keyVal.toString();
    s += "\n";
    s += "  value->key: " + valKey.toString();
    return s;
  }

  public static void main(String[] args)
  {

    BiMap biMap = new BiMap();
    biMap.put("A", 1);
    biMap.put("B", 2);
    System.out.println(biMap); // {A=1, B=2}

    biMap.put("C", 2);
    System.out.println(biMap); // {A=1, C=2}

    biMap.removeByVal(1);
    System.out.println(biMap); // {C=2}
  }
}

Java Bi-directional Maps: Apache commons or Google collections ?

In case you need a bi-directional Map in Java, you can, of course, easily roll your own.

But this is a common problem, so others have done this work already.

Here's a simple how-to on bi-directional maps with Apache and Google commons.

Apache commons collections offers a BidiMap interface with various implementations.

For example:

public class TestBidiMap
{
static BidiMap bimap = new DualHashBidiMap();
public static void main(String[] args)
{
bimap.put("D", 3);
System.out.println("D -> " + bimap.get("D") );
System.out.println("3 -> " + bimap.inverseBidiMap().get(3) );
}
}

Nice and easy, but unfortunately this version of BidiMap doesn't use Java generics, which I have learned to like over time (bimpap.get(3) will not show a compile error) !

Google collections has an alternative that uses generics: BiMap

public class TestBiMap
{
static BiMap<String,Integer> bimap = HashBiMap.create();
public static void main(String[] args)
{
 bimap.put("D", 3);
 System.out.println("D -> " + bimap.get("D") );
 System.out.println("3 -> " + bimap.inverse().get(3) );
}
}

Also nice and easy, what's interesting is the factory method HashBiMap.create(). This removes the need to duplicate the generics type specification of String, Integer. Kiss rules, so two points for Google collections here.

Summary: any mid-size Java project probably shouldn't live without Apache commons, but as a useful addition, Google collections is definitely worth a look.