         (pos? cmp) (recur arr l (dec m) k)
         :else m))
     l))
-
-(defn lookup ^number [^array arr key]
-  (binary-search arr 0 (dec (alength arr)) key))
-
-(defn -seek ^number [set key]
-  (loop [node (.-root set)
-         path  0
-         path-offset 0
-         depth 1]
-    (let [keys (.-keys node)
-          idx  (lookup keys key)]
-      (if (== depth (.-depth set))
-        (bit-or (bit-shift-left idx path-offset) path)
-        (let [idx (if (== idx (alength keys)) (dec idx) idx)]
-          (recur (aget (.-pointers node) idx)
-                 (bit-or (bit-shift-left idx path-offset) path)
-                 (+ path-offset path-bit-offset)
-                 (inc depth)))))))
-
-(defn seek [set key]
+    
+(defn ^number lookup-leaf [^array arr key]
+  (binary-search arr 0 (- (alength arr) 1) key))
+
+(defn ^number lookup-node [^array arr key]
+  (binary-search arr 0 (- (alength arr) 2) key))
+
+(defn ^number -seek [set key]
+  (loop [node  (.-root set)
+         path  empty-path
+         level (.-shift set)]
+    (if (== 0 level)
+      (path-set path level (lookup-leaf (.-keys node) key))
+      (let [idx (lookup-node (.-keys node) key)]
+        (recur (aget (.-pointers node) idx)
+               (path-set path level idx)
+               (- level level-shift))))))
+
+(defn ^number seek [set key]
   (binding [*cmp* (.-comparator set)]
     (-seek set key)))
 
 ;; Array operations
 
-(defn cut-n-splice ^array [^array  arr
+(defn ^array cut-n-splice [^array  arr
                            ^number cut-from
                            ^number cut-to
                            ^number splice-from


(deftype Node [keys pointers]
  Object
  (get_key [_ path]
    (let [path-idx (bit-and path path-mask)
          path-next (unsigned-bit-shift-right path path-bit-offset)]
      (.get_key (aget pointers path-idx) path-next)))
  
  (next_path [_ path]
    (let [path-idx      (bit-and path path-mask)
          path-next     (unsigned-bit-shift-right path path-bit-offset)
          path-next-new (.next_path (aget pointers path-idx) path-next)]
      (if (== -1 path-next-new)
        (if (< (inc path-idx) (alength pointers))
          (inc path-idx)  ;; keeping subpathes filled with 0
          -1)
        (bit-or path-idx 
                (bit-shift-left path-next-new path-bit-offset)))))
  
  (append [_ path key]
    (let [path-idx  (bit-and path path-mask)
          path-next (unsigned-bit-shift-right path path-bit-offset)
          nodes     (.append (aget pointers path-idx) path-next key)
          new-keys     (replace-keys keys     path-idx                (.map nodes lim-key))
          new-pointers (splice       pointers path-idx (inc path-idx) nodes)]
      (if (<= (alength new-pointers) max-len)
        ;; ok as is
        #js [(Node. new-keys new-pointers)]

        ;; ok as is
        #js [(LeafNode. (splice keys idx idx #js [key]))]))))

(defn ^array keys-for [set ^number path]
  (loop [level (.-shift set)
         node  (.-root set)]
    (if (pos? level)
      (recur (- level level-shift) (aget (.-pointers node) (path-get path level)))
      (.-keys node))))

(defn key-for [set ^number path]
  (let [keys (keys-for set path)
        idx  (path-get path 0)]
    (when (< idx (alength keys)) 
      (aget keys idx))))

(defn btset-conj [set key]
  (binding [*cmp* (.-comparator set)]
    (let [roots (.append (.-root set) (-seek set key) (.-shift set) key)]
      (if (== (alength roots) 1)
        ;; keeping single root
        (BTSet. (aget roots 0) (.-shift set) *cmp*)
        ;; introducing new root
        (BTSet. (Node. (.map roots lim-key) roots) (+ (.-shift set) level-shift) *cmp*)))))

;; iteration

(defn ^number -next-path [node
                          ^number path
                          ^number level]
  (let [idx (path-get path level)]
    (if (pos? level)
      ;; inner node
      (let [sub-path (-next-path (aget (.-pointers node) idx) path (- level level-shift))]
        (if (== -1 sub-path)
          ;; nested node overflow
          (if (< (inc idx) (alength (.-pointers node)))
            ;; advance current node idx, reset subsequent indexes
            (path-set empty-path level (inc idx))
            ;; current node overflow
            -1)
          ;; keep current idx
          (path-set sub-path level idx)))
      ;; leaf
      (if (< (inc idx) (alength (.-keys node)))
        ;; advance leaf idx
        (path-set empty-path 0 (inc idx))
        ;; leaf overflow
        -1))))

(defn next-path [set path]
  (-next-path (.-root set) path (.-shift set)))


(deftype BTSetIter [^BTSet  set
                    ^number path
                    ^array  keys
                    ^number idx]
  ISeqable
  (-seq [this]
    (when keys this))
  
  ISeq
  (-first [_]
    (when keys (aget keys idx)))
  
  (-rest [_]
    (if (< (inc idx) (alength keys))
      ;; can use cached array to move forward
      (BTSetIter. set (inc path) keys (inc idx))
      (let [path (next-path set path)]
        (if (== -1 path)
          (BTSetIter. set -1 nil -1)
          (BTSetIter. set path (keys-for set path) (path-get path 0))))))
  
  INext
  (-next [_]
    (if (< (inc idx) (alength keys))
      ;; can use cached array to move forward
      (BTSetIter. set (inc path) keys (inc idx))
      (let [path (next-path set path)]
        (when (not= -1 path)
          (BTSetIter. set path (keys-for set path) (path-get path 0)))))))

(defn btset-iter [set]
  (when (pos? (alength (.-keys (.-root set))))
    (BTSetIter. set empty-path (keys-for set empty-path) 0)))

;; public interface

(deftype BTSet [root shift comparator]
  Object
  (toString [this]
    (pr-str* this))
  
  ICollection
  (-conj [set key] (btset-conj set key))
