
New patches:

[When searching for an item in a bst, make sure that the node isn't a placeholder and actually has an element
Nathan Bird <nathan@acceleration.net>**20090306165250] {
hunk ./dev/trees.lisp 666
-       ((null node))
+       ((or (null node)
+	    (null (element node))))
}

[Adding several more tests on the trees
Nathan Bird <nathan@acceleration.net>**20090307191014] {
hunk ./tests/trees.lisp 9
-      '((binary-search-tree) 
+      '((binary-search-tree)
hunk ./tests/trees.lisp 18
+(addtest (test-trees)
+  searching-and-deleting-keyed
+  (ensure-cases (class)
+      '((binary-search-tree)
+	(red-black-tree))
+    (let ((b (make-container class
+			     :key #'first
+			     :test #'equal)))
+      (insert-list b '((2) (3) (10) (1) (4)))
+      (ensure-same (size b) 5)
+      (ensure-same (first (first-item b)) 1)
+      (ensure-same (search-for-node b 1 :key #'first) (containers::first-node b))
+      (delete-item b '(2))
+      (ensure-same (size b) 4)
+      (insert-item b '(7))
+      (insert-item b '(-2))
+      (insert-item b '(12))
+      (ensure-same (size b) 7)
+      (empty! b)
+      (ensure-same (size b) 0)
+      )))
+
+(addtest (test-trees)
+  find-on-nonexistant-item
+  (ensure-cases (class)
+      '((binary-search-tree)
+	(red-black-tree))
+    (let ((c (make-instance class)))
+      (ensure-null (item-at c 1))
+      (ensure-null (find-element c 1))
+      (ensure-null (find-item c 1))
+      (ensure-null (find-node c 1))
+      )))
+
+(addtest (test-trees)
+  find-on-nonexistant-item-nonempty
+
+  (ensure-cases (class)
+      '((binary-search-tree)
+	(red-black-tree))
+    (let ((c (make-instance class)))
+      (insert-list c '(64 83 68 84 97))
+      (ensure-null (item-at c 1))
+      (ensure-null (find-element c 1))
+      (ensure-null (find-item c 1))
+      (ensure-null (find-node c 1))
+      )))
+
+(addtest (test-trees)
+  randomized-testing
+  (ensure-cases (class)
+      '((binary-search-tree)
+	(red-black-tree))
+    (let* ((count 20)
+	   (randlist (loop repeat count
+			   collect (random 100)))
+	   (c (make-container class )))
+      (loop for n in randlist
+	    do (insert-item c n))
+      (ensure-same (size c) count)
+      (ensure-same (first-element c) (apply #'min randlist))
+      (ensure-same (last-element c) (apply #'max randlist))
+      (loop for n in randlist
+	    do (ensure (item-at c n))
+	    do (ensure (find-item c n)))
+      (ensure-same (collect-elements c)
+		   (sort (copy-list randlist) #'<)
+		   :test #'equal)
+
+
+      ;;now remove half the elements and make sure it still makes sense.
+      (loop repeat (/ count 2)
+	    for n = (pop randlist)
+	    do (ensure (typep (delete-element c n)
+			      'containers::bst-node)))
+
+      (ensure-same (size c) (length randlist))
+      (ensure-same (first-element c) (apply #'min randlist))
+      (ensure-same (last-element c) (apply #'max randlist))
+      (loop for n in randlist
+	    do (ensure (item-at c n))
+	    do (ensure (find-item c n)))
+      (ensure-same (collect-elements c)
+		   (sort (copy-list randlist) #'<)
+		   :test #'equal)
+
+      ;;remove the rest
+      (ensure-null (empty! c))
+      (ensure (empty-p c))
+      (ensure-same (size c) 0)
+      (ensure-null (collect-elements c)))))
+
hunk ./tests/trees.lisp 123
-(delete-element c 1) 
+(delete-element c 1)
}

[Getting rid of miscellaneous tests that were commented out.
Nathan Bird <nathan@acceleration.net>**20090307191034
 
 The one chunk of code in here (not active) got fixed up and moved to the other trees test file.
] {
hunk ./tests/misc.lisp 1
-(in-package #:cl-containers-test)
-
-(deftestsuite test-binary-search-tree (cl-containers-test) 
-  (b))
-
-(deftestsuite test-bst-simple (test-binary-search-tree)
-  ()
-  :setup (progn
-	   (setf b (make-container 'binary-search-tree
-				   :key #'first
-				   :test #'equal))
-	     (insert-list b '((2) (3) (10) (1) (4)))))
-
-#+(or)
-(addtest (test-binary-search-tree)
-  (setf b (make-container 'binary-search-tree
-                          :key #'first
-                          :test #'equal))
-  (insert-list b '((2) (3) (10) (1) (4)))
-  (ensure-same (size b) 5)
-  (ensure-same (first (element (first-item b))) 1)
-  (ensure-same (search-for-node b 1 :key #'first) (first-item b))
-  (delete-item b '(2))
-  (ensure-same (size b) 4)
-  (insert-item b '(7))
-  (insert-item b '(-2))
-  (insert-item b '(12))
-  (ensure-same (size b) 7)
-  (empty! b)
-  (ensure-same (size b) 0))
rmfile ./tests/misc.lisp
}

[Use node-empty-p function to test for empty node instead of looking at the element directly
Nathan Bird <nathan@acceleration.net>**20090307191211] {
hunk ./dev/trees.lisp 667
-	    (null (element node))))
+	    (node-empty-p node)))
}

Context:

[TAG version-0.11.3
Gary King <gwking@metabang.com>**20090206172358] 
Patch bundle hash:
317ee7a21fc70fd43a046fdb17a106d410c59dde
