[Boost-commit] svn:boost r50442 - in sandbox/SOC/2006/tree/trunk/boost/tree: . detail detail/balancers detail/cursor

Subject: [Boost-commit] svn:boost r50442 - in sandbox/SOC/2006/tree/trunk/boost/tree: . detail detail/balancers detail/cursor
From: ockham_at_[hidden]
Date: 2009-01-02 14:29:42

Author: bernhard.reiter
Date: 2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
New Revision: 50442
URL: http://svn.boost.org/trac/boost/changeset/50442

Log:
Continue detail directory re-organization.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/multiway_cursor.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/node_traits.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp                 |     8 ++++----                                
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp  |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp      |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/multiway.hpp      |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp          |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp                 |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp               |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp                   |     8 ++++----                                
   9 files changed, 15 insertions(+), 15 deletions(-)

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-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -16,8 +16,8 @@
 #include <boost/tree/algorithm.hpp>
 #include <boost/tree/insert_cursor.hpp>
 
-#include <boost/tree/detail/node/traits.hpp>
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/node_traits.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
 
 #include <memory>
 
@@ -47,9 +47,9 @@
     
     typedef typename Alloc::template rebind<node_type>::other 
         node_allocator_type;
-    typedef typename node_traits<node_type>::node_base_type node_base_type;
+    typedef typename detail::node_traits<node_type>::node_base_type node_base_type;
     typedef node_base_type* node_base_pointer;
-    typedef typename node_traits<node_type>::node_pointer node_pointer;
+    typedef typename detail::node_traits<node_type>::node_pointer node_pointer;
     
  public:
     typedef ascending_nary_cursor<node_type> cursor;

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/red_black.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -11,7 +11,7 @@
 //TODO: lots.
 //templatize with bool add_data?
 
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
 
 namespace boost {
 namespace tree {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -13,7 +13,7 @@
 #ifndef BOOST_TREE_BALANCERS_TREAP_HPP
 #define BOOST_TREE_BALANCERS_TREAP_HPP
 
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
 
 #include <limits.h>
 #include <stdlib.h>

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -7,7 +7,7 @@
 #ifndef BOOST_TREE_BALANCERS_UNBALANCED_HPP
 #define BOOST_TREE_BALANCERS_UNBALANCED_HPP
 
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
 #include <boost/tree/inorder_algorithms.hpp>
 
 namespace boost {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/multiway.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/multiway.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/multiway.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -9,7 +9,7 @@
 #ifndef BOOST_TREE_DETAIL_CURSOR_MULTIWAY_HPP
 #define BOOST_TREE_DETAIL_CURSOR_MULTIWAY_HPP
 
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
 
 #include <boost/tree/cursor.hpp>
 #include <boost/tree/cursor_adaptor.hpp>

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	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -14,7 +14,7 @@
 
 #include <boost/tree/cursor.hpp>
 #include <boost/tree/cursor_adaptor.hpp>
-#include <boost/tree/detail/node/nary.hpp>
+#include <boost/tree/detail/nary_node.hpp>
 
 #include <boost/mpl/eval_if.hpp>
 #include <boost/mpl/identity.hpp>

Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,132 @@
+//  Copyright (c) 2006-2009, Bernhard Reiter
+//
+//  Distributed under the Boost Software License, Version 1.0.
+//  (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+/** 
+ * @file forest_cursor.hpp
+ * Forest cursor template
+ */
+
+#ifndef BOOST_TREE_DETAIL_FOREST_CURSOR_HPP
+#define BOOST_TREE_DETAIL_FOREST_CURSOR_HPP
+
+#include <boost/tree/cursor.hpp>
+#include <boost/tree/cursor_adaptor.hpp>
+
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/utility/enable_if.hpp>
+
+#include <iterator>
+#include <utility>
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+using boost::tree::cursor_core_access;
+using boost::iterator_core_access;
+
+template <class Cursor> 
+class forest_cursor
+: public cursor_adaptor<forest_cursor<Cursor>
+      , Cursor
+      , boost::use_default
+      , bidirectional_traversal_tag
+      , ascending_vertical_traversal_tag
+    > {
+
+private:
+    struct enabler {};
+
+public:
+     //TODO: Tidy up typedefs
+
+    typedef Cursor base_cursor;
+    
+    typedef forest_cursor<Cursor> cursor;
+    typedef forest_cursor<Cursor const> const_cursor; //FIXME (?)
+
+    //typedef typename cursor_size<base_cursor>::type size_type;
+
+    //typedef bidirectional_traversal_tag cursor_category;
+        
+    // Container-specific:
+    typedef cursor iterator;  // For (range) concepts' sake, mainly
+//    typedef const_cursor const_iterator;
+    
+     // Common iterator facade stuff
+    forest_cursor()
+     : forest_cursor::cursor_adaptor_() {}
+
+    explicit forest_cursor(base_cursor p)
+     : forest_cursor::cursor_adaptor_(p) {}
+      
+    template <class OtherCursor>
+    forest_cursor(
+        forest_cursor<OtherCursor> const& other
+      , typename boost::enable_if<
+            boost::is_convertible<OtherCursor*, 
+               typename Cursor::base_pointer>  // is that correct?
+          , enabler
+        >::type = enabler()
+    )
+      : forest_cursor::cursor_adaptor_(other.base()) {}
+
+    operator base_cursor()
+    {
+        return forest_cursor::cursor_adaptor_::base();
+    }
+    
+    Cursor const& base() const
+    {
+        return forest_cursor::cursor_adaptor_::base();
+    }
+private:
+    
+    friend class cursor_core_access;
+    friend class iterator_core_access;
+
+    bool empty_() const
+    {
+        return this->base().begin().empty() && this->base().end().empty();
+    }
+
+    typename forest_cursor::cursor_adaptor_::reference dereference() const
+    {
+        return *this->base_reference().begin();
+    }
+
+    void increment()
+    {
+        this->base_reference().to_end();
+    }
+    
+    void decrement()
+    {
+        this->base_reference().to_parent();
+    }
+    
+    // Range stuff.
+    
+    // left() remains unchanged, so no need to re-implement it.
+
+    void right()
+    {
+        to_forest_end(this->base_reference());
+    }
+    
+    // Cursor stuff. 
+    
+    void up()
+    {
+        to_forest_parent(this->base_reference());
+    }
+};
+
+} // namespace detail
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_FOREST_CURSOR_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/multiway_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/multiway_cursor.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,181 @@
+//  Copyright (c) 2006-2009, Bernhard Reiter
+//
+//  Distributed under the Boost Software License, Version 1.0.
+//  (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+/** 
+ * @file multiway_cursor.hpp
+ * Multiway cursor template
+ */
+
+#ifndef BOOST_TREE_DETAIL_MULTIWAY_CURSOR_HPP
+#define BOOST_TREE_DETAIL_MULTIWAY_CURSOR_HPP
+
+#include <boost/tree/detail/nary_cursor.hpp>
+
+#include <boost/tree/cursor.hpp>
+#include <boost/tree/cursor_adaptor.hpp>
+
+#include <boost/type_traits/is_convertible.hpp>
+#include <boost/utility/enable_if.hpp>
+
+#include <iterator>
+#include <utility>
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+template <class Cursor>
+class multiway_tree_cursor;
+
+template<class Cursor>
+class const_multiway_tree_cursor
+ : public cursor_adaptor<const_multiway_tree_cursor<Cursor>
+      , Cursor const
+      , boost::use_default
+      , bidirectional_traversal_tag
+      , descending_vertical_traversal_tag
+    > {
+ private:
+    struct enabler {};
+
+ public:
+     //TODO: Tidy up typedefs
+
+    typedef Cursor base_cursor;
+    
+     typedef multiway_tree_cursor<Cursor> cursor;
+     typedef const_multiway_tree_cursor<Cursor> const_cursor;
+
+    typedef typename cursor_size<base_cursor>::type size_type;
+
+    typedef bidirectional_traversal_tag cursor_category;
+    
+    typedef typename Cursor::metadata_type metadata_type;
+    
+    // Container-specific:
+    typedef cursor iterator;  // For (range) concepts' sake, mainly
+    typedef const_cursor const_iterator;
+    
+     // Common iterator facade stuff
+    const_multiway_tree_cursor()
+     : const_multiway_tree_cursor::cursor_adaptor_() {}
+
+    explicit const_multiway_tree_cursor(base_cursor p)
+     : const_multiway_tree_cursor::cursor_adaptor_(p) {}
+      
+    template <class OtherCursor>
+    const_multiway_tree_cursor(
+        const_multiway_tree_cursor<OtherCursor> const& other
+      , typename boost::enable_if<
+            boost::is_convertible<OtherCursor*, 
+               typename Cursor::base_pointer>  // is that correct?
+          , enabler
+        >::type = enabler()
+    )
+      : const_multiway_tree_cursor::cursor_adaptor_(other.base()) {}
+
+    operator base_cursor()
+    {
+        return this->base();
+    }
+
+ private:
+    
+    friend class boost::iterator_core_access;
+    
+    typename const_multiway_tree_cursor::cursor_adaptor_::reference dereference() const
+    {
+        return this->base()->m_parent->operator[](this->index());
+    }
+};
+
+template <class Cursor> 
+class multiway_tree_cursor
+ : public cursor_adaptor<multiway_tree_cursor<Cursor>
+      , Cursor
+      , boost::use_default
+      , bidirectional_traversal_tag
+      , descending_vertical_traversal_tag
+    > {
+ private:
+    struct enabler {};
+    friend class cursor_core_access;
+ public:
+     //TODO: Tidy up typedefs
+
+    typedef Cursor base_cursor;
+    
+     typedef multiway_tree_cursor<Cursor> cursor;
+     typedef const_multiway_tree_cursor<Cursor> const_cursor;
+
+    typedef typename cursor_size<base_cursor>::type size_type;
+
+    //typedef bidirectional_traversal_tag cursor_category;
+        
+    // Container-specific:
+    typedef cursor iterator;  // For (range) concepts' sake, mainly
+    typedef const_cursor const_iterator;
+    
+     // Common iterator facade stuff
+    multiway_tree_cursor()
+     : multiway_tree_cursor::cursor_adaptor_() {}
+
+    explicit multiway_tree_cursor(base_cursor p)
+     : multiway_tree_cursor::cursor_adaptor_(p) {}
+      
+    template <class OtherCursor>
+    multiway_tree_cursor(
+        multiway_tree_cursor<OtherCursor> const& other
+      , typename boost::enable_if<
+            boost::is_convertible<OtherCursor*, 
+               typename Cursor::base_pointer>  // is that correct?
+          , enabler
+        >::type = enabler()
+    )
+      : multiway_tree_cursor::cursor_adaptor_(other.base()) {}
+
+    operator base_cursor()
+    {
+        return this->base();
+    }
+
+
+ private:
+    
+    friend class boost::iterator_core_access;
+    
+    typename multiway_tree_cursor::cursor_adaptor_::reference dereference() const
+    {
+        return this->base()->m_parent->operator[](this->index());
+    }
+    
+public:
+    // Range stuff.
+//    cursor begin()
+//    {
+//        return cursor(this->base_reference().begin()); 
+//    }
+    
+//    const_cursor begin() const
+//    {
+//        return const_cursor(this->base_reference().begin()); 
+//    }        
+
+    // Cursor stuff. 
+    
+//    const_cursor parent() const
+//    {
+//        if (!this->base_reference().index())) {
+//            return this->base_reference().parent();
+//        }
+//    }
+};
+
+} // namespace detail
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_MULTIWAY_CURSOR_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,258 @@
+//  Copyright (c) 2006-2009, Bernhard Reiter
+//
+//  Distributed under the Boost Software License, Version 1.0.
+//  (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+/** 
+ * @file nary_cursor.hpp
+ * Nary cursor implementation
+ */
+
+#ifndef BOOST_TREE_DETAIL_NARY_CURSOR_HPP
+#define BOOST_TREE_DETAIL_NARY_CURSOR_HPP
+
+#include <boost/tree/cursor.hpp>
+#include <boost/tree/cursor_adaptor.hpp>
+#include <boost/tree/detail/nary_node.hpp>
+
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/type_traits/is_const.hpp>
+#include <boost/type_traits/add_const.hpp>
+#include <boost/type_traits/add_pointer.hpp>
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+using boost::iterator_core_access;
+using boost::tree::cursor_core_access;
+
+template <class Node> 
+class ascending_nary_cursor
+ : public cursor_adaptor<ascending_nary_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>
+                  , mpl::identity<typename Node::value_type>
+                >::type
+      , random_access_traversal_tag
+      , ascending_vertical_traversal_tag
+    > {
+
+private:
+    typedef typename Node::base_type node_base;
+      
+    typedef typename mpl::eval_if<
+                        is_const<Node>
+                      , add_const<node_base>
+                      , mpl::identity<node_base>
+                    >::type base_type;
+
+    typedef base_type* base_pointer;
+      
+    struct enabler {};
+     
+    typedef Node node_type;
+    typedef node_type* node_pointer;
+    
+public:
+    typedef typename mpl::eval_if<
+                        is_const<Node>
+                       , add_const<typename Node::value_type>
+                       , mpl::identity<typename Node::value_type>
+                    >::type value_type;
+
+    // Container-specific:
+    typedef typename ascending_nary_cursor::cursor_adaptor_::size_type size_type;
+
+    // Cursor-specific
+    typedef ascending_nary_cursor<node_type> cursor;
+    typedef ascending_nary_cursor<node_type const> const_cursor;
+    typedef std::size_t subtree_size_type;
+    
+    // Container-specific:
+    typedef cursor iterator;
+    typedef const_cursor const_iterator;
+    
+    template <class OtherValue>
+    struct rebind {
+        typedef ascending_nary_cursor<OtherValue> other;
+    };
+    
+    ascending_nary_cursor()
+      : ascending_nary_cursor::cursor_adaptor_(0), m_pos(0) {}
+
+    explicit ascending_nary_cursor(base_pointer p, size_type pos) 
+    : ascending_nary_cursor::cursor_adaptor_(p), m_pos(pos) {}
+
+    template <class OtherNode>
+    ascending_nary_cursor(
+        ascending_nary_cursor<OtherNode> const& other
+      , typename boost::enable_if<
+            boost::is_convertible<OtherNode*, node_type*>
+          , enabler
+        >::type = enabler()
+    )
+    : ascending_nary_cursor::cursor_adaptor_(other.base()), m_pos(other.m_pos) {}
+
+     size_type m_pos;
+
+private: 
+
+    friend class iterator_core_access;
+    friend class cursor_core_access;
+    
+    friend class access_detach;
+    
+    value_type& dereference() const
+    {
+        return **static_cast<node_type*>(this->base_reference());
+    }
+    
+    bool equal(cursor const& other) const
+    {
+        return (this->base_reference() == other.base_reference()) && (this->m_pos == other.m_pos);
+    }
+    
+    void increment()
+    {
+        ++m_pos;
+        // this->base_reference() += sizeof(node_type);
+    }
+    
+    void decrement()
+    {
+        --m_pos;
+        //this->base_reference() -= sizeof(node_type);
+    }    
+    
+    void advance(typename ascending_nary_cursor::cursor_facade_::difference_type n)
+    {
+        m_pos += n;
+        //this->base_reference() += n * sizeof(node_type);
+    }
+    
+    typename ascending_nary_cursor::cursor_facade_::difference_type
+    distance_to(ascending_nary_cursor z) const //FIXME: convertible to instead of ascending_nary_cursor
+    {
+        return (z.m_pos - this->m_pos);
+        //return (z.base_reference() - this->base_reference()) / sizeof(node_type); 
+    }
+    
+    // Container specific
+    bool empty_() const
+    {
+        return this->base_reference()->m_children[m_pos] == node_type::nil(); //->empty();
+        //return this->base_reference()->get_index();
+    }
+    
+    size_type size_() const
+    {
+        return this->base_reference()->m_children.size();
+    }
+    
+    size_type max_size_() const
+    {
+        return this->base_reference()->m_children.max_size();
+    }
+    
+    size_type idx() const
+    {
+        return m_pos;
+        //return 
+    }
+
+    void left()
+    {
+        this->base_reference() = this->base_reference()->m_children[m_pos];
+        m_pos  = 0;
+        //this->base_reference() = this->base_reference()->operator[0];
+    }
+
+    void right()
+    {
+        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;
+        //this->base_reference() = this->base_reference()->operator[0];
+    }
+
+    // Cursor stuff
+    void up()
+    {
+        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>(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 = this->base_reference();
+        
+        // Only forest-relevant:
+//        p_node->operator[](1) = this->base_reference()->operator[](m_pos);
+//        this->base_reference()->operator[](m_pos)->m_parent = p_node;
+        
+        this->base_reference()->m_children[m_pos] = p_node;
+    }
+
+//    /** 
+//     * Detaches the node this cursor points to and returns a pointer to it;
+//     * this cursor will be set to its inorder successor afterwards (?)
+//     */
+//    node_pointer detach()
+//    {
+//        return static_cast<node_pointer>(m_node->detach(m_pos));
+//    }
+//    
+//    node_pointer detach(cursor y)
+//    {
+//        return static_cast<node_pointer>(m_node->detach(m_pos, y.m_pos, y.m_node));
+//    }
+
+};
+
+} // namespace detail
+
+template <class Node>
+typename detail::ascending_nary_cursor<Node>::size_type
+index(detail::ascending_nary_cursor<Node> const& cur)
+{
+    return cur.index();
+}
+
+} // namespace tree
+} // namespace boost
+
+
+#endif // BOOST_TREE_DETAIL_NARY_CURSOR_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,262 @@
+//  Copyright (c) 2006-2009, Bernhard Reiter
+//
+//  Distributed under the Boost Software License, Version 1.0.
+//  (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+/** 
+ * @file nary_node.hpp
+ * Nary node implementation (with N=2, i.e. binary specialization)
+ */
+ 
+//Templatize with arity (so we can use this for multiway trees, too?)
+
+#ifndef BOOST_TREE_DETAIL_NARY_NODE_HPP
+#define BOOST_TREE_DETAIL_NARY_NODE_HPP
+
+#include <boost/array.hpp>
+
+#include <iterator>
+#include <utility>
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+using boost::array;
+
+//template <class T> struct binary_array : public array<T, 2> { };
+
+//struct node_base;
+/*
+ * node_with_parent_base
+ */
+ 
+class node_with_parent_base {
+//    typedef node_with_parent_base self_type;
+//    typedef self_type* base_pointer;
+//    typedef self_type const* const_base_pointer;
+
+public:
+    node_with_parent_base* m_parent; // TODO: protect?
+    
+    node_with_parent_base()
+    {
+        m_parent = this;
+    }
+    
+    node_with_parent_base(node_with_parent_base* p) : m_parent(p) {}
+    
+    node_with_parent_base* parent()
+    {
+        return m_parent;
+    }
+    
+    node_with_parent_base* const parent() const
+    {
+        return m_parent;
+    }
+};
+
+//template <template <typename> class Container>
+//class node_base;
+//
+//template <template <typename> class Container>
+//class node_base : public node_with_parent_base, public Container<node_base<Container>*> {
+//    typedef node_base<Container> self_type;
+//    
+//public:
+// 
+//    typedef Container<node_base<Container>*> base_type;
+//    typedef typename base_type::size_type size_type;
+//    typedef self_type* base_pointer;
+//    typedef self_type const* const_base_pointer;
+//    
+//    node_base() : node_with_parent_base()
+//    { }
+//    
+//    static base_pointer nil()
+//    {
+//        static self_type m_nil_obj;
+//        static base_pointer m_nil = &m_nil_obj;
+//        return m_nil;
+//    }
+//    
+//    void init()
+//    {
+//        for (typename base_type::size_type i=0; i<base_type::size(); ++i)
+//            operator[](i) = nil();
+//    }
+//
+//    // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
+//    bool const empty() const
+//    {
+//        return ((this == nil()) || this->base_type::empty());
+//    }
+//
+//    // O(n); n is number of parent's children
+//    typename base_type::size_type const get_index() const
+//    {
+//        typename base_type::size_type i = 0;
+//        while (static_cast<base_pointer>(this->m_parent)->base_type::operator[](i++) != this);
+//        return --i;
+//        //return (static_cast<base_pointer>(this->m_parent)->base_type::operator[](0) == this ? 0 : 1);
+//    }
+//};
+
+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_children_base {
+    typedef node_base self_type;
+    
+public:
+    //typedef node_with_children_base::base_type base_type;
+    typedef self_type* base_pointer;
+    typedef self_type const* const_base_pointer;
+        
+    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;
+        static base_pointer m_nil = &m_nil_obj;
+        return m_nil;
+    }
+    
+    void init()
+    {
+        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());
+//    }
+    
+    // Binary specific
+    
+    children_type::size_type rotate(children_type::size_type const& c)
+    {
+        //TODO: Optimise.
+        base_pointer q = m_children[c];
+        
+        base_pointer B = m_children[c]->m_children[(c ? 0 : 1)];
+        //pre_rotate();
+        
+        //B swaps places with its m_parent:
+
+        m_children[c] = B;
+        B->m_parent = this;
+        q->m_parent = this->m_parent;
+
+        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;
+        return qp;
+        //return (c ? 0 : 1);
+    }
+    
+    base_pointer detach(children_type::size_type m_pos)
+    {
+        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;
+    }
+    
+    // TODO: actually implement this.
+    base_pointer detach(children_type::size_type index, 
+                        children_type::size_type other_index, 
+                        base_pointer other)
+    {
+        //Node::pre_splice(q, r);
+        // splice out q
+        base_pointer x = detach(index);
+
+        // q has been spliced out, now relink it in place of r.                
+        static_cast<base_pointer>(other->m_parent)->m_children[other_index] = this;
+        m_parent = other->m_parent;
+
+        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;
+        }
+        return x;
+    }
+    
+    // O(1)
+    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 ascending_node : public node_base {
+ public:
+    typedef T value_type;
+
+    typedef ascending_node<value_type> node_type;
+    typedef node_type* node_pointer;
+    typedef node_type& node_reference;
+
+    typedef node_base base_type;
+    typedef base_type* base_pointer;
+    typedef base_type const* const_base_pointer;
+    
+    typedef value_type& reference;
+    typedef value_type const& const_reference;
+    typedef value_type* pointer;
+
+    //enum size_t { first = 0, second = 1 };
+    //typedef std::size_t size_type;
+        
+    // TODO: add observers.
+
+    reference operator*() { return *m_data; } 
+
+    const_reference operator*() const { return *m_data; } 
+    
+    ascending_node(pointer data) : base_type(), m_data(data) {}
+ 
+    ascending_node(pointer data, base_pointer p) : base_type(p), m_data(data) {}
+    
+    pointer data()
+    {
+        return m_data;
+    }
+    
+ private:
+    pointer m_data;
+};
+
+} // namespace detail
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_NARY_NODE_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/node_traits.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/node_traits.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,40 @@
+//  Copyright (c) 2006-2009, Bernhard Reiter
+//
+//  Distributed under the Boost Software License, Version 1.0.
+//  (See accompanying file LICENSE_1_0.txt or copy at
+//  http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_TREE_DETAIL_NODE_TRAITS_HPP
+#define BOOST_TREE_DETAIL_NODE_TRAITS_HPP
+
+namespace boost {
+namespace tree {
+namespace detail {
+
+template <class Node>
+struct node_traits
+{
+    typedef Node node_type;
+    
+    // Value
+    typedef typename node_type::value_type    value_type;
+    typedef typename node_type::pointer        pointer;
+    typedef typename node_type::reference    reference;
+    //typedef typename node_type::size_type    size_type;
+    
+    // Node
+    typedef typename node_type::node_pointer node_pointer;
+    typedef typename node_type::node_reference node_reference;
+    
+    // Node base
+    typedef typename node_type::base_type node_base_type;
+    typedef typename node_type::base_pointer node_base_pointer;
+    
+    typedef node_base_pointer position_type;
+};
+
+} // namespace detail
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_NODE_TRAITS_HPP

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -12,7 +12,7 @@
 #ifndef BOOST_TREE_FOREST_TREE_HPP
 #define BOOST_TREE_FOREST_TREE_HPP
 
-#include <boost/tree/detail/cursor/forest.hpp>
+#include <boost/tree/detail/forest_cursor.hpp>
 
 #include <boost/tree/binary_tree.hpp>
 #include <boost/tree/algorithm.hpp>

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -16,7 +16,7 @@
 //#include <boost/tree/cursor.hpp>
 //#include <boost/tree/binary_tree.hpp>
 
-#include <boost/tree/detail/cursor/multiway.hpp>
+#include <boost/tree/detail/multiway_cursor.hpp>
 
 #include <boost/tree/nary_tree.hpp>
 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp	2009-01-02 14:29:41 EST (Fri, 02 Jan 2009)
@@ -15,8 +15,8 @@
 
 #include <boost/tree/cursor.hpp>
 
-#include <boost/tree/detail/node/traits.hpp>
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/node_traits.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
 
 #include <memory>
 #include <vector>
@@ -65,9 +65,9 @@
     typedef ascending_node<value_type/*, mycontainer*/> node_type;
     typedef typename Alloc::template rebind<node_type>::other 
         node_allocator_type;
-    typedef typename node_traits<node_type>::node_base_type node_base_type;
+    typedef typename detail::node_traits<node_type>::node_base_type node_base_type;
     typedef node_base_type* node_base_pointer;
-    typedef typename node_traits<node_type>::node_pointer node_pointer;
+    typedef typename detail::node_traits<node_type>::node_pointer node_pointer;
     
     typedef ascending_nary_cursor<node_type> cursor;
     typedef ascending_nary_cursor<node_type const> const_cursor;