               (do
                 (set! ix (+ ix 1))
                 (recur)))
-            (if-let [parent (.-parent node)]
-              ;; jump into parent and start again
-              (do
-                (set! ix (+ (.-parent-ix node) 1))
-                (set! node parent)
-                (recur))
-              ;; end of tree
-              nil)))
+            (let [parent (.-parent node)]
+              (if (instance? Node parent)
+                ;; jump into parent and start again
+                (do
+                  (set! ix (+ (.-parent-ix node) 1))
+                  (set! node parent)
+                  (recur))
+                ;; end of tree
+                nil))))
         ;; head downwards and across until we reach the least greater key
         (loop []
           (if (< ix (alength (.-keys node)))
             (if (<= key (aget (.-keys node) ix))
               ;; check for a child
               (if-let [child (and (.-children node) (> ix 0) (aget (.-children node) (- ix 1)))]
-                ;; jump in child and start again (assumes child cannot be empty)
+                ;; jump into child and start again (child cannot be empty if tree is correctly balanced)
                 (do
                   (set! node child)
                   (set! ix 0)

(ns aurora.btree
  (:require-macros [aurora.macros :refer [apush]]))

(deftype Tree [min-children max-children root])

(deftype Node [parent parent-ix keys vals children])

(deftype Iterator [^:mutable node ^:mutable ix]
  Object
  (next [this]
        (if (< ix (alength (.-keys node)))
          (let [result #js [(aget (.-keys node) ix) (aget (.-vals node) ix)]]
            ;; check for a child
            (if-let [child (and (.-children node) (aget (.-children node) ix))]
              ;; jump into child
              (do
                (set! node child)
                (set! ix 0))
              ;; move along
              (set! ix (+ ix 1)))
            result)
          (if-let [parent (.-parent node)]
            ;; jump into parent and start again
            (do
              (set! ix (+ (.-parent-ix node) 1))
              (set! node parent)
              (recur))
            ;; end of tree
            nil)))
  (seek [this key] ;; move the iterator forwards until it reaches a key greater than this one
        ;; head across and upwards until we reach a greater key
        (loop []

          nil)))

(defn iterator [tree]
  (Iterator. (.-max-keys tree) (.-root tree) 0))

(defn tree [min-keys]
  (let [node (Node. nil nil #js [] #js [] nil)
        tree (Tree. (* 2 min-keys) node)]
    (set! (.-parent node) tree)
    (set! (.-parent-ix node) 0)
    tree))

(comment
  (let [tree (tree 1)]
    (seq tree))

  (let [tree (tree 1)]
    (.assoc! tree :a 0)
    (seq tree))

  (let [tree (tree 1)]
    (.assoc! tree :a 0)
    (.assoc! tree :b 1)
    (js/console.log tree)
    (seq tree))

  (let [tree (tree 1)]
    (.assoc! tree :a 0)
    (.assoc! tree :b 1)
    (.assoc! tree :c 1)
    (js/console.log tree)
    (seq tree))

  (let [tree (tree 1)]
    (.assoc! tree :a 0)
    (.assoc! tree :b 1)
    (.assoc! tree :c 1)
    (.assoc! tree :d 1)
    (.assoc! tree :e 1)
    (.assoc! tree :f 1)
    (.assoc! tree :g 1)
    (.assoc! tree :h 1)
    (.assoc! tree :i 1)
    (.assoc! tree :j 1)
    (js/console.log tree)
    (seq tree))

  (let [tree (Tree. max-keys (Node. nil nil #js [] #js [] #js[]))
        iterator (iterator tree)]
    (take-while identity (repeatedly #(.next iterator))))

  (let [tree (Tree. max-keys (Node. nil nil #js [:a :b :c] #js [0 1 2] #js[]))
        iterator (iterator tree)]
    (take-while identity (repeatedly #(.next iterator))))

  (let [branch (Node. nil nil #js [:a :d :e] #js [0 3 4] #js[])
        _ (apush (.-children branch) (Node. branch 0 #js [:b :c] #js [1 2]))
        tree (Tree. max-keys branch)
        iterator (iterator tree)]
    (take-while identity (repeatedly #(.next iterator))))

  (let [branch (Node. nil nil #js [:a :d :f] #js [0 3 4] #js[])
        _ (apush (.-children branch) (Node. branch 0 #js [:b :c] #js [1 2]))
        tree (Tree. max-keys branch)
        iterator (iterator tree)]
    [(.seek iterator :0) (.seek iterator :c) (.seek iterator :a) (.seek iterator :e) (.seek iterator :e) (.seek iterator :p)])

  )
