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

Subject: [Boost-commit] svn:boost r49959 - 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-11-27 11:31:49

Author: bernhard.reiter
Date: 2008-11-27 11:31:48 EST (Thu, 27 Nov 2008)
New Revision: 49959
URL: http://svn.boost.org/trac/boost/changeset/49959

Log:
Don't derive node from array -- give node an array member instead (has-a, not is-a).
Use cursor_adaptor instead of facade for nary cursor.
Rename output_cursor_iterator_wrapper again: output_iterator_cursor
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                        |     3 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp                  |   112 ++++++++++++++++++++--------------------
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp                       |    51 ++++++++++--------                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp           |    83 +++++++++++++++++------------           
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp             |    36 ++++++------                            
   sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp  |    36 ++++++++++++                            
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp         |    19 ++++++                                  
   sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp  |    19 +++---                                  
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |     2                                         
   9 files changed, 217 insertions(+), 144 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -16,6 +16,7 @@
 General:
 * Fix forest copy
 * Fix cursor archetypes: *order copy checks don't compile
+* Test insert_cursor independently of algorithms.
 * Implement forest_tree::insert_above.
 * Revisit namespaces.
 * Move some of the secondary stuff to a util/ dir? Is that what they're used for?
@@ -101,6 +102,7 @@
   the STL's linear algorithms should there be a hierarchical version?
 
 Future: 
+* Add cool constructors/assignment à la C++0x, ie (nested) parentheses or Boost.Assign.
 * Do we need cursors that are not iterators, ie that provide to_begin() and to_end 
   (and possibly to_parent()) operations, but not operator++() and --?
 * Optimise insert_cursor for use with binary_tree insert and copy ctor 
@@ -154,6 +156,7 @@
 
 Documentation:
 
+* Include examples output (requires some Jamfile tweaking)!
 * Add a tree visualisation of the documentation structure (as some kind of frontispiece)
   to the docs!
 * Add FAQ

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	2008-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -69,8 +69,8 @@
     explicit binary_tree (allocator_type const& alloc = allocator_type())
     : m_header(), m_value_alloc(alloc)
     {
-        m_header[0] = node_base_type::nil();
-        m_header[1] = &m_header;
+        m_header.m_children[0] = node_base_type::nil();
+        m_header.m_children[1] = &m_header;
     }
 
 //    explicit binary_tree (size_type n, value_type const& value = value_type(), 
@@ -83,8 +83,8 @@
             allocator_type const& alloc = allocator_type())
             : m_header(), m_value_alloc(alloc)
     {
-        m_header[0] = node_base_type::nil();
-        m_header[1] = &m_header;
+        m_header.m_children[0] = node_base_type::nil();
+        m_header.m_children[1] = &m_header;
 
         insert(root(), subtree);
     }
@@ -99,8 +99,8 @@
     binary_tree (self_type const& x)
     : m_header(), m_value_alloc(x.m_value_alloc)
     {
-        m_header[0] = node_base_type::nil();
-        m_header[1] = &m_header;
+        m_header.m_children[0] = node_base_type::nil();
+        m_header.m_children[1] = &m_header;
         
         if (!x.empty())
             insert(root(), x.root());
@@ -169,7 +169,7 @@
      */      
     cursor inorder_first()
     {
-        return cursor(m_header[1], 0);
+        return cursor(m_header.m_children[1], 0);
     }
     
     /**
@@ -185,7 +185,7 @@
      */      
     const_cursor inorder_cfirst() const
     {
-        return const_cursor(m_header[1], 0);
+        return const_cursor(m_header.m_children[1], 0);
     }
     
     /**
@@ -193,7 +193,7 @@
      */
     bool empty() const
     {
-        return m_header[1] == &m_header;
+        return m_header.m_children[1] == &m_header;
     }
     
     // Hierarchy-specific
@@ -222,7 +222,7 @@
 
         // Readjust begin
         if ((pos == this->inorder_first()))
-            m_header[1] = p_node; 
+            m_header.m_children[1] = p_node; 
 
         return pos; 
     }
@@ -316,7 +316,7 @@
 
          if (!position.empty()) {
              node_pointer pos_node = 
-                 static_cast<node_pointer>(position.m_node->operator[](position.m_pos));
+                 static_cast<node_pointer>(position.base_node()->m_children[position.m_pos]);
              // delete the value position points to    
              m_value_alloc.destroy(pos_node->data());
              m_value_alloc.deallocate(pos_node->data(), 1);
@@ -334,8 +334,8 @@
     void rotate(cursor& pos)
     {
         //TODO: Take care of inorder_first pointer!
-        pos.m_pos = pos.m_node->rotate(pos.m_pos);
-        pos.m_node = static_cast<node_base_pointer>(pos.m_node->m_parent->m_parent);
+        pos.m_pos = pos.base_node()->rotate(pos.m_pos);
+        pos.base_node() = static_cast<node_base_pointer>(pos.base_node()->m_parent->m_parent);
     }
     
     /**
@@ -352,37 +352,37 @@
             if (other.empty())
                 return;
                 
-            m_header[0] = other.m_header[0];
-            m_header[0]->m_parent = &m_header;
+            m_header.m_children[0] = other.m_header.m_children[0];
+            m_header.m_children[0]->m_parent = &m_header;
 
-            m_header[1] = other.m_header[1];
+            m_header.m_children[1] = other.m_header.m_children[1];
             //m_header.m_parent = other.m_header.m_parent;
             
-            other.m_header[0] = node_base_type::nil();
-            other.m_header[1] = &other.m_header;
+            other.m_header.m_children[0] = node_base_type::nil();
+            other.m_header.m_children[1] = &other.m_header;
             //other.m_header.m_parent = &other.m_header;
             
             return;
         }
         
         if (other.empty()) {
-            other.m_header[0] = m_header[0];
-            other.m_header[0]->m_parent = &other.m_header;
+            other.m_header.m_children[0] = m_header.m_children[0];
+            other.m_header.m_children[0]->m_parent = &other.m_header;
             
-            other.m_header[1] = m_header[1];
+            other.m_header.m_children[1] = m_header.m_children[1];
             //other.m_header.m_parent = m_header.m_parent;
             
-            m_header[0] = node_base_type::nil();
-            m_header[1] = &m_header;
+            m_header.m_children[0] = node_base_type::nil();
+            m_header.m_children[1] = &m_header;
             //m_header.m_parent = &m_header;
             
             return;            
         }
         
         swap(m_header, other.m_header);
-        //swap(m_header[0]->m_parent, other.m_header[0]->m_parent);
-        m_header[0]->m_parent = &m_header;
-        other.m_header[0]->m_parent = &other.m_header;
+        //swap(m_header.m_children[0]->m_parent, other.m_header.m_children[0]->m_parent);
+        m_header.m_children[0]->m_parent = &m_header;
+        other.m_header.m_children[0]->m_parent = &other.m_header;
         
         return;
     }
@@ -394,8 +394,8 @@
      {
          clear(this->root());
          m_header.m_parent = &m_header;
-         m_header[0] = node_base_type::nil();
-        m_header[1] = &m_header;
+         m_header.m_children[0] = node_base_type::nil();
+        m_header.m_children[1] = &m_header;
      }
      
     // splice operations
@@ -415,12 +415,12 @@
     {
         if (!x.empty()) {
             if (position == inorder_first()) // Readjust inorder_first to x's
-                m_header[1] = x.m_header[1];
+                m_header.m_children[1] = x.m_header.m_children[1];
                 
-            position.m_node->node_base_type::operator[](position.m_pos) = x.m_header[0];
+            position.base_node()->m_children[position.m_pos] = x.m_header.m_children[0];
             //TODO: replace the following by some temporary-swapping?
-            x.m_header[0] = node_base_type::nil();
-            x.m_header[1] = &x.m_header;
+            x.m_header.m_children[0] = node_base_type::nil();
+            x.m_header.m_children[1] = &x.m_header;
             x.m_header.m_parent = &x.m_header;
         }
     }
@@ -439,18 +439,18 @@
     {
         if (!x.empty()) {
             if (inorder_first == x.inorder_first())
-                x.m_header[1] = inorder_first.m_node;
+                x.m_header.m_children[1] = inorder_first.base_node();
             if (position == inorder_first()) // Readjust inorder_first to x's
-                m_header[1] = inorder_first.m_node;
+                m_header.m_children[1] = inorder_first.base_node();
                 
-            position.m_node->node_base_type::operator[](position.m_pos) = root.m_node;
+            position.base_node()->node_base_type::operator[](position.m_pos) = root.base_node();
             
-            root.m_node[0] = node_base_type::nil();
+            root.base_node()->m_children[0] = node_base_type::nil();
             if (root == x.root()) {
-                x.m_header[1] = &x.m_header;
+                x.m_header.m_children[1] = &x.m_header;
                 x.m_header.m_parent = &x.m_header;            
             } else
-                root.m_node[1] = node_base_type::nil();
+                root.base_node()->m_children[1] = node_base_type::nil();
         }        
     }
     
@@ -494,7 +494,7 @@
      */
     cursor inorder_erase(cursor position)
     {
-        node_pointer p_node = static_cast<node_pointer>(position.m_node);
+        node_pointer p_node = static_cast<node_pointer>(position.base_node());
         ++position;
         
         if (position.empty()) {                        
@@ -506,9 +506,9 @@
                 position = position.parent();
         } else {
             position = position.begin();
-            position.m_node->m_parent = p_node->m_parent;
+            position.base_node()->m_parent = p_node->m_parent;
             static_cast<node_base_pointer>(p_node->m_parent)
-                ->node_base_type::operator[](1) = position.m_node;
+                ->node_base_type::operator[](1) = position.base_node();
             
             while (!position.empty())
                 position = position.begin();
@@ -525,7 +525,7 @@
 
     cursor inorder_erase(cursor position, cursor descendant)
     {
-        node_pointer p_node = static_cast<node_pointer>(descendant.m_node);
+        node_pointer p_node = static_cast<node_pointer>(descendant.base_node());
         ++descendant;
         
         if (descendant.empty()) {                        
@@ -534,26 +534,26 @@
                 ->node_base_type::operator[](0) = (*p_node)[0];
         } else {
             descendant = descendant.begin();
-            descendant.m_node->m_parent = p_node->m_parent;
+            descendant.base_node()->m_parent = p_node->m_parent;
             static_cast<node_base_pointer>(p_node->m_parent)
-                ->node_base_type::operator[](1) = descendant.m_node;
+                ->node_base_type::operator[](1) = descendant.base_node();
         }
         
         cursor pos_parent = position.parent();        
-        pos_parent.m_node->node_base_type::operator[](pos_parent.m_pos)
-            = descendant.m_node;
-        descendant.m_node->m_parent = pos_parent.m_node;
-        descendant.m_node->node_base_type::operator[](0)
-            = position.m_node->node_base_type::operator[](0);
-        descendant.m_node->node_base_type::operator[](1)
-            = position.m_node->node_base_type::operator[](1);
-        descendant.m_node->node_base_type::operator[](0)->m_parent
-            = descendant.m_node;
-        descendant.m_node->node_base_type::operator[](1)->m_parent
-            = descendant.m_node;
+        pos_parent.base_node()->node_base_type::operator[](pos_parent.m_pos)
+            = descendant.base_node();
+        descendant.base_node()->m_parent = pos_parent.base_node();
+        descendant.base_node()->node_base_type::operator[](0)
+            = position.base_node()->node_base_type::operator[](0);
+        descendant.base_node()->node_base_type::operator[](1)
+            = position.base_node()->node_base_type::operator[](1);
+        descendant.base_node()->node_base_type::operator[](0)->m_parent
+            = descendant.base_node();
+        descendant.base_node()->node_base_type::operator[](1)->m_parent
+            = descendant.base_node();
 
         p_node = 
-            static_cast<node_pointer>(position.m_node->node_base_type::operator[](position.m_pos));
+            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);

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-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -58,6 +58,11 @@
     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;
@@ -129,7 +134,7 @@
 //  , class Difference                
 //  , class Size                          
 >
-class output_cursor_iterator_wrapper;
+class output_iterator_cursor;
 
 /**
  * @brief Output cursor wrapper around an output iterator.
@@ -152,11 +157,11 @@
 //  , class Difference                    = use_default
 //  , class Size                          = use_default
 >
-class output_cursor_iterator_wrapper {
+class output_iterator_cursor {
 protected:
     OutputIterator* iter;
 //private:
-//    typedef iterator_adaptor<output_cursor_iterator_wrapper<OutputIterator> 
+//    typedef iterator_adaptor<output_iterator_cursor<OutputIterator> 
 //                         , OutputIterator
 //                         , Value
 //                         , HorizontalTraversalOrCategory
@@ -167,9 +172,9 @@
     typedef OutputIterator iterator;
 
     // FIXME: Very adhoc.
-    typedef output_cursor_iterator_wrapper<OutputIterator> value_type;
+    typedef output_iterator_cursor<OutputIterator> value_type;
     typedef std::size_t size_type;
-    typedef output_cursor_iterator_wrapper<OutputIterator> const_cursor;
+    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;
@@ -180,7 +185,7 @@
     /**
      * For construction, we obviously need an Output Iterator to work on (i.e., write to).
      */
-    explicit output_cursor_iterator_wrapper(OutputIterator& i) : iter(&i) {}
+    explicit output_iterator_cursor(OutputIterator& i) : iter(&i) {}
 
     /** 
      * @param value A const& value of the value_type of container that iter is
@@ -195,38 +200,38 @@
      */
     // TODO: Consult C++0x if this has been changed
     template <class ValueType>
-    output_cursor_iterator_wrapper& operator=(ValueType const& value)
+    output_iterator_cursor& operator=(ValueType const& value)
     { 
         *((*iter)++) = value;
         return *this; 
     }
 
     /// Returns *this.
-    output_cursor_iterator_wrapper& operator*() { return *this; }
+    output_iterator_cursor& operator*() { return *this; }
 
     /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& operator++() { return *this; }
+    output_iterator_cursor& operator++() { return *this; }
 
     /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper operator++(int) { return *this; }
+    output_iterator_cursor operator++(int) { return *this; }
 
     /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& operator--() { return *this; }
+    output_iterator_cursor& operator--() { return *this; }
 
     /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper operator--(int) { return *this; }
+    output_iterator_cursor operator--(int) { return *this; }
     
     /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& to_begin() { return *this; }
-    output_cursor_iterator_wrapper& begin() { return *this; }
+    output_iterator_cursor& to_begin() { return *this; }
+    output_iterator_cursor& begin() { return *this; }
 
     /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& to_end() { return *this; }
-    output_cursor_iterator_wrapper& end() { return *this; }
+    output_iterator_cursor& to_end() { return *this; }
+    output_iterator_cursor& end() { return *this; }
 
     /// Returns *this, as this %cursor doesn't "move".
-    output_cursor_iterator_wrapper& to_parent() { return *this; }
-    output_cursor_iterator_wrapper& parent() { return *this; }
+    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; }
@@ -238,23 +243,23 @@
 };
 
 template <class OutputIterator>
-typename output_cursor_iterator_wrapper<OutputIterator>::size_type
-index(output_cursor_iterator_wrapper<OutputIterator> const& cur)
+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_cursor_iterator_wrapper working on o.
+ * @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_cursor_iterator_wrapper<OutputIterator>
+inline output_iterator_cursor<OutputIterator>
 outputter_cursor_iterator_wrapper(OutputIterator o)
 {
-    return output_cursor_iterator_wrapper<OutputIterator>(o);
+    return output_iterator_cursor<OutputIterator>(o);
 }
 
 } // namespace tree

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-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -12,10 +12,8 @@
 #ifndef BOOST_TREE_DETAIL_CURSOR_NARY_HPP
 #define BOOST_TREE_DETAIL_CURSOR_NARY_HPP
 
-
-#include <boost/tree/cursor_facade.hpp>
+#include <boost/tree/cursor_adaptor.hpp>
 #include <boost/tree/detail/node/nary.hpp>
-//#include <boost/tree/iterator.hpp>
 
 #include <boost/mpl/eval_if.hpp>
 #include <boost/mpl/identity.hpp>
@@ -32,7 +30,12 @@
 
 template <class Node> 
 class nary_tree_cursor
- : public cursor_facade<nary_tree_cursor<Node>
+ : public cursor_adaptor<nary_tree_cursor<Node>
+      , typename mpl::eval_if<
+                        is_const<Node>
+                      , add_const<typename Node::base_type>
+                      , mpl::identity<typename Node::base_type>
+                    >::type*                  
       , typename mpl::eval_if<
                     is_const<Node>
                   , add_const<typename Node::value_type>
@@ -67,7 +70,7 @@
                     >::type value_type;
 
     // Container-specific:
-    typedef typename node_type::size_type size_type;
+    typedef typename nary_tree_cursor::cursor_adaptor_::size_type size_type;
 
     // Cursor-specific
     typedef nary_tree_cursor<node_type> cursor;
@@ -84,10 +87,10 @@
     };
     
     nary_tree_cursor()
-      : m_node(0), m_pos(0) {}
+      : nary_tree_cursor::cursor_adaptor_(0), m_pos(0) {}
 
     explicit nary_tree_cursor(base_pointer p, size_type pos) 
-    : m_node(p), m_pos(pos) {}
+    : nary_tree_cursor::cursor_adaptor_(p), m_pos(pos) {}
 
     template <class OtherNode>
     nary_tree_cursor(
@@ -97,12 +100,11 @@
           , enabler
         >::type = enabler()
     )
-      : m_node(other.m_node), m_pos(other.m_pos) {}
+    : nary_tree_cursor::cursor_adaptor_(other.base()), m_pos(other.m_pos) {}
 
-     base_pointer m_node;
      size_type m_pos;
 
- private: 
+private: 
 
     friend class iterator_core_access;
     friend class cursor_core_access;
@@ -111,54 +113,54 @@
     
     value_type& dereference() const
     {
-        return **static_cast<node_type*>(m_node);
+        return **static_cast<node_type*>(this->base_reference());
     }
     
     bool equal(cursor const& other) const
     {
-        return (this->m_node == other.m_node) && (this->m_pos == other.m_pos);
+        return (this->base_reference() == other.base_reference()) && (this->m_pos == other.m_pos);
     }
     
     void increment()
     {
         ++m_pos;
-        // m_node += sizeof(node_type);
+        // this->base_reference() += sizeof(node_type);
     }
     
     void decrement()
     {
         --m_pos;
-        //m_node -= sizeof(node_type);
+        //this->base_reference() -= sizeof(node_type);
     }    
     
     void advance(typename nary_tree_cursor::cursor_facade_::difference_type n)
     {
         m_pos += n;
-        //m_node += n * sizeof(node_type);
+        //this->base_reference() += n * sizeof(node_type);
     }
     
     typename nary_tree_cursor::cursor_facade_::difference_type
     distance_to(nary_tree_cursor z) const //FIXME: convertible to instead of nary_tree_cursor
     {
         return (z.m_pos - this->m_pos);
-        //return (z.m_node - this->m_node) / sizeof(node_type); 
+        //return (z.base_reference() - this->base_reference()) / sizeof(node_type); 
     }
     
     // Container specific
     bool empty_() const
     {
-        return m_node->operator[](m_pos)->empty();
-        //return m_node->get_index();
+        return this->base_reference()->m_children[m_pos]->empty();
+        //return this->base_reference()->get_index();
     }
     
     size_type size_() const
     {
-        return m_node->size();
+        return this->base_reference()->m_children.size();
     }
     
     size_type max_size_() const
     {
-        return m_node->max_size();
+        return this->base_reference()->m_children.max_size();
     }
     
     size_type idx() const
@@ -169,48 +171,59 @@
 
     void left()
     {
-        m_node = m_node->operator[](m_pos);
+        this->base_reference() = this->base_reference()->m_children[m_pos];
         m_pos  = 0;
-        //m_node = m_node->operator[0];
+        //this->base_reference() = this->base_reference()->operator[0];
     }
 
     void right()
     {
-        size_type new_pos = m_node->size()-1; 
-        m_node = m_node->operator[](m_pos);
+        size_type new_pos = this->base_reference()->m_children.size()-1; 
+        this->base_reference() = this->base_reference()->m_children[m_pos];
         m_pos  = new_pos;
-        //m_node = m_node->operator[0];
+        //this->base_reference() = this->base_reference()->operator[0];
     }
 
     // Cursor stuff
     void up()
     {
-        m_pos  = m_node->get_index();
-        m_node = static_cast<base_pointer>(m_node->parent());
-        //m_node = m_node->parent();
+        m_pos  = this->base_reference()->get_index();
+        this->base_reference() = static_cast<base_pointer>(this->base_reference()->parent());
+        //this->base_reference() = this->base_reference()->parent();
     }
     
 protected:
     bool is_on_top() const
     {
         base_pointer parent_begin_node = 
-            static_cast<base_pointer>(m_node->parent())
-            ->operator[](m_node->get_index());
-        return (!m_pos && (m_node != parent_begin_node));
+            static_cast<base_pointer>(this->base_reference()->parent())
+            ->m_children[this->base_reference()->get_index()];
+        return (!m_pos && (this->base_reference() != parent_begin_node));
         // (*this != this->parent().begin())
     }
 
 public:
+    
+    base_pointer const& base_node() const
+    {
+        return this->base_reference();
+    }
+
+    base_pointer& base_node()
+    {
+        return this->base_reference();
+    }
+    
     // TODO: protect?
     void attach(node_pointer p_node)
     {
-        p_node->m_parent = m_node;
+        p_node->m_parent = this->base_reference();
         
         // Only forest-relevant:
-//        p_node->operator[](1) = m_node->operator[](m_pos);
-//        m_node->operator[](m_pos)->m_parent = p_node;
+//        p_node->operator[](1) = this->base_reference()->operator[](m_pos);
+//        this->base_reference()->operator[](m_pos)->m_parent = p_node;
         
-        m_node->operator[](m_pos) = p_node;
+        this->base_reference()->m_children[m_pos] = p_node;
     }
 
 //    /** 

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-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -109,7 +109,7 @@
 
 template <>
 class node_base<binary_array>
-: public node_with_parent_base, public binary_array<node_base<binary_array>*> {
+: public node_with_parent_base/*, public binary_array<node_base<binary_array>*>*/ {
     typedef node_base<binary_array> self_type;
     
 public:
@@ -118,6 +118,8 @@
     typedef self_type* base_pointer;
     typedef self_type const* const_base_pointer;
     
+    base_type m_children;
+    
     node_base() : node_with_parent_base()
     { }
     
@@ -131,7 +133,7 @@
     void init()
     {
         for (base_type::size_type i=0; i<base_type::max_size(); ++i)
-            operator[](i) = nil();
+            m_children[i] = nil();
     }
 
     // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
@@ -145,33 +147,33 @@
     base_type::size_type rotate(base_type::size_type const& c)
     {
         //TODO: Optimise.
-        base_pointer q = base_type::operator[](c);
+        base_pointer q = m_children[c];
         
-        base_pointer B = (base_type::operator[](c))->base_type::operator[](c ? 0 : 1);
+        base_pointer B = m_children[c]->m_children[(c ? 0 : 1)];
         //pre_rotate();
         
         //B swaps places with its m_parent:
 
-        base_type::operator[](c) = B;
+        m_children[c] = B;
         B->m_parent = this;
         q->m_parent = this->m_parent;
 
         base_type::size_type qp = get_index();
-        static_cast<base_pointer>(q->m_parent)->base_type::operator[](qp) = q;
+        static_cast<base_pointer>(q->m_parent)->m_children[qp] = q;
         this->m_parent = q;
-        q->base_type::operator[](c ? 0 : 1) = this;
+        q->m_children[(c ? 0 : 1)] = this;
         return qp;
         //return (c ? 0 : 1);
     }
     
     base_pointer detach(base_type::size_type m_pos)
     {
-        base_pointer q = base_type::operator[](m_pos);
-        base_type::operator[](m_pos) = 
-            base_type::operator[](m_pos)
-          ->base_type::operator[]((base_type::operator[](m_pos))
-          ->base_type::operator[](0) == node_base::nil() ? 1 : 0);
-        base_type::operator[](m_pos)->m_parent = this;
+        base_pointer q = m_children[m_pos];
+        m_children[m_pos] = 
+            m_children[m_pos]
+          ->m_children[((m_children[m_pos])
+          ->m_children[0] == node_base::nil() ? 1 : 0)];
+        m_children[m_pos]->m_parent = this;
         return q;
     }
     
@@ -185,12 +187,12 @@
         base_pointer x = detach(index);
 
         // q has been spliced out, now relink it in place of r.                
-        static_cast<base_pointer>(other->m_parent)->base_type::operator[](other_index) = this;
+        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) {
-            base_type::operator[](i) = other->base_type::operator[](i);
-            base_type::operator[](i)->m_parent = this;
+            m_children[i] = other->m_children[i];
+            m_children[i]->m_parent = this;
         }
         return x;
     }
@@ -198,7 +200,7 @@
     // O(1)
     base_type::size_type const get_index() const
     {
-        return (static_cast<base_pointer>(this->m_parent)->base_type::operator[](0) == this ? 0 : 1);
+        return (static_cast<base_pointer>(this->m_parent)->m_children[0] == this ? 0 : 1);
     }
     
 };

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/algorithm_concepts_test.cpp	2008-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -36,9 +36,41 @@
     boost::tree::for_each(Order(), c, f);
 }
 
+//BOOST_AUTO_TEST_CASE_TEMPLATE( test_std_copy, Order, orders )
+//{
+//    boost::detail::dummy_constructor dummy_cons;
+//    boost::iterator_archetype< boost::null_archetype<>
+//                      , boost::iterator_archetypes::readable_lvalue_iterator_t // Really lvalue?
+//                      , boost::forward_traversal_tag
+//                      > i;
+//    boost::iterator_archetype< boost::null_archetype<>
+//                      , boost::iterator_archetypes::writable_iterator_t // Really lvalue?
+//                      , boost::forward_traversal_tag
+//                      > o(dummy_cons);
+//    
+//    std::copy(i, i, o);
+//}
+
 //BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy, Order, orders )
 //{
 //    cursor_archetype< boost::null_archetype<>
+//                      , boost::iterator_archetypes::readable_iterator_t // Really lvalue?
+//                      , boost::forward_traversal_tag
+//                      , boost::forward_traversal_tag
+//                      > i;
+//    cursor_archetype< boost::assignable_archetype<>
+//                      , boost::iterator_archetypes::writable_iterator_t // Really lvalue?
+//                      , boost::forward_traversal_tag
+//                      , boost::forward_traversal_tag
+//                      > o;
+//    
+//    boost::tree::copy(Order(), i, o);
+//}
+
+//BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform, Order, orders )
+//{
+//    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
@@ -48,8 +80,10 @@
 //                      , boost::forward_traversal_tag
 //                      , boost::forward_traversal_tag
 //                      > o;
+//    boost::unary_function_archetype< boost::null_archetype<> , boost::null_archetype<> > 
+//      f(dummy_cons);
 //    
-//    boost::tree::copy(Order(), i, o);
+//    boost::tree::transform(Order(), i, o, f);
 //}
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

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-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -137,7 +137,7 @@
     
     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;
+    typedef output_iterator_cursor<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);
     
@@ -162,7 +162,7 @@
 //    
 //    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;
+//    typedef output_iterator_cursor<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);
 //    
@@ -170,7 +170,22 @@
 //    test_traversal(typename Order::second(), test_list.begin(), test_list.end());
 //    BOOST_CHECK_EQUAL(test_list.size(), 11);
 //    test_list.clear();
+//}
+
+//BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence_transform, Order
+//                             , corresponding_orders )
+//{
+//    using namespace boost::tree;
+//
+//    forest_tree<int> ft(bt);
 //    
+//    //validate_corresponding_forest_tree(ft);
+//    
+//    std::list<int> test_list;
+//    typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
+//    typedef output_iterator_cursor<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::transform(typename Order::first(), ft.root(), oc_test_list
 //                         , std::bind2nd(std::plus<int>(),0));
 //    test_traversal(typename Order::second(), test_list.begin(), test_list.end());

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp	2008-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -151,14 +151,15 @@
                       , end(Order(), make_ascending_cursor(bt.root()))), 11);
 }
 
-//BOOST_AUTO_TEST_CASE( test_ascending_iterator_algorithms )
-//{
-//    binary_tree<int>::cursor c = bt.root();
-//    typedef boost::tree::iterator<ascending, binary_tree<int>::cursor> ai;
-//    c.to_begin().to_end().to_begin().to_begin();
-//    BOOST_CHECK_EQUAL(*c, 4);
-//
-//    test_traversal_from_leaf4(ai(c), ai(bt.root()));
-//}
+BOOST_AUTO_TEST_CASE( test_ascending_iterator_algorithms )
+{
+    binary_tree<int>::cursor c = bt.root();
+    typedef boost::tree::root_tracking_cursor<binary_tree<int>::cursor> rtc;
+    typedef boost::tree::iterator<ascending, rtc> ai;
+    c.to_begin().to_end().to_begin().to_begin();
+    BOOST_CHECK_EQUAL(*c, 4);
+
+    test_traversal_from_leaf4(ai(rtc(c)), ai(rtc(bt.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-11-27 11:31:48 EST (Thu, 27 Nov 2008)
@@ -90,7 +90,7 @@
 struct test_binary_tree_with_list_fixture
 : public test_binary_tree_fixture<T> {
     typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
-    typedef boost::tree::output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
+    typedef boost::tree::output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
     
     test_binary_tree_with_list_fixture()
     : test_binary_tree_fixture<T>(), l(), i(l), o(i) { }