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

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) {}