Subject: [Boost-commit] svn:boost r54290 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-06-23 17:37:33
Author: bernhard.reiter
Date: 2009-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
New Revision: 54290
URL: http://svn.boost.org/trac/boost/changeset/54290
Log:
binary_tree:
Fix unary inorder_erase.
Remove m_value_allocator.
Some experiments with forest algorithms.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 2
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 7 +
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 115 +++++++++++---------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp | 1
sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp | 10 +-
sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp | 4
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 70 +++++++------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp | 63 ++++++++---------
sandbox/SOC/2006/tree/trunk/libs/tree/test/for_each_test.cpp | 141 ++++++++++++++++++++++++++++++++++-----
9 files changed, 231 insertions(+), 182 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -25,7 +25,7 @@
* Add checks for correspondence of concepts and archetypes!
* Re-do forest (again!).
This seems to raise one issue, though: subtree algorithms operate on subtree root cursors,
- not ranges.* binary_tree_search_test -> lower_bound_test
+ not ranges.
(They might, however, work for "subforests". Consult Austern's segmented
iterators paper!)
They also work for the important special case in which forest consists of only one
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp 2009-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -148,6 +148,13 @@
, typename cursor_vertical_traversal<Cursor>::type());
}
+template <class Order, class Cursor, class Op>
+Op for_each(Order, Cursor s, Cursor t, Op f)
+{
+ return detail::for_each(Order(), s, t, f
+ , typename cursor_vertical_traversal<Cursor>::type());
+}
+
/**
* @brief Apply a function to every element of a subforest,
* in the order specified by the first parameter.
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2009-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -28,18 +28,18 @@
/**
* @brief A %binary_tree.
- * This class models the hierarchy concept, the container concept and the
- * sequence concept. TODO: complete this...
+ * This class models the hierarchy concept. TODO: complete this...
*
*/
template < class Tp, class Alloc = std::allocator<Tp> >
class binary_tree {
typedef binary_tree<Tp, Alloc> self_type;
- public:
+public:
typedef Tp value_type;
typedef typename Alloc::template rebind<value_type>::other allocator_type;
+ // Allocator usage roghly follows gcc's stl_list.h practice.
- private:
+private:
typedef detail::ascending_node<value_type> node_type;
typedef typename Alloc::template rebind<node_type>::other
@@ -63,14 +63,14 @@
};
explicit binary_tree (allocator_type const& alloc = allocator_type())
- : m_header(), m_value_alloc(alloc)
+ : m_header(), m_node_alloc(alloc)
{
}
template <class InputCursor>
binary_tree (InputCursor subtree,
allocator_type const& alloc = allocator_type())
- : m_header(), m_value_alloc(alloc)
+ : m_header(), m_node_alloc(alloc)
{
insert(root(), subtree);
}
@@ -83,7 +83,7 @@
*/
binary_tree (self_type const& x)
- : m_header(), m_value_alloc(x.m_value_alloc)
+ : m_header(), m_node_alloc(x.m_node_alloc)
{
if (!x.empty())
insert(root(), x.root());
@@ -118,7 +118,7 @@
/// Get a copy of the memory allocation object.
allocator_type get_allocator() const
{
- return m_value_alloc;
+ return allocator_type(m_node_alloc);
}
/// Functions returning cursors (as required by the Hierarchy concept)
@@ -208,7 +208,7 @@
// TODO: Optimise. Especially wrt header links.
// Making the other insert() a special case of this one might be more
- // reasonable.
+ // reasonable -- cf. gcc's C++0X optimisations wrt sequence ctors.
/**
* @brief Inserts val in front of @a pos, or, if @a pos' parent is
* already full, creates a new child node containing @a val
@@ -253,9 +253,6 @@
//// augmentor_type::pre_detach(*this, pos, ret,);
//// p_node = pos.detach(ret);
//// }
-//
-// m_value_alloc.destroy(p_node->data());
-// m_value_alloc.deallocate(p_node->data(), 1);
//
// m_node_alloc.destroy(p_node);
// m_node_alloc.deallocate(p_node, 1);
@@ -267,8 +264,6 @@
// node_pointer pos_node =
// static_cast<node_pointer>(position.m_node->operator[](position.m_pos));
// // delete the value position points to
-// m_value_alloc.destroy(pos_node->data());
-// m_value_alloc.deallocate(pos_node->data(), 1);
//
// // recurse
//// clear(position.begin());
@@ -286,26 +281,28 @@
* @param c Cursor pointing to the node to be removed.
*/
// TODO: Take care of header-pointers
- void clear(cursor position)
- {
+ void clear(cursor position)
+ {
// return cursor(boost::tree::for_each(boost::tree::postorder()
// , direct_cursor(position)
// , destroy_node
// , descending_vertical_traversal_tag()));
- if (!position.is_leaf()) {
- node_pointer pos_node =
- static_cast<node_pointer>(position.base_node()->m_children[position.m_pos]);
-
+ if (!position.is_leaf()) {
+ node_pointer pos_node =
+ static_cast<node_pointer>(
+ position.base_node()->m_children[position.m_pos]
+ );
+
// recurse
clear(position.begin());
clear(position.end());
// delete the node position points to
m_node_alloc.destroy(pos_node);
- m_node_alloc.deallocate(pos_node, 1);
- }
- }
+ m_node_alloc.deallocate(pos_node, 1);
+ }
+ }
void rotate(cursor& pos)
{
@@ -429,38 +426,6 @@
root.base_node()->m_children[1] = 0;
}
}
-
- // TODO: only one inorder_erase?
- // Use boost::optional (or variant?) e.g.!!!
- // What we actually want is: return an object containing
- // all required (either one or two) parameters and that
- // is somehow applied to inorder_erase (either with one or two
- // parameters) -- but not requiring inorder_erase is provided
- // [from a "what should know what" POV.]
- // MPL?
- // The class that is supposed to handle this should probably have two ctors,
- // one taking one, the other taking two parameters
- /*
- template <class T>
- class return_type_for_use_with_inorder_erase {
- public:
- ctor(T const& arg1): m_arg1(arg) {}
- ctor(T const& arg1, T const& arg2): m_arg1(arg1), m_arg2(arg2) {}
-
- // and, e.g.
- template <Fun F>
- call_function_with_arg_or_args(Fun) //...
- //use like call_function_with_arg_or_args(mem_fun(inorder_erase))
- // will call inorder_erase(m_arg1) or inorder_erase(m_arg1, m_arg2), resp.
- private:
- // some object
-
- };
- */
-
- // Nah. Guess a good compiler should just optimise that anyway.
- // That would still require a way of passing one or alternatively two values:
- // SO will it be (?): pair<cursor, optional<cursor> > //?
/**
* @brief Erases the value of the given cursor, keeping the binary_tree's
@@ -470,32 +435,36 @@
*/
cursor inorder_erase(cursor position)
{
+ node_pointer parent_node
+ = static_cast<node_pointer>(position.parent().base_node());
+
+ size_type idx = index(position.parent());
+
node_pointer p_node = static_cast<node_pointer>(position.base_node());
+ cursor orig_pos = position;
++position;
- if (position.is_leaf()) {
- (*p_node)[0]->m_parent = p_node->m_parent;
- static_cast<node_base_pointer>(p_node->m_parent)
- ->node_base_type::operator[](0) = (*p_node)[0];
-
+ if (position.is_leaf()) {
+ if (!orig_pos.is_leaf()) { // Set child's parent only if there _is_ a child
+ static_cast<node_base_pointer>(p_node->m_children[0])->m_parent
+ = parent_node;
+ }
+ parent_node->m_children[idx] = p_node->m_children[0];
+
+ // to_leftmost_parent(position);
while (index(position))
position = position.parent();
} else {
- position = position.begin();
- position.base_node()->m_parent = p_node->m_parent;
- static_cast<node_base_pointer>(p_node->m_parent)
- ->node_base_type::operator[](1) = position.base_node();
+ position.to_begin();
+ position.base_node()->m_parent = parent_node;
+ parent_node->m_children[idx] = position.base_node();
- while (!position.is_leaf())
- position = position.begin();
+ to_leftmost(position);
}
-
- m_value_alloc.destroy(p_node->data());
- m_value_alloc.deallocate(p_node->data(), 1);
-
+
m_node_alloc.destroy(p_node);
m_node_alloc.deallocate(p_node, 1);
-
+
return position;
}
@@ -530,9 +499,6 @@
p_node =
static_cast<node_pointer>(position.base_node()->node_base_type::operator[](position.m_pos));
-
- m_value_alloc.destroy(p_node->data());
- m_value_alloc.deallocate(p_node->data(), 1);
m_node_alloc.destroy(p_node);
m_node_alloc.deallocate(p_node, 1);
@@ -543,7 +509,6 @@
private:
node_base_type m_header;
- allocator_type m_value_alloc;
node_allocator_type m_node_alloc;
};
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp 2009-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -87,7 +87,6 @@
}
private:
-
friend class cursor_core_access;
friend class iterator_core_access;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp 2009-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -33,12 +33,12 @@
Cursor t = s.end();
for (s.to_begin(); s != t; ++s) {
f(*s);
- if (!s.is_leaf() || s == t2)
+ if (!s.is_leaf() && s != t2)
for_each_recursive(preorder(), s, t2, f);
}
// Multiway cursor
- if (!s.is_leaf() || s == t2)
+ if (!s.is_leaf() && s != t2)
for_each_recursive(preorder(), s, t2, f);
}
@@ -76,13 +76,13 @@
--t2; // Bit tweaky.
for (s.to_begin(); s != t ; ++s) {
f(*s);
- if (!s.is_leaf() || s == t2)
+ if (!s.is_leaf() && s != t2)
for_each_recursive(preorder(), s, t2, f);
}
// Multiway cursor
- if (!s.is_leaf() || s == t2)
- for_each_recursive(preorder(), s, t2, f);
+ if (!t.is_leaf() && t != t2)
+ for_each_recursive(preorder(), t, t2, f);
return f;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp 2009-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -84,13 +84,13 @@
successor(preorder, Cursor& c, Cursor& r)
{
// If we have a left child, go there.
- if (!c.is_leaf()) {
+ if (!c.is_leaf() && c!=r) {
c.to_begin();
return;
}
// No left child. So if we have a right child, go there.
- if (!(++c).is_leaf()) {
+ if (!(++c).is_leaf() && c!=r) {
c.to_begin();
return;
}
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-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -29,7 +29,6 @@
BOOST_AUTO_TEST_CASE( insert_value_test )
{
binary_tree<int> bt0;
- BOOST_CHECK(bt0.root().is_leaf());
binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8); //FIXME
c.to_begin();
@@ -172,31 +171,37 @@
}
-template <class Tree>
-void inorder_erase_test_dataset1_tree(Tree& mytree)
+BOOST_AUTO_TEST_CASE( inorder_erase_non_leaf_node_test )
{
- typename Tree::cursor c = mytree.root().end().end().begin();
- BOOST_CHECK_EQUAL(*c, 14);
-
- c = c.parent().parent();
- BOOST_CHECK_EQUAL(*(c.begin()), 10);
- BOOST_CHECK(c.begin().is_leaf());
- BOOST_CHECK(!c.end().is_leaf());
- BOOST_CHECK_EQUAL(*c.end().begin(), 14);
- c = c.begin();
+ binary_tree<int>::cursor c = bt.root().end().begin();
+ BOOST_CHECK_EQUAL(*c, 10);
// Left child empty
- c = mytree.inorder_erase(c);
- BOOST_CHECK_EQUAL(*c, 11);
+ BOOST_CHECK(c.is_leaf());
+ BOOST_CHECK(!(++c).is_leaf());
+ --c;
- ++c;
- BOOST_CHECK_EQUAL(*c.begin(), 12);
- BOOST_CHECK(c.begin().is_leaf());
- BOOST_CHECK(c.end().is_leaf());
- c = c.begin();
+ binary_tree<int>::size_type sz = size(bt.root());
+ c = bt.inorder_erase(c);
+ BOOST_CHECK_EQUAL(--sz, size(bt.root()));
+ BOOST_CHECK_EQUAL(*c, 11);
+}
+
+BOOST_AUTO_TEST_CASE( inorder_erase_leaf_node_test )
+{
+ binary_tree<int>::cursor c = bt.root().end().end().begin().begin().end().begin();
+ BOOST_CHECK_EQUAL(*c, 12);
+
// Both children empty
- c = mytree.inorder_erase(c);
+ BOOST_CHECK(c.is_leaf());
+ BOOST_CHECK((++c).is_leaf());
+ --c;
+
+ binary_tree<int>::size_type sz = size(bt.root());
+ c = bt.inorder_erase(c);
+ BOOST_CHECK_EQUAL(--sz, size(bt.root()));
+
BOOST_CHECK_EQUAL(*c, 13);
}
@@ -247,6 +252,7 @@
BOOST_AUTO_TEST_CASE( comparison_operator_test )
{
+ BOOST_CHECK(bt != bt2);
*bt2.root().begin().end().begin().begin()
= *bt.root().begin().end().begin().begin();
BOOST_CHECK(bt == bt2);
@@ -261,30 +267,6 @@
validate_test_dataset1_tree(bt0.root());
}
-BOOST_AUTO_TEST_CASE( binary_tree_test )
-{
- binary_tree<int> bt0(bt);
-
- // Change one value in bt0
- binary_tree<int>::cursor c = bt0.root().begin().end().begin().begin();
- int tmp = *c;
- *c = tmp + 1;
- BOOST_CHECK(bt != bt0);
-
- // Change it back
- c = bt0.root().begin().end().begin().begin();
- *c = tmp;
- BOOST_CHECK(bt == bt0);
-
-// c = bt0.inorder_first();
-// BOOST_CHECK_EQUAL(*c, 1);
- c = bt0.root();
- //back(inorder(), c);
- //BOOST_CHECK_EQUAL(*c, 14);
-
- //inorder_erase_test_dataset1_tree(bt);
-}
-
BOOST_AUTO_TEST_CASE( rotate_binary_tree_test )
{
binary_tree<int>::cursor c = bt.root().begin().end();
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-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -14,11 +14,8 @@
#include "test_data.hpp"
-template <class T>
-struct fake_descending_binary_cursor;
-
-template <class T>
-struct fake_ascending_binary_cursor;
+template <class T, class HT>
+class fake_binary_cursor;
template <class T>
struct fake_root_tracking_binary_cursor;
@@ -39,15 +36,15 @@
typedef typename children_type::pointer pointer;
typedef typename children_type::reference reference;
- typedef fake_descending_binary_cursor<T> descending_cursor;
- typedef fake_descending_binary_cursor<T/* const*/> const_descending_cursor; //FIXME
+ typedef fake_binary_cursor<T, descending_vertical_traversal_tag> descending_cursor;
+ typedef fake_binary_cursor<T/* const*/, descending_vertical_traversal_tag> const_descending_cursor; //FIXME
typedef descending_cursor cursor;
typedef const_descending_cursor const_cursor;
protected:
- typedef fake_ascending_binary_cursor<T> ascending_cursor;
- typedef fake_ascending_binary_cursor<T> const_ascending_cursor; //FIXME
+ typedef fake_binary_cursor<T, ascending_vertical_traversal_tag> ascending_cursor;
+ typedef fake_binary_cursor<T, ascending_vertical_traversal_tag> const_ascending_cursor; //FIXME
typedef fake_root_tracking_binary_cursor<T> root_tracking_cursor;
typedef fake_root_tracking_binary_cursor<T> const_root_tracking_cursor; //FIXME
@@ -196,30 +193,30 @@
// This should be easily extensible to nary by replacing the
// factor 2 by n in dereference, left, right and idx.
template <class T>
-class fake_descending_binary_cursor
+class fake_binary_cursor<T, descending_vertical_traversal_tag>
: public boost::tree::cursor_facade<
- fake_descending_binary_cursor<T>
+ fake_binary_cursor<T, descending_vertical_traversal_tag>
, T
, boost::bidirectional_traversal_tag
, boost::tree::descending_vertical_traversal_tag
>
{
public:
- typedef fake_descending_binary_cursor<T> cursor;
- typedef fake_descending_binary_cursor<T/* const*/> const_cursor;
+ typedef fake_binary_cursor<T, descending_vertical_traversal_tag> cursor;
+ typedef fake_binary_cursor<T/* const*/, descending_vertical_traversal_tag> const_cursor;
- typedef typename fake_descending_binary_cursor<T>::cursor_facade_::size_type size_type;
+ typedef typename fake_binary_cursor<T, descending_vertical_traversal_tag>::cursor_facade_::size_type size_type;
- fake_descending_binary_cursor()
+ fake_binary_cursor()
: m_tree(0), m_pos(0) {}
- explicit fake_descending_binary_cursor(fake_binary_tree<T>& t, size_type p = 0)
+ explicit fake_binary_cursor(fake_binary_tree<T>& t, size_type p = 0)
: m_tree(&t), m_pos(p) {}
- fake_descending_binary_cursor(fake_descending_binary_cursor<T> const& other)
+ fake_binary_cursor(fake_binary_cursor<T, descending_vertical_traversal_tag> const& other)
: m_tree(other.m_tree), m_pos(other.m_pos) {}
- fake_descending_binary_cursor<T>& operator=(fake_descending_binary_cursor<T> const& other)
+ fake_binary_cursor<T, descending_vertical_traversal_tag>& operator=(fake_binary_cursor<T, descending_vertical_traversal_tag> const& other)
{
m_tree = other.m_tree;
m_pos = other.m_pos;
@@ -234,16 +231,16 @@
friend class boost::tree::cursor_core_access;
static const
- typename fake_descending_binary_cursor<T>::cursor_facade_::value_type def_val
- = typename fake_descending_binary_cursor<T>::cursor_facade_::value_type();
+ typename fake_binary_cursor<T, descending_vertical_traversal_tag>::cursor_facade_::value_type def_val
+ = typename fake_binary_cursor<T, descending_vertical_traversal_tag>::cursor_facade_::value_type();
- typename fake_descending_binary_cursor<T>::cursor_facade_::reference
+ typename fake_binary_cursor<T, descending_vertical_traversal_tag>::cursor_facade_::reference
dereference() const
{
return m_tree->m_data[(m_pos-1)/2];
}
- bool equal(fake_descending_binary_cursor<T> const& other) const
+ bool equal(fake_binary_cursor<T, descending_vertical_traversal_tag> const& other) const
{
return (this->m_tree == other.m_tree)
&& (this->m_pos == other.m_pos);
@@ -287,26 +284,26 @@
};
template <class T>
-typename fake_descending_binary_cursor<T>::size_type
-index(fake_descending_binary_cursor<T> const& cur)
+typename fake_binary_cursor<T, descending_vertical_traversal_tag>::size_type
+index(fake_binary_cursor<T, descending_vertical_traversal_tag> const& cur)
{
return cur.index();
}
template <class T>
-struct fake_ascending_binary_cursor
-: public boost::tree::cursor_adaptor<fake_ascending_binary_cursor<T>
- , fake_descending_binary_cursor<T>
+struct fake_binary_cursor<T, ascending_vertical_traversal_tag>
+: public boost::tree::cursor_adaptor<fake_binary_cursor<T, ascending_vertical_traversal_tag>
+ , fake_binary_cursor<T, descending_vertical_traversal_tag>
, boost::use_default
, boost::use_default
, boost::tree::ascending_vertical_traversal_tag >
{
- typedef fake_ascending_binary_cursor<T> cursor;
- typedef fake_ascending_binary_cursor<T const> const_cursor;
+ typedef fake_binary_cursor<T, ascending_vertical_traversal_tag> cursor;
+ typedef fake_binary_cursor<T const, ascending_vertical_traversal_tag> const_cursor;
- fake_ascending_binary_cursor(fake_binary_tree<T>& t
+ fake_binary_cursor(fake_binary_tree<T>& t
, typename fake_binary_tree<T>::size_type p)
- : fake_ascending_binary_cursor::cursor_adaptor_(fake_descending_binary_cursor<T>(t, p)) {}
+ : fake_binary_cursor::cursor_adaptor_(fake_binary_cursor<T, descending_vertical_traversal_tag>(t, p)) {}
private:
friend class boost::iterator_core_access;
@@ -328,7 +325,7 @@
template <class T>
struct fake_root_tracking_binary_cursor
: public boost::tree::cursor_adaptor<fake_root_tracking_binary_cursor<T>
- , fake_ascending_binary_cursor<T>
+ , fake_binary_cursor<T, ascending_vertical_traversal_tag>
>
{
typedef fake_root_tracking_binary_cursor<T> cursor;
@@ -336,7 +333,7 @@
fake_root_tracking_binary_cursor(fake_binary_tree<T>& t
, typename fake_binary_tree<T>::size_type p)
- : fake_root_tracking_binary_cursor::cursor_adaptor_(fake_ascending_binary_cursor<T>(t, p)) {}
+ : fake_root_tracking_binary_cursor::cursor_adaptor_(fake_binary_cursor<T, ascending_vertical_traversal_tag>(t, p)) {}
private:
friend class boost::iterator_core_access;
Modified: 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/for_each_test.cpp 2009-06-23 17:37:32 EDT (Tue, 23 Jun 2009)
@@ -85,7 +85,7 @@
);
}
-BOOST_AUTO_TEST_CASE( test_forest_for_each_descending_preorder)
+BOOST_AUTO_TEST_CASE( test_subforest_for_each_descending_preorder)
{
test_data_set mpo;
mock_cursor_data(mpo);
@@ -111,7 +111,7 @@
// );
}
-BOOST_AUTO_TEST_CASE( test_forest_for_each_ascending_preorder)
+BOOST_AUTO_TEST_CASE( test_subforest_for_each_ascending_preorder)
{
test_data_set mpo;
mock_cursor_data(mpo);
@@ -125,36 +125,135 @@
cie = ci;
++++++++cie; // 7
- fake_root_tracking_binary_tree<int> fabt1(fbt1);
- boost::tree::forest<int, fake_root_tracking_binary_tree<int> > ft0(fabt1);
+ 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;
+ 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(),
-// 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()?
-// ft0.begin().end(), //boost::tree::detail::forest_cursor< fake_ascending_binary_cursor<int> >(fabt1.root().begin().end().end().begin()),
+// 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_root_tracking_binary_cursor<int> > dfc0(ft0.begin().begin().end());
+ //boost::tree::detail::forest_cursor< fake_ascending_binary_cursor<int> > dfc0(ft0.begin().begin().end());
// Also try ft0.begin and ft0.end consistency!
- fake_root_tracking_binary_cursor<int> dfc(ft0.begin().begin().begin().base()); //(fabt1.root().begin().begin());
- fake_root_tracking_binary_cursor<int> dfce(ft0.begin().end().base());
- --dfce;
- BOOST_CHECK_EQUAL(*dfce, 7);
+}
+
+BOOST_AUTO_TEST_CASE( test_two_cursor_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();
+
+ 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_AUTO_TEST_CASE( test_forest_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();
+
+ //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_CHECK_EQUAL(*dfc, ci->val);
- successor(preorder(), dfc);
- BOOST_CHECK_EQUAL(*dfc, (++ci)->val);
- successor(preorder(), dfc);
- BOOST_CHECK_EQUAL(*dfc, 6);
- successor(preorder(), dfc);
- BOOST_CHECK_EQUAL(*dfc, 4);
- successor(preorder(), dfc);
- BOOST_CHECK_EQUAL(*dfc, 7);
- BOOST_CHECK(dfc == dfce);
+ boost::tree::for_each(
+ preorder(),
+ ft0.begin(),
+ ft0.end(),
+ muc
+ );
+}
+
+BOOST_AUTO_TEST_CASE( test_forest_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();
+
+ 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_AUTO_TEST_SUITE_END()
\ No newline at end of file