Bidirectional Map

Bi-directional Map in Java?

You can use the Google Collections API for that, recently renamed to Guava, specifically a BiMap

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.

How to create a 2 way map in java

It seems like you may be looking for a bimap.

The Google Collections (now a part of Guava) contains an BiMap interface with a few implementations.

From the BiMap documentation:

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.

The BiMap.inverse method appears to return a Map with the values as the keys, and the keys as the values, so that Map can be used to call get on the value and retrieve a key.

In addition the Map returned by inverse is a view of the underlying data, so it does not have to make extra copies of the original data.

From the BiMap.inverse method documentation:

Returns the inverse view of this
bimap, which maps each of this bimap's
values to its associated key. The two
bimaps are backed by the same data;
any changes to one will appear in the
other.

Is there a more efficient implementation for a bidirectional map?

There is a certain problem with double-storing your data in all simple implementations of a bimap. If you can break it down to a bimap of pointers from outside, then you can readily ignore this and simply keep both maps of the form std::map<A*,B*> like Arkaitz Jimenez already suggested (though contrary to his answer you have to care about the storage from outside to avoid a A->A* lookup). But if you have the pointers anyway, why not simply store a std::pair<A,B> at the point where you would otherwise store A and B separately?

It would be nice to have std::map<A,B*> instead of std::map<A*,B*> as this would allow for example the lookup of an element associated to an string by a newly created string with the same content instead of the pointer to the original string that created the pair. But it is customary to store a full copy of the key with every entry and only rely on the hash to find the right bucket. This way the returned item will be the correct one even in the case of a hash-collision...

If you want to have it quick and dirty though, there is this

hackish solution:

Create two maps std::map<size_t, A> mapA and std::map<size_t, B> mapB. Upon insertion hash both elements that are to be inserted to get the keys to the respective maps.

void insert(const A &a, const B &b) {
    size_t hashA = std::hash<A>(a);
    size_t hashB = std::hash<B>(b);

    mapA.insert({hashB, a});
    mapB.insert({hashA, b});
}

Lookup is implemented analogously.

Using a multimap instead of a map and verifying every element you get with a lookup in the respectively other map (get candidate b from mapA, hash b and look in mapB if it matches the wanted key, iterate to the next candidate b otherwise) this is a valid implementation - but still hackish in my opinion...

You can get a much nicer solution by using the copies of the elements that are used to compare the entries (see above) as only storage. It is a bit harder to get your head around that though. To elaborate:

a nicer solution:

Create two sets of pairs as std::set<pair<A, B*>> and std::set<pair<B, A*>> and overload the operator< and operator== to only take the first element of the pairs into account (or provide an corresponding comparion class). It is necessary to create sets of pairs instead of maps (which internally look similarly) because we need a guarantee that A and B will be at constant positions in memory. Upon insertion of an pair<A, B> we split it into two elements that fit into the above sets.

  std::set<pair<B, A*>> mapA;
  std::set<pair<A, B*>> mapB;

  void insert(const A &a, const B &b) {
      auto aitr = mapA.insert({b, nullptr}).first; // creates first pair
      B *bp = &(aitr->first);  // get pointer of our stored copy of b
      auto bitr = mapB.insert({a, bp}).first; 
      // insert second pair {a, pointer_to_b}
      A *ap = &(bitr->first);  // update pointer in mapA to point to a
      aitr->second = ap;
  }

Lookup can now simply be done by a simple std::set lookup and a pointer dereference.

This nicer solution is similar to the solution that boost uses - even though they use some annonymized pointers as second elements of the pairs and thus have to use reinterpret_casts.

Note that the .second part of the pairs need to be mutable (so I'm not sure std::pair can be used), or you have to add another layer of abstraction (std::set<pair<B, A**>> mapA) even for this simple insertion. In both solutions you need temporary elements to return non-const references to elements.

How to write a bidirectional mapping in Go?

[I assume your example is just minimal and that your actual mapping has more than two options. I also assume you meant bi-directonal mapping]

I would write one map:

var player2string = map[int]string{
  0: "0",
  1: "X",
  // etc...
}

And then would create a function to populate a different map string2player programmatically. Something like this:

var player2string = map[int]string{
    0: "0",
    1: "X",
    // etc...
}

var string2player map[string]int = convertMap(player2string)

func convertMap(m map[int]string) map[string]int {
    inv := make(map[string]int)
    for k, v := range m {
        inv[v] = k
    }
    return inv

}

func main() {
    fmt.Println(player2string)
    fmt.Println(string2player)
}

Try it on the Go playground

Two-way / bidirectional Dictionary in C#?

I wrote a quick couple of classes that lets you do what you want. You'd probably need to extend it with more features, but it is a good starting point.

The use of the code looks like this:

var map = new Map<int, string>();

map.Add(42, "Hello");

Console.WriteLine(map.Forward[42]);
// Outputs "Hello"

Console.WriteLine(map.Reverse["Hello"]);
//Outputs 42

Here's the definition:

public class Map<T1, T2>
{
    private Dictionary<T1, T2> _forward = new Dictionary<T1, T2>();
    private Dictionary<T2, T1> _reverse = new Dictionary<T2, T1>();

    public Map()
    {
        this.Forward = new Indexer<T1, T2>(_forward);
        this.Reverse = new Indexer<T2, T1>(_reverse);
    }

    public class Indexer<T3, T4>
    {
        private Dictionary<T3, T4> _dictionary;
        public Indexer(Dictionary<T3, T4> dictionary)
        {
            _dictionary = dictionary;
        }
        public T4 this[T3 index]
        {
            get { return _dictionary[index]; }
            set { _dictionary[index] = value; }
        }
    }

    public void Add(T1 t1, T2 t2)
    {
        _forward.Add(t1, t2);
        _reverse.Add(t2, t1);
    }

    public Indexer<T1, T2> Forward { get; private set; }
    public Indexer<T2, T1> Reverse { get; private set; }
}

A bi-directional map in clojure?

You could always use a Java library for this, like one of the collections in Apache commons. TreeBidiMap implements java.util.Map so it's even seq-able without any effort.

user> (def x (org.apache.commons.collections.bidimap.TreeBidiMap.))
#'user/x
user> (.put x :foo :bar)
nil 
user> (keys x)
(:foo)
user> (.getKey x :bar)
:foo
user> (:foo x)
:bar
user> (map (fn [[k v]] (str k ", " v)) x)
(":foo, :bar")

Some things won't work though, like assoc and dissoc, since they expect persistent collections and TreeBidiMap is mutable.

If you really want to do this in native Clojure, you could use metadata to hold the reverse-direction hash. This is still going to double your memory requirements and double the time for every add and delete, but lookups will be fast enough and at least everything is bundled.

(defn make-bidi []
  (with-meta {} {}))

(defn assoc-bidi [h k v]
  (vary-meta (assoc h k v)
             assoc v k))

(defn dissoc-bidi [h k]
  (let [v (h k)]
   (vary-meta (dissoc h k)
              dissoc v)))

(defn getkey [h v]
  ((meta h) v))

You'd probably have to implement a bunch of other functions to get full functionality of course. Not sure how feasible this approach is.

user> (def x (assoc-bidi (make-bidi) :foo :bar))
#'user/x
user> (:foo x)
:bar
user> (getkey x :bar)
:foo

---

Related Topics