[funds-cvs] r32 - trunk/funds/src/trees

[abaine at common-lisp.net]

Author: abaine
Date: Wed Jun 20 14:47:38 2007
New Revision: 32

Modified:
   trunk/funds/src/trees/avl-tree.lisp
Log:
Added avl-find-value function.

Modified: trunk/funds/src/trees/avl-tree.lisp
==============================================================================
--- trunk/funds/src/trees/avl-tree.lisp	(original)
+++ trunk/funds/src/trees/avl-tree.lisp	Wed Jun 20 14:47:38 2007
@@ -43,7 +43,7 @@
 should be supplied as arguments."
   (let ((left (avl-insert (avl-left tree) key value :test test :order order))
 	(right (avl-right tree)))
-    (if (imbalanced left right)n
+    (if (imbalanced left right)
 	(if (left-heavy left)
 	    (right-rotate left tree right)
 	    (right-rotate (left-rotate (avl-left left)
@@ -103,6 +103,13 @@
 	      :left a
 	      :right new-c)))
 
+(defun avl-find-value (tree key &key (order #'<) (test #'eql))
+  (cond ((avl-empty-p tree) (values nil nil))
+	((funcall test key (avl-key tree)) (values (avl-value tree) t))
+	((funcall order key (avl-key tree)) 
+	 (avl-find-value (avl-left tree) key :order order :test test))
+	(t (avl-find-value (avl-right tree) key :order order :test test))))
+
 (defun imbalanced (left right)
   "Whether the heights of the given sub-trees differ,
 in their absolute values, by more than one."