[Boost-commit] svn:boost r39961 - in sandbox/SOC/2006/tree/trunk: boost/tree/algorithm libs/tree/test

From: ockham_at_[hidden]
Date: 2007-10-12 10:08:16

Author: bernhard.reiter
Date: 2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
New Revision: 39961
URL: http://svn.boost.org/trac/boost/changeset/39961

Log:
* Add *order::transform algorithms
* More test simplification (regarding *order redundancies)
Added:
   sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp   (contents, props changed)
Removed:
   sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp             |    24 +++++++++++++++++++++++                 
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp           |    27 ++++++++++++++++++++++++++              
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp            |    27 +++++++++++++++++++++++++               
   sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp                   |     5 +++                                     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp  |    41 ++++++++++++++++++++++++++++++++------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp |    18 ++++++++--------                        
   6 files changed, 123 insertions(+), 19 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp	2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
@@ -76,6 +76,30 @@
         return t;
 }
 
+/**
+ * @brief	 Performs an operation on a subtree, by traversing it in inorder.
+ * @param s  An input cursor.
+ * @param t  An output cursor.
+ * @param op A unary operation.
+ * @result	 A cursor past t's inorder end, after the transforming has 
+ * 			 finished.
+ * 
+ * By traversing the input subtree s in inorder, apply the operation op 
+ * to each element and write the result to the output subtree t.
+ * 
+ * op must not change its argument.
+ */
+template <class InCursor, class OutCursor, class Op>
+OutCursor transform (InCursor s, OutCursor t, Op op)
+{
+	if (!s.empty())
+		transform(s.begin(), t.begin(), op);
+	*t = op(*s);
+	if (!(++s).empty())
+		transform(s.begin(), (++t).begin(), op);
+	return t;
+}
+
 template <class MultiwayTree>
 iterator<typename MultiwayTree::cursor, forward_traversal_tag> 
 begin(MultiwayTree& t, forward_traversal_tag)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp	2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
@@ -82,6 +82,33 @@
         return outsubtree;
 }
 
+/**
+ * @brief	 Performs an operation on a subtree, by traversing it in postorder.
+ * @param s  An input cursor.
+ * @param t  An output cursor.
+ * @param op A unary operation.
+ * @result	 A cursor past t's postorder end, after the transforming has
+ * 			 finished.
+ * 
+ * By traversing the input subtree s in postorder, apply the operation op 
+ * to each element and write the result to the output subtree t.
+ * 
+ * op must not change its argument.
+ */
+template <class InCursor, class OutCursor, class Op>
+OutCursor transform (InCursor s, OutCursor t, Op op)
+{
+	InCursor insubtree = s;
+	OutCursor outsubtree = t;
+	if (!s.empty())
+		transform(s.begin(), t.begin(), op);
+	if (!(++s).empty()) {
+		transform(s.begin(), (++t).begin(), op);
+	}
+	*outsubtree = op(*insubtree);
+	return outsubtree;
+}
+
 ///Iterators
 
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp	2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
@@ -64,7 +64,8 @@
  * @param t An output cursor.
  * @result	A cursor past t's preorder end, after the copying operation.
  */
- // TODO: Should work with root() instead of root().begin() (same for in- and postorder)
+// TODO: Should work with root() instead of root().begin() (same for in- and postorder, )
+// plus a couple of other algorithms
 template <class InCursor, class OutCursor>
 OutCursor copy (InCursor s, OutCursor t)
 {
@@ -77,6 +78,30 @@
 }
 
 /**
+ * @brief	 Performs an operation on a subtree, by traversing it in preorder.
+ * @param s  An input cursor.
+ * @param t  An output cursor.
+ * @param op A unary operation.
+ * @result	 A cursor past t's preorder end, after the transforming has 
+ * 			 finished.
+ * 
+ * By traversing the input subtree s in preorder, apply the operation op 
+ * to each element and write the result to the output subtree t.
+ * 
+ * op must not change its argument.
+ */
+template <class InCursor, class OutCursor, class Op>
+OutCursor transform (InCursor s, OutCursor t, Op op)
+{
+	*t = op(*s);
+	if (!s.empty())
+		transform(s.begin(), t.begin(), op);
+	if (!(++s).empty())
+		transform(s.begin(), (++t).begin(), op);
+	return t;
+}
+
+/**
  * @brief	First element of a MultiwayTree in preorder traversal
  * @param t	A MultiwayTree
  * @return	Mutable preorder iterator to the first element of @a t

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp	2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
@@ -4,6 +4,9 @@
 //  (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
 
+#ifndef LIBS_TREE_TEST_HELPERS_HPP
+#define LIBS_TREE_TEST_HELPERS_HPP
+
 #include <boost/tree/binary_tree.hpp>
 #include <boost/tree/balanced_tree.hpp>
 #include <boost/tree/searcher.hpp>
@@ -88,4 +91,4 @@
         my_tree.push_back(7);
 }
 
-
+#endif // LIBS_TREE_TEST_HELPERS_HPP

Added: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp	2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
@@ -0,0 +1,57 @@
+//  Copyright (c) 2006, 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/algorithm.hpp>
+
+#include <list>
+#include <algorithm>
+#include <iterator>
+
+#include "helpers.hpp"
+#include "test_tree_traversal_data.hpp"
+
+using namespace boost::tree;
+
+namespace test {
+namespace ORDER {
+
+template <class Cursor, class OutCursor, class Container>
+void test_copy(Cursor c, OutCursor& o, Container& cont)
+{	
+	boost::tree::ORDER::copy(c.begin(), o);
+	test::ORDER::traversal(cont.begin(), cont.end());
+}
+
+template <class Cursor, class OutCursor, class Container>
+void test_transform(Cursor c, Cursor d, OutCursor& o, Container& cont)
+{
+	// First copy test_tree to test_tree2, by adding 1 to each element,
+	// then copy test_tree2 to test_list, by subtracting 1 - so 
+	// test_list should hold test_tree's original elements in ORDER.
+	boost::tree::ORDER::transform(c.begin(), d.begin(), 
+		std::bind2nd(std::plus<int>(),1));
+	boost::tree::ORDER::transform(d.begin(), o,
+		std::bind2nd(std::minus<int>(),1));
+	test::ORDER::traversal(cont.begin(), cont.end());
+}
+
+template <class Cursor>
+void algorithms(Cursor c, Cursor d)
+{
+	std::list<int> test_list;
+	typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
+	typedef output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
+	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);
+	
+	test_copy(c, oc_test_list, test_list);
+	
+	test_list.clear();
+	test_transform(c, d, oc_test_list, test_list);
+}
+
+}
+}

Deleted: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp	2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
+++ (empty file)
@@ -1,84 +0,0 @@
-//  Copyright (c) 2006, 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)
-
-//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>
-
-#include <boost/tree/iterator.hpp>
-#include <boost/tree/traversal.hpp>
-
-#include <boost/test/minimal.hpp>
-
-#include <list>
-#include <iterator>
-
-#include "helpers.hpp"
-#include "test_tree_traversal_data.hpp"
-
-using namespace boost::tree;
-
-
-int test_main(int, char* [])
-{
-	using boost::forward_traversal_tag;
-	
-	binary_tree<int> test_tree, test_tree2;
-	create_test_data_tree(test_tree);
-	create_test_data_tree(test_tree2);
-//	BOOST_CHECK(test_tree == test_tree2);
-	
-	binary_tree<int>::cursor c = test_tree.root();
-	binary_tree<int>::cursor d = test_tree2.root();
-
-	d = d.begin().end().begin().begin();
-	*d = 29;
-	
-	d = test_tree2.root();
-
-	// output_cursor_iterator_wrapper tests
-	
-	// preorder::copy tests
-	std::list<int> test_list;
-	typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
-	typedef output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
-	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);
-	preorder::copy(c.begin(), oc_test_list);
-	test_preorder_traversal(test_list.begin(), test_list.end());
-
-	// inorder::copy tests
-	test_list.clear();
-	it_test_list = std::back_inserter(test_list);
-	oc_test_list = oc_bi_lst_type(it_test_list);
-	inorder::copy(c.begin(), oc_test_list);
-	test_inorder_traversal(test_list.begin(), test_list.end());
-	
-	// postorder::copy tests
-	test_list.clear();
-	it_test_list = std::back_inserter(test_list);
-	oc_test_list = oc_bi_lst_type(it_test_list);
-	postorder::copy(c.begin(), oc_test_list);
-	test_postorder_traversal(test_list.begin(), test_list.end());
-		
-	// Using a list iterator
-	test_list.clear();
-	test_list.resize(11);
-	typedef output_cursor_iterator_wrapper<std::list<int>::iterator> oc_lst_type;
-	std::list<int>::iterator li = test_list.begin();
-	oc_lst_type oc_lst(li);
-	postorder::copy(c.begin(), oc_lst);
-	test_postorder_traversal(test_list.begin(), test_list.end());
-		
-	return 0;
-}
-
-

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	2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
@@ -4,6 +4,8 @@
 //  (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
 
+#ifndef LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
+#define LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
 
 #include <boost/test/minimal.hpp>
 
@@ -44,9 +46,13 @@
         BOOST_CHECK(*ret.root().end().end().begin().begin().end().begin() == 12);
 }
 
+namespace test {
+
+namespace preorder {
+
 template <class Iterator>
-void test_preorder_traversal(Iterator a, Iterator b)
-{	
+void traversal(Iterator a, Iterator b) 
+{
         BOOST_CHECK(*a++ == 8);
         BOOST_CHECK(*a++ == 3);
         BOOST_CHECK(*a++ == 1);
@@ -62,7 +68,7 @@
 }
 
 template <class Iterator>
-void test_reverse_preorder_traversal(Iterator a, Iterator b)
+void reverse_traversal(Iterator a, Iterator b)
 {	 
         BOOST_CHECK(*--a == 12);
         BOOST_CHECK(*--a == 11);
@@ -78,8 +84,12 @@
         BOOST_CHECK(a == b);
 }
 
+} // namespace preorder
+
+namespace inorder {
+
 template <class Iterator>
-void test_inorder_traversal(Iterator a, Iterator b)
+void traversal(Iterator a, Iterator b)
 {		
         BOOST_CHECK(*a++ == 1);
         BOOST_CHECK(*a++ == 3);
@@ -96,7 +106,7 @@
 }
 
 template <class Iterator>
-void test_reverse_inorder_traversal(Iterator a, Iterator b)
+void reverse_traversal(Iterator a, Iterator b)
 {	
         BOOST_CHECK(*--a == 14);
         BOOST_CHECK(*--a == 13);
@@ -112,8 +122,12 @@
         BOOST_CHECK(a == b);
 }
 
+} // namespace inorder
+
+namespace postorder {
+
 template <class Iterator>
-void test_postorder_traversal(Iterator a, Iterator b)
+void traversal(Iterator a, Iterator b)
 {	
         BOOST_CHECK(*a++ == 1);	
         BOOST_CHECK(*a++ == 4);
@@ -130,7 +144,7 @@
 }
 
 template <class Iterator>
-void test_reverse_postorder_traversal(Iterator a, Iterator b)
+void reverse_traversal(Iterator a, Iterator b)
 {	
         BOOST_CHECK(*--a == 8);	
         BOOST_CHECK(*--a == 10);
@@ -146,8 +160,12 @@
         BOOST_CHECK(a == b);
 }
 
+} // namespace postorder
+
+namespace ascending {
+
 template <class Iterator>
-void test_ascending_traversal_from_leaf4(Iterator a, Iterator b)
+void traversal_from_leaf4(Iterator a, Iterator b)
 {	
         BOOST_CHECK(*a == 4);
         BOOST_CHECK(*++a == 6);
@@ -155,3 +173,10 @@
         BOOST_CHECK(*++a == 8);
         BOOST_CHECK(++a == b);
 }
+
+} // namespace ascending
+
+} // namespace test
+
+
+#endif // LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp	2007-10-12 10:08:15 EDT (Fri, 12 Oct 2007)
@@ -33,25 +33,25 @@
         binary_tree<int> test_tree;
         create_test_data_tree(test_tree);
         
-	test_inorder_traversal(inorder::begin(test_tree), 
+	test::inorder::traversal(inorder::begin(test_tree), 
                                                    inorder::end(test_tree));
-	test_reverse_inorder_traversal(inorder::end(test_tree), 
+	test::inorder::reverse_traversal(inorder::end(test_tree), 
                                                                    inorder::begin(test_tree));
                 
-	test_preorder_traversal(preorder::begin(test_tree),
+	test::preorder::traversal(preorder::begin(test_tree),
                                                         preorder::end(test_tree));
 //FIXME
-//	test_reverse_preorder_traversal(preorder::end(test_tree),
+//	test::preorder::reverse_traversal(preorder::end(test_tree),
 //									preorder::begin(test_tree));
         
-	test_postorder_traversal(postorder::begin(test_tree), 
+	test::postorder::traversal(postorder::begin(test_tree), 
                                                          postorder::end(test_tree));
-	test_reverse_postorder_traversal(postorder::end(test_tree), 
+	test::postorder::reverse_traversal(postorder::end(test_tree), 
                                                                          postorder::begin(test_tree));
         
-	test_inorder_traversal(inorder::begin(test_tree, forward_traversal_tag()), 
+	test::inorder::traversal(inorder::begin(test_tree, forward_traversal_tag()), 
                                                    inorder::end(test_tree, forward_traversal_tag()));
-	test_reverse_inorder_traversal(inorder::end(test_tree, forward_traversal_tag()), 
+	test::inorder::reverse_traversal(inorder::end(test_tree, forward_traversal_tag()), 
                                                                    inorder::begin(test_tree, forward_traversal_tag()));
 
         binary_tree<int>::cursor c = test_tree.root();
@@ -60,7 +60,7 @@
         BOOST_CHECK(*c == 4);
 
         ascending::iterator<binary_tree<int>::cursor> ais(c);
-	test_ascending_traversal_from_leaf4(ais, ai_root);
+	test::ascending::traversal_from_leaf4(ais, ai_root);
 
         return 0;
 }