 
 (declare insert*)
 
-(defn- internal-node [ks vs size]
+(defn- internal-node [b ks vs size]
   {:pre [(= (count vs)
             (inc (count ks)))]}
-  {:type :internal
+  {:b b
+   :type :internal
    :ks ks
    :vs vs
    :size size})

          nks       (concat ks1 [k] ks2)
          nvs       (concat vs1 [v] vs2)]
      #_(println "IINS" nks nvs)
      (internal-node nks nvs nsize))
    (let [nvs (-> vs butlast (concat [v]))]
      #_(println "IINS (INF)" ks nvs)
      (internal-node ks nvs size))))

(defn- inode-insert [{:keys [ks vs] :as n} k v]
  (let [[childk childv] (inode-lookup n k)
        [n1 nk n2]      (insert* childv k v)
        nn              (if (nil? n2)
                          (inode-ins n childk n1)
                          (-> (inode-ins n nk n1)
                              (inode-ins childk n2)))]
    (if (>= (-> nn :ks count) 3)
      (inode-split nn)
      [nn])))


(defn- leaf-node
  ([ks vs size]
   {:pre [(= (count vs)
             (count ks))]}
   {:type :leaf
    :m (->> (interleave ks vs)
            (apply sorted-map))
    :size size})

  ([]
   (leaf-node nil nil 0))

  ([m size]
   {:type :leaf
    :m m
    :size size}))

(defn- lnode-lookup [{:keys [m] :as n} k]
  [nil (get m k)])

(defn- lnode-split [{:keys [m size] :as n}]
  (let [partition-size (-> size (/ 2) Math/ceil int)
        [ks1 ks2] (partition-all partition-size (keys m))
        m1 (apply dissoc m ks2)
        m2 (apply dissoc m ks1)]
    #_(println "LSPLIT" m1 m2)
    [(leaf-node m1 partition-size)
     (last ks1)
     (leaf-node m2 (- partition-size (rem size 2)))]))

(defn- lnode-ins [{:keys [m size] :as n} k v]
  (let [nm (assoc m k v)]
    #_(println "LINS" nm)
    (leaf-node nm (inc size))))

(defn- lnode-insert [{:keys [m] :as n} k v]
  (let [nn (lnode-ins n k v)]
    (if (>= (-> nn :m count) 3)
      (lnode-split nn)
      [nn])))


    (insert 1 11)
    #_(lookup 3))

#_(let [kvs (take 100000 (repeatedly #(let [k (-> (rand-int 9000000)
                                                (+ 1000000))]
                                      [k (str "v" k)])))
      t (time (reduce (fn [t [k v]]
                        (insert t k v))
                      (tree 100)
                      kvs))]
  [(first kvs)
   (time (lookup t (-> kvs first first)))])


(defrecord B+TreeNode [b size children leaf?]
