CODEWITHSUNDEEP
searchtreelispcommon-lisp
JNevens
JNevens

Reputation: 11982

Searching an item in a k-d tree

I am developing a k-d tree in Lisp. I am writing a function that allows me to search a node in the k-d tree. This function is defined as follows:

(defmethod find-node ((kdt kdtree) target &key (key #'value) (test #'equal))
  (unless (null (root kdt))
    (find-node (root kdt) target :key key :test test)))

(defmethod find-node ((node kdnode) target &key (key #'value) (test #'equal))
  (format t "Testing node ~a~%" (value node))
  (format t "Result is ~a~%" (funcall test (funcall key node) target))
  (if (funcall test (funcall key node) target)
      node
      (progn
        (unless (null (left node))
          (find-node (left node) target :key key :test test))
        (unless (null (right node))
          (find-node (right node) target :key key :test test)))))

I build up a tree with the following data: '((2 3) (5 4) (9 6) (4 7) (8 1) (7 2)). So now, I am using this function to find the node '(2 3).

(find-node kdt '(2 3))

With the format statements, I get this output:

Testing node (7 2)
Result is NIL
Testing node (5 4)
Result is NIL
Testing node (2 3)
Result is T
Testing node (4 7)
Result is NIL
Testing node (9 6)
Result is NIL
Testing node (8 1)
Result is NIL
NIL

So, as you can see, the node is found since the result of the test is T, however, the search continues and the result is NIL. Why doesn't this function return the node?

Upvotes: 0

Views: 96

Answers (3)

coredump
coredump

Reputation: 38799

You can simplify things a little, and stop searching once you find an item, by defining a method for nil nodes and using or: 

(defmethod find-node ((empty null) target &key &allow-other-keys)
  nil)

(defmethod find-node ((node kdnode) target &key (key #'value) (test #'equal))
  (if (funcall test (funcall key node) target)
      node
      (or (find-node (left node) target :key key :test test)
          (find-node (right node) target :key key :test test))))

You could combine this with Rainer Joswig's answer, of course. For example, you could define an :around method for kdnode:

(defvar *searching* nil)

(defmethod find-node :around ((x kdnode) target &key &allow-other-keys)
  (if *searching*
      (let ((result (call-next-method)))
        (when result
          (throw 'found result)))
      (let ((*searching* t))
        (catch 'found
          (call-next-method)))))

You could also place the catch block explicitly in the code. If you are sure you never initiate a search on a kdnode but always on kdtree instances, then you can put the catch around kdtree instead and get rid of the special variable *searching*.

Note that this example is only here to demonstrate methods. It makes the code a little bit "too clever"; I would probably implement the throw/catch behavior explicitly in practice.

Upvotes: 2

Rainer Joswig
Rainer Joswig

Reputation: 139261

You might want to directly return a result, when you find something.

Use the following example to improve your code:

(defun find-it (item list)
  (labels ((find-it-aux (item list)
             (when list
               (if (eql item (first list))
                   (return-from find-it (first list))
                 (find-it-aux item (rest list))))))
    (find-it-aux item list)))

CL-USER 89 > (find-it 1 '(2 3 1 5))
1

CL-USER 90 > (find-it 1 '(2 3 5))
NIL

or

(defun find-it (item list)
  (catch 'found-it
    (find-it-aux item list)))

(defun find-it-aux (item list)
  (when list
    (if (eql item (first list))
        (throw 'found-it (first list))
      (find-it-aux item (rest list)))))


CL-USER 91 > (find-it 1 '(2 3 1 5))
1

CL-USER 92 > (find-it 1 '(2 3 5))
NIL

Upvotes: 4

JNevens
JNevens

Reputation: 11982

The function keeps on testing nodes because it is recursive. If you descend left (find-node (left node) ...), than the search in the right branch is put on the stack (find-node (right node) ...). So, the nodes being tested are all because of the recursion. One way to solve this is to rewrite the function like this:

(defmethod find-node ((node kdnode) target &key (key #'value) (test #'equal))
  (let ((left (unless (null (left node))
                (find-node (left node) target :key key :test test)))
        (right (unless (null (right node))
                 (find-node (right node) target :key key :test test)))
        (this (funcall test (funcall key node) target)))
    (if this
        node
        (if left
            left
            right))))

Upvotes: 0

Related Questions