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

Subject: [Boost-commit] svn:boost r51837 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-03-18 10:12:24

Author: bernhard.reiter
Date: 2009-03-18 10:12:23 EDT (Wed, 18 Mar 2009)
New Revision: 51837
URL: http://svn.boost.org/trac/boost/changeset/51837

Log:
Add horizontal_reverse_cursor adaptor
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/horizontal_reverse_cursor.hpp
      - copied, changed from r51785, /sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp
   sandbox/SOC/2006/tree/trunk/libs/tree/test/horizontal_reverse_cursor_test.cpp
      - copied, changed from r51785, /sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                              |     1                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/horizontal_reverse_cursor.hpp          |   100 ++++++++++++--------------------------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2                         |     1                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/horizontal_reverse_cursor_test.cpp |    45 ++++++++++++------                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp               |     7 +-                                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp                 |     7 +-                                      
   6 files changed, 70 insertions(+), 91 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-03-18 10:12:23 EDT (Wed, 18 Mar 2009)
@@ -16,7 +16,6 @@
 General:
 * Do we need to_{left|right}most_ancestor?
 * Do we need multiway and plain cursor "flavor" tags (for algorithms)?
-* Add a (horizontal) reverse_cursor adaptor
 * Fix cursor archetype
 * In case of forest cursor, is_leaf() should really be empty().
 * Further reduce test data redundancy: make mock cursor use the data from fake_binary_tree, 

Copied: sandbox/SOC/2006/tree/trunk/boost/tree/horizontal_reverse_cursor.hpp (from r51785, /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/horizontal_reverse_cursor.hpp	2009-03-18 10:12:23 EDT (Wed, 18 Mar 2009)
@@ -5,12 +5,12 @@
 //  http://www.boost.org/LICENSE_1_0.txt)
 
 /** 
- * @file root_tracking_cursor.hpp
- * Root tracking cursor adaptor implementation
+ * @file horizontal_reverse_cursor.hpp
+ * Horizontal reverse cursor adaptor implementation
  */
 
-#ifndef BOOST_TREE_ROOT_TRACKING_CURSOR_HPP
-#define BOOST_TREE_ROOT_TRACKING_CURSOR_HPP
+#ifndef BOOST_TREE_HORIZONTAL_REVERSE_CURSOR_HPP
+#define BOOST_TREE_HORIZONTAL_REVERSE_CURSOR_HPP
 
 
 #include <boost/tree/cursor_adaptor.hpp>
@@ -26,23 +26,9 @@
 /** \addtogroup cursor_adaptors
  *  \@{ */
 
-/**
- * @brief Turns any cursor into an root tracking one. 
- * 
- * This wrapper tracks the cursor it is initially given as root.
- * When later descending and possibly re-ascending, it can thus
- * tell if any cursor reached via those operations is the root.
- * 
- * It works for any cursor, but doesn't make much sense
- * with descending ones as they will never re-ascend.
- * 
- * This adaptor is required for the treatment of subtrees - if we were only
- * requiring algorithms to work on entire trees (as in many textbooks),
- * we wouldn't really need such a device.
- */
 template <class Cursor> 
-class root_tracking_cursor
-: public cursor_adaptor<root_tracking_cursor<Cursor>
+class horizontal_reverse_cursor
+: public cursor_adaptor<horizontal_reverse_cursor<Cursor>
                       , Cursor 
 //                      , boost::use_default
 //                      , typename cursor_horizontal_traversal<Cursor>::type
@@ -50,16 +36,12 @@
     > {
 private:
     struct enabler {};
-    typedef root_tracking_cursor<Cursor> self_type;
+    typedef horizontal_reverse_cursor<Cursor> self_type;
 public:
-    typedef typename Cursor::value_type value_type;
-
-    // Container-specific:
-    typedef typename Cursor::size_type size_type;
 
     // Cursor-specific
-    typedef root_tracking_cursor<Cursor> cursor;
-    typedef root_tracking_cursor<typename Cursor::const_cursor> const_cursor;
+    typedef horizontal_reverse_cursor<Cursor> cursor;
+    typedef horizontal_reverse_cursor<typename Cursor::const_cursor> const_cursor;
     
     // Container-specific:
     typedef cursor iterator;
@@ -67,77 +49,57 @@
     
     template <class OtherCursor>
     struct rebind {
-        typedef root_tracking_cursor<OtherCursor> other;
+        typedef horizontal_reverse_cursor<OtherCursor> other;
     };
     
-    root_tracking_cursor()
-    : root_tracking_cursor::cursor_adaptor_(), m_depth(0) {}
+    horizontal_reverse_cursor()
+    : horizontal_reverse_cursor::cursor_adaptor_() {}
 
-    explicit root_tracking_cursor(Cursor c)
-    : root_tracking_cursor::cursor_adaptor_(c), m_depth(0) {}
+    explicit horizontal_reverse_cursor(Cursor c)
+    : horizontal_reverse_cursor::cursor_adaptor_(c) {}
 
 //    template <class OtherCursor>
-//    root_tracking_cursor(
-//        root_tracking_cursor<OtherCursor> const& other
+//    horizontal_reverse_cursor(
+//        horizontal_reverse_cursor<OtherCursor> const& other
 //      , typename boost::enable_if<
 //            boost::is_convertible<OtherCursor*, Cursor*>
 //          , enabler
 //        >::type = enabler()
 //    )
-//    : root_tracking_cursor::cursor_adaptor_(other.base())
+//    : horizontal_reverse_cursor::cursor_adaptor_(other.base())
 //    , m_depth(other.m_depth) {}
 
-    Cursor const& base() const
-    {
-        return this->base(); 
-    }
+//    Cursor const& base() const
+//    {
+//        return this->base(); 
+//    }
 
 private: 
     friend class boost::iterator_core_access;
     friend class boost::tree::cursor_core_access;
-     
-    std::size_t m_depth;
          
-//    bool equal(cursor const& other) const
-//    {
-//    }
-
-    void left()
+    void increment()
     {
-        ++m_depth;
-        this->base_reference().to_begin();
+        --this->base_reference();
     }
 
-    void right()
+    void decrement()
     {
-        ++m_depth;
-        this->base_reference().to_end();
+        ++this->base_reference();
     }
 
-    void up()
+    void left()
     {
-        --m_depth;
-        this->base_reference().to_parent();
+        this->base_reference().to_end();
     }
 
-    bool is_root_() const
+    void right()
     {
-        return !m_depth;
+        this->base_reference().to_begin();
     }
+
 };
 
-template <class Cursor>
-typename root_tracking_cursor<Cursor>::size_type
-index(root_tracking_cursor<Cursor> const& cur)
-{
-    return cur.index();
-}
-
-template <class Cursor>
-inline root_tracking_cursor<Cursor> track_root(Cursor c)
-{
-    return root_tracking_cursor<Cursor>(c);
-}
 
 /** @} */
 
@@ -145,4 +107,4 @@
 } // namespace boost
 
 
-#endif // BOOST_TREE_ROOT_TRACKING_CURSOR_HPP
+#endif // BOOST_TREE_HORIZONTAL_REVERSE_CURSOR_HPP

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	2009-03-18 10:12:23 EDT (Wed, 18 Mar 2009)
@@ -38,6 +38,7 @@
 #	[ run key_search_binary_tree_test.cpp ]	
 #	[ run rank_search_binary_tree_test.cpp ]
         [ run ascending_cursor_test.cpp ]
+	[ run horizontal_reverse_cursor_test.cpp ]
         [ run insert_cursor_test.cpp ]
         [ run algorithm_concepts_test.cpp ]	
         [ run cursor_algorithm_test.cpp ]

Copied: sandbox/SOC/2006/tree/trunk/libs/tree/test/horizontal_reverse_cursor_test.cpp (from r51785, /sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/horizontal_reverse_cursor_test.cpp	2009-03-18 10:12:23 EDT (Wed, 18 Mar 2009)
@@ -7,28 +7,43 @@
 #define BOOST_TEST_MODULE cursor_algorithm test
 #include <boost/test/included/unit_test.hpp>
 
-#include <boost/tree/ascending_cursor.hpp>
+#include <boost/tree/horizontal_reverse_cursor.hpp>
 
 #include "fake_binary_tree.hpp"
 
 using namespace boost::tree;
 
-BOOST_FIXTURE_TEST_SUITE( ascending_cursor_test, fake_binary_tree_fixture<int> )
+BOOST_FIXTURE_TEST_SUITE( horizontal_reverse_cursor_test, fake_binary_tree_fixture<int> )
 
-BOOST_AUTO_TEST_CASE( test_ascending_cursor )
+BOOST_AUTO_TEST_CASE( test_horizontal_reverse_cursor )
 {
-    typedef fake_binary_tree<int>::descending_cursor dc_t;
-    ascending_cursor<dc_t> ac = make_ascending_cursor(fbt1.descending_root());
-
-    ac.to_begin().to_end().to_begin().to_begin();
-
-    BOOST_CHECK_EQUAL(*ac, 4);
-    ac.to_parent();
-    BOOST_CHECK_EQUAL(*ac, 6);
-    ac.to_parent();
-    BOOST_CHECK_EQUAL(*ac, 3);
-    ac.to_parent();
-    BOOST_CHECK_EQUAL(*ac, 8);
+    horizontal_reverse_cursor<fake_binary_tree<int>::descending_cursor> cur(fbt1.root());
+    
+    // TODO: Also check ++ and -- operators!
+    
+    BOOST_CHECK_EQUAL(*cur.end(), 8);
+    BOOST_CHECK_EQUAL(*cur.end().end(), 3);
+    BOOST_CHECK_EQUAL(*cur.end().end().end(), 1);
+    BOOST_CHECK(cur.end().end().begin().is_leaf());
+    BOOST_CHECK(cur.end().end().end().is_leaf()); //Leaf
+    
+    BOOST_CHECK_EQUAL(*cur.end().begin().end(), 6);
+    BOOST_CHECK_EQUAL(*cur.end().begin().end().end(), 4);
+    BOOST_CHECK(cur.end().begin().end().end().is_leaf()); //Leaf
+
+    BOOST_CHECK_EQUAL(*cur.end().begin().begin().end(), 7);
+    BOOST_CHECK(cur.end().begin().begin().end().is_leaf()); //Leaf
+
+    BOOST_CHECK_EQUAL(*cur.begin().end(), 10);
+    BOOST_CHECK(cur.begin().end().is_leaf());
+    BOOST_CHECK_EQUAL(*cur.begin().begin().end(), 14);
+    BOOST_CHECK(cur.begin().begin().begin().is_leaf());
+    BOOST_CHECK_EQUAL(*cur.begin().begin().end().end(), 13);
+    BOOST_CHECK(cur.begin().begin().end().begin().is_leaf());
+    BOOST_CHECK_EQUAL(*cur.begin().begin().end().end().end(), 11);
+    BOOST_CHECK(cur.begin().begin().end().end().end().is_leaf()); 
+    BOOST_CHECK_EQUAL(*cur.begin().begin().end().end().begin().end(), 12);
+    BOOST_CHECK(cur.begin().begin().end().end().begin().end().is_leaf()); //Leaf
 }
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp	2009-03-18 10:12:23 EDT (Wed, 18 Mar 2009)
@@ -21,14 +21,15 @@
 
 BOOST_AUTO_TEST_CASE( test_rightmost )
 {
-    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
+    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root();
     to_rightmost(c);
-    BOOST_CHECK_EQUAL(*c, 14);
+    BOOST_CHECK(c.is_leaf());
+    BOOST_CHECK(c == fbt1.root_tracking_root().end().end().end());
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE( test_predecessor, Order, orders )
 {
-    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
+    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root();
     to_last(Order(), c);
     // Replace by a fake_to_first function for dependency minimization's sake?
     // preorder: fbt1.root_tracking_root().end().end().begin().begin().end().begin();

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp	2009-03-18 10:12:23 EDT (Wed, 18 Mar 2009)
@@ -19,14 +19,15 @@
 
 BOOST_AUTO_TEST_CASE( test_leftmost )
 {
-    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
+    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root();
     to_leftmost(c);
-    BOOST_CHECK_EQUAL(*c, 1);
+    BOOST_CHECK(c.is_leaf());
+    BOOST_CHECK(c == fbt1.root_tracking_root().begin().begin().begin());
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE( test_successor, Order, orders )
 {
-    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
+    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root();
     to_first(Order(), c);
     // Replace by a fake_to_first function for dependency minimization's sake?
     // preorder: fbt1.root_tracking_root().begin();