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