Switch branches/tags
clojure-1.9.0-alpha17 clojure-1.9.0-alpha16 clojure-1.9.0-alpha15 clojure-1.9.0-alpha14 clojure-1.9.0-alpha13 clojure-1.9.0-alpha12 clojure-1.9.0-alpha11 clojure-1.9.0-alpha10 clojure-1.9.0-alpha9 clojure-1.9.0-alpha8 clojure-1.9.0-alpha7 clojure-1.9.0-alpha6 clojure-1.9.0-alpha5 clojure-1.9.0-alpha4 clojure-1.9.0-alpha3 clojure-1.9.0-alpha2 clojure-1.9.0-alpha1 clojure-1.8.0 clojure-1.8.0-beta2 clojure-1.8.0-beta1 clojure-1.8.0-alpha5 clojure-1.8.0-alpha4 clojure-1.8.0-alpha3 clojure-1.8.0-alpha2 clojure-1.8.0-alpha1 clojure-1.8.0-RC5 clojure-1.8.0-RC4 clojure-1.8.0-RC3 clojure-1.8.0-RC2 clojure-1.8.0-RC1 clojure-1.7.0 clojure-1.7.0-beta3 clojure-1.7.0-beta2 clojure-1.7.0-beta1 clojure-1.7.0-alpha6 clojure-1.7.0-alpha5 clojure-1.7.0-alpha4 clojure-1.7.0-alpha3 clojure-1.7.0-alpha2 clojure-1.7.0-alpha1 clojure-1.7.0-RC2 clojure-1.7.0-RC1 clojure-1.6.0 clojure-1.6.0-beta2 clojure-1.6.0-beta1 clojure-1.6.0-alpha3 clojure-1.6.0-alpha2 clojure-1.6.0-alpha1 clojure-1.6.0-RC4 clojure-1.6.0-RC3 clojure-1.6.0-RC2 clojure-1.6.0-RC1 clojure-1.5.1 clojure-1.5.0 clojure-1.5.0-beta13 clojure-1.5.0-beta12 clojure-1.5.0-beta11 clojure-1.5.0-beta10 clojure-1.5.0-beta9 clojure-1.5.0-beta8 clojure-1.5.0-beta7 clojure-1.5.0-beta2 clojure-1.5.0-beta1 clojure-1.5.0-alpha7 clojure-1.5.0-alpha6 clojure-1.5.0-alpha5 clojure-1.5.0-alpha4 clojure-1.5.0-alpha3 clojure-1.5.0-alpha2 clojure-1.5.0-alpha1 clojure-1.5.0-RC17 clojure-1.5.0-RC16 clojure-1.5.0-RC15 clojure-1.5.0-RC14 clojure-1.5.0-RC6 clojure-1.5.0-RC5 clojure-1.5.0-RC4 clojure-1.5.0-RC3 clojure-1.5.0-RC2 clojure-1.5.0-RC1 clojure-1.4.0 clojure-1.4.0-beta7 clojure-1.4.0-beta6 clojure-1.4.0-beta5 clojure-1.4.0-beta4 clojure-1.4.0-beta3 clojure-1.4.0-beta2 clojure-1.4.0-beta1 clojure-1.4.0-alpha5 clojure-1.4.0-alpha4 clojure-1.4.0-alpha3 clojure-1.4.0-alpha2 clojure-1.4.0-alpha1 clojure-1.3.0 clojure-1.3.0-beta3 clojure-1.3.0-beta2 clojure-1.3.0-beta1 clojure-1.3.0-alpha8 clojure-1.3.0-alpha7 clojure-1.3.0-alpha6
Nothing to show
Find file
177 lines (155 sloc) 5.15 KB
; Copyright (c) Rich Hickey. All rights reserved.
; The use and distribution terms for this software are covered by the
; Eclipse Public License 1.0 (
; which can be found in the file epl-v10.html at the root of this distribution.
; By using this software in any fashion, you are agreeing to be bound by
; the terms of this license.
; You must not remove this notice, or any other, from this software.
(ns ^{:doc "Set operations such as union/intersection."
:author "Rich Hickey"}
(defn- bubble-max-key [k coll]
"Move a maximal element of coll according to fn k (which returns a number)
to the front of coll."
(let [max (apply max-key k coll)]
(cons max (remove #(identical? max %) coll))))
(defn union
"Return a set that is the union of the input sets"
{:added "1.0"}
([] #{})
([s1] s1)
([s1 s2]
(if (< (count s1) (count s2))
(reduce conj s2 s1)
(reduce conj s1 s2)))
([s1 s2 & sets]
(let [bubbled-sets (bubble-max-key count (conj sets s2 s1))]
(reduce into (first bubbled-sets) (rest bubbled-sets)))))
(defn intersection
"Return a set that is the intersection of the input sets"
{:added "1.0"}
([s1] s1)
([s1 s2]
(if (< (count s2) (count s1))
(recur s2 s1)
(reduce (fn [result item]
(if (contains? s2 item)
(disj result item)))
s1 s1)))
([s1 s2 & sets]
(let [bubbled-sets (bubble-max-key #(- (count %)) (conj sets s2 s1))]
(reduce intersection (first bubbled-sets) (rest bubbled-sets)))))
(defn difference
"Return a set that is the first set without elements of the remaining sets"
{:added "1.0"}
([s1] s1)
([s1 s2]
(if (< (count s1) (count s2))
(reduce (fn [result item]
(if (contains? s2 item)
(disj result item)
s1 s1)
(reduce disj s1 s2)))
([s1 s2 & sets]
(reduce difference s1 (conj sets s2))))
(defn select
"Returns a set of the elements for which pred is true"
{:added "1.0"}
[pred xset]
(reduce (fn [s k] (if (pred k) s (disj s k)))
xset xset))
(defn project
"Returns a rel of the elements of xrel with only the keys in ks"
{:added "1.0"}
[xrel ks]
(with-meta (set (map #(select-keys % ks) xrel)) (meta xrel)))
(defn rename-keys
"Returns the map with the keys in kmap renamed to the vals in kmap"
{:added "1.0"}
[map kmap]
(fn [m [old new]]
(if (contains? map old)
(assoc m new (get map old))
(apply dissoc map (keys kmap)) kmap))
(defn rename
"Returns a rel of the maps in xrel with the keys in kmap renamed to the vals in kmap"
{:added "1.0"}
[xrel kmap]
(with-meta (set (map #(rename-keys % kmap) xrel)) (meta xrel)))
(defn index
"Returns a map of the distinct values of ks in the xrel mapped to a
set of the maps in xrel with the corresponding values of ks."
{:added "1.0"}
[xrel ks]
(fn [m x]
(let [ik (select-keys x ks)]
(assoc m ik (conj (get m ik #{}) x))))
{} xrel))
(defn map-invert
"Returns the map with the vals mapped to the keys."
{:added "1.0"}
[m] (reduce (fn [m [k v]] (assoc m v k)) {} m))
(defn join
"When passed 2 rels, returns the rel corresponding to the natural
join. When passed an additional keymap, joins on the corresponding
{:added "1.0"}
([xrel yrel] ;natural join
(if (and (seq xrel) (seq yrel))
(let [ks (intersection (set (keys (first xrel))) (set (keys (first yrel))))
[r s] (if (<= (count xrel) (count yrel))
[xrel yrel]
[yrel xrel])
idx (index r ks)]
(reduce (fn [ret x]
(let [found (idx (select-keys x ks))]
(if found
(reduce #(conj %1 (merge %2 x)) ret found)
#{} s))
([xrel yrel km] ;arbitrary key mapping
(let [[r s k] (if (<= (count xrel) (count yrel))
[xrel yrel (map-invert km)]
[yrel xrel km])
idx (index r (vals k))]
(reduce (fn [ret x]
(let [found (idx (rename-keys (select-keys x (keys k)) k))]
(if found
(reduce #(conj %1 (merge %2 x)) ret found)
#{} s))))
(defn subset?
"Is set1 a subset of set2?"
{:added "1.2",
:tag Boolean}
[set1 set2]
(and (<= (count set1) (count set2))
(every? #(contains? set2 %) set1)))
(defn superset?
"Is set1 a superset of set2?"
{:added "1.2",
:tag Boolean}
[set1 set2]
(and (>= (count set1) (count set2))
(every? #(contains? set1 %) set2)))
(refer 'set)
(def xs #{{:a 11 :b 1 :c 1 :d 4}
{:a 2 :b 12 :c 2 :d 6}
{:a 3 :b 3 :c 3 :d 8 :f 42}})
(def ys #{{:a 11 :b 11 :c 11 :e 5}
{:a 12 :b 11 :c 12 :e 3}
{:a 3 :b 3 :c 3 :e 7 }})
(join xs ys)
(join xs (rename ys {:b :yb :c :yc}) {:a :a})
(union #{:a :b :c} #{:c :d :e })
(difference #{:a :b :c} #{:c :d :e})
(intersection #{:a :b :c} #{:c :d :e})
(index ys [:b])