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

Subject: [Boost-commit] svn:boost r50397 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/cursor libs/tree/test
From: ockham_at_[hidden]
Date: 2008-12-29 08:55:43

Author: bernhard.reiter
Date: 2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
New Revision: 50397
URL: http://svn.boost.org/trac/boost/changeset/50397

Log:
Rename nary_tree_cursor to ascending_nary_cursor.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                  |    12 ++++++++++++                            
   sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp          |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp            |     6 +++---                                  
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp     |    36 ++++++++++++++++++------------------    
   sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp              |     6 +++---                                  
   sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp |    14 ++++++--------                          
   6 files changed, 43 insertions(+), 33 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -14,6 +14,12 @@
 [section TODO]
 
 General:
+* Remove a cursor's cursor, const_cursor, iterator and const_iterator typedefs?
+  The latter two only make sense in a range algorithm context, where they might actually be
+  useful. (The former two are just aliases for completeness' sake.)
+* Make Order the last (instead of first) parameter in algorithms? That way, we could
+  assume reasonable defaults while offering explicit choice (eg for size(), find(), 
+  maybe even copy(): default to preorder).
 * Rename node -> ascending_node; implement descending_node; and corresponding cursors.
 * Fix freestanding index() and members (esp. wrt cursor facade and adaptor!)
 * Redo all that balance(==balanced_tree)/searcher stuff. Avoid redundancy, that is, make them both use 
@@ -111,7 +117,13 @@
 * Start an RFC: what subtree algorithms should there be? In particular, of which of
   the STL's linear algorithms should there be a hierarchical version?
 
+Pre-release:
+* Cleanup headers/ #include dependencies.
+* Run Boost Inspect.
+
 Future: 
+* Exception safety?
+* Thread safety?
 * 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 --?

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp	2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -32,7 +32,7 @@
 namespace tree {
 
 using detail::node;
-using detail::nary_tree_cursor;
+using detail::ascending_nary_cursor;
 
 using detail::augmented_iterator;
 

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-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -25,7 +25,7 @@
 namespace tree {
 
 using detail::node;
-using detail::nary_tree_cursor;
+using detail::ascending_nary_cursor;
 
 // TODO: Remove shoot() remains (was m_header->m_parent)
 
@@ -52,8 +52,8 @@
     typedef typename node_traits<node_type>::node_pointer node_pointer;
     
  public:
-    typedef nary_tree_cursor<node_type> cursor;
-    typedef nary_tree_cursor<node_type const> const_cursor;
+    typedef ascending_nary_cursor<node_type> cursor;
+    typedef ascending_nary_cursor<node_type const> const_cursor;
 
     typedef typename allocator_type::pointer pointer;
     typedef typename allocator_type::reference reference;

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-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -29,8 +29,8 @@
 using boost::tree::cursor_core_access;
 
 template <class Node> 
-class nary_tree_cursor
- : public cursor_adaptor<nary_tree_cursor<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>
@@ -69,11 +69,11 @@
                     >::type value_type;
 
     // Container-specific:
-    typedef typename nary_tree_cursor::cursor_adaptor_::size_type size_type;
+    typedef typename ascending_nary_cursor::cursor_adaptor_::size_type size_type;
 
     // Cursor-specific
-    typedef nary_tree_cursor<node_type> cursor;
-    typedef nary_tree_cursor<node_type const> const_cursor;
+    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:
@@ -82,24 +82,24 @@
     
     template <class OtherValue>
     struct rebind {
-        typedef nary_tree_cursor<OtherValue> other;
+        typedef ascending_nary_cursor<OtherValue> other;
     };
     
-    nary_tree_cursor()
-      : nary_tree_cursor::cursor_adaptor_(0), m_pos(0) {}
+    ascending_nary_cursor()
+      : ascending_nary_cursor::cursor_adaptor_(0), m_pos(0) {}
 
-    explicit nary_tree_cursor(base_pointer p, size_type pos) 
-    : nary_tree_cursor::cursor_adaptor_(p), m_pos(pos) {}
+    explicit ascending_nary_cursor(base_pointer p, size_type pos) 
+    : ascending_nary_cursor::cursor_adaptor_(p), m_pos(pos) {}
 
     template <class OtherNode>
-    nary_tree_cursor(
-        nary_tree_cursor<OtherNode> const& other
+    ascending_nary_cursor(
+        ascending_nary_cursor<OtherNode> const& other
       , typename boost::enable_if<
             boost::is_convertible<OtherNode*, node_type*>
           , enabler
         >::type = enabler()
     )
-    : nary_tree_cursor::cursor_adaptor_(other.base()), m_pos(other.m_pos) {}
+    : ascending_nary_cursor::cursor_adaptor_(other.base()), m_pos(other.m_pos) {}
 
      size_type m_pos;
 
@@ -132,14 +132,14 @@
         //this->base_reference() -= sizeof(node_type);
     }    
     
-    void advance(typename nary_tree_cursor::cursor_facade_::difference_type n)
+    void advance(typename ascending_nary_cursor::cursor_facade_::difference_type n)
     {
         m_pos += n;
         //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
+    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); 
@@ -244,8 +244,8 @@
 } // namespace detail
 
 template <class Node>
-typename detail::nary_tree_cursor<Node>::size_type
-index(detail::nary_tree_cursor<Node> const& cur)
+typename detail::ascending_nary_cursor<Node>::size_type
+index(detail::ascending_nary_cursor<Node> const& cur)
 {
     return cur.index();
 }

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	2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -26,7 +26,7 @@
 namespace tree {
 
 using detail::node;
-using detail::nary_tree_cursor;
+using detail::ascending_nary_cursor;
 
 /** 
  * @brief An %nary_tree.
@@ -69,8 +69,8 @@
     typedef node_base_type* node_base_pointer;
     typedef typename node_traits<node_type>::node_pointer node_pointer;
     
-    typedef nary_tree_cursor<node_type> cursor;
-    typedef nary_tree_cursor<node_type const> const_cursor;
+    typedef ascending_nary_cursor<node_type> cursor;
+    typedef ascending_nary_cursor<node_type const> const_cursor;
 
 //    typedef iterator<inorder, , cursor> iterator;
 //    typedef iterator<inorder, , const_cursor> const_iterator;

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp	2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -5,17 +5,11 @@
 //  http://www.boost.org/LICENSE_1_0.txt)
 
 #include <boost/tree/binary_tree.hpp>
-#include <boost/tree/iterator.hpp>
-#include <boost/tree/algorithm.hpp>
+//#include <boost/tree/iterator.hpp>
+//#include <boost/tree/algorithm.hpp>
 
 #include <boost/tree/insert_cursor.hpp>
 
-//#include <boost/lambda/bind.hpp>
-
-//#include <list>
-//#include <algorithm>
-//#include <iterator>
-
 #define BOOST_TEST_MODULE cursor_algorithm test
 #include <boost/test/included/unit_test.hpp>
 #include <boost/test/test_case_template.hpp>
@@ -29,6 +23,10 @@
 
 BOOST_FIXTURE_TEST_SUITE(insert_cursor_test, test_binary_tree_fixture<int>)
 
+// Maybe suffix this by "_preorder", and add
+// emulated inorder and postorder versions, so
+// we can check whether insert_cursor works in all cases
+// without relying on algorithms. 
 template <class Cursor>
 void fill_subtree_with_data(Cursor cur)
 {