gistfile1.clj

;; From "Transform columnar data into a tree?" Clojure Google Groups thread:
;; http://groups.google.com/group/clojure/browse_thread/thread/91142e34913e6e28

(use 'clojure.contrib.pprint)

(defn add-path [root path]
  (let [add-child (fn [parent child-path]
                    (if (get-in parent child-path)
                      parent
                      (assoc-in parent child-path
                                {:data (peek child-path)
                                 :children (sorted-map)})))
        ancestor-paths (for [i (range 1 (inc (count path)))]
                         (vec (interpose :children (take i path))))]
    (reduce add-child root ancestor-paths)))

(defn rows->tree [rows]
  {:data :root
   :children (reduce add-path (sorted-map) rows)})

;; Note: consumes stack space
(defn tree-map->vec [node]
  (vec
   (for [[k v] node]
     (if (zero? (count (:children v)))
       (dissoc v :children)
       (assoc v :children (tree-map->vec (:children v)))))))

;; Examples

(def data1 [[:a1 :b1 :c1]
            [:a1 :b1 :c2]
            [:a1 :b2 :c3]
            [:a1 :b2 :c4]
            [:a2 :b3 :c5]
            [:a2 :b3 :c6]
            [:a2 :b4 :c7]
            [:a2 :b4 :c8]])

(def data2 [[:a1 :b1]
            [:a1 :b2]
            [:a1 :b3]])

(def data3 [[:a1 :b1 :c1 :d1]
            [:a1 :b1 :c1 :d2]
            [:a1 :b1 :c1 :d3]])

(doseq [data [data1 data2 data3]]
  (let [tree (rows->tree data)
        tree-vec (tree-map->vec (:children tree))]
    (pprint tree)
    (println "\n--\n")
    (pprint tree-vec)
    (println "\n--\n")))

gistfile2.txt

{:data :root,
 :children
 {:a1
  {:data :a1,
   :children
   {:b1
    {:data :b1,
     :children
     {:c1 {:data :c1, :children {}}, :c2 {:data :c2, :children {}}}},
    :b2
    {:data :b2,
     :children
     {:c3 {:data :c3, :children {}}, :c4 {:data :c4, :children {}}}}}},
  :a2
  {:data :a2,
   :children
   {:b3
    {:data :b3,
     :children
     {:c5 {:data :c5, :children {}}, :c6 {:data :c6, :children {}}}},
    :b4
    {:data :b4,
     :children
     {:c7 {:data :c7, :children {}},
      :c8 {:data :c8, :children {}}}}}}}}

--

[{:data :a1,
  :children
  [{:data :b1, :children [{:data :c1} {:data :c2}]}
   {:data :b2, :children [{:data :c3} {:data :c4}]}]}
 {:data :a2,
  :children
  [{:data :b3, :children [{:data :c5} {:data :c6}]}
   {:data :b4, :children [{:data :c7} {:data :c8}]}]}]

--

{:data :root,
 :children
 {:a1
  {:data :a1,
   :children
   {:b1 {:data :b1, :children {}},
    :b2 {:data :b2, :children {}},
    :b3 {:data :b3, :children {}}}}}}

--

[{:data :a1, :children [{:data :b1} {:data :b2} {:data :b3}]}]

--

{:data :root,
 :children
 {:a1
  {:data :a1,
   :children
   {:b1
    {:data :b1,
     :children
     {:c1
      {:data :c1,
       :children
       {:d1 {:data :d1, :children {}},
        :d2 {:data :d2, :children {}},
        :d3 {:data :d3, :children {}}}}}}}}}}

--

[{:data :a1,
  :children
  [{:data :b1,
    :children
    [{:data :c1, :children [{:data :d1} {:data :d2} {:data :d3}]}]}]}]

--