Subject: [Boost-commit] svn:boost r49664 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/example libs/tree/test
From: ockham_at_[hidden]
Date: 2008-11-09 10:46:20
Author: bernhard.reiter
Date: 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
New Revision: 49664
URL: http://svn.boost.org/trac/boost/changeset/49664
Log:
Start tidying up binary_tree_test.
Prepare usage of preorder copy/insert cursor within binary_tree subtree insert.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 6
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 3
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 10 +
sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp | 5 +
sandbox/SOC/2006/tree/trunk/libs/tree/example/for_each.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 173 +++++++++++++++++++--------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp | 21 +++-
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 39 ++++----
11 files changed, 138 insertions(+), 127 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -37,8 +37,7 @@
* Look into SOC 2008 projects dsearch (already using concepts from Boost.Tree) and
spacial_indexing (with tree classes of its own)
* Can't we really do without inorder_erase()?
-* Possibly rename *_recursive algorithms to *_with_references or so, and implement iterative versions.
-* Check if Cursor(balanced_tree_iterator) really has no is_root member()!
+* Check if Cursor(balanced_tree_iterator) really has no is_root member()! (BOOST_STATIC_ASSERT?)
* Revisit binary_tree (inorder::)iterator functions
* Possibly sort out some more concepts, like trees with "downwards" or "upwards" insertion
(insert()/insert_above()), trees with values only at the leaves (makes sense in combination
@@ -93,7 +92,7 @@
pp. 348--351). Those should be especially useful for automated testing of "real" (binary,
forest) trees.
* have `erase()` operations return cursor/iterator instead of void (as in new STD)
-* modify parity/parent specs according to newsgroup thread, but members add to binary_tree cursor!
+* modify parity/parent specs according to newsgroup thread, but add members to binary_tree cursor!
* We might need still more binary_tree members for more efficient functions operating on
ranges...
* `insert()` and `erase()` semantics need reworking. For instance, Proposal 23.X.4.1.4 §2
@@ -191,5 +190,6 @@
* Implement associative containers and priority_queue specialization using searcher
* Implement (binary) heap
* Is it possible to implement BGL's traversal algorithms using tree semantics?
+* Trie
[endsect]
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -53,7 +53,8 @@
value_type data;
metadata_type meta;
- augmented_type(value_type const& d, metadata_type const& m = metadata_type())
+ augmented_type(value_type const& d = value_type()
+ , metadata_type const& m = metadata_type())
: data(d), meta(m) {}
augmented_type(augmented_type const& x)
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 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -15,6 +15,7 @@
#include <boost/tree/cursor.hpp>
#include <boost/tree/iterator.hpp>
#include <boost/tree/algorithm.hpp>
+#include <boost/tree/insert_cursor.hpp>
#include <boost/tree/detail/node/traits.hpp>
#include <boost/tree/detail/cursor/nary.hpp>
@@ -160,7 +161,7 @@
*/
const_cursor croot() const
{
- return const_cursor(/*cursor(*/&m_header, 0/*)*/);
+ return const_cursor(&m_header, 0);
}
/**
@@ -242,7 +243,12 @@
template <class InputCursor>
cursor insert(cursor pos, InputCursor subtree)
{
- //boost::tree::copy(boost::tree::preorder(), subtree, pos, forward_traversal_tag());
+// // Optimise insert_cursor before using this
+// return cursor(boost::tree::copy(boost::tree::preorder()
+// , subtree
+// , boost::tree::tree_inserter(*this, pos)
+// , forward_traversal_tag()));
+
subtree.to_begin();
insert(pos, *subtree);
if (!subtree.empty())
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -56,6 +56,11 @@
typedef insert_cursor<typename Tree::cursor> cursor;
typedef insert_cursor<typename Tree::const_cursor> const_cursor;
+ operator typename Tree::cursor()
+ {
+ return this->base_reference();
+ }
+
private:
friend class boost::iterator_core_access;
friend class boost::tree::cursor_core_access;
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/example/for_each.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/example/for_each.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/example/for_each.cpp 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -25,7 +25,7 @@
binary_tree<int> bt;
// Fill it with data...
- create_test_data_tree(bt);
+ create_test_dataset1_tree(bt);
std::cout << "Preorder:";
preorder::for_each(bt.root(), to_cout);
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -63,7 +63,7 @@
//BOOST_CHECK(next(inorder(), c, 2) == d);
*c.to_parent() = 6;
- validate_test_data_tree(bt);
+ validate_test_dataset1_tree(bt);
}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
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 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -15,12 +15,12 @@
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
-BOOST_FIXTURE_TEST_SUITE(graph_algorithms_test, test_binary_tree_with_list_fixture<int>)
+BOOST_FIXTURE_TEST_SUITE(binary_tree_test, test_binary_tree_with_list_fixture<int>)
using namespace boost::tree;
template <class Tree>
-void create_binary_tree(Tree& mytree)
+void create_test_dataset2_tree(Tree& mytree)
{
typename Tree::cursor c, c1, c2, c3, c4;
@@ -33,9 +33,6 @@
BOOST_CHECK(!c.empty());
- BOOST_CHECK(c1.m_node->m_parent != 0);
- BOOST_CHECK(c1.m_node->m_parent != c1.m_node);
- BOOST_CHECK(c1.m_node->m_parent == c.m_node);
BOOST_CHECK(c1.parent() == c);
c2 = mytree.insert(c1, 2);
@@ -68,8 +65,6 @@
--c4;
BOOST_CHECK_EQUAL(*c4, 2);
BOOST_CHECK(c4.parent() == c1);
- c = boost::tree::lower_bound(mytree.root(), 2, std::less<int>());
- BOOST_CHECK_EQUAL(*c, 2);
BOOST_CHECK(c4.empty());
BOOST_CHECK_EQUAL(*c1, 14);
@@ -82,7 +77,28 @@
}
template <class Tree>
-void inorder_erase_test_data_tree(Tree& mytree)
+void validate_test_dataset2_tree(Tree const& mytree)
+{
+ typename Tree::const_cursor c = mytree.root();
+
+ BOOST_CHECK(!c.empty());
+
+ c.to_begin();
+ BOOST_CHECK(c.parent() == mytree.root());
+ BOOST_CHECK_EQUAL(*c, 14);
+
+ c.to_begin();
+ BOOST_CHECK(c.parent() == mytree.root().begin());
+ BOOST_CHECK_EQUAL(*c, 2);
+
+ ++c;
+ BOOST_CHECK(c.parent() == mytree.root().begin());
+ BOOST_CHECK_EQUAL(*c.begin(), 4);
+
+}
+
+template <class Tree>
+void inorder_erase_test_dataset1_tree(Tree& mytree)
{
typename Tree::cursor c = mytree.root().end().end().begin();
BOOST_CHECK_EQUAL(*c, 14);
@@ -109,119 +125,96 @@
BOOST_CHECK_EQUAL(*c, 13);
}
-template <class Tree>
-void destroy_binary_tree(Tree& mytree)
-{
- mytree.clear();
- BOOST_CHECK(mytree.empty());
-}
-
-template <class Tree>
-void validate_binary_tree(Tree const& mytree)
-{
- typename Tree::const_cursor c, c1, c2, c3, c4;
-
- c = mytree.root();
- BOOST_CHECK(!c.empty());
-
- c1 = c.begin();
- BOOST_CHECK(c1.parent() == c);
- BOOST_CHECK_EQUAL(*c1, 14);
-
- c2 = c1.begin();
- BOOST_CHECK(c2.parent() == c1);
- BOOST_CHECK_EQUAL(*c2, 2);
-
- c3 = c1.end();
- BOOST_CHECK(c3.parent() == c1);
- BOOST_CHECK_EQUAL(*c3.begin(), 4);
-
-}
-
-template <class Tree>
-void test_swap_binary_trees(Tree& one, Tree& two)
+BOOST_AUTO_TEST_CASE( clear_test )
{
- using std::swap;
- swap(one, two);
+ bt.clear();
+ BOOST_CHECK(bt.empty());
}
BOOST_AUTO_TEST_CASE( constructors_test )
{
- typedef binary_tree<int> tree_t;
- tree_t bt;
- BOOST_CHECK(bt.root().empty());
+ binary_tree<int> bt0;
+ BOOST_CHECK(bt0.root().empty());
//BOOST_CHECK_EQUAL(0, 1);
// test with allocator
}
-BOOST_AUTO_TEST_CASE( binary_tree_test )
+BOOST_AUTO_TEST_CASE( swap_binary_tree_test )
{
+ using std::swap;
typedef binary_tree<int> tree_t;
tree_t tree1, tree2;
// Filling with test data.
- create_binary_tree(tree1);
- validate_binary_tree(tree1);
+ create_test_dataset2_tree(tree1);
+ validate_test_dataset2_tree(tree1);
// Swap tree1 with empty tree2
- test_swap_binary_trees(tree1, tree2);
- validate_binary_tree(tree2);
+ swap(tree1, tree2);
+ validate_test_dataset2_tree(tree2);
BOOST_CHECK(tree1.empty());
-
+
// Swap back
- test_swap_binary_trees(tree1, tree2);
- validate_binary_tree(tree1);
+ swap(tree1, tree2);
+ validate_test_dataset2_tree(tree1);
BOOST_CHECK(tree2.empty());
- // Fill empty tree2 with different data
- //create_test_data_tree(tree2);
- validate_test_data_tree(bt);
- BOOST_CHECK(tree1 != bt);
-
- // Swap
- test_swap_binary_trees(tree1, bt);
- validate_test_data_tree(tree1);
- validate_binary_tree(bt);
-
- destroy_binary_tree(bt);
-
- // Insert subtree
- tree_t::cursor c = bt.insert(bt.root(), tree1.root());
- BOOST_CHECK_EQUAL(*c, 8);
- validate_test_data_tree(bt);
-
- // Copy constructor
- tree_t tree3(bt);
- validate_test_data_tree(tree3);
- BOOST_CHECK(bt == tree3);
-
- // Change one value in test_tree3
- c = tree3.root().begin().end().begin().begin();
+ // Swap with tree containing different data
+ swap(tree1, bt);
+ validate_test_dataset1_tree(tree1);
+ validate_test_dataset2_tree(bt);
+}
+
+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);
+}
+
+BOOST_AUTO_TEST_CASE( copy_constructor_test )
+{
+ binary_tree<int> bt0(bt);
+ validate_test_dataset1_tree(bt0);
+}
+
+BOOST_AUTO_TEST_CASE( comparison_operator_test )
+{
+ BOOST_CHECK(bt == bt2);
+}
+
+BOOST_AUTO_TEST_CASE( splice_test )
+{
+ binary_tree<int> bt0;
+ bt0.splice(bt0.root(), bt);
+
+ BOOST_CHECK(bt.empty());
+ validate_test_dataset1_tree(bt0);
+}
+
+BOOST_AUTO_TEST_CASE( binary_tree_test )
+{
+ binary_tree<int> bt0(bt);
+
+ // Change one value in bt0
+ binary_tree<int>::cursor c = bt0.root().begin().end().begin().begin();
int tmp = *c;
*c = tmp + 1;
- BOOST_CHECK(bt != tree3);
+ BOOST_CHECK(bt != bt0);
// Change it back
- c = tree3.root().begin().end().begin().begin();
+ c = bt0.root().begin().end().begin().begin();
*c = tmp;
- BOOST_CHECK(bt == tree3);
+ BOOST_CHECK(bt == bt0);
- c = tree3.inorder_first();
+ c = bt0.inorder_first();
BOOST_CHECK_EQUAL(*c, 1);
- c = tree3.root();
+ c = bt0.root();
//inorder::back(c);
//BOOST_CHECK_EQUAL(*c, 14);
-
- destroy_binary_tree(bt);
- bt.splice(bt.root(), tree3);
-
- BOOST_CHECK(tree3.empty());
- validate_test_data_tree(bt);
- c = bt.inorder_first();
- BOOST_CHECK_EQUAL(*c, 1);
- //inorder_erase_test_data_tree(bt);
+ //inorder_erase_test_dataset1_tree(bt);
}
BOOST_AUTO_TEST_CASE( rotate_binary_tree_test )
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -43,19 +43,26 @@
test_traversal(Order(), l.begin(), l.end());
}
-BOOST_AUTO_TEST_CASE_TEMPLATE ( test_inserter, Order, orders )
+BOOST_AUTO_TEST_CASE_TEMPLATE ( test_desc_copy_using_insert_cursor, Order, orders )
{
- //boost::unit_test::unit_test_log.set_threshold_level(boost::unit_test::log_messages ) ;
bt2.clear();
- boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root()), boost::forward_traversal_tag());
- validate_test_data_tree(bt2);
+ boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
+ , boost::forward_traversal_tag());
+
+ validate_test_dataset1_tree(bt2);
BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE ( test_asc_copy_using_insert_cursor, Order, orders )
+{
bt2.clear();
- boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root()));
- validate_test_data_tree(bt2);
- BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
+ boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
+ , boost::bidirectional_traversal_tag());
+
+ validate_test_dataset1_tree(bt2);
+ BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
}
BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform, Order, orders)
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 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -52,7 +52,7 @@
BOOST_CHECK_EQUAL(*c, 6);
tree_type forest;
- //create_test_data_tree(forest);
+ //create_test_dataset1_tree(forest);
c = forest.insert(forest.root(), 8);
BOOST_CHECK(c == forest.root().begin());
BOOST_CHECK_EQUAL(*c, 8);
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -34,7 +34,7 @@
typedef tree_type::cursor cursor;
//tree_type test_tree;
- //create_test_data_tree(test_tree);
+ //create_test_dataset1_tree(test_tree);
std::list<int> test_list;
typedef std::back_insert_iterator< std::list<int> > bi_list_int_type;
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 2008-11-09 10:46:19 EST (Sun, 09 Nov 2008)
@@ -17,8 +17,8 @@
struct test_binary_tree_fixture {
test_binary_tree_fixture()
{
- create_test_data_tree(bt);
- create_test_data_tree(bt2);
+ create_test_dataset1_tree(bt);
+ create_test_dataset1_tree(bt2);
typename boost::tree::binary_tree<T>::cursor d = bt2.root();
@@ -33,7 +33,7 @@
// (With two additional nodes: 11 inserted left of 13; 12 right of 11)
// and in combination with http://en.wikipedia.org/wiki/Tree_traversal#Examples
// (as tree shapes are equal [apart from the extra nodes])
- static void create_test_data_tree(boost::tree::binary_tree<T>& ret)
+ static void create_test_dataset1_tree(boost::tree::binary_tree<T>& ret)
{
// For augmented trees. (Why is this necessary? Nothing here is explicit!)
typedef typename boost::tree::binary_tree<T>::value_type value_type;
@@ -51,6 +51,22 @@
cur = ret.insert(++cur, value_type(12));
}
+ static void validate_test_dataset1_tree(boost::tree::binary_tree<T>& ret)
+ {
+ BOOST_CHECK_EQUAL(*ret.root().begin(), 8);
+ BOOST_CHECK_EQUAL(*ret.root().begin().begin(), 3);
+ BOOST_CHECK_EQUAL(*ret.root().begin().begin().begin(), 1); //Leaf
+ BOOST_CHECK_EQUAL(*ret.root().begin().end().begin(), 6);
+ BOOST_CHECK_EQUAL(*ret.root().begin().end().begin().begin(), 4); //Leaf
+ BOOST_CHECK_EQUAL(*ret.root().begin().end().end().begin(), 7); //Leaf
+
+ BOOST_CHECK_EQUAL(*ret.root().end().begin(), 10);
+ BOOST_CHECK_EQUAL(*ret.root().end().end().begin(), 14);
+ BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin(), 13);
+ BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().begin(), 11);
+ BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().end().begin(), 12); //Leaf
+ }
+
boost::tree::binary_tree<T> bt, bt2;
};
@@ -69,23 +85,6 @@
};
template <class Tree>
-void validate_test_data_tree(Tree const& ret)
-{
- BOOST_CHECK_EQUAL(*ret.root().begin(), 8);
- BOOST_CHECK_EQUAL(*ret.root().begin().begin(), 3);
- BOOST_CHECK_EQUAL(*ret.root().begin().begin().begin(), 1); //Leaf
- BOOST_CHECK_EQUAL(*ret.root().begin().end().begin(), 6);
- BOOST_CHECK_EQUAL(*ret.root().begin().end().begin().begin(), 4); //Leaf
- BOOST_CHECK_EQUAL(*ret.root().begin().end().end().begin(), 7); //Leaf
-
- BOOST_CHECK_EQUAL(*ret.root().end().begin(), 10);
- BOOST_CHECK_EQUAL(*ret.root().end().end().begin(), 14);
- BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin(), 13);
- BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().begin(), 11);
- BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().end().begin(), 12); //Leaf
-}
-
-template <class Tree>
void validate_corresponding_forest_tree(Tree const& t)
{
typename Tree::const_cursor c = t.root().begin();