A bi-directional map in clojure?

Question

What would be the best way to implement a bi-directional map in clojure? (By bi-directional map, I mean an associative map which can provide both A->B and B->A access. So in effect, the values themselves would be keys for going in the opposite direction.)

I suppose I could set up two maps, one in each direction, but is there a more idiomatic way of doing this?

I'm interested both in cases where we want a bijection, implying that no two keys could map to the same value, and cases where that condition isn't imposed.

Answer 1

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