20091201-libsvm-model-parser.clj

(defn lazy-combine-sorted [xs ys]
  "lazily combines xs and ys and returns their union (assumes xs ys sorted)"
  (lazy-seq
   (if-let [[x & xs*] xs]
     (if-let [[y & ys*] ys]
       (cond (= x y) (cons x (lazy-combine-sorted xs* ys*))
             (< x y) (cons x (lazy-combine-sorted xs* ys))
             (> x y) (cons y (lazy-combine-sorted xs ys*)))
       xs) ; no more ys
     ys))) ; no more xs

(defn combine-lazy [xs ys]
  "combines xs and ys and returns their union"
  (lazy-combine-sorted (sort xs) (sort ys)))

(defn combine-sorted [a+ b+]
  (loop [[a & a-] a+
         [b & b-] b+
         acc []]
    (if (not a) ;; list a ended
      (concat acc b+)
      (if (not b) ;; list b ended
        (concat acc a+)
          (if (= a b) ;; items are the same
            (recur a- b- (conj acc a))
            (if (< a b) ;; either way
              (recur a- b+ (conj acc a))
              (recur a+ b- (conj acc b)))))))))

(defn combine [A B]
  (combine-sorted (sort A) (sort B)))