gistfile1.clj

(ns redblack-clj.core
  (:use matchure))

(defn- leaf [val] [:red nil val nil])

(def empty-tree nil)

(defn new-tree [val]
  [:black nil val nil])

(defn balance [tree]
  (if-match [(or [:black [:red [:red ?a ?x ?b] ?y ?c] ?z ?d]
		 [:black [:red ?a ?x [:red ?b ?y ?c]] ?z ?d]
		 [:black ?a ?x [:red [:red ?b ?y ?c] ?z ?d]] 
		 [:black ?a ?x [:red ?b ?y [:red ?c ?z ?d]]]) tree]
	    [:red [:black a x b] y [:black c z d]]
	    tree))

(defn- rec-insert [[color l val r] new-val]
  (balance
   (if (< new-val val)
     (if (= l nil)
       [color (leaf new-val) val r]
       [color (rec-insert l new-val) val r])
     (if (= r nil)
       [color l val (leaf new-val)]
       [color l val (rec-insert r new-val)]))))

(defn insert [root new-val]
  (if root
    (let [[_ l val r] (rec-insert root new-val)] [:black l val r])
    (new-tree new-val)))

(defn to-list [tree]
  (when-let [[color l val r] tree]
    (concat (to-list l) [val] (to-list r))))

(defn- depth [tree f]
  (if-let [[_ l _ r] tree]
    (inc (f (depth l f) (depth r f)))
    0))

(defn depths [tree]
     [(depth tree min) (depth tree max)])