On Wednesday, November 17, 2010, Sunil S Nandihalli
<sunil.nandiha...@gmail.com> wrote:
> Regarding your bimap implementation, in terms of complexity, I feel, it will
> be linear in the number of elements, when accessing the pair via the value ..
> Is that true?
No I use two maps and rmap is O(1) so rmap+get is O(log32 n) like a
direct get. What may confuse you is that only the direct map is
hinted. The reverse map doesn't need to: no interop calls on it while
it is in reverse position.
> On Tue, Nov 16, 2010 at 2:36 PM, Christophe Grand <christo...@cgrand.net>
> wrote:
>
>
> You can implement your own, prettu easily with deftype.
> However it can be tedious to track every methods, so we need a repl helper
> function to scaffold the code for us.
>
> (defn scaffold [iface]
> (doseq [[iface methods] (->> iface .getMethods
> (map #(vector (.getName (.getDeclaringClass %))
> (symbol (.getName %))
> (count (.getParameterTypes %))))
> (group-by first))]
> (println (str " " iface))
> (doseq [[_ name argcount] methods]
> (println
> (str " "
> (list name (into ['this] (take argcount (repeatedly gensym)))))))))
>
> user=> (scaffold clojure.lang.IPersistentMap)
> clojure.lang.IPersistentMap
> (assoc [this G__441 G__442])
> (without [this G__443])
> (assocEx [this G__444 G__445])
> java.lang.Iterable
> (iterator [this])
> clojure.lang.Associative
> (containsKey [this G__446])
> (assoc [this G__447 G__448])
> (entryAt [this G__449])
> clojure.lang.IPersistentCollection
> (count [this])
> (cons [this G__450])
> (empty [this])
> (equiv [this G__451])
> clojure.lang.Seqable
> (seq [this])
> clojure.lang.ILookup
> (valAt [this G__452 G__453])
> (valAt [this G__454])
> clojure.lang.Counted
> (count [this])
> nil
>
> Now you need to remove the duplicates (count and assoc), wrap everything in a
> deftype form and implement it:
> (including a new protocol fn to reverse a bidi map)
>
> (defprotocol ReversibleMap
> (rmap [m]))
>
> (defn- rdissoc [d r v]
> (if-let [[_ k] (find r v)] (dissoc d k) d))
>
> (deftype Bimap [^clojure.lang.IPersistentMap direct reverse]
> Object
> (hashCode [x]
> (.hashCode direct))
> (equals [x y]
> (.equals direct y))
> clojure.lang.IPersistentMap
> (without [this k]
> (Bimap.
> (dissoc direct k)
> (rdissoc reverse direct k)))
> (assocEx [this k v]
> (if (or (contains? direct k) (contains? reverse v))
> (throw (Exception. "Key or value already present"))
> (assoc this k v)))
> java.lang.Iterable
> (iterator [this]
> (.iterator direct))
> clojure.lang.Associative
> (assoc [this k v]
> (Bimap.
> (assoc (rdissoc direct reverse v) k v)
> (assoc (rdissoc reverse direct k) v k)))
> (containsKey [this k]
> (contains? direct k))
> (entryAt [this k]
> (find direct k))
> clojure.lang.IPersistentCollection
> (cons [this x]
> (if-let [[k v] (and (vector? x) x)]
> (assoc this k v)
> (reduce (fn [m [k v]] (assoc m k v)) this x)))
> (empty [this]
> (.empty direct))
> (equiv [this x]
> (.equiv direct x))
> clojure.lang.Seqable
> (seq [this]
> (seq direct))
> clojure.lang.ILookup
> (valAt [this k else]
> (direct k else))
> (valAt [this k]
> (direct k))
> clojure.lang.Counted
> (count [this]
> (count direct))
> ReversibleMap
> (rmap [this]
> (Bimap. reverse direct)))
>
> (defn bimap [& kvs]
> (reduce (fn [m [k v]] (assoc m k v)) (Bimap. {} {}) (partition 2 kvs)))
>
> Some quick tests:
> user=> (assoc (bimap :a 1 :b 2) [:c 3] [:d 4] [:e 5])
> {[:e 5] nil, [:c 3] [:d 4], :b 2, :a 1}
> user=> (assoc (bimap :a 1 :b 2) :c 3 :d 4 :e 5)
> {:e 5, :d 4, :c 3, :b 2, :a 1}
> user=> (assoc (bimap :a 1 :b 2) :c 3 :d 2 :e 5)
> {:e 5, :d 2, :c 3, :a 1}
> user=> (dissoc *1 :d)
> {:e 5, :c 3, :a 1}
> user=> (rmap *1)
> {5 :e, 3 :c, 1 :a}
> user=> (assoc *1 2 :c)
> {2 :c, 5 :e, 1 :a}
>
> hth,
>
> Christophe
>
>
>
>
>
> On Tue, Nov 16, 2010 at 8:16 AM, Sunil S Nandihalli
> <sunil.nandiha...@gmail.com> wrote:
>
>
>
> A bimap is a map where each elements of the pair can be used as key to access
> it..
> Sunil.
>
> On Tue, Nov 16, 2010 at 12:44 PM, Sunil S Nandihalli
> <sunil.nandiha...@gmail.com> wrote:
--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.cgrand.net/ (en)
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
