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

Subject: [Boost-commit] svn:boost r48985 - in sandbox/SOC/2006/tree/trunk/boost/tree: . detail/algorithm/cursor
From: ockham_at_[hidden]
Date: 2008-09-27 16:57:23

Author: bernhard.reiter
Date: 2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
New Revision: 48985
URL: http://svn.boost.org/trac/boost/changeset/48985

Log:
Outsource redundant cursor algorithms.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp                         |    24 +++++++++---                            
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order_iterative.hpp |    75 +++++++++++++++++++++++++++++++++++++-- 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp          |    75 +++++++++++---------------------------- 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp        |    73 ++++++++++++--------------------------  
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp         |    67 ++++++++++-------------------------     
   sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp                     |    24 ++++++------                            
   6 files changed, 165 insertions(+), 173 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp	2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -216,7 +216,7 @@
     struct enabler {};
     typedef root_tracking_cursor< ascending_cursor<Cursor> > self_type;
  public:
-      typedef typename ascending_cursor<Cursor>::value_type value_type;
+    typedef typename ascending_cursor<Cursor>::value_type value_type;
 
     // Container-specific:
     typedef typename ascending_cursor<Cursor>::size_type size_type;
@@ -245,18 +245,30 @@
     root_tracking_cursor(
         root_tracking_cursor< ascending_cursor<OtherCursor> > const& other
       , typename boost::enable_if<
-            boost::is_convertible<ascending_cursor<OtherCursor>*
-                                , ascending_cursor<Cursor>*>
+            boost::is_convertible<OtherCursor*
+                                , Cursor*>
           , enabler
         >::type = enabler()
     )
     : root_tracking_cursor::cursor_adaptor_(other.base())
-    , m_root_depth(other.base().m_s.size()) {}
+    , m_root_depth(other.m_root_depth) {}
+//
+//    template <class OtherCursor>
+//    root_tracking_cursor(
+//        root_tracking_cursor<OtherCursor> const& other
+//      , typename boost::enable_if<
+//            boost::is_convertible<OtherCursor*
+//                                , ascending_cursor<Cursor>*>
+//          , enabler
+//        >::type = enabler()
+//    )
+//    : root_tracking_cursor::cursor_adaptor_(other.base())
+//    , m_root_depth(other.base().m_s.size()) {}
 
  private: 
-     std::size_t const m_root_depth;
+    std::size_t const m_root_depth;
      
-     friend class boost::iterator_core_access;
+    friend class boost::iterator_core_access;
     friend class boost::tree::cursor_core_access;
          
 //    bool equal(cursor const& other) const

Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order.hpp	2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -0,0 +1,70 @@
+//  Copyright (c) 2006-2008, 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    _order.hpp
+ * 
+ * Some algorithm versions that are identical for all *order cursors 
+ * (as we are just calling the appropriate traversal function that are 
+ * defined in the respective *order.hpp files).
+ */
+
+// NO guards, as this is context-included!
+
+/**
+ * @brief   Successor
+ * @param c A cursor
+ * @param n Optional parameter to indicate how many steps to move forward
+ * @return  Successor of @a c
+ */
+template <class Cursor>
+inline Cursor next(Cursor c
+                 , typename Cursor::difference_type n = 1)
+{
+    for (; n!=0; --n)
+        forward(c);
+    return c;
+}
+
+/**
+ * @brief   Predecessor
+ * @param c A cursor
+ * @param n Optional parameter to indicate how many steps to move back
+ * @return  Predecessor of @a c
+ */
+template <class Cursor>
+inline Cursor prior(Cursor c
+                  , typename Cursor::difference_type n = 1)
+{
+    for (; n!=0; --n)
+        back(c);
+    return c;
+}
+
+/**
+ * @brief   First element of a subtree in preorder traversal
+ * @param c A cursor
+ * @return  Cursor to the first element of @a c in preorder traversal
+ */
+template <class Cursor>
+Cursor first(Cursor c)
+{
+    to_first(c);
+    return c;
+}
+
+/**
+ * @brief   One position past the last element of a subtree in preorder 
+ *          traversal
+ * @param c A cursor
+ * @return  Cursor one position past the last element of @a c in preorder
+ *          traversal
+ */
+template <class Cursor>
+Cursor last(Cursor c)
+{
+    to_last(c);
+    return c;
+}
\ No newline at end of file

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order_iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order_iterative.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order_iterative.hpp	2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -4,7 +4,7 @@
 //  (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
 
-/** @file    _order.hpp
+/** @file    _order_iterative.hpp
  * 
  * Some iterative algorithm versions that are identical for all *order cursors 
  * (as we are just calling the appropriate traversal function that are 
@@ -16,18 +16,85 @@
 template <class Cursor, class Op>
 Op for_each(root_tracking_cursor<Cursor> s, Op f)
 {
-    root_tracking_cursor<Cursor> t = last(s);
+    root_tracking_cursor<Cursor> s2 = last(s);
     s = first(s);
-    while (s!=t) {
+    while (s!=s2) {
         f(*s);
         forward(s);
     }
     return f;
 }
 
-
+/**
+ * @brief   Apply a function to every element of a subtree, in the given order.
+ * @param s A cursor.
+ * @param f A unary function object.
+ * @return  @p f
+ *
+ * Applies the function object @p f to each element in the @p subtree. 
+ * @p f must not modify the order of the sequence.
+ * If @p f has a return value it is ignored.
+ */
+//[ for_each
 template <class Cursor, class Op>
 Op for_each(Cursor s, Op f)
+//]
 {
     return for_each(root_tracking_cursor<Cursor>(s), f);
+}
+
+template <class InCursor, class OutCursor>
+OutCursor copy (root_tracking_cursor<InCursor> s, OutCursor t)
+{
+    root_tracking_cursor<InCursor> s2(last(s));
+    s = first(s);
+    while (s!=s2) {
+        *t = *s;
+        forward(s);
+    }
+    return t;
+}
+
+/**
+ * @brief   Copies the subtree s into t, by traversing s in the given order.
+ * @param s An input cursor.
+ * @param t An output cursor.
+ * @result  A cursor past t's *order end, after the copying operation.
+ */
+template <class InCursor, class OutCursor>
+OutCursor copy (InCursor s, OutCursor t)
+{
+    return copy(root_tracking_cursor<InCursor>(s), t);
+}
+
+template <class InCursor, class OutCursor, class Op>
+OutCursor transform (root_tracking_cursor<InCursor> s, OutCursor t, Op op)
+{
+    root_tracking_cursor<InCursor> s2(last(s));
+    s = first(s);
+    while (s!=s2) {
+        *t = op(*s);
+        forward(s);
+    }
+    return t;
+}
+
+/**
+ * @brief       Performs an operation on a subtree, by traversing it in 
+ *              the given order.
+ * @param s     An input cursor.
+ * @param t     An output cursor.
+ * @param op    A unary operation.
+ * @result      A cursor past t's preorder end, after the transforming has 
+ *              finished.
+ * 
+ * By traversing the input subtree s, apply the operation op 
+ * to each element and write the result to the output subtree t.
+ * 
+ * op must not change its argument.
+ */
+template <class InCursor, class OutCursor, class Op>
+OutCursor transform (InCursor s, OutCursor t, Op op)
+{
+    return transform(root_tracking_cursor<InCursor>(s), t, op);
 }
\ No newline at end of file

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp	2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -15,6 +15,7 @@
 #define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
 
 #include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
 
 #include <algorithm>
 
@@ -45,22 +46,6 @@
 }
 
 /**
- * @brief    Inorder successor
- * @param c    A cursor
- * @param n    Optional parameter to indicate how many steps to move forward
- * @return    Inorder successor of @a c
- * @ingroup    traversal
- */
-template <class MultiwayCursor>
-inline MultiwayCursor next(MultiwayCursor c
-                         , typename MultiwayCursor::difference_type n = 1)
-{
-    for (; n!=0; --n)
-        forward(c);
-    return c;
-}
-
-/**
  * @brief    Inorder predecessor
  * @param c    MultiwayCursor to be set to its inorder predecessor
  */
@@ -81,49 +66,35 @@
 }
 
 /**
- * @brief    Inorder predecessor
- * @param c    MultiwayCursor
- * @param n    Optional parameter to indicate how many steps to move back
- * @return    Inorder predecessor of @a c
- */
-template <class MultiwayCursor>
-inline MultiwayCursor prior(MultiwayCursor c
-                          , typename MultiwayCursor::difference_type n = 1)
-{
-    for (; n!=0; --n)
-        back(c);
-    return c;
-}
-
-/**
- * @brief    First element of a Multiway subtree in inorder traversal
- * @param c    A MultiwayCursor
- * @return    Cursor to the first element of @a c in inorder traversal
+ * @brief   First element of a subtree in inorder traversal
+ * @param c Subtree root cursor that will be set to the first inorder 
+ *          position in the subtree.
  */
-template <class MultiwayCursor>
-MultiwayCursor first(MultiwayCursor c)
+template <class Cursor>
+void to_first(Cursor& c)
 {
     while (!c.empty())
         c.to_begin();
-    return c;
 }
 
 /**
- * @brief    One position past the last element of a Multiway subtree in 
- *             inorder traversal
- * @param c    A MultiwayCursor
- * @return    Cursor one position past the last element of @a c in inorder
- *             traversal
- */
-template <class MultiwayCursor>
-MultiwayCursor last(MultiwayCursor c)
-{
-    return c;
-}
+ * @brief   One position past the last element of a subtree in inorder 
+ *          traversal
+ * @param c Subtree root cursor that will be set to the last inorder 
+ *          position in the subtree.
+ */
+template <class Cursor>
+void to_last(Cursor& c)
+{ }
+
+#include <boost/tree/detail/algorithm/cursor/_order.hpp>
 
 /*\@}*/
 
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
+//#else
+
 /**
  * @if maint
  * Helper function for for_each, using a reference parameter in order to
@@ -176,10 +147,6 @@
     return f;
 }
 
-#else
-#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
 /**
  * @brief    Copies the subtree s into t, by traversing s in inorder.
  * @param s    An input cursor.
@@ -239,6 +206,8 @@
     return t;
 }
 
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+
 /// Search
 
 /**

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp	2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -15,6 +15,7 @@
 #define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
 
 #include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
 
 namespace boost {
 namespace tree {
@@ -54,21 +55,6 @@
 }
 
 /**
- * @brief    Postorder successor
- * @param c    A cursor
- * @param n    Optional parameter to indicate how many steps to move forward
- * @return    Postorder successor of @a c
- */
-template <class Cursor>
-inline Cursor next(Cursor c
-                 , typename Cursor::difference_type n = 1)
-{
-    for (; n!=0; --n)
-        forward(c);
-    return c;
-}
-
-/**
  * @brief    Postorder predecessor
  * @param c    Cursor to be set to its postorder predecessor
  */
@@ -103,53 +89,42 @@
 }
 
 /**
- * @brief    Postorder predecessor
- * @param c    A cursor
- * @param n    Optional parameter to indicate how many steps to move back
- * @return    Postorder predecessor of @a c
- */
-template <class Cursor>
-inline Cursor prior(Cursor c
-                  , typename Cursor::difference_type n = 1)
-{
-    for (; n!=0; --n)
-        back(c);
-    return c;
-}
-
-/**
- * @brief    First element of a subtree in postorder traversal
- * @param c    A cursor
- * @return    Cursor to the first element of @a c in postorder traversal
+ * @brief   First element of a subtree in postorder traversal
+ * @param c Subtree root cursor that will be set to the first postorder 
+ *          position in the subtree.
  */
 template <class Cursor>
-Cursor first(Cursor c)
+void to_first(Cursor& c)
 {
     while (true)
         if (!c.empty())
             c.to_begin();
         else if (!(++c).empty())
             c.to_begin();
-        else
-            return --c;
+        else {
+            --c;
+            return;
+        }
 }
 
 /**
- * @brief    One position past the last element of a subtree in postorder 
- *             traversal
- * @param c    A cursor
- * @return    Cursor one position past the last element of @a c in 
- *             postorder traversal
+ * @brief   One position past the last element of a subtree in postorder 
+ *          traversal
+ * @param c Subtree root cursor that will be set to the last postorder 
+ *          position in the subtree.
  */
 template <class Cursor>
-Cursor last(Cursor c)
-{
-    return c;
-}
+void to_last(Cursor& c)
+{ }
+
+#include <boost/tree/detail/algorithm/cursor/_order.hpp>
 
 /*\@}*/
 
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
+//#else
+
 /**
  * @if maint
  * Helper function for for_each, using a reference parameter in order to
@@ -200,10 +175,6 @@
     return f;
 }
 
-#else
-#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
 /**
  * @brief    Copies the subtree s into t, by traversing s in postorder.
  * @param s    An input cursor.
@@ -264,6 +235,8 @@
     return t;
 }
 
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+
 } // namespace postorder
 
 } // namespace tree

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp	2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -15,6 +15,7 @@
 #define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
 
 #include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
 
 namespace boost {
 namespace tree {
@@ -61,21 +62,6 @@
 }
 
 /**
- * @brief    Preorder successor
- * @param c    A cursor
- * @param n    Optional parameter to indicate how many steps to move forward
- * @return    Preorder successor of @a c
- */
-template <class Cursor>
-inline Cursor next(Cursor c
-                 , typename Cursor::difference_type n = 1)
-{
-    for (; n!=0; --n)
-        forward(c);
-    return c;
-}
-
-/**
  * @brief    Preorder predecessor
  * @param c    Cursor to be set to its preorder predecessor
  */
@@ -106,47 +92,34 @@
 }
 
 /**
- * @brief    Preorder predecessor
- * @param c    A cursor
- * @param n    Optional parameter to indicate how many steps to move back
- * @return    Preorder predecessor of @a c
+ * @brief   First element of a subtree in preorder traversal
+ * @param c Subtree root cursor that will be set to the first preorder 
+ *          position in the subtree.
  */
 template <class Cursor>
-inline Cursor prior(Cursor c
-                  , typename Cursor::difference_type n = 1)
+void to_first(Cursor& c)
 {
-    for (; n!=0; --n)
-        back(c);
-    return c;
+    c.to_begin();
 }
 
 /**
- * @brief    First element of a subtree in preorder traversal
- * @param c    A cursor
- * @return    Cursor to the first element of @a c in preorder traversal
+ * @brief   One position past the last element of a subtree in preorder 
+ *          traversal
+ * @param c Subtree root cursor that will be set to the last preorder 
+ *          position in the subtree.
  */
 template <class Cursor>
-Cursor first(Cursor c)
-{
-    return c.begin();
-}
+void to_last(Cursor& c)
+{ }
 
-/**
- * @brief    One position past the last element of a subtree in preorder 
- *             traversal
- * @param c    A cursor
- * @return    Cursor one position past the last element of @a c in preorder
- *             traversal
- */
-template <class Cursor>
-Cursor last(Cursor c)
-{
-    return c;
-}
+#include <boost/tree/detail/algorithm/cursor/_order.hpp>
 
 /*\@}*/
 
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
+//#else
+
 /**
  * @if maint
  * Helper function for for_each, using a reference parameter in order to
@@ -197,10 +170,6 @@
     return f;
 }
 
-#else
-#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
 /**
  * @brief    Copies the subtree s into t, by traversing s in preorder.
  * @param s    An input cursor.
@@ -259,6 +228,8 @@
     return t;
 }
 
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+
 } // namespace preorder
 
 } // namespace tree

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp	2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -60,22 +60,22 @@
     explicit root_tracking_cursor(Cursor c)
     : root_tracking_cursor::cursor_adaptor_(c), m_depth(0) {}
 
-    template <class OtherCursor>
-    root_tracking_cursor(
-        root_tracking_cursor<OtherCursor> const& other
-      , typename boost::enable_if<
-            boost::is_convertible<OtherCursor*, Cursor*>
-          , enabler
-        >::type = enabler()
-    )
-    : root_tracking_cursor::cursor_adaptor_(other.base())
-    , m_depth(other.m_depth) {}
+//    template <class OtherCursor>
+//    root_tracking_cursor(
+//        root_tracking_cursor<OtherCursor> const& other
+//      , typename boost::enable_if<
+//            boost::is_convertible<OtherCursor*, Cursor*>
+//          , enabler
+//        >::type = enabler()
+//    )
+//    : root_tracking_cursor::cursor_adaptor_(other.base())
+//    , m_depth(other.m_depth) {}
 
  private: 
-     friend class boost::iterator_core_access;
+    friend class boost::iterator_core_access;
     friend class boost::tree::cursor_core_access;
      
-     std::size_t m_depth;
+    std::size_t m_depth;
          
 //    bool equal(cursor const& other) const
 //    {