Here is a bag implementation:
(defprotocol SetOps
(disjoin* [this obj])
(has* [this obj])
(total [this obj])
(counts [this]))
(defn disjoin
([s] s)
([s obj]
(disjoin* s obj))
([s obj & more]
(apply disjoin (disjoin s obj) more)))
(defn difference
([s] s)
([s other]
(apply disjoin s other))
([s other & more]
(apply difference (difference s other) more)))
(defn intersection
([s] s)
([s other]
(difference s (difference s other)))
([s other & more]
(apply intersection (intersection s other) more)))
(defn union
([s] s)
([s other]
(if (empty? other) s (apply conj s other)))
([s other & more]
(apply union (union s other) more)))
(defn has?
([s] true)
([s obj]
(has* s obj))
([s obj & more]
(and (has? s obj) (apply has? s more))))
(extend-type clojure.lang.IPersistentSet
SetOps
(disjoin* [this obj] (disj this obj))
(has* [this obj] (contains? this obj))
(total [this obj] (if (contains? this obj) 1 0))
(counts [this] (zipmap this (repeat 1))))
(deftype Bag [m c]
clojure.lang.IObj
(withMeta [this, mtd]
(Bag. (with-meta m mtd) c))
(meta [this] (meta m))
clojure.lang.IPersistentCollection
(count [this] c)
(empty [this] (Bag. {} 0))
(equiv [this other] (= (seq this) other))
(seq [this]
(mapcat
(fn [[k v]]
(repeat v k))
m))
(cons [this obj]
(Bag. (merge-with + m {obj 1}) (inc c)))
SetOps
(disjoin* [this obj]
(if-let [n (m obj)]
(if (= 1 n)
(Bag. (dissoc m obj) (dec c))
(Bag. (assoc m obj (dec n)) (dec c)))
this))
(has* [this obj] (contains? m obj))
(total [this obj] (m obj 0))
(counts [this] m)
Object
(toString [this]
(apply str
(interpose " "
(seq this)))))
(defn bag [& objects]
(Bag. (frequencies objects) (count objects)))
user=> (difference (bag 1 6 3 6 8 4 5 6 6 9 9) (bag 9 9 6 8 1))
#<Bag 6 6 6 3 4 5>
The difference, union, disjoin, intersection etc. functions are also
made to work on Clojure sets, and via extend-type or extend-protocol
can be extended to other types. (I didn't make Bag implement
IPersistentSet because I considered nonduplication to be part of the
latter's contract. So SetOps is a broader umbrella: unordered
collection with efficient membership test.)
The has? function is like contains?, but works on bags and sets rather
than on sets and maps and may take more arguments, in which case it
checks for all being contained. Note that (has? (bag 1) 1 1 1) will
return true; to check for containing at least a certain number of
occurrences use (not (empty? (difference bag-1 bag-2))) where bag-2
has the items we want to check for in the appropriate quantities.
Well, except that count and empty are broken for some reason:
user=> (.count (Bag. {} 0))
0
user=> (count (Bag. {} 0))
1
I don't understand what's causing this, but empty bags are always
returning a count of 1 (and false from empty?) although the .count
method correctly returns zero. I've traced the problem as far as the
Java method clojure.lang.RT/count but no farther at this time.
--
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
