Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r56987 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-10-18 16:05:27


Author: bernhard.reiter
Date: 2009-10-18 16:05:26 EDT (Sun, 18 Oct 2009)
New Revision: 56987
URL: http://svn.boost.org/trac/boost/changeset/56987

Log:
Fix the equal algorithms, plus add concept checks (also to size()), and add tests for all of them.
Added:
   sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp
      - copied, changed from r56984, /sandbox/SOC/2006/tree/trunk/libs/tree/test/for_each_test.cpp
Text files modified:
   sandbox/SOC/2006/tree/trunk/TODO | 2
   sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp | 39 +++++-
   sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 1
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 24 ++-
   sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp | 232 +--------------------------------------
   sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp | 1
   6 files changed, 53 insertions(+), 246 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-10-18 16:05:26 EDT (Sun, 18 Oct 2009)
@@ -14,7 +14,7 @@
 [section TODO]
 
 General:
-* Add a test for the equal() algorithm
+* Fix binary_tree_test (rotate)
 * Apply all binary_tree_test cchecks also to fake_binary_tree in order to check if semantics
   are mapped properly.
 * Subforest algorithms: with a first and last parameter (which, for binary tree based

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp 2009-10-18 16:05:26 EDT (Sun, 18 Oct 2009)
@@ -15,6 +15,7 @@
 #include <boost/tree/cursor_concepts.hpp>
 
 #include <boost/concept/requires.hpp>
+#include <boost/concept_check.hpp>
 
 namespace boost {
 namespace tree {
@@ -72,14 +73,20 @@
  */
 //[ equal
 template <class InCursor1, class InCursor2>
-bool equal(InCursor1 c1, InCursor2 c2)
+BOOST_CONCEPT_REQUIRES(
+ ((DescendingCursor<InCursor1>))
+ ((DescendingCursor<InCursor2>)),
+ (bool)) // return type
+equal(InCursor1 c1, InCursor2 c2)
 //]
 {
+ if (!(*c1 == *c2))
+ return false;
+
     InCursor1 d1 = c1.end();
     c1.to_begin();
     c2.to_begin();
- if (!(*c1 == *c2))
- return false;
+
     do {
         if (!c1.is_leaf())
             if (!equal(c1, c2))
@@ -103,14 +110,24 @@
  */
 //[ equal_pred
 template <class InCursor1, class InCursor2, class BinPred>
-bool equal(InCursor1 c1, InCursor2 c2, BinPred p)
+//FIXME
+//BOOST_CONCEPT_REQUIRES(
+// ((DescendingCursor<InCursor1>))
+// ((DescendingCursor<InCursor2>))
+// ((BinaryPredicate<BinPred, typename cursor_value<InCursor1>::type
+// , typename cursor_value<InCursor2>::type>)),
+// (bool)) // return type
+bool
+equal(InCursor1 c1, InCursor2 c2, BinPred p)
 //]
 {
+ if (!p(*c1,*c2))
+ return false;
+
     InCursor1 d1 = c1.end();
     c1.to_begin();
     c2.to_begin();
- if (!p(*c1,*c2))
- return false;
+
     do {
         if (!c1.is_leaf())
             if (!equal(c1, c2))
@@ -129,7 +146,10 @@
  * After finishing, s will have been increased by the number of elements in c.
  */
 template <class InCursor>
-void size(InCursor c, typename InCursor::subtree_size_type& s)
+BOOST_CONCEPT_REQUIRES(
+ ((DescendingCursor<InCursor>)),
+ (void)) // return type
+size(InCursor c, typename InCursor::subtree_size_type& s)
 {
     InCursor d = c.end();
     c.to_begin();
@@ -147,7 +167,10 @@
  */
 //[ size
 template <class InCursor>
-typename InCursor::subtree_size_type size(InCursor c)
+BOOST_CONCEPT_REQUIRES(
+ ((DescendingCursor<InCursor>)),
+ (typename InCursor::subtree_size_type)) // return type
+size(InCursor c)
 //]
 {
     typename InCursor::subtree_size_type s = 0;

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 2009-10-18 16:05:26 EDT (Sun, 18 Oct 2009)
@@ -23,6 +23,7 @@
         
 test-suite tree :
 # Algorithms
+ [ run equal_test.cpp ]
         [ run to_first_test.cpp ]
         [ run to_last_test.cpp ]
         [ run successor_test.cpp ]

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp 2009-10-18 16:05:26 EDT (Sun, 18 Oct 2009)
@@ -375,7 +375,7 @@
     bt0.splice(bt0.root().end(), bt, bt.root().end());
     BOOST_CHECK(bt.root().end().is_leaf());
 
- BOOST_CHECK_EQUAL(*bt.root().begin(), 8);
+ BOOST_CHECK_EQUAL(*bt.root(), 8);
     validate_test_dataset1_tree(bt0.root());
 }
 
@@ -391,20 +391,23 @@
 BOOST_AUTO_TEST_CASE( rotate_binary_tree_test )
 {
     binary_tree<int>::cursor c = bt.root().begin().end();
- BOOST_CHECK_EQUAL(*c.begin(), 6);
+ BOOST_CHECK_EQUAL(*c, 6);
 
- BOOST_CHECK_EQUAL(*c.parent(), 8);
- BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant candidate
+ BOOST_CHECK_EQUAL(*c.parent().parent(), 8);
+ BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 3); // invariant candidate
     
- BOOST_CHECK_EQUAL(*--c, 3); // differently (not invariantly!) spoken
- BOOST_CHECK_EQUAL(*c.begin(), 1);
- BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
- BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
+ BOOST_CHECK_EQUAL(*c.parent(), 3); // differently (not invariantly!) spoken
+ BOOST_CHECK_EQUAL(*--c, 1);
+ BOOST_CHECK_EQUAL(*(++c).begin(), 4);
+ BOOST_CHECK_EQUAL(*++c, 7);
 
     BOOST_CHECK_EQUAL(index(c), 1);
- BOOST_CHECK_EQUAL(*c.begin(), 6);
-
+ BOOST_CHECK_EQUAL(*c, 6);
+
+ c.to_begin();
+
     bt.rotate(c); // Left rotate
+
     c.to_parent().to_parent();
 
     BOOST_CHECK_EQUAL(*c.begin(), 6);
@@ -446,7 +449,6 @@
 // BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
 // BOOST_CHECK_EQUAL(*c.parent().parent().parent().begin(), 8);
 // BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
-
 }
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

Copied: sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp (from r56984, /sandbox/SOC/2006/tree/trunk/libs/tree/test/for_each_test.cpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/libs/tree/test/for_each_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp 2009-10-18 16:05:26 EDT (Sun, 18 Oct 2009)
@@ -23,239 +23,19 @@
 
 BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
 
-template <class Iter>
-class mock_unary_functor {
-private:
- Iter& m_iter, m_end;
-
-public:
- mock_unary_functor(Iter& iter, Iter& end)
- : m_iter(iter), m_end(end) {}
-
- mock_unary_functor(mock_unary_functor<Iter> const& other)
- : m_iter(other.m_iter), m_end(other.m_end) {}
-
- void operator()(typename Iter::value_type::value_type const& val)
- {
- BOOST_CHECK(m_iter != m_end);
- if (m_iter == m_end)
- return;
- BOOST_CHECK_EQUAL(val, m_iter->val);
- ++m_iter;
- }
-};
-
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_for_each_descending, Order, orders)
-{
- test_data_set mpo;
- mock_cursor_data(mpo);
-
- typedef typename test_data_set::index<Order>::type container_type;
- const container_type& order_index = mpo.get<Order>();
-
- typename container_type::const_iterator ci = order_index.begin();
- typename container_type::const_iterator cie = order_index.end();
-
- mock_unary_functor<typename container_type::const_iterator> muc(ci, cie);
- boost::tree::for_each(
- Order(),
- fbt1.descending_root(),
- muc
- );
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_for_each_ascending, Order, orders)
-{
- test_data_set mpo;
- mock_cursor_data(mpo);
-
- typedef typename test_data_set::index<Order>::type container_type;
- const container_type& order_index = mpo.get<Order>();
-
- typename container_type::const_iterator ci = order_index.begin();
- typename container_type::const_iterator cie = order_index.end();
-
- fake_binary_tree<int, boost::tree::ascending_vertical_traversal_tag> fabt1(fbt1);
-
- mock_unary_functor<typename container_type::const_iterator> muc(ci, cie);
- boost::tree::for_each(
- Order(),
- fabt1.root(),
- muc
- );
-}
-
-BOOST_AUTO_TEST_CASE( test_subforest_for_each_descending_preorder)
-{
- test_data_set mpo;
- mock_cursor_data(mpo);
-
- typedef test_data_set::index<preorder>::type container_type;
- const container_type& order_index = mpo.get<preorder>();
-
- container_type::const_iterator ci = order_index.begin();
- container_type::const_iterator cie = order_index.end();
- ++ci; // 3
- cie = ci;
- ++++++++cie; // 7
-
- boost::tree::forest<int, fake_binary_tree<int> > ft0(fbt1);
-
- mock_unary_functor<container_type::const_iterator> muc(ci, cie);
- //FIXME:
-// boost::tree::for_each(
-// preorder(),
-// ft0.begin().begin(),
-// ft0.begin().end(),
-// muc
-// );
-}
-
-BOOST_AUTO_TEST_CASE( test_subforest_for_each_ascending_preorder)
-{
- test_data_set mpo;
- mock_cursor_data(mpo);
-
- typedef test_data_set::index<preorder>::type container_type;
- const container_type& order_index = mpo.get<preorder>();
-
- container_type::const_iterator ci = order_index.begin();
- container_type::const_iterator cie = order_index.end();
- ++ci; // 3
- cie = ci;
- ++++++++cie; // 7
-
- fake_binary_tree<int, ascending_vertical_traversal_tag> fabt1(fbt1);
- boost::tree::forest<int, fake_binary_tree<int, ascending_vertical_traversal_tag> > ft0(fabt1);
-
- mock_unary_functor<container_type::const_iterator> muc(ci, cie);
-
- fake_binary_cursor<int, ascending_vertical_traversal_tag> dfc(ft0.begin().begin().begin().base()); //(fabt1.root().begin().begin());
- fake_binary_cursor<int, ascending_vertical_traversal_tag> dfce(ft0.begin().end().base());
- --dfce;
-
- //FIXME
- //BOOST_CHECK_EQUAL(*dfce, 7);
-
- //fake_ascending_binary_cursor<int> dfc2(ft0.begin().begin().begin().base());
- //fake_ascending_binary_cursor<int> dfc2e(dfc2); //ft0.begin().end().base()
- //to_forest_end(dfc2e);
-
-// boost::tree::forest<int, fake_binary_tree<int, ascending_vertical_traversal_tag> >::cursor fc1(ft0.begin().begin());
-// boost::tree::forest<int, fake_binary_tree<int, ascending_vertical_traversal_tag> >::cursor fc2(fc1);
-//
-// fc1.to_begin().to_begin();
-// fc2.to_begin().to_end();
-
-// make this a test of its own: just a binary cursor subrange.
-// for a proper end parameter, we'll have to use a root tracker.
-// boost::tree::for_each(
-// preorder(),
-// dfc, //ft0.begin().begin().begin(), //boost::tree::detail::forest_cursor< fake_ascending_binary_cursor<int> >(fabt1.root().begin().begin()), //Shouldn't that just be one begin()?
-// dfce, //ft0.begin().end(), //boost::tree::detail::forest_cursor< fake_ascending_binary_cursor<int> >(fabt1.root().begin().end().end().begin()),
-// muc
-// //, boost::tree::ascending_vertical_traversal_tag()
-// );
-
- //boost::tree::detail::forest_cursor< fake_ascending_binary_cursor<int> > dfc0(ft0.begin().begin().end());
-
- // Also try ft0.begin and ft0.end consistency!
-
-}
-
-BOOST_AUTO_TEST_CASE( test_two_cursor_for_each_descending_preorder)
+BOOST_AUTO_TEST_CASE( test_equal )
 {
- test_data_set mpo;
- mock_cursor_data(mpo);
-
- typedef test_data_set::index<preorder>::type container_type;
- const container_type& order_index = mpo.get<preorder>();
-
- container_type::const_iterator ci = order_index.begin();
- container_type::const_iterator cie = order_index.end();
-
- fake_binary_tree<int, descending_vertical_traversal_tag> fabt1(fbt1);
- boost::tree::forest<int, fake_binary_tree<int, descending_vertical_traversal_tag> > ft0(fabt1);
-
- mock_unary_functor<container_type::const_iterator> muc(ci, cie);
-
- fake_binary_cursor<int, descending_vertical_traversal_tag> dfc = fbt1.root();
- fake_binary_cursor<int, descending_vertical_traversal_tag> dfce(dfc);
- to_forest_end(dfce);
-
- boost::tree::detail::for_each(
- preorder(),
- dfc,
- dfce,
- muc,
- boost::tree::descending_vertical_traversal_tag()
- );
+ BOOST_CHECK(equal(fbt1.root(), fbt1.root()));
 }
 
-BOOST_AUTO_TEST_CASE( test_forest_for_each_descending_preorder)
+BOOST_AUTO_TEST_CASE( test_equal_pred )
 {
- test_data_set mpo;
- mock_cursor_data(mpo);
-
- typedef test_data_set::index<preorder>::type container_type;
- const container_type& order_index = mpo.get<preorder>();
-
- container_type::const_iterator ci = order_index.begin();
- container_type::const_iterator cie = order_index.end();
-
- //fake_binary_tree<int, descending_vertical_traversal_tag> fabt1(fbt1);
- boost::tree::forest<int, fake_binary_tree<int, descending_vertical_traversal_tag> > ft0(fbt1);
-
- mock_unary_functor<container_type::const_iterator> muc(ci, cie);
-
- boost::tree::for_each(
- preorder(),
- ft0.begin(),
- ft0.end(),
- muc
- );
+ BOOST_CHECK(boost::tree::equal(fbt1.root(), fbt1.root(), std::equal_to<int>()));
 }
 
-BOOST_AUTO_TEST_CASE( test_forest_for_each_ascending_preorder)
+BOOST_AUTO_TEST_CASE( test_size )
 {
- test_data_set mpo;
- mock_cursor_data(mpo);
-
- typedef test_data_set::index<preorder>::type container_type;
- const container_type& order_index = mpo.get<preorder>();
-
- container_type::const_iterator ci = order_index.begin();
- container_type::const_iterator cie = order_index.end();
-
- fake_binary_tree<int, ascending_vertical_traversal_tag> fabt1(fbt1);
- boost::tree::forest<int, fake_binary_tree<int, ascending_vertical_traversal_tag> > ft0(fabt1);
-
- mock_unary_functor<container_type::const_iterator> muc(ci, cie);
-
- fake_binary_cursor<int, ascending_vertical_traversal_tag> dfc(ft0.begin().base()); //(fabt1.root().begin().begin());
- fake_binary_cursor<int, ascending_vertical_traversal_tag> dfce(ft0.end().base());
-
- //fake_ascending_binary_cursor<int> dfc2(ft0.begin().begin().begin().base());
- //fake_ascending_binary_cursor<int> dfc2e(dfc2); //ft0.begin().end().base()
- //to_forest_end(dfc2e);
-
-// boost::tree::forest<int, fake_binary_tree<int, ascending_vertical_traversal_tag> >::cursor fc1(ft0.begin().begin());
-// boost::tree::forest<int, fake_binary_tree<int, ascending_vertical_traversal_tag> >::cursor fc2(fc1);
-//
-// fc1.to_begin().to_begin();
-// fc2.to_begin().to_end();
-
-// make this a test of its own: just a binary cursor subrange.
-// for a proper end parameter, we'll have to use a root tracker.
-// boost::tree::for_each(
-// preorder(),
-// dfc, //ft0.begin().begin().begin(), //boost::tree::detail::forest_cursor< fake_ascending_binary_cursor<int> >(fabt1.root().begin().begin()), //Shouldn't that just be one begin()?
-// dfce, //ft0.begin().end(), //boost::tree::detail::forest_cursor< fake_ascending_binary_cursor<int> >(fabt1.root().begin().end().end().begin()),
-// muc
-// //, boost::tree::ascending_vertical_traversal_tag()
-// );
-
- //boost::tree::detail::forest_cursor< fake_ascending_binary_cursor<int> > dfc0(ft0.begin().begin().end());
+ BOOST_CHECK_EQUAL(size(fbt1.root()), 11);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp 2009-10-18 16:05:26 EDT (Sun, 18 Oct 2009)
@@ -206,6 +206,7 @@
     typedef fake_binary_cursor<T/* const*/, descending_vertical_traversal_tag> const_cursor;
 
     typedef typename fake_binary_cursor<T, descending_vertical_traversal_tag>::cursor_facade_::size_type size_type;
+ typedef size_type subtree_size_type;
 
     fake_binary_cursor()
     : m_tree(0), m_pos(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