   (-replace [this entry left right]
     (make-black-node entry left right)))
 
-(deftype SortedBlackNodeVal ^{:private true}
-  [-map-entry]
-
-  SortedNode
-  (-color [this] :black)
-  (-entry [this] -map-entry)
-  (-left [this] nil)
-  (-right [this] nil)
-  (-add-left [this node]
-    (-balance-left node this))
-  (-add-right [this node]
-    (-balance-right node this))
-  (-remove-left [this node]
-    (balance-left-del -map-entry node nil))
-  (-remove-right [this node]
-    (balance-right-del -map-entry nil node))
-  (-balance-left [this node]
-    (make-black-node (-entry node) this (-right node)))
-  (-balance-right [this node]
-    (make-black-node (-entry node) (-left node) this))
-  (-blacken [this] this)
-  (-redden [this]
-    (make-sorted-red-node-val -map-entry))
-  (-replace [this entry left right]
-    (make-black-node entry left right)))
-
 (deftype SortedBlackBranch ^{:private true}
   [-map-entry -left-node -right-node]
 

(defn- make-sorted-red-node [-map-entry]
  (SortedRedNode. -map-entry))

(defn- make-sorted-red-node-val [-map-entry]
  (SortedRedNodeVal. -map-entry))

(defn- make-sorted-red-branch [-map-entry -left -right]
  (SortedRedBranch. -map-entry -left -right))

(defn- make-sorted-red-branch-val [-map-entry -left -right]
  (SortedRedBranchVal. -map-entry -left -right))

(defn- make-sorted-black-node [-map-entry]
  (SortedBlackNode. -map-entry))

(defn- make-sorted-black-node-val [-map-entry]
  (SortedBlackNodeVal. -map-entry))

(defn- make-sorted-black-branch [-map-entry -left -right]
  (SortedBlackBranch. -map-entry -left -right))

(defn- make-sorted-black-branch-val [-map-entry -left -right]
  (SortedBlackBranchVal. -map-entry -left -right))

(defn- make-black-node [-map-entry left right]
  (let [v (val -map-entry)]
    (if (and (nil? left) (nil? right))
      (if (nil? v)
        (make-sorted-black-node -map-entry)
        (make-sorted-black-node-val -map-entry))
      (if (nil? v)
        (make-sorted-black-branch -map-entry left right)
        (make-sorted-black-branch-val -map-entry left right)))))

(defn- make-red-node [-map-entry left right]
  (let [v (val -map-entry)]
    (if (and (nil? left) (nil? right))
      (if (nil? v)
        (make-sorted-red-node -map-entry)
        (make-sorted-red-node-val -map-entry))
      (if (nil? v)
        (make-sorted-red-branch -map-entry left right)
        (make-sorted-red-branch-val -map-entry left right)))))

(defn- left-balance [-map-entry ins right]
  (cond


(defn- sorted-map-add [root compare-fn k v]
  (if (nil? root)
    [(make-sorted-red-node (make-map-entry k v)) false]
    (let [comparison (compare-fn k (key (-entry root)))]
      (if (zero? comparison)
        [root true]
