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

[abaine at common-lisp.net]

Author: abaine
Date: Sun Aug 19 17:22:39 2007
New Revision: 174

Added:
   trunk/funds/src/trees/utilities.lisp
Log:
Added tree-count and tree-count-if.

Added: trunk/funds/src/trees/utilities.lisp
==============================================================================
--- (empty file)
+++ trunk/funds/src/trees/utilities.lisp	Sun Aug 19 17:22:39 2007
@@ -0,0 +1,18 @@
+
+(in-package :funds)
+
+(defun tree-count (item tree &key (key #'bt-value) (test #'eql))
+  "The number of sub-trees in the tree that satisfy the test."
+  (tree-count #'(lambda (x)
+		  (funcall test x item))
+	      :key key))
+
+(defun tree-count-if (predicate tree &key (key #'bt-value))
+  "The number of sub-trees in the given tree that satisfy the test."
+  (if (tree-empty-p tree)
+      0
+      (+ (tree-count-if predicate (bt-left tree) :key key)
+	 (funcall predicate (funcall key tree))
+	 (tree-count-if predicate (bt-right tree) :key key))))
+
+