From: ockham_at_[hidden]
Date: 2008-06-27 12:08:28
Author: bernhard.reiter
Date: 2008-06-27 12:08:27 EDT (Fri, 27 Jun 2008)
New Revision: 46775
URL: http://svn.boost.org/trac/boost/changeset/46775
Log:
forest_tree related tests.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 9 ++++++++
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp | 41 +++++++++++++++++++++++++----------
sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp | 4 +++
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp | 45 ++++++++++++++++++++++++++++++++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 22 +++++++++++++++++++
5 files changed, 103 insertions(+), 18 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-06-27 12:08:27 EDT (Fri, 27 Jun 2008)
@@ -14,6 +14,8 @@
[section TODO]
General:
+* Do we want/need an O(1) inorder_begin() for binary_tree?
+ Does Gnu's rb_tree (used in std::map) have one?
* Is it really a good idea to use InCursor::size_type for size(Cursor)?
For a binary_cursor, a boolean size_type would be enough - but
not for a subtree algorithm like this one. Maybe we need two different size_types for
@@ -78,6 +80,12 @@
* Start an RFC: what subtree algorithms should there be? In particular, of which of
the STL's linear algorithms should there be a hierarchical version?
+Ask on the mailing list:
+
+* [iterator] Can we get rid of the need to declare iterator_core_access a friend (as we're already
+ doing so with cursor_core_access, this should be enough).
+* [property_map]: any need for an extract_property_map?
+
Proposal:
* Change complexity requirements for *order end() to constant? We're using root(), and
@@ -131,5 +139,6 @@
* Implement associative containers and priority_queue specialization using searcher
* Implement (binary) heap
+* Is it possible to implement BGL's traversal algorithms using tree semantics?
[endsect]
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp 2008-06-27 12:08:27 EDT (Fri, 27 Jun 2008)
@@ -206,7 +206,21 @@
friend class cursor_core_access;
typedef iterator_adaptor<Derived, Base, Value, HorizontalTraversal, Reference,
Difference> iterator_adaptor_;
- public:
+
+private:
+ // Curiously Recurring Template interface.
+
+ Derived& derived()
+ {
+ return *static_cast<Derived*>(this);
+ }
+
+ Derived const& derived() const
+ {
+ return *static_cast<Derived const*>(this);
+ }
+
+public:
cursor_adaptor() : iterator_adaptor_()
{ }
@@ -224,29 +238,30 @@
typedef cursor_adaptor cursor_adaptor_;
public:
- bool const empty_() const
+ bool const empty() const
{
- return iterator_adaptor_::base().empty();
+ return this->base().empty();
}
- size_type const size_() const
+ size_type const size() const
{
- return iterator_adaptor_::base().size();
+ return this->base().size();
}
- size_type const max_size_() const
+ size_type const max_size() const
{
- return iterator_adaptor_::base().max_size();
+ return this->base().max_size();
}
- size_type const par() const
+ size_type const parity() const
{
- return iterator_adaptor_::base().parity();
+ return this->base().parity();
}
Derived& to_begin()
{
- return Derived(this->base_reference().to_begin());
+ this->base_reference().to_begin();
+ return this->derived();
}
Derived begin()
@@ -256,7 +271,8 @@
Derived& to_end()
{
- return Derived(this->base_reference().to_end());
+ this->base_reference().to_end();
+ return this->derived();
}
Derived end()
@@ -266,7 +282,8 @@
Derived& to_parent()
{
- return Derived(this->base_reference().to_parent());
+ this->base_reference().to_parent();
+ return this->derived();
}
Derived parent()
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp 2008-06-27 12:08:27 EDT (Fri, 27 Jun 2008)
@@ -31,6 +31,7 @@
namespace tree {
+// TODO: For ascendant cursors, we don't really need a pair<Cursor, Cursor>
template <class Cursor>
class out_edge_iterator
: public iterator_facade<out_edge_iterator<Cursor>
@@ -93,6 +94,9 @@
using boost::tree::binary_tree;
+// Unsure how we can avoid redundancies here, as this should be pretty much the same for
+// all kinds of trees.
+
template <class Tp, class Alloc>
struct graph_traits< binary_tree<Tp, Alloc> > {
typedef typename binary_tree<Tp, Alloc>::cursor vertex_descriptor;
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp 2008-06-27 12:08:27 EDT (Fri, 27 Jun 2008)
@@ -5,9 +5,12 @@
// http://www.boost.org/LICENSE_1_0.txt)
#include <boost/tree/forest_tree.hpp>
+#include <boost/tree/algorithm.hpp>
#include <boost/test/minimal.hpp>
+#include <list>
+
#include "test_tree_traversal_data.hpp"
//TODO: Make this a test suite.
@@ -27,19 +30,19 @@
c = mytree.insert(c, 6);
BOOST_CHECK(*c == 6);
- cur = tree_type::base_cursor(c);
- BOOST_CHECK(*cur == 6);
+ //cur = tree_type::base_cursor(c);
+ //BOOST_CHECK(*cur == 6);
// BOOST_CHECK(cur == mytree.h.root().begin());
c = mytree.insert(c, 5);
BOOST_CHECK(*c == 5);
- cur = tree_type::base_cursor(c);
+ //cur = tree_type::base_cursor(c);
// BOOST_CHECK(cur == mytree.h.root().begin());
c = mytree.insert(c, 4);
BOOST_CHECK(*c == 4);
- BOOST_CHECK(c == mytree.root().begin());
+ BOOST_CHECK(c == mytree.root().begin()); // Do we want this?
cur = tree_type::base_cursor(c);
// BOOST_CHECK(cur == mytree.h.root().begin());
@@ -70,7 +73,7 @@
tree_type forest;
//create_test_data_tree(forest);
c = forest.insert(forest.root(), 8);
- BOOST_CHECK(c == forest.root().begin());
+ BOOST_CHECK(c == forest.root().begin()); // Do we want this?
BOOST_CHECK(*c == 8);
c = forest.insert(c, 3);
BOOST_CHECK(*c == 3);
@@ -79,10 +82,40 @@
}
-
+void test_natural_correspondence()
+{
+ using namespace boost::tree;
+
+ typedef binary_tree<int> binary_tree_type;
+ binary_tree_type bt;
+ create_test_data_tree(bt);
+
+ typedef forest_tree<int> forest_tree_type;
+ forest_tree_type ft(bt);
+
+ validate_corresponding_forest_tree(ft);
+
+ // Now test *order correspondence:
+ // forest binary
+ // pre pre
+ // post in
+ 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);
+
+ //boost::tree::preorder::copy(ft.root(), oc_test_list);
+ //test::preorder::traversal(test_list.begin(), test_list.end());
+
+ test_list.clear();
+ //boost::tree::postorder::copy(ft.root(), oc_test_list);
+ //test::inorder::traversal(test_list.begin(), test_list.end());
+}
int test_main(int, char* [])
{
test_forest_tree();
+ test_natural_correspondence();
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 2008-06-27 12:08:27 EDT (Fri, 27 Jun 2008)
@@ -51,6 +51,28 @@
BOOST_CHECK(*ret.root().end().end().begin().begin().end().begin() == 12); //Leaf
}
+template <class Tree>
+void validate_corresponding_forest_tree(Tree const& t)
+{
+ typename Tree::const_cursor c = t.root().begin();
+ BOOST_CHECK(*c == 8);
+ BOOST_CHECK(*c.to_begin() == 3);
+ BOOST_CHECK(*c.to_begin() == 1);
+ c.to_parent();
+ BOOST_CHECK(*++c == 6);
+ BOOST_CHECK(*c.to_begin() == 4);
+ c.to_parent();
+ BOOST_CHECK(*++c == 7);
+ c = t.root().begin();
+ BOOST_CHECK(*++c == 10);
+ BOOST_CHECK(*++c == 14);
+ //BOOST_CHECK(++c == t.root().end());
+ //--c;
+ BOOST_CHECK(*c.to_begin() == 13);
+ BOOST_CHECK(*c.to_begin() == 11);
+ BOOST_CHECK(*++c == 12);
+}
+
namespace test {
namespace preorder {