lcd.clj

(ns lcs.core)

;(def a [:a :b :b :c :d :e :f :z])
;(def b [:a :b :b    :d :e :f :g :a])

(def a "abcabba")
(def b "cbabac")

(defn indexed [coll] (map vector (iterate inc 1) coll))

(defn comp-comparator [& funs]
  (fn [a b]
   (loop [funs funs]
     (let [c ((first funs) a b)]
       (if-not (zero? c) c
               (if (= 1 (count funs))
                 0
                 (recur (rest funs))))))))

(defn sort-by-many [keyfns coll]
  (let [c-fn (apply
              comp-comparator
              (map #(fn [a b] (compare (% a) (% b))) keyfns))]
    (sort c-fn coll)))

(defn binary-search [comp-fn key coll & [not-found]]
  (let [index (java.util.Collections/binarySearch
               coll key
               (fn [a b] (compare (comp-fn a) (comp-fn b))))]
    (if (neg? index)
      not-found
      (nth coll index))))

(defn process-b [b]
  (partition-by
   :hash
   (sort-by-many [:hash :index]
    (map (fn [[index x]] {:content x
                          :index index
                          :hash (hash x)}) (indexed b)))))

(defn process-a [a b-mapped]
  (map
   (fn [[index x]]
     {:content x
      :index index
      :b-map
      (binary-search (comp :hash first)
                     [{:hash (hash x)}]
                     b-mapped
                     ::not-found)})
   (indexed a)))

#_(pprint (process-a a (process-b a)))

(defn cand [a b previous]
  {:a a
   :b b
   :previous previous})

(def k [(cand 0 0 nil)
        (cand (inc (count a)) (inc (count b)) nil)])

#_(defn merge [k k-last (process-b b) (process-a a (process-b))]
  )

(in progress)