Subject: [Boost-commit] svn:boost r49758 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail/algorithm libs/tree/test
From: ockham_at_[hidden]
Date: 2008-11-14 12:51:59
Author: bernhard.reiter
Date: 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
New Revision: 49758
URL: http://svn.boost.org/trac/boost/changeset/49758
Log:
More concepts, plus archetypes.
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp
- copied, changed from r49755, /sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp
sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp
- copied, changed from r49756, /sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp | 121 ++++++++++++++++++++++++++++-----------
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp | 35 ++++------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/ascending.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp | 5 +
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 3
sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp | 75 +++++------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp | 2
10 files changed, 132 insertions(+), 117 deletions(-)
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp (from r49755, /sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -5,68 +5,117 @@
// http://www.boost.org/LICENSE_1_0.txt)
/**
- * @file cursor_concepts.hpp
- * Cursor concepts
+ * @file cursor_archetypes.hpp
+ * Cursor archetypes
*/
-#ifndef BOOST_TREE_CURSOR_CONCEPTS_HPP
-#define BOOST_TREE_CURSOR_CONCEPTS_HPP
+#ifndef BOOST_TREE_CURSOR_ARCHETYPES_HPP
+#define BOOST_TREE_CURSOR_ARCHETYPES_HPP
-#include <boost/concept_check.hpp>
+#include <boost/iterator/iterator_archetypes.hpp>
namespace boost {
namespace tree {
-template <class X>
-struct DescendingCursor
+class descendor_archetype
{
public:
- typedef typename cursor_value<X>::type value_type;
-
- BOOST_CONCEPT_USAGE(DescendingCursor)
- {
- d.to_begin();
- d.begin();
- d.to_end();
- d.end();
- }
+ typedef forward_traversal_tag vertical_traversal;
-private:
- X d;
+ descendor_archetype& to_begin() { return *this; }
+ descendor_archetype& to_end() { return *this; }
+
+ descendor_archetype begin() const { return *this; }
+ descendor_archetype end() const { return *this; }
+ bool empty() const { return true; }
};
-template <class T>
-class descending_cursor_archetype
+class ascendor_archetype
{
public:
- void to_begin() {}
- void to_end() {}
+ ascendor_archetype& to_parent() { return *this; }
+
+ ascendor_archetype parent() const { return *this; }
+};
+
+template <
+ class Value
+ , class AccessCategory
+ , class HorizontalTraversal
+ , class VerticalTraversal
+>
+class cursor_archetype;
+
+template <
+ class Value
+ , class AccessCategory
+ , class HorizontalTraversal
+ , class VerticalTraversal
+>
+class cursor_archetype
+: public iterator_archetype<Value, AccessCategory, HorizontalTraversal>
+{
+
};
-// Derive from DescendingCursor or not?
-template <class X>
-struct AscendingCursor
+// Ideally derive from ascendor_archetype.
+// The problem: begin() and end() return the wrong type!
+template <
+ class Value
+ , class AccessCategory
+ , class HorizontalTraversal
+>
+class cursor_archetype<Value
+ , AccessCategory
+ , HorizontalTraversal
+ , forward_traversal_tag>
+: public iterator_archetype<Value, AccessCategory, HorizontalTraversal>
+//, public descendor_archetype
{
+private:
+ typedef class cursor_archetype<Value
+ , AccessCategory
+ , HorizontalTraversal
+ , forward_traversal_tag> self_type;
public:
- BOOST_CONCEPT_USAGE(AscendingCursor)
- {
- a.to_parent();
- a.parent();
- }
+ typedef forward_traversal_tag vertical_traversal;
-private:
- X a;
+ self_type& to_begin() { return *this; }
+ self_type& to_end() { return *this; }
+
+ self_type begin() const { return *this; }
+ self_type end() const { return *this; }
+
+ bool empty() const { return true; }
};
-template <class T>
-class ascending_cursor_archetype
+template <
+ class Value
+ , class AccessCategory
+ , class HorizontalTraversal
+>
+class cursor_archetype<Value
+ , AccessCategory
+ , HorizontalTraversal
+ , bidirectional_traversal_tag>
+: public iterator_archetype<Value, AccessCategory, HorizontalTraversal>
+//, public ascendor_archetype
{
+private:
+ typedef class cursor_archetype<Value
+ , AccessCategory
+ , HorizontalTraversal
+ , bidirectional_traversal_tag> self_type;
public:
- void to_parent() {}
+ typedef bidirectional_traversal_tag vertical_traversal;
+
+ self_type& to_parent() { return *this; }
+
+ self_type parent() const { return *this; }
};
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_CURSOR_CONCEPTS_HPP
+#endif // BOOST_TREE_CURSOR_ARCHETYPES_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -13,17 +13,22 @@
#define BOOST_TREE_CURSOR_CONCEPTS_HPP
#include <boost/concept_check.hpp>
+#include <boost/iterator/iterator_concepts.hpp>
-namespace boost {
-namespace tree {
+namespace boost_concepts {
+// TODO: Adapt concept requirements for algorithms according to archetypes!
+
+
+// Even split up into two types: one with only to_begin() and to_end(), and
+// one with also begin() and end() ?
+// I think we're lacking some requirements imposed on the return types of these
+// member functions, but that might overlap with iterator requirements.
template <class X>
-struct DescendingCursor
+struct Descendor
{
public:
- typedef typename cursor_value<X>::type value_type;
-
- BOOST_CONCEPT_USAGE(DescendingCursor)
+ BOOST_CONCEPT_USAGE(Descendor)
{
d.to_begin();
d.begin();
@@ -36,12 +41,10 @@
};
-template <class T>
-class descending_cursor_archetype
+template <class X>
+struct DescendingCursor
+ : Descendor<X>, LvalueIterator<X>
{
-public:
- void to_begin() {}
- void to_end() {}
};
// Derive from DescendingCursor or not?
@@ -59,14 +62,6 @@
X a;
};
-template <class T>
-class ascending_cursor_archetype
-{
-public:
- void to_parent() {}
-};
-
-} // namespace tree
-} // namespace boost
+} // namespace boost_concepts
#endif // BOOST_TREE_CURSOR_CONCEPTS_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/ascending.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/ascending.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/ascending.hpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -9,10 +9,10 @@
* Ascending traversal algorithms for cursors
*/
-
#ifndef BOOST_TREE_DETAIL_ALGORITHM_ASCENDING_HPP
#define BOOST_TREE_DETAIL_ALGORITHM_ASCENDING_HPP
+#include <boost/iterator/iterator_categories.hpp>
namespace boost {
namespace tree {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -23,6 +23,8 @@
namespace boost {
namespace tree {
+using namespace boost_concepts;
+
/** \addtogroup traversal */
/*\@{*/
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -21,6 +21,8 @@
namespace boost {
namespace tree {
+using namespace boost_concepts;
+
/** \addtogroup traversal */
/*\@{*/
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -23,6 +23,8 @@
namespace boost {
namespace tree {
+using namespace boost_concepts;
+
/** \addtogroup traversal */
/*\@{*/
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -14,6 +14,7 @@
#include <boost/tree/detail/cursor/forest.hpp>
#include <boost/tree/binary_tree.hpp>
+#include <boost/tree/cursor_concepts.hpp>
#include <boost/concept_check.hpp>
@@ -21,7 +22,7 @@
namespace tree {
using detail::forest_cursor;
-
+using namespace boost_concepts;
/**
* @brief A %forest_tree.
@@ -34,6 +35,8 @@
class forest_tree {
BOOST_CONCEPT_ASSERT((DefaultConstructible<T>));
+BOOST_CONCEPT_ASSERT((DescendingCursor< typename binary_tree<T>::cursor >));
+BOOST_CONCEPT_ASSERT((DescendingCursor< typename binary_tree<T>::const_cursor >));
//BOOST_CONCEPT_ASSERT((SameType<T, typename Hierarchy::value_type>));
// Is there a SameType concept in BCCL?
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 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -26,7 +26,8 @@
[ run binary_tree_test.cpp ]
[ run binary_tree_search_test.cpp ]
# [ run key_search_binary_tree_test.cpp ]
-# [ run rank_search_binary_tree_test.cpp ]
+# [ run rank_search_binary_tree_test.cpp ]
+ [ run algorithm_concepts_test.cpp ]
[ run cursor_algorithm_test.cpp ]
[ run iterator_algorithm_test.cpp ]
# [ run string_search_binary_tree_test.cpp ]
Copied: sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp (from r49756, /sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -4,75 +4,36 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/iterator.hpp>
#include <boost/tree/algorithm.hpp>
-#include <boost/tree/insert_cursor.hpp>
+#include <boost/iterator/iterator_categories.hpp>
-#include <boost/lambda/bind.hpp>
+#include <boost/tree/cursor_archetypes.hpp>
+#include <boost/concept_archetype.hpp>
-#include <list>
-#include <algorithm>
-#include <iterator>
-
-#define BOOST_TEST_MODULE cursor_algorithm test
+#define BOOST_TEST_MODULE algorithm_concepts_algorithm test
#include <boost/test/included/unit_test.hpp>
#include <boost/test/test_case_template.hpp>
#include "helpers.hpp"
-#include "test_tree_traversal_data.hpp"
using namespace boost::tree;
-BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, test_binary_tree_with_list_fixture<int>)
-
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_foreach, Order, orders)
-{
- boost::tree::for_each(
- Order(),
- bt.root(),
- boost::lambda::bind(&std::list<int>::push_back, &l, boost::lambda::_1)
- );
- test_traversal(Order(), l.begin(), l.end());
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy, Order, orders)
-{
- boost::tree::copy(Order(), bt.root(), o);
- test_traversal(Order(), l.begin(), l.end());
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE ( test_desc_copy_using_insert_cursor, Order, orders )
-{
- bt2.clear();
-
- boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
- , boost::forward_traversal_tag());
-
- validate_test_dataset1_tree(bt2);
- BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE ( test_asc_copy_using_insert_cursor, Order, orders )
-{
- bt2.clear();
-
- boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
- , boost::bidirectional_traversal_tag());
-
- validate_test_dataset1_tree(bt2);
- BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
-}
+BOOST_AUTO_TEST_SUITE( algorithm_concepts_covering_test )
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform, Order, orders)
+// Each order probably requires different concepts (eg inorder: multiway)!
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_foreach, Order, orders )
{
- // 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::transform(Order(), bt.root(), bt2.root(), std::bind2nd(std::plus<int>(),1));
- boost::tree::transform(Order(), bt2.root(), o, std::bind2nd(std::minus<int>(),1));
- test_traversal(Order(), l.begin(), l.end());
+ boost::detail::dummy_constructor dummy_cons;
+ cursor_archetype< boost::null_archetype<>
+ , boost::iterator_archetypes::readable_lvalue_iterator_t // Really lvalue?
+ , boost::forward_traversal_tag
+ , boost::forward_traversal_tag
+ > c;
+ boost::unary_function_archetype< boost::null_archetype<> , boost::null_archetype<> >
+ f(dummy_cons);
+
+ boost::tree::for_each(Order(), c, f);
}
-BOOST_AUTO_TEST_SUITE_END()
+BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp 2008-11-14 12:51:58 EST (Fri, 14 Nov 2008)
@@ -75,4 +75,4 @@
test_traversal(Order(), l.begin(), l.end());
}
-BOOST_AUTO_TEST_SUITE_END()
+BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file