[Boost-commit] svn:boost r50324 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail/cursor boost/tree/detail/node libs/tree/test

Subject: [Boost-commit] svn:boost r50324 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail/cursor boost/tree/detail/node libs/tree/test
From: ockham_at_[hidden]
Date: 2008-12-19 12:00:06

Author: bernhard.reiter
Date: 2008-12-19 12:00:05 EST (Fri, 19 Dec 2008)
New Revision: 50324
URL: http://svn.boost.org/trac/boost/changeset/50324

Log:
Move output_iterator_cursor to a header of its own.
Some preparations for use of mock trees.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/output_iterator_cursor.hpp
      - copied, changed from r50323, /sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp                       |   147 --------------------------------------- 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp           |     2                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp             |    72 ++++++++++++-------                     
   sandbox/SOC/2006/tree/trunk/boost/tree/output_iterator_cursor.hpp       |   126 ++-------------------------------       
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp  |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp         |    28 +++---                                  
   sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp    |     8 +-                                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |   127 +++++++++++++++++++++++++++-------      
   8 files changed, 177 insertions(+), 335 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp	2008-12-19 12:00:05 EST (Fri, 19 Dec 2008)
@@ -12,22 +12,18 @@
 #ifndef BOOST_TREE_CURSOR_HPP
 #define BOOST_TREE_CURSOR_HPP
 
-#include <boost/iterator/iterator_facade.hpp>
-#include <boost/iterator/iterator_adaptor.hpp>
-
 #include <stddef.h>
 #include <iterator>
 
+namespace boost {
+namespace tree {
+
 using std::input_iterator_tag;
 using std::output_iterator_tag;
 using std::forward_iterator_tag;
 using std::bidirectional_iterator_tag;
 using std::random_access_iterator_tag;
 
-namespace boost {
-namespace tree {
-
-
 template <class Cursor>
 struct cursor_value {
     typedef typename Cursor::value_type type;
@@ -125,143 +121,6 @@
 
 //define freestanding begin, end, size, empty using cursor's member fns?
 
-template <
-    class OutputIterator
-//  , class Value                         
-//  , class HorizontalTraversalOrCategory 
-//  , class VerticalTraversalOrCategory
-//  , class Reference                     
-//  , class Difference                
-//  , class Size                          
->
-class output_iterator_cursor;
-
-/**
- * @brief Output cursor wrapper around an output iterator.
- * 
- * This can be very useful e.g. to have cursor algorithms actually work on
- * iterators, thus permitting some kind of linearization of a given subtree.
- * (Modelled after std::insert_iterator and the like.)
- * 
- * For construction, the outputter_cursor_iterator_wrapper might come in useful
- * in saving keystrokes.
- */
-// TODO: Complete this.
-// Shouldn't we be using cursor_facade?
-template <
-    class OutputIterator
-//  , class Value                         = use_default
-//  , class HorizontalTraversalOrCategory = use_default
-//  , class VerticalTraversalOrCategory   = bidirectional_traversal_tag
-//  , class Reference                     = use_default
-//  , class Difference                    = use_default
-//  , class Size                          = use_default
->
-class output_iterator_cursor {
-protected:
-    OutputIterator* iter;
-//private:
-//    typedef iterator_adaptor<output_iterator_cursor<OutputIterator> 
-//                         , OutputIterator
-//                         , Value
-//                         , HorizontalTraversalOrCategory
-//                         , Reference
-//                         , Difference> ia_type;
-public:
-    /// Make the iterator type publicly accessible.
-    typedef OutputIterator iterator;
-
-    // FIXME: Very adhoc.
-    typedef output_iterator_cursor<OutputIterator> value_type;
-    typedef std::size_t size_type;
-    typedef output_iterator_cursor<OutputIterator> const_cursor;
-    typedef forward_traversal_tag horizontal_traversal;
-    typedef bidirectional_traversal_tag vertical_traversal;
-    typedef forward_traversal_tag iterator_category;
-    typedef std::ptrdiff_t difference_type;
-    typedef value_type* pointer;
-    typedef value_type& reference;
-        
-    /**
-     * For construction, we obviously need an Output Iterator to work on (i.e., write to).
-     */
-    explicit output_iterator_cursor(OutputIterator& i) : iter(&i) {}
-
-    /** 
-     * @param value A const& value of the value_type of container that iter is
-     *              associated with.
-     * @return      This cursor, for chained operations.
-     * Assigning a value to this cursor will insert it before iter, the iterator it is
-     * wrapped around.
-     * 
-     * Unfortunately, Output Iterators do not necessarily expose their
-     * value_type (they might just give back void), so the following assignment operator
-     * has to be a template.
-     */
-    // TODO: Consult C++0x if this has been changed
-    template <class ValueType>
-    output_iterator_cursor& operator=(ValueType const& value)
-    { 
-        *((*iter)++) = value;
-        return *this; 
-    }
-
-    /// Returns *this.
-    output_iterator_cursor& operator*() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& operator++() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor operator++(int) { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& operator--() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor operator--(int) { return *this; }
-    
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& to_begin() { return *this; }
-    output_iterator_cursor& begin() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& to_end() { return *this; }
-    output_iterator_cursor& end() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& to_parent() { return *this; }
-    output_iterator_cursor& parent() { return *this; }
-    
-    /// Returns true, in case an algorithm has a loop only terminating at root.
-    bool is_root() const { return true; }
-    
-    /// Returns true, in case an algorithm has a loop only terminating at a leaf.
-    bool empty() const { return true; }
-    
-    std::size_t const index() const { return 0; }
-};
-
-template <class OutputIterator>
-typename output_iterator_cursor<OutputIterator>::size_type
-index(output_iterator_cursor<OutputIterator> const& cur)
-{
-    return cur.index();
-}
-
-/** 
- * @param o    An output iterator.
- * @result    An instance of output_iterator_cursor working on o.
- * 
- * Use as shortcut for cumbersome typenames, just as with std::inserter and the like.
- */
-template<class OutputIterator>
-inline output_iterator_cursor<OutputIterator>
-outputter_cursor_iterator_wrapper(OutputIterator o)
-{
-    return output_iterator_cursor<OutputIterator>(o);
-}
-
 } // namespace tree
 } // namespace boost
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp	2008-12-19 12:00:05 EST (Fri, 19 Dec 2008)
@@ -148,7 +148,7 @@
     // Container specific
     bool empty_() const
     {
-        return this->base_reference()->m_children[m_pos]->empty();
+        return this->base_reference()->m_children[m_pos] == node_type::nil(); //->empty();
         //return this->base_reference()->get_index();
     }
     

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp	2008-12-19 12:00:05 EST (Fri, 19 Dec 2008)
@@ -34,24 +34,26 @@
  */
  
 class node_with_parent_base {
-    typedef node_with_parent_base self_type;
-    typedef self_type* base_pointer;
-    typedef self_type const* const_base_pointer;
+//    typedef node_with_parent_base self_type;
+//    typedef self_type* base_pointer;
+//    typedef self_type const* const_base_pointer;
 
- public:
-    base_pointer m_parent; // TODO: protect?
+public:
+    node_with_parent_base* m_parent; // TODO: protect?
     
     node_with_parent_base()
     {
         m_parent = this;
     }
     
-    base_pointer parent()
+    node_with_parent_base(node_with_parent_base* p) : m_parent(p) {}
+    
+    node_with_parent_base* parent()
     {
         return m_parent;
     }
     
-    base_pointer const parent() const
+    node_with_parent_base* const parent() const
     {
         return m_parent;
     }
@@ -103,22 +105,32 @@
 //    }
 //};
 
+class node_base;
+
+class node_with_children_base {
+public:
+    typedef array<node_base*, 2> children_type;
+    
+//protected:
+    children_type m_children;
+};
 
 class node_base
-: public node_with_parent_base {
+: public node_with_parent_base, public node_with_children_base {
     typedef node_base self_type;
     
 public:
- 
-    typedef array<node_base*, 2> base_type;
+    //typedef node_with_children_base::base_type base_type;
     typedef self_type* base_pointer;
     typedef self_type const* const_base_pointer;
-    
-    base_type m_children;
-    
-    node_base() : node_with_parent_base()
+        
+    node_base() : node_with_parent_base(), node_with_children_base()
     { }
-    
+
+    node_base(node_with_parent_base* p)
+    : node_with_parent_base(p), node_with_children_base()
+    { }
+        
     static base_pointer nil()
     {
         static self_type m_nil_obj;
@@ -128,19 +140,19 @@
     
     void init()
     {
-        for (base_type::size_type i=0; i<base_type::max_size(); ++i)
+        for (children_type::size_type i=0; i<children_type::max_size(); ++i)
             m_children[i] = nil();
     }
 
     // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
-    bool const empty() const
-    {
-        return (this == nil());
-    }
+//    bool const empty() const
+//    {
+//        return (this == nil());
+//    }
     
     // Binary specific
     
-    base_type::size_type rotate(base_type::size_type const& c)
+    children_type::size_type rotate(children_type::size_type const& c)
     {
         //TODO: Optimise.
         base_pointer q = m_children[c];
@@ -154,7 +166,7 @@
         B->m_parent = this;
         q->m_parent = this->m_parent;
 
-        base_type::size_type qp = get_index();
+        children_type::size_type qp = get_index();
         static_cast<base_pointer>(q->m_parent)->m_children[qp] = q;
         this->m_parent = q;
         q->m_children[(c ? 0 : 1)] = this;
@@ -162,7 +174,7 @@
         //return (c ? 0 : 1);
     }
     
-    base_pointer detach(base_type::size_type m_pos)
+    base_pointer detach(children_type::size_type m_pos)
     {
         base_pointer q = m_children[m_pos];
         m_children[m_pos] = 
@@ -174,8 +186,8 @@
     }
     
     // TODO: actually implement this.
-    base_pointer detach(base_type::size_type index, 
-                        base_type::size_type other_index, 
+    base_pointer detach(children_type::size_type index, 
+                        children_type::size_type other_index, 
                         base_pointer other)
     {
         //Node::pre_splice(q, r);
@@ -186,7 +198,7 @@
         static_cast<base_pointer>(other->m_parent)->m_children[other_index] = this;
         m_parent = other->m_parent;
 
-        for (base_type::size_type i=0; i<base_type::max_size(); ++i) {
+        for (children_type::size_type i=0; i<children_type::max_size(); ++i) {
             m_children[i] = other->m_children[i];
             m_children[i]->m_parent = this;
         }
@@ -194,13 +206,17 @@
     }
     
     // O(1)
-    base_type::size_type const get_index() const
+    children_type::size_type const get_index() const
     {
         return (static_cast<base_pointer>(this->m_parent)->m_children[0] == this ? 0 : 1);
     }
     
 };
 
+class descending_node_base
+: public node_with_children_base {
+};
+
 template <typename T>
 class node : public node_base {
  public:
@@ -228,6 +244,8 @@
     const_reference operator*() const { return *m_data; } 
     
     node(pointer data) : base_type(), m_data(data) {}
+ 
+    node(pointer data, base_pointer p) : base_type(p), m_data(data) {}
     
     pointer data()
     {

Copied: sandbox/SOC/2006/tree/trunk/boost/tree/output_iterator_cursor.hpp (from r50323, /sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/output_iterator_cursor.hpp	2008-12-19 12:00:05 EST (Fri, 19 Dec 2008)
@@ -5,126 +5,18 @@
 //  http://www.boost.org/LICENSE_1_0.txt)
 
 /** 
- * @file cursor.hpp
- * Cursor traits structs, traversal tags, ...
+ * @file output_iterator_cursor.hpp
+ * Cursor wrapper around a given output iterator.
  */
  
-#ifndef BOOST_TREE_CURSOR_HPP
-#define BOOST_TREE_CURSOR_HPP
+#ifndef BOOST_TREE_OUTPUT_ITERATOR_CURSOR_HPP
+#define BOOST_TREE_OUTPUT_ITERATOR_CURSOR_HPP
 
-#include <boost/iterator/iterator_facade.hpp>
-#include <boost/iterator/iterator_adaptor.hpp>
-
-#include <stddef.h>
-#include <iterator>
-
-using std::input_iterator_tag;
-using std::output_iterator_tag;
-using std::forward_iterator_tag;
-using std::bidirectional_iterator_tag;
-using std::random_access_iterator_tag;
+#include <boost/tree/cursor.hpp>
 
 namespace boost {
 namespace tree {
 
-
-template <class Cursor>
-struct cursor_value {
-    typedef typename Cursor::value_type type;
-};
-
-template <class Cursor>
-struct cursor_reference {
-    typedef typename Cursor::reference type;
-};
-
-template <class Cursor>
-struct cursor_const_reference {
-    typedef typename Cursor::const_reference type;
-};
-
-template <class Cursor>
-struct cursor_pointer {
-    typedef typename Cursor::pointer type;
-};
-
-template <class Cursor>
-struct cursor_difference {
-    typedef typename Cursor::difference_type type;
-};
-
-template <class Cursor>
-struct cursor_size {
-    typedef typename Cursor::size_type type;
-};
-
-template <class T>
-struct cursor_size<T*> {
-    typedef std::size_t type;
-};
-
-template <class Cursor>
-struct cursor_category {
-    typedef typename Cursor::cursor_category type;
-};
-
-template <class Cursor>
-struct cursor_horizontal_traversal {
-    typedef typename Cursor::horizontal_traversal type;
-};
-
-template <class Cursor>
-struct cursor_vertical_traversal {
-    typedef typename Cursor::vertical_traversal type;
-};
-
-template <class Cat, class T, class Dist = ptrdiff_t, class Size = size_t,
-          class Ptr = T*, class Ref = T&>
-struct cursor {
-    typedef Cat        cursor_category;
-    typedef T        value_type;
-    typedef Dist    difference_type;
-    typedef Size    size_type;
-    typedef Ptr        pointer;
-    typedef Ref        reference;    
-};
-
-// Deprecate?
-struct cursor_tag {};
-
-struct descending_tag {}; 
-struct descending_cursor_tag
-    : public cursor_tag, public descending_tag, 
-      public input_iterator_tag, public output_iterator_tag {};
-struct descending_forward_cursor_tag
-    : public cursor_tag, public descending_tag, public forward_iterator_tag {};
-struct descending_bidirectional_cursor_tag
-    : public cursor_tag, public descending_tag, public bidirectional_iterator_tag {};
-struct descending_random_access_cursor_tag
-    : public cursor_tag, public descending_tag, public random_access_iterator_tag {};
-
-struct ascending_tag {};
-struct ascending_cursor_tag
-    : public descending_cursor_tag, public ascending_tag {};
-struct ascending_forward_cursor_tag
-    : public descending_forward_cursor_tag, public ascending_tag {};
-struct ascending_bidirectional_cursor_tag
-    : public descending_bidirectional_cursor_tag, public ascending_tag {};
-struct ascending_random_access_cursor_tag
-    : public descending_random_access_cursor_tag, public ascending_tag {};
-
-/*
-template <class Hor, class Vert>
-struct produce_cursor_category;
-
-template <>
-struct produce_cursor_category<> {
-    typedef descending_cursor_tag type;
-};
-*/
-
-//define freestanding begin, end, size, empty using cursor's member fns?
-
 template <
     class OutputIterator
 //  , class Value                         
@@ -175,9 +67,9 @@
     typedef output_iterator_cursor<OutputIterator> value_type;
     typedef std::size_t size_type;
     typedef output_iterator_cursor<OutputIterator> const_cursor;
-    typedef forward_traversal_tag horizontal_traversal;
-    typedef bidirectional_traversal_tag vertical_traversal;
-    typedef forward_traversal_tag iterator_category;
+    typedef boost::forward_traversal_tag horizontal_traversal;
+    typedef boost::bidirectional_traversal_tag vertical_traversal;
+    typedef boost::forward_traversal_tag iterator_category;
     typedef std::ptrdiff_t difference_type;
     typedef value_type* pointer;
     typedef value_type& reference;
@@ -266,4 +158,4 @@
 } // namespace boost
 
 
-#endif // BOOST_TREE_CURSOR_HPP
+#endif // BOOST_TREE_OUTPUT_ITERATOR_CURSOR_HPP

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp	2008-12-19 12:00:05 EST (Fri, 19 Dec 2008)
@@ -63,7 +63,7 @@
     //BOOST_CHECK(next(inorder(), c, 2) == d);
     
     *c.to_parent() = 6;
-    validate_test_dataset1_tree(bt);
+    validate_test_dataset1_tree(bt.root());
 }
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

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	2008-12-19 12:00:05 EST (Fri, 19 Dec 2008)
@@ -128,23 +128,23 @@
 
 }
 
-template <class Tree>
-void validate_test_dataset2_tree(Tree const& mytree)
+template <class Cursor>
+void validate_test_dataset2_tree(Cursor cur)
 {
-    typename Tree::const_cursor c = mytree.root();
+    Cursor c = cur;
 
     BOOST_CHECK(!c.empty());
     
     c.to_begin();
-    BOOST_CHECK(c.parent() == mytree.root());
+    BOOST_CHECK(c.parent() == cur);
     BOOST_CHECK_EQUAL(*c, 14);
     
     c.to_begin();
-    BOOST_CHECK(c.parent() == mytree.root().begin());
+    BOOST_CHECK(c.parent() == cur.begin());
     BOOST_CHECK_EQUAL(*c, 2);
     
     ++c;
-    BOOST_CHECK(c.parent() == mytree.root().begin());
+    BOOST_CHECK(c.parent() == cur.begin());
     BOOST_CHECK_EQUAL(*c.begin(), 4);
     
 }
@@ -191,35 +191,35 @@
     
     // Filling with test data.
     create_test_dataset2_tree(tree1);
-    validate_test_dataset2_tree(tree1);
+    validate_test_dataset2_tree(tree1.root());
 
     // Swap tree1 with empty tree2
     swap(tree1, tree2);
-    validate_test_dataset2_tree(tree2);
+    validate_test_dataset2_tree(tree2.root());
     BOOST_CHECK(tree1.empty());
     
     // Swap back
     swap(tree1, tree2);
-    validate_test_dataset2_tree(tree1);
+    validate_test_dataset2_tree(tree1.root());
     BOOST_CHECK(tree2.empty());
     
     // Swap with tree containing different data
     swap(tree1, bt);
-    validate_test_dataset1_tree(tree1);
-    validate_test_dataset2_tree(bt);
+    validate_test_dataset1_tree(tree1.root());
+    validate_test_dataset2_tree(bt.root());
 }
 
 BOOST_AUTO_TEST_CASE( insert_subtree_test )
 {
     binary_tree<int> bt0;
     binary_tree<int>::cursor c = bt0.insert(bt0.root(), bt.root());    
-    validate_test_dataset1_tree(bt0);
+    validate_test_dataset1_tree(bt0.root());
 }
 
 BOOST_AUTO_TEST_CASE( copy_constructor_test )
 {
     binary_tree<int> bt0(bt);
-    validate_test_dataset1_tree(bt0);
+    validate_test_dataset1_tree(bt0.root());
 }
 
 BOOST_AUTO_TEST_CASE( comparison_operator_test )
@@ -235,7 +235,7 @@
     bt0.splice(bt0.root(), bt);
 
     BOOST_CHECK(bt.empty());    
-    validate_test_dataset1_tree(bt0);
+    validate_test_dataset1_tree(bt0.root());
 }
 
 BOOST_AUTO_TEST_CASE( binary_tree_test )

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-12-19 12:00:05 EST (Fri, 19 Dec 2008)
@@ -59,7 +59,7 @@
     BOOST_CHECK(bt != bt2);
     boost::tree::copy(Order(), bt.root(), bt2.root());
     BOOST_CHECK(bt == bt2);
-    validate_test_dataset1_tree(bt2);
+    validate_test_dataset1_tree(bt2.root());
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE ( test_desc_copy_using_insert_cursor, Order, orders )
@@ -69,7 +69,7 @@
     boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
                     , boost::forward_traversal_tag());
 
-    validate_test_dataset1_tree(bt2);
+    validate_test_dataset1_tree(bt2.root());
     BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
 }
 
@@ -80,7 +80,7 @@
     boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
                     , boost::bidirectional_traversal_tag());
 
-    validate_test_dataset1_tree(bt2);
+    validate_test_dataset1_tree(bt2.root());
     BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root())); 
 }
 
@@ -99,7 +99,7 @@
     BOOST_CHECK(bt != bt2);
     boost::tree::transform(Order(), bt.root(), bt2.root()
                          , std::bind2nd(std::minus<int>(),1));
-    validate_test_dataset1_minus_1_tree(bt2);
+    validate_test_dataset1_minus_1_tree(bt2.root());
 }
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

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-12-19 12:00:05 EST (Fri, 19 Dec 2008)
@@ -9,9 +9,82 @@
 
 #include <boost/tree/binary_tree.hpp>
 #include <boost/tree/algorithm.hpp>
-#include <boost/tree/cursor.hpp>
+#include <boost/tree/output_iterator_cursor.hpp>
+
+//#include <boost/array.hpp>
 
 #include <list>
+#include <vector>
+
+template <class T>
+struct mock_tree;
+
+template <class T>
+struct mock_tree {
+    mock_tree(T const& v = T()) : value(v), m(2) {}
+
+    typedef std::vector< mock_tree<T> > children_type;
+    
+    T value; 
+    children_type m;
+};
+
+template <class T>
+struct mock_tree_cursor {
+    typedef typename mock_tree<T>::children_type cur; 
+    cur c;
+    //bool pos;
+    
+    T const& operator*() const
+    {
+        return c->value;
+    }
+
+    T& operator*()
+    {
+        return c->value;
+    }
+    
+    void to_begin()
+    {
+        c = c->m.begin();
+    }
+    
+    void to_end()
+    {
+        c = c->m.end();
+    }
+    
+    mock_tree_cursor& operator++()
+    {
+        ++c;
+    }
+    
+    mock_tree_cursor& operator--()
+    {
+        --c;
+    }
+};
+
+mock_tree<int> mock_tree_data()
+{
+    mock_tree<int> mt;
+    
+    mt.m[0] = 8;
+    mt.m[0].m[0] = 3;
+    mt.m[0].m[0].m[0] = 1;
+    mt.m[0].m[1] = 6;
+    mt.m[0].m[1].m[0] = 4;
+    mt.m[0].m[1].m[1] = 7;
+
+    mt.m[0].m[1] = 10;
+    mt.m[0].m[1].m[1] = 14;
+    mt.m[0].m[1].m[1].m[0] = 13;
+    mt.m[0].m[1].m[1].m[0].m[0] = 11;
+    mt.m[0].m[1].m[1].m[0].m[0].m[1] = 12;
+
+    return mt;
+}
 
 template <class T = int>
 struct test_binary_tree_fixture {
@@ -51,36 +124,36 @@
         cur = ret.insert(++cur.to_begin(), value_type(12));
     }
     
-    static void validate_test_dataset1_tree(boost::tree::binary_tree<T>& ret)
+    static void validate_test_dataset1_tree(typename boost::tree::binary_tree<T>::const_cursor cur)
     {
-        BOOST_CHECK_EQUAL(*ret.root().begin(), 8);
-        BOOST_CHECK_EQUAL(*ret.root().begin().begin(), 3);    
-        BOOST_CHECK_EQUAL(*ret.root().begin().begin().begin(), 1);  //Leaf
-        BOOST_CHECK_EQUAL(*ret.root().begin().end().begin(), 6);        
-        BOOST_CHECK_EQUAL(*ret.root().begin().end().begin().begin(), 4); //Leaf
-        BOOST_CHECK_EQUAL(*ret.root().begin().end().end().begin(), 7); //Leaf
-    
-        BOOST_CHECK_EQUAL(*ret.root().end().begin(), 10);
-        BOOST_CHECK_EQUAL(*ret.root().end().end().begin(), 14);
-        BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin(), 13);
-        BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().begin(), 11); 
-        BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().end().begin(), 12); //Leaf
+        BOOST_CHECK_EQUAL(*cur.begin(), 8);
+        BOOST_CHECK_EQUAL(*cur.begin().begin(), 3);    
+        BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 1);  //Leaf
+        BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 6);        
+        BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4); //Leaf
+        BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7); //Leaf
+    
+        BOOST_CHECK_EQUAL(*cur.end().begin(), 10);
+        BOOST_CHECK_EQUAL(*cur.end().end().begin(), 14);
+        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 13);
+        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 11); 
+        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 12); //Leaf
     }
 
-    static void validate_test_dataset1_minus_1_tree(boost::tree::binary_tree<T>& ret)
+    static void validate_test_dataset1_minus_1_tree(typename boost::tree::binary_tree<T>::const_cursor cur)
     {
-        BOOST_CHECK_EQUAL(*ret.root().begin(), 7);
-        BOOST_CHECK_EQUAL(*ret.root().begin().begin(), 2);    
-        BOOST_CHECK_EQUAL(*ret.root().begin().begin().begin(), 0);  //Leaf
-        BOOST_CHECK_EQUAL(*ret.root().begin().end().begin(), 5);        
-        BOOST_CHECK_EQUAL(*ret.root().begin().end().begin().begin(), 3); //Leaf
-        BOOST_CHECK_EQUAL(*ret.root().begin().end().end().begin(), 6); //Leaf
-    
-        BOOST_CHECK_EQUAL(*ret.root().end().begin(), 9);
-        BOOST_CHECK_EQUAL(*ret.root().end().end().begin(), 13);
-        BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin(), 12);
-        BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().begin(), 10); 
-        BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().end().begin(), 11); //Leaf
+        BOOST_CHECK_EQUAL(*cur.begin(), 7);
+        BOOST_CHECK_EQUAL(*cur.begin().begin(), 2);    
+        BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 0);  //Leaf
+        BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 5);        
+        BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 3); //Leaf
+        BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 6); //Leaf
+    
+        BOOST_CHECK_EQUAL(*cur.end().begin(), 9);
+        BOOST_CHECK_EQUAL(*cur.end().end().begin(), 13);
+        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 12);
+        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 10); 
+        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 11); //Leaf
     }
     
     boost::tree::binary_tree<T> bt, bt2;