I'd like some input on my implementation of
bst-range, which follows below.
Before we can get to bst-range, we first need some setup code to build the BST.
(You can imagine that node label
count didn't exist if you want, as it's not used for range search).
(defstruct (node (:print-function (lambda (n s d) (format s "#<~A ~A ~A ~A>" (node-elt n) (node-l n) (node-r n) (node-count n))))) elt count (l nil) (r nil)) (defun node-size (node) (if (null node) 0 (node-count node))) (defun bst-insert (obj bst <) (if (null bst) (make-node :elt obj :count 1) (let ((elt (node-elt bst))) (if (eql obj elt) bst (if (funcall < obj elt) (let ((new-l (bst-insert obj (node-l bst) <))) (make-node :elt elt :count (+ (node-size new-l) (node-size (node-r bst)) 1) :l new-l :r (node-r bst))) (let ((new-r (bst-insert obj (node-r bst) <))) (make-node :elt elt :count (+ (node-size (node-l bst)) (node-size new-r) 1) :l (node-l bst) :r new-r)))))))
The above code was the subject of my earlier question and is working fine. It's assumed here.
(defun bst-range (min max bst <) (if (null bst) nil (let ((elt (node-elt bst))) (when (funcall < min elt) (bst-range min max (node-l bst) <)) (when (and (or (eql min elt) (funcall < min elt)) (or (eql max elt) (funcall < elt max))) (setf *result* (cons elt *result*))) (when (funcall < elt max) (bst-range min max (node-r bst) <)))))
It runs like this
(defparameter *bst* nil) ;  (dolist (x '(1 6 3 7 21 40)) (setf *bst* (bst-insert x *bst* #'<))) > (defparameter *result* nil) ;  *RESULT* > (bst-range 5 10 *bst* #'<) ;  NIL > *result* ;  (7 6) > ;;  first build a BST ;;  use global var to store result of range search (seems ugly) ;;  call the range search ;;  see the result ;; Here we are searching for all the entries in the bst between ;; 5 and 10, which are, as we can see from what we inserted, just 6 & 7.
Is there a nice way to accumulate the result via an optional parameter? I tried (and failed) on that, which is why I ended up with defparameter. Not certain the accumulator is the right path for this function though. Is it? If not, why?
Would some datastructure for result other than a list be better here? If so, why?
Here's another idea for
bst-range, implemented via a higher order function.
(defun bst-traverse (fn bst) (when bst (bst-traverse fn (node-l bst)) (funcall fn (node-elt bst)) (bst-traverse fn (node-r bst)))) (defun bst-range (min max bst <) (bst-traverse (lambda (elt) (when (<= min elt max) (princ elt))) ;  bst)) ;;  We need to enqueue onto some ds here instead of princ. ;; Wondering how best to organise this code...