On Mon, Mar 7, 2011 at 1:14 PM, Tassilo Horn <[email protected]> wrote:
> Hello all,
>
> does clojure have sets that keep the insertion order, like Java's
> LinkedHashSet?
>
> Currently, I use lazy vectors in conjunction with `distinct', but that
> seems to perform not too well.
>
> Bye,
> Tassilo
Try something like:
(deftype OrderPreservingSet [v m s]
clojure.lang.IObj
(withMeta [this md] (OrderPreservingSet. v (with-meta m md) s))
(meta [this] (meta m))
clojure.lang.IPersistentSet
(cons [this object]
(if (contains? m object)
this
(OrderPreservingSet.
(conj v object)
(assoc m object (count v))
s)))
(count [this] (count m))
(empty [this] (OrderPreservingSet. [] {} (Object.)))
(equiv [this other] (= (seq this) other))
(seq [this] (seq (remove #{s} v)))
(get [this object]
(v (m object)))
(contains [this object]
(contains? m object))
(disjoin [this object]
(if-let [idx (m object)]
(OrderPreservingSet.
(assoc v idx s)
(dissoc m object)
s)
this))
clojure.lang.IFn
(invoke [this object]
(get this object))
(invoke [this object not-found]
(get this object not-found)))
(defn order-preserving-set [& things]
(reduce conj (OrderPreservingSet. [] {} (Object.)) things))
Cursory testing shows this working as expected (other than that
calling it as a function with the wrong arity will produce a different
exception from the usual IAE):
user=> (def foo (order-preserving-set 300 900 150 650 300))
#'user/foo
user=> foo
#{300 900 150 650}
user=> (def bar (Integer. 450))
#'user/bar
user=> (= bar (Integer. 450))
true
user=> (identical? bar (Integer. 450))
false
user=> (identical? ((conj foo bar) bar) bar)
true
user=> (disj foo 900)
#{300 150 650}
user=>
It should be substitutable for a normal set in Clojure code, but it
seqs and prints itself in insertion order. Performance caveat: if you
keep conjing and disjing items from an open-ended set the internal
vector may keep growing. The alternative isn't pretty though: actually
delete items from the internal vector, which would make disj O(n).
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
