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)
{