wapiti-graph.clj

(defn node [x y]
  {:x x :y y})

(defn split-node [x y left right]
  (merge (node x y )
         {:left left
          :right right
          :intersect :split}))

(defn join-node [x y]
  (merge (node x y)
         {:intersect :join}))

(defn gen-node? []
  (= 1 (rand-int 2)))

(defn gen-split-node? []
  (= 1 (rand-int 4)))

(defn gen-nodes [starting-position ending-position y]
  (let [max-position (+ starting-position
                        (rand-int (Math/abs (- starting-position ending-position))))]
    (loop [nodes (vector)
           position starting-position]
      (if (= position max-position)
        nodes
        (let [node? (gen-node?)]
          (recur (if node?
                   (conj nodes (node position y))
                   nodes)
                 (inc position)))))))

(defn gen-random-nodes [starting-position ending-position initial-y]
  (assert (< starting-position ending-position))
  (loop [nodes (vector)
         position starting-position]
    (if (= position ending-position)
      nodes
      (let [node? (gen-node?)
            split? (gen-split-node?)
            node (if split?
                   (split-node position  initial-y
                               (gen-nodes (inc position) ending-position (inc initial-y))
                               (gen-nodes (inc position) ending-position (dec initial-y)))
                   (node position initial-y))
            nodes (if node?
                    (conj nodes node)
                    nodes)
            pos (if (and node? split?)
                  (max
                   (or (:x (last (:left node))) 0)
                   (or (:x (last (:right node))) 0))
                  position)]
        (recur nodes (inc pos))))))

(defn gen-graph [width]
  (let [initial-x 1
        initial-y 3
        start-position (inc initial-x)
        end-position (dec width)]
    (assert (< start-position  end-position)
            (str "Given width should be greater than " (inc start-position)))
    (concat
     (list (node initial-x initial-y))
     (gen-random-nodes start-position  end-position initial-y)
     (list (node width initial-y)))))

(defn select-nodes [fn-filter graph]
  (loop [graph graph
         nodes []]
    (if (empty? graph)
      nodes
      (let [node (first graph)]
        (recur (rest graph)
               (concat
                (if (fn-filter node)
                  (conj nodes node)
                  nodes)
                (select-nodes fn-filter (:left node))
                (select-nodes fn-filter (:right node))))))))

(defn str-nodes [nodes]
  (let [nodes (sort-by :x (distinct (map #(select-keys % [:x :y]) nodes)))]
    (reduce (fn [acc {:keys [x y]}]
              (let [diff (Math/abs (- (count acc) x))]
                (str acc (clojure.string/join (repeat (dec diff) " ")) "o")))
            ""
            nodes)))

(defn print-graph [graph]
  (let [base-y (:y (last graph))
        top-y (inc base-y)
        bottom-y (dec base-y)]
    (->> [top-y base-y bottom-y]
       (map #(select-nodes (fn [node] (= (:y node) %)) graph))
       (map str-nodes)
       (clojure.string/join "\n"))))