[Boost-commit] svn:boost r46810 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/algorithm/cursor boost/tree/detail/cursor libs/tree/test

From: ockham_at_[hidden]
Date: 2008-06-28 10:48:11

Author: bernhard.reiter
Date: 2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
New Revision: 46810
URL: http://svn.boost.org/trac/boost/changeset/46810

Log:
Add binary_search_tree_test.cpp
Added:
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                            |     1                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp                 |     2                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp |     6 ++                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp             |     9 ++-                                     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2                       |     1                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp        |     8 ---                                     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp             |    85 +++++++++++++++++++++++---------------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp     |     5 ++                                      
   8 files changed, 70 insertions(+), 47 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -14,6 +14,7 @@
 [section TODO]
 
 General:
+
 * Do we want/need an O(1) inorder_begin() for binary_tree? 
   Does Gnu's rb_tree (used in std::map) have one?
 * Is it really a good idea to use InCursor::size_type for size(Cursor)?

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -161,7 +161,7 @@
                 m_s.push(m_s.top().end());
         }
 
-	// DescendingCursor stuff
+	// This is what actually makes it an AscendingCursor
         void up()
         {
                 m_s.pop();

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -197,7 +197,11 @@
                 if (!s.empty())
                         copy(s, t);
                 ++t;
-	} while (s++ != r);
+		++s;
+	} while (s != r);
+
+	if (!r.empty())
+		copy(r, t);
 
         return t;
 }

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -88,7 +88,10 @@
     friend class iterator_core_access;
 
 //	bool empty_() const
-//	{ 
+//	{
+//		if (this->base().parity())
+//			return true;
+//		return this->base().empty();
 //	}
 
         void increment()
@@ -99,7 +102,7 @@
     
     void decrement()
     {
-    	if (!this->base_reference().parity())
+    	if (!this->base().parity())
                         this->base_reference().to_parent();
             --this->base_reference();
     }
@@ -117,7 +120,7 @@
         
         void up()
         {
-		if (!this->base_reference().parity())
+		if (!this->base().parity())
                         this->base_reference().to_parent();
         }
 };

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -20,6 +20,7 @@
 test-suite tree :
         [ run range_helpers_test.cpp ]
         [ run binary_tree_test.cpp ]
+	[ run binary_tree_search_test.cpp ]
 #	[ run key_search_binary_tree_test.cpp ]	
 #	[ run rank_search_binary_tree_test.cpp ]	
         [ run cursor_algorithm_test.cpp ]

Added: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -0,0 +1,63 @@
+//  Copyright (c) 2006-2008, Bernhard Reiter
+//
+//  Distributed under the Boost Software License, Version 1.0.
+//  (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+
+#include <boost/tree/binary_tree.hpp>
+
+#include <boost/tree/iterator.hpp>
+#include <boost/tree/algorithm.hpp>
+
+#include <boost/test/minimal.hpp>
+
+#include <list>
+#include <algorithm>
+#include <iterator>
+
+#include "helpers.hpp"
+#include "test_tree_traversal_data.hpp"
+
+using namespace boost::tree;
+
+int test_main(int, char* [])
+{
+	binary_tree<int> test_tree;
+	create_test_data_tree(test_tree);
+		
+	binary_tree<int>::cursor c = test_tree.root();
+
+	c = inorder::lower_bound(test_tree.root(), 4); // Leaf
+	BOOST_CHECK(*c == 4);
+
+	c = inorder::lower_bound(test_tree.root(), 7); // Leaf
+	BOOST_CHECK(*c == 7);
+	
+	c = inorder::lower_bound(test_tree.root(), 6); // Non-leaf
+	BOOST_CHECK(*c == 6);
+
+	c = inorder::lower_bound(test_tree.root(), 8); // root().begin()
+	BOOST_CHECK(*c == 8);
+
+	c = inorder::lower_bound(test_tree.root(), 5); // Not in tree
+	BOOST_CHECK(*c == 6);
+	
+	*c = 4;
+	
+	c = inorder::lower_bound(test_tree.root(), 5); // Not in tree
+	BOOST_CHECK(*c == 7);
+
+	c = inorder::lower_bound(test_tree.root(), 4); // Twice in tree
+	BOOST_CHECK(*c == 4);
+	BOOST_CHECK(*c.to_parent() == 4);
+	
+	//binary_tree<int>::cursor d = inorder::upper_bound(test_tree.root(), 4); // Twice in tree
+	//BOOST_CHECK(*d == 4);
+	
+	*c = 6;
+	
+	validate_test_data_tree(test_tree);
+	
+	return 0;
+}

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -4,12 +4,6 @@
 //  (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
 
-//TODO: Make this a test suite.
-//		Add iterator traversal tests - check if proper overloads (if present)
-//		are used.
-
-// TODO: get timings. that makes that no testcase anymore, right?
-//does boost have timers? what does the austern et al one look like?
 
 #include <boost/tree/binary_tree.hpp>
 
@@ -65,6 +59,6 @@
         test::preorder::algorithms (test_tree.root(), test_tree2.root());
         test::inorder::algorithms  (test_tree.root(), test_tree2.root());
         test::postorder::algorithms(test_tree.root(), test_tree2.root());
-			
+
         return 0;
 }

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -23,52 +23,20 @@
         tree_type mytree;
         
         tree_type::cursor c = mytree.root();
-	tree_type::base_cursor cur = tree_type::base_cursor(c);
-	BOOST_CHECK(!cur.parity());
-	cur = cur.parent();
-	BOOST_CHECK(cur.parity());
-	
         c = mytree.insert(c, 6);	
         BOOST_CHECK(*c == 6);
-	//cur = tree_type::base_cursor(c);
-	//BOOST_CHECK(*cur == 6);
-	
-//	BOOST_CHECK(cur == mytree.h.root().begin());
-	
+
         c = mytree.insert(c, 5);	
         BOOST_CHECK(*c == 5);
-	//cur = tree_type::base_cursor(c);
-//	BOOST_CHECK(cur == mytree.h.root().begin());
 
         c = mytree.insert(c, 4);	
         BOOST_CHECK(*c == 4);
         BOOST_CHECK(c == mytree.root().begin());
-	
-	cur = tree_type::base_cursor(c);
-//	BOOST_CHECK(cur == mytree.h.root().begin());
-
-//	++cur;
-//	cur = cur.begin();	
-//	BOOST_CHECK(*cur == 5);
-//	cur = cur.parent();
-//	--cur;
 
         ++c;
         BOOST_CHECK(*c == 5);
         ++c;
         BOOST_CHECK(*c == 6);
-//	--c;
-//	BOOST_CHECK(*c == 5);
-//	--c;
-//	BOOST_CHECK(*c == 4);
-	
-	
-//	cur = tree_type::base_cursor(c);
-//	BOOST_CHECK(*cur == 4);
-//	//cur = cur.parent().parent().parent().begin();
-//	BOOST_CHECK(*cur == 4);
-	
-	//BOOST_CHECK(*++c == 5);
         
         tree_type forest;
         //create_test_data_tree(forest);
@@ -105,8 +73,55 @@
         back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
         oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
         
-//	boost::tree::preorder::copy(ft.root(), oc_test_list);
-//	test::preorder::traversal(test_list.begin(), test_list.end());
+//  Preliminary checks, delete as soon as issues are resolved
+
+//	forest_tree_type::cursor s = ft.root();
+//	forest_tree_type::cursor r = s.end();
+//	*t.to_begin() = *s.to_begin();
+//		BOOST_CHECK(!s.empty());
+//		if (!s.empty()) {
+//			r = s.end();
+//			*t.to_begin() = *s.to_begin();
+//		}
+//		
+//		BOOST_CHECK(!s.empty());
+//		if (!s.empty()) {
+//			r = s.end();
+//			*t.to_begin() = *s.to_begin();
+//		}
+//	
+//	BOOST_CHECK(s.empty());
+//	++t;
+//	
+//	BOOST_CHECK(s != r);
+//	BOOST_CHECK(s++ != r);
+//	BOOST_CHECK(s == r);
+//	
+//	BOOST_CHECK(s.empty());
+//	++t;
+
+	//BOOST_CHECK(s++ == r);
+		
+//	do {
+//		if (!s.empty())
+//			*t = *s;
+//			//copy(s, t);
+//		++t;
+//	} while (s++ != r);
+	
+	
+	boost::tree::preorder::copy(ft.root(), oc_test_list);
+	//test::preorder::traversal(test_list.begin(), test_list.end());
+	
+	BOOST_CHECK(test_list.size() == 6);
+	
+	std::list<int>::const_iterator lci = test_list.begin();
+	BOOST_CHECK(*lci == 8);
+	BOOST_CHECK(*++lci == 3);
+	BOOST_CHECK(*++lci == 1);
+//	BOOST_CHECK(*++lci != 4); // wrong!
+//	BOOST_CHECK(*++lci != 13 ); // wrong!
+//	BOOST_CHECK(*++lci != 11); // wrong!
         
         test_list.clear();
         //boost::tree::postorder::copy(ft.root(), oc_test_list);

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp	2008-06-28 10:48:10 EDT (Sat, 28 Jun 2008)
@@ -58,11 +58,16 @@
         BOOST_CHECK(*c == 8);
         BOOST_CHECK(*c.to_begin() == 3);
         BOOST_CHECK(*c.to_begin() == 1);
+	BOOST_CHECK(c.empty());
+	BOOST_CHECK(++c == t.root().begin().begin().end());
+	--c;
         c.to_parent();
         BOOST_CHECK(*++c == 6);
         BOOST_CHECK(*c.to_begin() == 4);
         c.to_parent();
         BOOST_CHECK(*++c == 7);
+	BOOST_CHECK(++c == t.root().begin().end());
+	
         c = t.root().begin();
         BOOST_CHECK(*++c == 10);
         BOOST_CHECK(*++c == 14);