froydnj/trees — pull request #1 by rpav (2012-05-17 14:20:38+00:00)
Title: fix upper/lower-bound and change INSERT to return already-inserted key

Thanks for uploading TREES. I am working on integrating interval
trees, and I noticed a few things.

In cases where there is an existing key, TREES:INSERT returns the
value passed rather than the existing key. It seems it would be far
more useful to return the node key, since this may contain attached
data we wish to modify, and a flag as to whether the new key was
inserted is already returned. E.g.:

```lisp
(multiple-value-bind (key inserted)
(trees:insert new-item tree)
(unless inserted
(setf (attached-data key) new-value)))
```

Currently, the tree would have to be searched again if INSERTED is
false, since the existing key is returned.

The other issue is with FIND, UPPER-BOUND, and LOWER-BOUND. With
certain PRED combinations, these will fail when an item is the root
node:

```lisp
(defvar *t*)

(setf *t* (trees:make-binary-tree :red-black #'<=
:key #'identity
:test #'=))

(trees:insert 1 *t*)
(trees:find 1 *t*) ; => NIL, NIL
(trees:upper-bound 1 *t*) ; => 1, T

(setf *t* (trees:make-binary-tree :red-black #'>
:key #'identity
:test #'=))

(trees:insert 1 *t*)
(trees:find 1 *t*) ; => 1, T
(trees:upper-bound 1 *t*) ; => NIL, NIL
```

Additionally, regardless of the operand, they never both return
according to their documentation:

```lisp
(setf *t* (trees:make-binary-tree :red-black #'< :key #'identity
:test #'=))
(dolist (i '(1 2 3))
(trees:insert 1 *t*))

(trees:upper-bound 3) ; => NIL
```

The fix I have made here is to start with the root node as a candidate
in both cases, and use both TEST and PRED to ensure congruent results:

```lisp
;;; After changes, this returns the same for #'< or #'<=.
;;; If the test is reversed, i.e. #'> or #'>=, these are
;;; of course reversed.

(trees:lower-bound 0 *t*) ;; => NIL
(trees:lower-bound 1 *t*) ;; => 1
(trees:lower-bound 2 *t*) ;; => 2
(trees:lower-bound 3 *t*) ;; => 3
(trees:lower-bound 4 *t*) ;; => 3

(trees:upper-bound 0 *t*) ;; => 1
(trees:upper-bound 1 *t*) ;; => 1
(trees:upper-bound 2 *t*) ;; => 2
(trees:upper-bound 3 *t*) ;; => 3
(trees:upper-bound 4 *t*) ;; => NIL
```

All tests in the included suite pass.