Boost logo

Boost-Commit :

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 {


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