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

Subject: [Boost-commit] svn:boost r50702 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-21 12:02:55

Author: bernhard.reiter
Date: 2009-01-21 12:02:54 EST (Wed, 21 Jan 2009)
New Revision: 50702
URL: http://svn.boost.org/trac/boost/changeset/50702

Log:
Build output_iterator_cursor around cursor_facade (like mock_cursor)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                        |     1                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp               |     7 -                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/output_iterator_cursor.hpp       |   156 +++++++++++++-------------------------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp                |    58 +++-----------                          
   sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp         |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp       |     6 +                                       
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |    51 +++++++++++++                           
   7 files changed, 125 insertions(+), 156 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-01-21 12:02:54 EST (Wed, 21 Jan 2009)
@@ -14,7 +14,6 @@
 [section TODO]
 
 General:
-* Build output_iterator_cursor around cursor_facade (like mock_cursor)
 * Get rid of lists used for order checking. Use mock cursor instead.
 * Clean up binary_tree_test
 * binary_tree_search_test -> lower_bound_test

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp	2009-01-21 12:02:54 EST (Wed, 21 Jan 2009)
@@ -28,11 +28,6 @@
 
 using boost::iterator_core_access;
 
-class dummy {
-private:
-dummy() {}
-};
-
 // We'll abuse iterator_adaptor to determine our types.
 template <
     class Derived
@@ -144,7 +139,7 @@
     typedef typename cursor_facade_::difference_type difference_type;
     typedef typename cursor_facade_::size_type size_type;
  
-    cursor_adaptor() {}
+//    cursor_adaptor() {}
     
     explicit cursor_adaptor(Base const& cur) : m_cursor(cur)
     { }

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/output_iterator_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/output_iterator_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/output_iterator_cursor.hpp	2009-01-21 12:02:54 EST (Wed, 21 Jan 2009)
@@ -12,126 +12,76 @@
 #ifndef BOOST_TREE_OUTPUT_ITERATOR_CURSOR_HPP
 #define BOOST_TREE_OUTPUT_ITERATOR_CURSOR_HPP
 
+#include <boost/tree/cursor_facade.hpp>
 #include <boost/tree/cursor.hpp>
 
 namespace boost {
 namespace tree {
 
-template <
-    class OutputIterator
-//  , class Value                         
-//  , class HorizontalTraversalOrCategory 
-//  , class VerticalTraversal
-//  , class Reference                     
-//  , class Difference                
-//  , class Size                          
->
+template <class OutputIterator>
 class output_iterator_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 OutputIterator
-//  , class Value                         = use_default
-//  , class HorizontalTraversalOrCategory = use_default
-//  , class VerticalTraversal   = bidirectional_traversal_tag
-//  , class Reference                     = use_default
-//  , class Difference                    = use_default
-//  , class Size                          = use_default
+template <class OutputIterator>
+class output_iterator_cursor
+: public boost::tree::cursor_facade<
+        output_iterator_cursor<OutputIterator>
+      , output_iterator_cursor<OutputIterator>
+      , boost::bidirectional_traversal_tag
+      , boost::tree::ascending_vertical_traversal_tag
 >
-class output_iterator_cursor {
-protected:
-    OutputIterator* iter;
-//private:
-//    typedef iterator_adaptor<output_iterator_cursor<OutputIterator> 
-//                         , OutputIterator
-//                         , Value
-//                         , HorizontalTraversalOrCategory
-//                         , Reference
-//                         , Difference> ia_type;
+{
+private:
+    OutputIterator& m_iter;
 public:
-    /// Make the iterator type publicly accessible.
-    typedef OutputIterator iterator;
+    typedef output_iterator_cursor<OutputIterator> cursor;
+    typedef output_iterator_cursor<OutputIterator/* const*/> const_cursor;
+
+    typedef typename output_iterator_cursor<OutputIterator>::cursor_facade_::size_type size_type;
+    
+    output_iterator_cursor(OutputIterator& iter)
+    : m_iter(iter) {}
+
+    output_iterator_cursor(output_iterator_cursor<OutputIterator> const& other)
+    : m_iter(other.m_iter) {}
 
-    // FIXME: Very adhoc.
-    typedef output_iterator_cursor<OutputIterator> value_type;
-    typedef std::size_t size_type;
-    typedef output_iterator_cursor<OutputIterator> const_cursor;
-    typedef boost::forward_traversal_tag horizontal_traversal;
-    typedef boost::tree::ascending_vertical_traversal_tag vertical_traversal;
-    typedef boost::forward_traversal_tag iterator_category;
-    typedef std::ptrdiff_t difference_type;
-    typedef value_type* pointer;
-    typedef value_type& reference;
-        
-    /**
-     * For construction, we obviously need an Output Iterator to work on (i.e., write to).
-     */
-    explicit output_iterator_cursor(OutputIterator& i) : iter(&i) {}
-
-    /** 
-     * @param value A const& value of the value_type of container that iter is
-     *              associated with.
-     * @return      This cursor, for chained operations.
-     * Assigning a value to this cursor will insert it before iter, the iterator it is
-     * wrapped around.
-     * 
-     * Unfortunately, Output Iterators do not necessarily expose their
-     * value_type (they might just give back void), so the following assignment operator
-     * has to be a template.
-     */
-    // TODO: Consult C++0x if this has been changed
     template <class ValueType>
-    output_iterator_cursor& operator=(ValueType const& value)
-    { 
-        *((*iter)++) = value;
+    output_iterator_cursor&
+    operator=(ValueType const& val)
+    {
+        *m_iter++ = val;
         return *this; 
     }
-
-    /// Returns *this.
-    output_iterator_cursor& operator*() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& operator++() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor operator++(int) { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& operator--() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor operator--(int) { return *this; }
     
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& to_begin() { return *this; }
-    output_iterator_cursor& begin() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& to_end() { return *this; }
-    output_iterator_cursor& end() { return *this; }
-
-    /// Returns *this, as this %cursor doesn't "move".
-    output_iterator_cursor& to_parent() { return *this; }
-    output_iterator_cursor& parent() { return *this; }
+private:
+    friend class boost::iterator_core_access;
+    friend class boost::tree::cursor_core_access;
     
-    /// Returns true, in case an algorithm has a loop only terminating at root.
-    bool is_root() const { return true; }
+    typename output_iterator_cursor<OutputIterator>::cursor_facade_::reference
+    dereference() const
+    {
+        return const_cast< output_iterator_cursor<OutputIterator>& >(*this);
+    }
+
+    bool equal(output_iterator_cursor<OutputIterator> const& other) const
+    {
+        return m_iter == other.m_iter;
+    }
     
-    /// Returns true, in case an algorithm has a loop only terminating at a leaf.
-    bool empty() const { return true; }
+    bool const empty_() const
+    {
+        return true;
+    }
+
+    size_type const idx() const
+    {
+        return 0;
+    }
     
-    std::size_t const index() const { return 0; }
+    void increment() {}
+    void decrement() {}
+    void left() {}
+    void right() {}
+    void up() {}
 };
 
 template <class OutputIterator>

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp	2009-01-21 12:02:54 EST (Wed, 21 Jan 2009)
@@ -19,62 +19,30 @@
 using namespace boost::tree;
 
 BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test_with_fixture
-                       , fake_binary_tree_with_list_fixture<int>)
+                       , fake_binary_tree_fixture<int>)
 
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_descending, Order, orders)
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_descending, Order, orders )
 {
-    boost::tree::copy(Order(), fbt1.descending_root(), o);
-    test_traversal(Order(), l.begin(), l.end());
-}
-
-BOOST_AUTO_TEST_CASE( alternate_test_copy_descending )
-{
-    using std::make_pair;
     typedef std::vector< std::pair<std::size_t, int> > container_type;
     container_type po(11);
-    po[0] = make_pair(0, 8);
-    po[1] = make_pair(1, 3);
-    po[2] = make_pair(3, 1);
-    po[3] = make_pair(4, 6);
-    po[4] = make_pair(9, 4);
-    po[5] = make_pair(10, 7);
-    po[6] = make_pair(2, 10);
-    po[7] = make_pair(6, 14);
-    po[8] = make_pair(13, 13);
-    po[9] = make_pair(27, 11);
-    po[10] = make_pair(56, 12);
+    generate_mock_cursor_data(Order(), po);
     container_type::const_iterator ci = po.begin();
     container_type::const_iterator cie = po.end();
     mock_binary_cursor< container_type::const_iterator > mc(ci, cie);
     
-    boost::tree::copy(preorder(), fbt1.descending_root(), mc);
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_ascending, Order, orders)
-{
-    boost::tree::copy(Order(), fbt1.ascending_root(), o);
-    test_traversal(Order(), l.begin(), l.end());
-}
-
-BOOST_AUTO_TEST_SUITE_END()
-
-
-BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
-
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_trees_descending, Order, orders)
-{
-    BOOST_CHECK(fbt1 != fbt2);
-    boost::tree::copy(Order(), fbt1.descending_root(), fbt2.descending_root());
-    BOOST_CHECK(fbt1 == fbt2);
-    validate_test_dataset1_tree(fbt2.descending_root());
+    boost::tree::copy(Order(), fbt1.descending_root(), mc);
 }
 
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_trees_ascending, Order, orders)
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_ascending, Order, orders )
 {
-    BOOST_CHECK(fbt1 != fbt2);
-    boost::tree::copy(Order(), fbt1.ascending_root(), fbt2.ascending_root());
-    BOOST_CHECK(fbt1 == fbt2);
-    validate_test_dataset1_tree(fbt2.ascending_root());
+    typedef std::vector< std::pair<std::size_t, int> > container_type;
+    container_type po(11);
+    generate_mock_cursor_data(Order(), po);
+    container_type::const_iterator ci = po.begin();
+    container_type::const_iterator cie = po.end();
+    mock_binary_cursor< container_type::const_iterator > mc(ci, cie);
+    
+    boost::tree::copy(Order(), fbt1.ascending_root(), mc);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp	2009-01-21 12:02:54 EST (Wed, 21 Jan 2009)
@@ -226,7 +226,7 @@
     void up()
     {
         --this->base_reference().m_pos;
-        this->base_reference().m_pos >>= 1;
+        this->base_reference().m_pos /= 2;
     }
 
 public:

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp	2009-01-21 12:02:54 EST (Wed, 21 Jan 2009)
@@ -86,6 +86,12 @@
         ++m_pos;
         m_pos *= 2;
     }
+
+    void up()
+    {
+        --m_pos;
+        m_pos /= 2;
+    }
     
     bool const empty_() const
     {

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	2009-01-21 12:02:54 EST (Wed, 21 Jan 2009)
@@ -141,6 +141,57 @@
     BOOST_CHECK_EQUAL(*++c, 12);
 }
 
+template <class Container>
+void generate_mock_cursor_data(boost::tree::preorder, Container& data)
+{
+    using std::make_pair;
+    data[0] = make_pair(0, 8);
+    data[1] = make_pair(1, 3);
+    data[2] = make_pair(3, 1);
+    data[3] = make_pair(4, 6);
+    data[4] = make_pair(9, 4);
+    data[5] = make_pair(10, 7);
+    data[6] = make_pair(2, 10);
+    data[7] = make_pair(6, 14);
+    data[8] = make_pair(13, 13);
+    data[9] = make_pair(27, 11);
+    data[10] = make_pair(56, 12);
+}
+
+template <class Container>
+void generate_mock_cursor_data(boost::tree::inorder, Container& data)
+{
+    using std::make_pair;
+    data[0] = make_pair(3, 1);
+    data[1] = make_pair(1, 3);
+    data[2] = make_pair(9, 4); 
+    data[3] = make_pair(4, 6);
+    data[4] = make_pair(10, 7);
+    data[5] = make_pair(0, 8);
+    data[6] = make_pair(2, 10);
+    data[7] = make_pair(27, 11);
+    data[8] = make_pair(56, 12);
+    data[9] = make_pair(13, 13);
+    data[10] = make_pair(6, 14);
+}
+
+template <class Container>
+void generate_mock_cursor_data(boost::tree::postorder, Container& data)
+{
+    using std::make_pair;
+    data[0] = make_pair(3, 1);
+    data[1] = make_pair(9, 4);
+    data[2] = make_pair(10, 7);
+    data[3] = make_pair(4, 6);
+    data[4] = make_pair(1, 3);
+    data[5] = make_pair(56, 12);
+    data[6] = make_pair(27, 11);
+    data[7] = make_pair(13, 13);
+    data[8] = make_pair(6, 14);
+    data[9] = make_pair(2, 10);
+    data[10] = make_pair(0, 8);
+}
+
 template <class Iterator>
 void test_traversal(boost::tree::preorder, Iterator a, Iterator b) 
 {