set.clj

(ns timl.set)

;start clojure.core
(defn max-key
  ([k x] x)
  ([k x y] (if (> (k x) (k y)) x y))
  ([k x y & more]
   (reduce #(max-key k %1 %2) (max-key k x y) more)))

(defn remove
  [pred coll]
  (filter (complement pred) coll))

(defn select-keys
  [map keyseq]
  (loop [ret {} keys (seq keyseq)]
        (if keys
          (let [entry (find map (first keys))]
            (recur
              (if entry
                (conj ret entry)
                ret)
              (next keys)))
          (with-meta ret (meta map)))))

(defn some
  [pred coll]
  (when (seq coll)
    (or (pred (first coll)) (recur pred (next coll)))))


(defn merge
  [& maps]
  (when (some identity maps)
    (reduce #(conj (or %1 {}) %2) maps)))
;end clojure.core



(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
  ([] #{})
  ([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
  ([s1] s1)
  ([s1 s2]
     (if (< (count s2) (count s1))
       (recur s2 s1)
       (reduce (fn [result item]
                   (if (contains? s2 item)
         result
                     (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
  ([s1] s1)
  ([s1 s2] 
     (if (< (count s1) (count s2))
       (reduce (fn [result item] 
                   (if (contains? s2 item) 
                     (disj result item) 
                     result))
               s1 s1)
       (reduce disj s1 s2)))
  ([s1 s2 & sets] 
     (reduce difference s1 (conj sets s2))))


(defn select
  [pred xset]
    (reduce (fn [s k] (if (pred k) s (disj s k)))
            xset xset))

(defn project
  [xrel ks]
  (with-meta (set (map #(select-keys % ks) xrel)) (meta xrel)))

(defn rename-keys
  [map kmap]
    (reduce 
     (fn [m [old new]]
       (if (contains? map old)
         (assoc m new (get map old))
         m)) 
     (apply dissoc map (keys kmap)) kmap))

(defn rename
  [xrel kmap]
  (with-meta (set (map #(rename-keys % kmap) xrel)) (meta xrel)))

(defn index
  [xrel ks]
    (reduce
     (fn [m x]
       (let [ik (select-keys x ks)]
         (assoc m ik (conj (get m ik #{}) x))))
     {} xrel))
   
(defn map-invert
  [m] (reduce (fn [m [k v]] (assoc m v k)) {} m))

(defn join
  ([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)
                     ret)))
               #{} 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)
                   ret)))
             #{} s))))

(defn subset? 
  [set1 set2]
  (and (<= (count set1) (count set2))
       (every? #(contains? set2 %) set1)))

(defn superset? 
  [set1 set2]
  (and (>= (count set1) (count set2))
       (every? #(contains? set1 %) set2)))

(use 'timl.test)

(assert (= (union #{}) #{}))
(assert (= (union #{1}) #{1}))
(assert (= (union #{1 2 3}) #{1 2 3}))

(assert (= (intersection #{}) #{}))
(assert (= (intersection #{1}) #{1}))
(assert (= (intersection #{1 2 3}) #{1 2 3}))

(assert (= (difference #{}) #{}))
(assert (= (difference #{1}) #{1}))
(assert (= (difference #{1 2 3}) #{1 2 3}))

(assert (= (select integer? #{}) #{}))
(assert (= (select integer? #{1 2}) #{1 2}))
(assert (= (select integer? #{1 2 :a :b :c}) #{1 2}))
(assert (= (select integer? #{:a :b :c}) #{}))

(def compositions
  #{{:name "Art of the Fugue" :composer "J. S. Bach"}
    {:name "Musical Offering" :composer "J. S. Bach"}
    {:name "Requiem" :composer "Giuseppe Verdi"}
    {:name "Requiem" :composer "W. A. Mozart"}})

; FIXME HashMap needs metadata
;(= (project compositions [:name]) #{{:name "Art of the Fugue"}
;                                    {:name "Requiem"}
;                                    {:name "Musical Offering"}})
;(= (project compositions [:composer]) #{{:composer "W. A. Mozart"}
;                                        {:composer "Giuseppe Verdi"}
;                                        {:composer "J. S. Bach"}})
;(= (project compositions [:year]) #{{}})
;(= (project #{{}} [:name]) #{{}} )))
;

; FIXME HashSet needs metadata
;(= (rename compositions {:name :title}) #{{:title "Art of the Fugue" :composer "J. S. Bach"}
;                                          {:title "Musical Offering" :composer "J. S. Bach"}
;                                          {:title "Requiem" :composer "Giuseppe Verdi"}
;                                          {:title "Requiem" :composer "W. A. Mozart"}})
;(= (rename compositions {:year :decade}) #{{:name "Art of the Fugue" :composer "J. S. Bach"}
;                                            {:name "Musical Offering" :composer "J. S. Bach"}
;                                            {:name "Requiem" :composer "Giuseppe Verdi"}
;                                           {:name "Requiem" :composer "W. A. Mozart"}})
;(= (rename #{{}} {:year :decade}) #{{}})

(assert (= (rename-keys {:a "one" :b "two"} {:a :z}) {:z "one" :b "two"}))
(assert (= (rename-keys {:a "one" :b "two"} {:a :z :c :y}) {:z "one" :b "two"}))
(assert (= (rename-keys {:a "one" :b "two" :c "three"} {:a :b :b :a}) {:a "two" :b "one" :c "three"}))

;FIXME HashMap needs metadata
;(= (index  #{{:c 2} {:b 1} {:a 1 :b 2}} [:b]) {{:b 2} #{{:a 1 :b 2}}, {:b 1} #{{:b 1}} {} #{{:c 2}}})

;FIXME HashMap needs metadata
(assert (= (join compositions compositions) compositions))
(assert (= (join compositions #{{:name "Art of the Fugue" :genre "Classical"}})
           #{{:name "Art of the Fugue" :composer "J. S. Bach" :genre "Classical"}}))


(assert (= (map-invert {:a "one" :b "two"}) {"one" :a "two" :b}))

(assert (subset? #{} #{}))
(assert (subset? #{} #{1}))
(assert (subset? #{1} #{1}))
(assert (subset? #{1 2} #{1 2}))
(assert (subset? #{1 2} #{1 2 42}))
(assert (subset? #{false} #{false}))

(assert (superset? #{} #{}))
(assert (superset? #{1} #{}))
(assert (superset? #{1} #{1}))
(assert (superset? #{1 2} #{1 2}))
(assert (superset? #{1 2 42} #{1 2}))
(assert (superset? #{false}  #{false}))
(assert (superset? #{nil}    #{nil}))
(assert (superset? #{false nil} #{false}))
(assert (superset? #{1 2 4 nil false} #{1 2 nil})))