[rucksack-devel] PATCH: b-tree binary search

[Arthur Lemmens]

Cyrus Harmon wrote:

> +  (let ((btree-key< (btree-key< btree))
> +        (last (1- (btree-node-index-count node))))
> +    (labels ((binary-search (start end)
> +               (let* ((mid (+ start (truncate (- end start) 2)))
> +                      (mid-binding (node-binding node mid)))
> +                 (if (= start mid)
> +                     (if (not (funcall btree-key< (binding-key mid-binding) key))
> +                         (binding-value mid-binding)
> +                         (binding-value (node-binding node (1+ mid))))

I would be inclined to get rid of the IF NOT by reversing the order
of the branches:

             (if (funcall btree-key< (binding-key mid-binding) key)
                 (binding-value (node-binding node (1+ mid))
                 (binding-value mid-binding))

But that's no big deal.

> +                     (if (not (funcall btree-key< (binding-key mid-binding) key))
> +                         (binary-search start mid)
> +                         (binary-search mid end))))))

Same here.

> +      (if (funcall btree-key< (binding-key (node-binding node (1- last))) key)
> +          (binding-value (node-binding node last))
> +          (binary-search 0 (1- last)))))

I find the (1- LAST) a bit suspicious here, because LAST is already
(1- (BTREE-NODE-INDEX-COUNT NODE)).  So if a node has only one element,
this would fail, right?  (It's been a while, so I don't even remember
if it's possible that a node has only 1 element.  But I'd feel safer
if you wrote this part in such a way that it doesn't depend on a minimum
number of node elements.)

Thanks,

Arthur