gistfile1.clj

; Translated from the ruby original by Heinz N. Gies, original by:
;
; The Computer Language Shootout Benchmarks
; http://shootout.alioth.debian.org
;
; contributed by Jesse Millikan

(ns net.licenser.bm.so.binary-trees
  (:use clojure.contrib.trace))

(defstruct btree :item :left :right)


(defn bottom-up-tree
  [item depth]
  (lazy-seq (if (> depth 0)
    (let
      [depth (dec depth)
       next_item (* 2 item)]
    (struct-map
      :item item
      :left (bottom-up-tree (dec next_item) depth)
      :right (bottom-up-tree next_item depth)))
    (struct-map
      :item item
      :left "end"
      :right "end"))))

(defn check-tree
  [tree]
  (if-not (or (= (:left tree) "end") (=(:right tree) "end"))
    (:item tree)
    (+ (:item tree) (- (check-tree (:left tree)) (check-tree (:right tree))))))
 
(defn bm
  []
  (trace ;do
    (println "so_binary_trees: ")
    (time (let
      [max-depth 12
       min-depth 4
       stretch-depth (+ max-depth 1)
       stretch-check (check-tree (bottom-up-tree 0 stretch-depth))
       long-lived-tree (bottom-up-tree 0 max-depth)
       check-list (map (fn [depth]
                         (let
                           [iterations (+ 1 (int (Math/pow 2 (- max-depth (+ depth min-depth)))))]
                           (reduce (fn [r i]
                                     (+ r
                                       (check-tree (bottom-up-tree i depth))
                                       0)) (range 0 (+ iterations 1)))))
                                       ;(check-tree (bottom-up-tree (* i -1) depth)))) (range 0 (+ iterations 1)))))
                    (range min-depth (+ max-depth 2) 2))
       ;check-count (reduce + check-list)
       long-lived-check (check-tree long-lived-tree)]
            (println check-list)))))