Boost logo

Boost-Commit :

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();


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk