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

Subject: [Boost-commit] svn:boost r49580 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/algorithm libs/tree/test
From: ockham_at_[hidden]
Date: 2008-11-03 18:17:15

Author: bernhard.reiter
Date: 2008-11-03 18:17:14 EST (Mon, 03 Nov 2008)
New Revision: 49580
URL: http://svn.boost.org/trac/boost/changeset/49580

Log:
Introduce coupling_cursor for use with iterative algorithms.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/coupling_cursor.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                      |     4 ++--                                    
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp |    18 +++++++++++-------                      
   sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp              |     8 ++++++--                                
   sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp  |     2 +-                                      
   4 files changed, 20 insertions(+), 12 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-11-03 18:17:14 EST (Mon, 03 Nov 2008)
@@ -16,8 +16,8 @@
 General:
 * Remove algorithm overloads for root_tracking_cursors, as track_root is a very
   context dependent thing; so merge it into the general iterative algorithm versions.
-* Get insert_cursor to work with linear (ascending cursor) algorithm
-  versions.
+* Get insert_cursor to work with linear (ascending cursor) inorder algorithm
+  version.
 * Move some of the secondary stuff to a util/ dir? Is that what they're used for?
 * Redo testing. Right now, it's just chaotic.
 * Fix recursive algorithms for use with forest.

Added: sandbox/SOC/2006/tree/trunk/boost/tree/coupling_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/coupling_cursor.hpp	2008-11-03 18:17:14 EST (Mon, 03 Nov 2008)
@@ -0,0 +1,135 @@
+//  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 coupling_cursor.hpp
+ * Coupling cursor implementation
+ */
+
+#ifndef BOOST_TREE_COUPLING_CURSOR_HPP
+#define BOOST_TREE_COUPLING_CURSOR_HPP
+
+#include <boost/tree/cursor_adaptor.hpp>
+
+namespace boost {
+namespace tree {
+
+using boost::iterator_core_access;
+
+template <class InCursor, class OutCursor>
+class coupling_cursor;
+
+/**
+ * @brief Output cursor wrapper around an output iterator.
+ * 
+ * This can be very useful e.g. to have cursor algorithms actually work on
+ * iterators, thus permitting some kind of linearization of a given subtree.
+ * (Modelled after std::insert_iterator and the like.)
+ * 
+ * For construction, the outputter_cursor_iterator_wrapper might come in useful
+ * in saving keystrokes.
+ */
+// TODO: Complete this.
+// Shouldn't we be using cursor_facade?
+template <class InCursor, class OutCursor>
+class coupling_cursor
+: public cursor_adaptor<coupling_cursor<InCursor, OutCursor>
+                      , InCursor
+//                      , boost::use_default
+//                      , boost::use_default
+//                      , boost::use_default
+    >
+ {
+protected:
+    mutable OutCursor m_out;
+public:        
+    /**
+     * For construction, we obviously need a tree and a cursor to work on (i.e., write to).
+     */
+    explicit coupling_cursor(InCursor i, OutCursor o)
+    : coupling_cursor::cursor_adaptor_(i), m_out(o) {}
+
+    // Cursor-specific
+    typedef coupling_cursor<InCursor, OutCursor> cursor;
+    typedef coupling_cursor<typename InCursor::const_cursor, OutCursor> const_cursor;
+
+//    operator InCursor() {
+//        return this->base_reference();
+//    }
+//
+
+// if InCursor != OutCursor
+//    operator OutCursor() {
+//        return m_out;
+//    }
+
+    InCursor& in()
+    {
+        return this->base_reference();
+    }
+
+    OutCursor& out()
+    {
+        return m_out;
+    }
+
+    bool is_root() const
+    {
+        return this->base_reference().is_root();
+    }
+    
+private:
+    friend class boost::iterator_core_access;
+    friend class boost::tree::cursor_core_access;
+    
+    void increment()
+    {
+        ++this->base_reference();
+        ++m_out;
+    }
+
+    void decrement()
+    {
+        --this->base_reference();
+        --m_out;
+    }
+    
+    void left()
+    {
+        this->base_reference().to_begin();
+        m_out.to_begin();
+    }
+    
+    void right()
+    {
+        this->base_reference().to_end();
+        m_out.to_end();
+    }
+    
+    void up()
+    {
+        this->base_reference().to_parent();
+        m_out.to_parent();
+    }
+};
+
+/** 
+ * @param o    An output iterator.
+ * @result    An instance of coupling_cursor working on o.
+ * 
+ * Use as shortcut for cumbersome typenames, just as with std::inserter and the like.
+ */
+template<class InCursor, class OutCursor>
+inline coupling_cursor<InCursor, OutCursor>
+make_coupling_cursor(InCursor i, OutCursor o)
+{
+    return coupling_cursor<InCursor, OutCursor>(i, o);
+}
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_COUPLING_CURSOR_HPP

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp	2008-11-03 18:17:14 EST (Mon, 03 Nov 2008)
@@ -14,6 +14,8 @@
 #ifndef BOOST_TREE_DETAIL_ALGORITHM_ITERATIVE_HPP
 #define BOOST_TREE_DETAIL_ALGORITHM_ITERATIVE_HPP
 
+#include <boost/tree/coupling_cursor.hpp>
+
 #include <boost/tree/detail/algorithm/preorder.hpp>
 #include <boost/tree/detail/algorithm/inorder.hpp>
 #include <boost/tree/detail/algorithm/postorder.hpp>
@@ -47,15 +49,17 @@
                                          , Op op)
 {
     root_tracking_cursor<InCursor> s2(s);
-    to_first(Order(), s);
+    
+    boost::tree::coupling_cursor< root_tracking_cursor<InCursor>, root_tracking_cursor<OutCursor> > cc(s, t);
+
+    to_first(Order(), cc);
     to_last(Order(), s2);
-    to_first(Order(), t);
-    while (s!=s2) {
-        *t = op(*s);
-        forward(Order(), s);
-        forward(Order(), t);
+
+    while (cc.in()!=s2) {
+        *cc.out() = op(*cc.in());
+        forward(Order(), cc);
     }
-    return t;
+    return cc.out();
 }
 
 template <class Order, class InCursor, class OutCursor, class Op>

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp	2008-11-03 18:17:14 EST (Mon, 03 Nov 2008)
@@ -53,6 +53,10 @@
     explicit insert_cursor(Tree& x, typename Tree::cursor cur)
     : insert_cursor::cursor_adaptor_(cur), tree(x), ins(false) {}
 
+    // Cursor-specific
+    typedef insert_cursor<typename Tree::cursor> cursor;
+    typedef insert_cursor<typename Tree::const_cursor> const_cursor;
+
 private:
     friend class boost::iterator_core_access;
     friend class boost::tree::cursor_core_access;
@@ -60,8 +64,8 @@
     typename insert_cursor::cursor_adaptor_::reference dereference() const
     {
         if (ins) {
-            const_cast<typename Tree::cursor&>(this->base_reference()) =
-            tree.insert(this->base_reference(), typename Tree::value_type());
+            const_cast<typename Tree::cursor&>(this->base_reference())
+            = tree.insert(this->base_reference(), typename Tree::value_type());
         }
         return *this->base_reference();
     }

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp	2008-11-03 18:17:14 EST (Mon, 03 Nov 2008)
@@ -49,8 +49,8 @@
     bt2.clear();
     l.clear();
     boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root()), boost::forward_traversal_tag());
-    boost::tree::copy(Order(), bt2.root(), o);
     validate_test_data_tree(bt2);
+    BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform, Order, orders)