Subject: [Boost-commit] svn:boost r50580 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-14 12:00:20
Author: bernhard.reiter
Date: 2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
New Revision: 50580
URL: http://svn.boost.org/trac/boost/changeset/50580
Log:
Add some tests.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 3 -
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 3 +
sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp | 20 +++++++++++-------
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 32 ++++++++++++++++++++---------
sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp | 12 +++++++---
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp | 43 +++++++++++++++++++++++++++++++++++++--
7 files changed, 87 insertions(+), 30 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -15,8 +15,6 @@
General:
* preorder_insert_cursor: hopefully easy to implement...
-* Fix binary tree/node: empty() -> root.begin() == root.end() !
-* Check forest/binary_tree correspondence in a hard wired fashion.
* Add checks for correspondence of concepts and archetypes!
* Re-do forest (again!). No root(); begin() and end() instead. No default element at
construction time (that would really suck). Rename forest_tree to forest,
@@ -146,6 +144,7 @@
* Optimise insert_cursor for use with binary_tree insert and copy ctor
(preorder copy; ideally, we can guarantee RAII for every single element)
and clear/dtor (postorder for_each).
+* Deprecate non-preorder insert cursors.
Ask on the mailing list:
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -197,7 +197,8 @@
void* node_hint = 0;
node_pointer p_node = m_node_alloc.allocate(1, node_hint);
- m_node_alloc.construct(p_node, val);
+ //m_node_alloc.construct(p_node, val);
+ *p_node = node_type(val);
p_node->init();
pos.attach(p_node);
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp 2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -67,8 +67,8 @@
forest_cursor(
forest_cursor<OtherCursor> const& other
, typename boost::enable_if<
- boost::is_convertible<OtherCursor*,
- typename Cursor::base_pointer> // is that correct?
+ boost::is_convertible<OtherCursor,
+ Cursor> // is that correct?
, enabler
>::type = enabler()
)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp 2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -93,8 +93,8 @@
*/
cursor begin()
{
- cursor c(h.root());
- return c.begin();
+ //cursor c(h.root());
+ return cursor(h.root());
}
/**
@@ -112,8 +112,8 @@
*/
const_cursor cbegin() const
{
- const_cursor c(h.croot());
- return c.begin();
+ //const_cursor c(h.croot());
+ return const_cursor(h.croot());
}
// TODO: end.
@@ -124,8 +124,10 @@
*/
cursor end()
{
- cursor c(h.root());
- return c.end();
+ base_cursor b(h.root());
+ while (!b.empty())
+ b.to_end();
+ return cursor(b);
}
/**
@@ -143,8 +145,10 @@
*/
const_cursor cend() const
{
- const_cursor c(h.croot());
- return c.end();
+ base_const_cursor b(h.croot());
+ while (!b.empty())
+ b.to_end();
+ return const_cursor(b);
}
/**
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp 2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -14,11 +14,12 @@
//#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
-
-BOOST_AUTO_TEST_SUITE( basic_binary_tree_test )
+#include "fake_binary_tree.hpp"
using boost::tree::binary_tree;
+BOOST_AUTO_TEST_SUITE( basic_binary_tree_test )
+
BOOST_AUTO_TEST_CASE( constructors_test )
{
binary_tree<int> bt0;
@@ -61,7 +62,25 @@
BOOST_AUTO_TEST_SUITE_END()
-BOOST_FIXTURE_TEST_SUITE(binary_tree_test, test_binary_tree_with_list_fixture<int>)
+BOOST_FIXTURE_TEST_SUITE( binary_tree_using_fake_binary_tree_test
+ , fake_binary_tree_fixture<int> )
+
+BOOST_AUTO_TEST_CASE( subtree_constructor_test )
+{
+ binary_tree<int> bt0(fbt1.root());
+ validate_test_dataset1_tree(bt0.root());
+}
+
+BOOST_AUTO_TEST_CASE( insert_subtree_test )
+{
+ binary_tree<int> bt0;
+ binary_tree<int>::cursor c = bt0.insert(bt0.root(), fbt1.root());
+ validate_test_dataset1_tree(bt0.root());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+BOOST_FIXTURE_TEST_SUITE( binary_tree_test, test_binary_tree_with_list_fixture<int> )
using namespace boost::tree;
@@ -208,13 +227,6 @@
validate_test_dataset2_tree(bt.root());
}
-BOOST_AUTO_TEST_CASE( insert_subtree_test )
-{
- binary_tree<int> bt0;
- binary_tree<int>::cursor c = bt0.insert(bt0.root(), bt.root());
- validate_test_dataset1_tree(bt0.root());
-}
-
BOOST_AUTO_TEST_CASE( copy_constructor_test )
{
binary_tree<int> bt0(bt);
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-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -75,6 +75,8 @@
descending_cursor insert(descending_cursor c, value_type const& v)
{
+ if (c.m_pos >= m_data.size())
+ m_data.resize(c.m_pos + 1);
m_data[c.m_pos] = v;
return c;
}
@@ -123,14 +125,16 @@
explicit fake_descending_binary_cursor(fake_binary_tree<T>& t, size_type p = 0)
: m_tree(t), m_pos(p) {}
-
-// explicit fake_descending_binary_cursor(fake_binary_tree<T> const& t, size_type p = 0)
-// : m_tree(t), m_pos(p) {}
fake_descending_binary_cursor(fake_descending_binary_cursor<T> const& other)
: m_tree(other.m_tree), m_pos(other.m_pos) {}
-// fake_descending_binary_cursor<T> operator=(fake_descending_binary_cursor<T> const&)
+ fake_descending_binary_cursor<T>& operator=(fake_descending_binary_cursor<T> const& other)
+ {
+ m_pos = other.m_pos;
+ return *this;
+ }
+
fake_binary_tree<T>& m_tree;
typename fake_binary_tree<T>::size_type m_pos;
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp 2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -20,6 +20,7 @@
#include <boost/test/test_case_template.hpp>
#include "test_tree_traversal_data.hpp"
+#include "fake_binary_tree.hpp"
using namespace boost::tree;
@@ -117,9 +118,45 @@
BOOST_AUTO_TEST_SUITE_END()
-//BOOST_FIXTURE_TEST_SUITE(forest_fixture_test, fake_binary_tree_with_list_fixture<int>)
-//
-//BOOST_AUTO_TEST_SUITE_END()
+BOOST_FIXTURE_TEST_SUITE(forest_fixture_test, fake_binary_tree_fixture<int>)
+
+BOOST_AUTO_TEST_CASE( binary_tree_constructor_test )
+{
+ forest_tree<int, fake_binary_tree<int> > ft0(fbt1);
+ forest_tree<int, fake_binary_tree<int> >::const_cursor c = ft0.begin();
+
+ //TODO: validate
+ BOOST_CHECK_EQUAL(*c, 8);
+ BOOST_CHECK_EQUAL(*c.to_begin(), 3);
+ BOOST_CHECK_EQUAL(*++c, 6);
+ BOOST_CHECK_EQUAL(*++c, 7);
+ BOOST_CHECK(++c == ft0.begin().end());
+
+ c = ft0.begin().begin();
+ BOOST_CHECK_EQUAL(*c.to_begin(), 1);
+ BOOST_CHECK(++c == ft0.begin().begin().end());
+
+ c = ft0.begin().begin();
+ ++c;
+ forest_tree<int, fake_binary_tree<int> >::const_cursor d = c;
+ BOOST_CHECK_EQUAL(*c.to_begin(), 4);
+ BOOST_CHECK(++c == d.end());
+
+ c = ft0.begin();
+ BOOST_CHECK_EQUAL(*++c, 10);
+ BOOST_CHECK_EQUAL(*++c, 14);
+ d = c;
+ BOOST_CHECK(++c == ft0.end());
+ c = d;
+ BOOST_CHECK_EQUAL(*c.to_begin(), 13);
+ BOOST_CHECK(++c == d.end());
+ c = d.to_begin();
+ BOOST_CHECK_EQUAL(*c.to_begin(), 11);
+ BOOST_CHECK_EQUAL(*++c, 12);
+ BOOST_CHECK(++c == d.end());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
//BOOST_FIXTURE_TEST_SUITE(forest_algorithms_test, test_binary_tree_with_list_fixture<int>)
//