Boost logo

Boost-Commit :

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;
 }


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk