Subject: [Boost-commit] svn:boost r50398 - in sandbox/SOC/2006/tree: branches/optimise-binary-tree-cursor/boost/tree branches/optimise-binary-tree-cursor/libs/tree/test trunk trunk/boost/tree trunk/boost/tree/detail/node
From: ockham_at_[hidden]
Date: 2008-12-29 09:02:39
Author: bernhard.reiter
Date: 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
New Revision: 50398
URL: http://svn.boost.org/trac/boost/changeset/50398
Log:
Rename node -> ascending_node.
Text files modified:
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/cursor.hpp | 51 ++-
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/Jamfile.v2 | 3
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_search_test.cpp | 2
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_test.cpp | 526 ++++++++++++++++++++-------------------
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/cursor_algorithm_test.cpp | 31 ++
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/forest_tree_test.cpp | 184 ++++++++++---
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/graph_test.cpp | 2
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/iterator_algorithm_test.cpp | 231 +++++------------
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/test_tree_traversal_data.hpp | 107 ++++++-
sandbox/SOC/2006/tree/trunk/TODO | 3
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 4
sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp | 8
sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 4
15 files changed, 635 insertions(+), 525 deletions(-)
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/cursor.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/cursor.hpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -58,6 +58,11 @@
typedef typename Cursor::size_type type;
};
+template <class T>
+struct cursor_size<T*> {
+ typedef std::size_t type;
+};
+
template <class Cursor>
struct cursor_category {
typedef typename Cursor::cursor_category type;
@@ -129,7 +134,7 @@
// , class Difference
// , class Size
>
-class output_cursor_iterator_wrapper;
+class output_iterator_cursor;
/**
* @brief Output cursor wrapper around an output iterator.
@@ -152,11 +157,11 @@
// , class Difference = use_default
// , class Size = use_default
>
-class output_cursor_iterator_wrapper {
+class output_iterator_cursor {
protected:
OutputIterator* iter;
//private:
-// typedef iterator_adaptor<output_cursor_iterator_wrapper<OutputIterator>
+// typedef iterator_adaptor<output_iterator_cursor<OutputIterator>
// , OutputIterator
// , Value
// , HorizontalTraversalOrCategory
@@ -167,9 +172,9 @@
typedef OutputIterator iterator;
// FIXME: Very adhoc.
- typedef output_cursor_iterator_wrapper<OutputIterator> value_type;
+ typedef output_iterator_cursor<OutputIterator> value_type;
typedef std::size_t size_type;
- typedef output_cursor_iterator_wrapper<OutputIterator> const_cursor;
+ typedef output_iterator_cursor<OutputIterator> const_cursor;
typedef forward_traversal_tag horizontal_traversal;
typedef bidirectional_traversal_tag vertical_traversal;
typedef forward_traversal_tag iterator_category;
@@ -180,7 +185,7 @@
/**
* For construction, we obviously need an Output Iterator to work on (i.e., write to).
*/
- explicit output_cursor_iterator_wrapper(OutputIterator& i) : iter(&i) {}
+ explicit output_iterator_cursor(OutputIterator& i) : iter(&i) {}
/**
* @param value A const& value of the value_type of container that iter is
@@ -195,38 +200,38 @@
*/
// TODO: Consult C++0x if this has been changed
template <class ValueType>
- output_cursor_iterator_wrapper& operator=(ValueType const& value)
+ output_iterator_cursor& operator=(ValueType const& value)
{
*((*iter)++) = value;
return *this;
}
/// Returns *this.
- output_cursor_iterator_wrapper& operator*() { return *this; }
+ output_iterator_cursor& operator*() { return *this; }
/// Returns *this, as this %cursor doesn't "move".
- output_cursor_iterator_wrapper& operator++() { return *this; }
+ output_iterator_cursor& operator++() { return *this; }
/// Returns *this, as this %cursor doesn't "move".
- output_cursor_iterator_wrapper operator++(int) { return *this; }
+ output_iterator_cursor operator++(int) { return *this; }
/// Returns *this, as this %cursor doesn't "move".
- output_cursor_iterator_wrapper& operator--() { return *this; }
+ output_iterator_cursor& operator--() { return *this; }
/// Returns *this, as this %cursor doesn't "move".
- output_cursor_iterator_wrapper operator--(int) { return *this; }
+ output_iterator_cursor operator--(int) { return *this; }
/// Returns *this, as this %cursor doesn't "move".
- output_cursor_iterator_wrapper& to_begin() { return *this; }
- output_cursor_iterator_wrapper& begin() { return *this; }
+ output_iterator_cursor& to_begin() { return *this; }
+ output_iterator_cursor& begin() { return *this; }
/// Returns *this, as this %cursor doesn't "move".
- output_cursor_iterator_wrapper& to_end() { return *this; }
- output_cursor_iterator_wrapper& end() { return *this; }
+ output_iterator_cursor& to_end() { return *this; }
+ output_iterator_cursor& end() { return *this; }
/// Returns *this, as this %cursor doesn't "move".
- output_cursor_iterator_wrapper& to_parent() { return *this; }
- output_cursor_iterator_wrapper& parent() { return *this; }
+ output_iterator_cursor& to_parent() { return *this; }
+ output_iterator_cursor& parent() { return *this; }
/// Returns true, in case an algorithm has a loop only terminating at root.
bool is_root() const { return true; }
@@ -238,23 +243,23 @@
};
template <class OutputIterator>
-typename output_cursor_iterator_wrapper<OutputIterator>::size_type
-index(output_cursor_iterator_wrapper<OutputIterator> const& cur)
+typename output_iterator_cursor<OutputIterator>::size_type
+index(output_iterator_cursor<OutputIterator> const& cur)
{
return cur.index();
}
/**
* @param o An output iterator.
- * @result An instance of output_cursor_iterator_wrapper working on o.
+ * @result An instance of output_iterator_cursor working on o.
*
* Use as shortcut for cumbersome typenames, just as with std::inserter and the like.
*/
template<class OutputIterator>
-inline output_cursor_iterator_wrapper<OutputIterator>
+inline output_iterator_cursor<OutputIterator>
outputter_cursor_iterator_wrapper(OutputIterator o)
{
- return output_cursor_iterator_wrapper<OutputIterator>(o);
+ return output_iterator_cursor<OutputIterator>(o);
}
} // namespace tree
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/Jamfile.v2 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -26,7 +26,8 @@
[ run binary_tree_test.cpp ]
[ run binary_tree_search_test.cpp ]
# [ run key_search_binary_tree_test.cpp ]
-# [ run rank_search_binary_tree_test.cpp ]
+# [ run rank_search_binary_tree_test.cpp ]
+ [ run algorithm_concepts_test.cpp ]
[ run cursor_algorithm_test.cpp ]
[ run iterator_algorithm_test.cpp ]
# [ run string_search_binary_tree_test.cpp ]
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_search_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_search_test.cpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_search_test.cpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -33,7 +33,7 @@
d = upper_bound(r, v);
BOOST_CHECK_EQUAL(*c, v);
- //BOOST_CHECK_EQUAL(inorder::next(c) , d);
+ //BOOST_CHECK_EQUAL(next(inorder(), c) , d);
}
BOOST_AUTO_TEST_CASE( binary_tree_search_test )
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/binary_tree_test.cpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -15,173 +15,25 @@
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
-BOOST_AUTO_TEST_SUITE( binary_tree_test /*, test_binary_tree_with_list_fixture<int>*/ )
-
-using namespace boost::tree;
-
-//template <class Tree>
-//void create_test_dataset2_tree(Tree& mytree)
-//{
-// typename Tree::cursor c, c1, c2, c3, c4;
-//
-// c = mytree.root();
-//
-// BOOST_CHECK(c.empty());
-//
-// c1 = mytree.insert(c, 1);
-// BOOST_CHECK_EQUAL(*c1, 1);
-//
-// BOOST_CHECK(!c.empty());
-//
-// BOOST_CHECK(c1.parent() == c);
-//
-// c2 = mytree.insert(c1, 2);
-// BOOST_CHECK(!c.empty());
-// BOOST_CHECK(c2.empty());
-// BOOST_CHECK_EQUAL(*c1, 1);
-// BOOST_CHECK_EQUAL(*c2, 2);
-// *c1 = 14;
-// BOOST_CHECK_EQUAL(*c1, 14);
-// BOOST_CHECK_EQUAL(*c2, 2);
-// BOOST_CHECK(c2.parent() == c1);
-// BOOST_CHECK(c1.parent() == c);
-//
-// c3 = c1.end();
-// BOOST_CHECK(c3 == c1.end());
-// --c3;
-// BOOST_CHECK_EQUAL(index(c3), 0);
-// BOOST_CHECK(c3.parent() != c3);
-// BOOST_CHECK(c3.parent() == c1);
-// BOOST_CHECK(c3 == c1.begin());
-//
-// *c3 = 3;
-// *(c1.begin()) = 2;
-//
-// BOOST_CHECK_EQUAL(*c3, 2);
-// ++c3;
-// c4 = mytree.insert(c3, 4);
-// BOOST_CHECK_EQUAL(*c4, 4);
-// c4 = c4.parent();
-// --c4;
-// BOOST_CHECK_EQUAL(*c4, 2);
-// BOOST_CHECK(c4.parent() == c1);
-// BOOST_CHECK(c4.empty());
-//
-// BOOST_CHECK_EQUAL(*c1, 14);
-//
-// BOOST_CHECK(c1.begin().empty() || c1.end().empty());
-//
-// //c1 = mytree.erase(c1);
-// //BOOST_CHECK_EQUAL(*c1, 2);
-//
-//}
-//
-//template <class Tree>
-//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);
-//
-// c = c.parent().parent();
-// BOOST_CHECK_EQUAL(*(c.begin()), 10);
-// BOOST_CHECK(c.begin().empty());
-// BOOST_CHECK(!c.end().empty());
-// BOOST_CHECK_EQUAL(*c.end().begin(), 14);
-// c = c.begin();
-//
-// // Left child empty
-// c = mytree.inorder_erase(c);
-// BOOST_CHECK_EQUAL(*c, 11);
-//
-// ++c;
-// BOOST_CHECK_EQUAL(*c.begin(), 12);
-// BOOST_CHECK(c.begin().empty());
-// BOOST_CHECK(c.end().empty());
-// c = c.begin();
-//
-// // Both children empty
-// c = mytree.inorder_erase(c);
-// BOOST_CHECK_EQUAL(*c, 13);
-//}
-//
-//BOOST_AUTO_TEST_CASE( clear_test )
-//{
-// bt.clear();
-// BOOST_CHECK(bt.empty());
-//}
+BOOST_AUTO_TEST_SUITE( basic_binary_tree_test )
BOOST_AUTO_TEST_CASE( constructors_test )
{
binary_tree<int> bt0;
- BOOST_CHECK(bt0.root().m_node == (*bt0.root().m_node)[1]);
-
BOOST_CHECK(bt0.root().empty());
- BOOST_CHECK_EQUAL(0, 1);
+ //BOOST_CHECK(bt0.root().begin() == bt0.root().end()); //FIXME
- // test with allocator
+ // test with allocator?
}
-//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_test_dataset2_tree(tree1);
-// validate_test_dataset2_tree(tree1);
-//
-// // Swap tree1 with empty tree2
-// swap(tree1, tree2);
-// validate_test_dataset2_tree(tree2);
-// BOOST_CHECK(tree1.empty());
-//
-// // Swap back
-// swap(tree1, tree2);
-// validate_test_dataset2_tree(tree1);
-// BOOST_CHECK(tree2.empty());
-//
-// // 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( insert_value_test )
{
binary_tree<int> bt0;
BOOST_CHECK(bt0.root().empty());
- binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8);
-
+ binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8); //FIXME
+ c.to_begin();
+
BOOST_CHECK(c == bt0.root().begin());
BOOST_CHECK(bt0.root().begin().parent() == bt0.root());
BOOST_CHECK(!bt0.root().empty());
@@ -189,6 +41,7 @@
BOOST_CHECK(bt0.root().begin().empty());
c = bt0.insert(c, 3);
+ c.to_begin();
// The 8 valued cursor still ok?
BOOST_CHECK(bt0.root().begin().parent() == bt0.root());
@@ -203,116 +56,269 @@
BOOST_CHECK(bt0.root().begin().begin().empty());
BOOST_CHECK(++c == bt0.root().begin().end());
+ //BOOST_CHECK_EQUAL(1, 2);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+BOOST_FIXTURE_TEST_SUITE(binary_tree_test, test_binary_tree_with_list_fixture<int>)
+
+using namespace boost::tree;
+
+template <class Tree>
+void create_test_dataset2_tree(Tree& mytree)
+{
+ typename Tree::cursor c, c1, c2, c3, c4;
+
+ c = mytree.root();
+
+ BOOST_CHECK(c.empty());
+
+ c1 = mytree.insert(c, 1);
+ c1.to_begin();
+
+ BOOST_CHECK_EQUAL(*c1, 1);
+
+ BOOST_CHECK(!c.empty());
+
+ BOOST_CHECK(c1.parent() == c);
+
+ c2 = mytree.insert(c1, 2);
+ c2.to_begin();
+
+ BOOST_CHECK(!c.empty());
+ BOOST_CHECK(c2.empty());
+ BOOST_CHECK_EQUAL(*c1, 1);
+ BOOST_CHECK_EQUAL(*c2, 2);
+ *c1 = 14;
+ BOOST_CHECK_EQUAL(*c1, 14);
+ BOOST_CHECK_EQUAL(*c2, 2);
+ BOOST_CHECK(c2.parent() == c1);
+ BOOST_CHECK(c1.parent() == c);
+
+ c3 = c1.end();
+ BOOST_CHECK(c3 == c1.end());
+ --c3;
+ BOOST_CHECK_EQUAL(index(c3), 0);
+ BOOST_CHECK(c3.parent() != c3);
+ BOOST_CHECK(c3.parent() == c1);
+ BOOST_CHECK(c3 == c1.begin());
+
+ *c3 = 3;
+ *(c1.begin()) = 2;
+
+ BOOST_CHECK_EQUAL(*c3, 2);
+ ++c3;
+ c4 = mytree.insert(c3, 4);
+ c4.to_begin();
+
+ BOOST_CHECK_EQUAL(*c4, 4);
+ c4 = c4.parent();
+ --c4;
+ BOOST_CHECK_EQUAL(*c4, 2);
+ BOOST_CHECK(c4.parent() == c1);
+ BOOST_CHECK(c4.empty());
+
+ BOOST_CHECK_EQUAL(*c1, 14);
+
+ BOOST_CHECK(c1.begin().empty() || c1.end().empty());
- BOOST_CHECK_EQUAL(1, 2);
+ //c1 = mytree.erase(c1);
+ //BOOST_CHECK_EQUAL(*c1, 2);
+
}
-//BOOST_AUTO_TEST_CASE( insert_values_test )
-//{
-// validate_test_dataset1_tree(bt);
-//}
-
-//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 != bt0);
-//
-// // Change it back
-// c = bt0.root().begin().end().begin().begin();
-// *c = tmp;
-// BOOST_CHECK(bt == bt0);
-//
-// c = bt0.inorder_first();
-// BOOST_CHECK_EQUAL(*c, 1);
-// c = bt0.root();
-// //inorder::back(c);
-// //BOOST_CHECK_EQUAL(*c, 14);
-//
-// //inorder_erase_test_dataset1_tree(bt);
-//}
-//
-//BOOST_AUTO_TEST_CASE( rotate_binary_tree_test )
-//{
-// binary_tree<int>::cursor c = bt.root().begin().end();
-// BOOST_CHECK_EQUAL(*c.begin(), 6);
-//
-// BOOST_CHECK_EQUAL(*c.parent(), 8);
-// BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant candidate
-//
-// BOOST_CHECK_EQUAL(*--c, 3); // differently (not invariantly!) spoken
-// BOOST_CHECK_EQUAL(*c.begin(), 1);
-// BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
-// BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
-//
-// BOOST_CHECK_EQUAL(index(c), 1);
-// BOOST_CHECK_EQUAL(*c.begin(), 6);
-//
-// bt.rotate(c); // Left rotate
-//
-// BOOST_CHECK_EQUAL(*c.begin(), 6);
-// BOOST_CHECK_EQUAL(*c.parent().begin(), 8);
-//
-// BOOST_CHECK_EQUAL(*c.end().begin(), 7);
-// BOOST_CHECK_EQUAL(*c.begin().begin(), 3);
-// BOOST_CHECK_EQUAL(*c.begin().begin().begin(), 1);
-//
-// BOOST_CHECK_EQUAL(*c.begin().end().begin(), 4);
-//
-// c = c.begin();
-// BOOST_CHECK_EQUAL(*c.begin(), 3);
-//
-// bt.rotate(c); // Right rotate
-//
-// BOOST_CHECK_EQUAL(*c.begin(), 3);
-// c = c.end();
-//
-// BOOST_CHECK_EQUAL(*c.begin(), 6);
-//
-// BOOST_CHECK_EQUAL(*c.parent(), 8);
-// BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // other invariant candidate
-//
-// BOOST_CHECK_EQUAL(*--c, 3);
+template <class Tree>
+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);
+
+ c = c.parent().parent();
+ BOOST_CHECK_EQUAL(*(c.begin()), 10);
+ BOOST_CHECK(c.begin().empty());
+ BOOST_CHECK(!c.end().empty());
+ BOOST_CHECK_EQUAL(*c.end().begin(), 14);
+ c = c.begin();
+
+ // Left child empty
+ c = mytree.inorder_erase(c);
+ BOOST_CHECK_EQUAL(*c, 11);
+
+ ++c;
+ BOOST_CHECK_EQUAL(*c.begin(), 12);
+ BOOST_CHECK(c.begin().empty());
+ BOOST_CHECK(c.end().empty());
+ c = c.begin();
+
+ // Both children empty
+ c = mytree.inorder_erase(c);
+ BOOST_CHECK_EQUAL(*c, 13);
+}
+
+BOOST_AUTO_TEST_CASE( clear_test )
+{
+ bt.clear();
+ BOOST_CHECK(bt.empty());
+}
+
+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_test_dataset2_tree(tree1);
+ validate_test_dataset2_tree(tree1);
+
+ // Swap tree1 with empty tree2
+ swap(tree1, tree2);
+ validate_test_dataset2_tree(tree2);
+ BOOST_CHECK(tree1.empty());
+
+ // Swap back
+ swap(tree1, tree2);
+ validate_test_dataset2_tree(tree1);
+ BOOST_CHECK(tree2.empty());
+
+ // 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 )
+{
+ *bt2.root().begin().end().begin().begin()
+ = *bt.root().begin().end().begin().begin();
+ 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 != bt0);
+
+ // Change it back
+ c = bt0.root().begin().end().begin().begin();
+ *c = tmp;
+ BOOST_CHECK(bt == bt0);
+
+ c = bt0.inorder_first();
+ BOOST_CHECK_EQUAL(*c, 1);
+ c = bt0.root();
+ //back(inorder(), c);
+ //BOOST_CHECK_EQUAL(*c, 14);
+
+ //inorder_erase_test_dataset1_tree(bt);
+}
+
+BOOST_AUTO_TEST_CASE( rotate_binary_tree_test )
+{
+ binary_tree<int>::cursor c = bt.root().begin().end();
+ BOOST_CHECK_EQUAL(*c.begin(), 6);
+
+ BOOST_CHECK_EQUAL(*c.parent(), 8);
+ BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant candidate
+
+ BOOST_CHECK_EQUAL(*--c, 3); // differently (not invariantly!) spoken
+ BOOST_CHECK_EQUAL(*c.begin(), 1);
+ BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
+ BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
+
+ BOOST_CHECK_EQUAL(index(c), 1);
+ BOOST_CHECK_EQUAL(*c.begin(), 6);
+
+ bt.rotate(c); // Left rotate
+
+ BOOST_CHECK_EQUAL(*c.begin(), 6);
+ BOOST_CHECK_EQUAL(*c.parent().begin(), 8);
+
+ BOOST_CHECK_EQUAL(*c.end().begin(), 7);
+ BOOST_CHECK_EQUAL(*c.begin().begin(), 3);
+ BOOST_CHECK_EQUAL(*c.begin().begin().begin(), 1);
+
+ BOOST_CHECK_EQUAL(*c.begin().end().begin(), 4);
+
+ c = c.begin();
+ BOOST_CHECK_EQUAL(*c.begin(), 3);
+
+ bt.rotate(c); // Right rotate
+
+ BOOST_CHECK_EQUAL(*c.begin(), 3);
+ c = c.end();
+
+ BOOST_CHECK_EQUAL(*c.begin(), 6);
+
+ BOOST_CHECK_EQUAL(*c.parent(), 8);
+ BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // other invariant candidate
+
+ BOOST_CHECK_EQUAL(*--c, 3);
+ BOOST_CHECK_EQUAL(*c.begin(), 1);
+ BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
+ BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
+
+ BOOST_CHECK_EQUAL(*c.begin(), 6);
+
+// BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
+// BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
+
// BOOST_CHECK_EQUAL(*c.begin(), 1);
-// BOOST_CHECK_EQUAL(*((++c).begin()).begin(), 4);
-// BOOST_CHECK_EQUAL(*(++c.begin()).begin(), 7);
-//
-// BOOST_CHECK_EQUAL(*c.begin(), 6);
-//
-//// BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
-//// BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
+// BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant?
//
-//// BOOST_CHECK_EQUAL(*c.begin(), 1);
-//// BOOST_CHECK_EQUAL(*c.parent().begin(), 3); // invariant?
-////
-//// BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
-//// BOOST_CHECK_EQUAL(*c.parent().parent().parent().begin(), 8);
-//// BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
-//
-//}
+// BOOST_CHECK_EQUAL(*c.parent().parent().begin(), 6);
+// BOOST_CHECK_EQUAL(*c.parent().parent().parent().begin(), 8);
+// BOOST_CHECK_EQUAL(*c.parent().parent().end().begin(), 7);
+
+}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/cursor_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/cursor_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/cursor_algorithm_test.cpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -37,12 +37,31 @@
test_traversal(Order(), l.begin(), l.end());
}
+BOOST_AUTO_TEST_CASE( test_foreach_subtree3 )
+{
+ boost::tree::for_each(
+ preorder(),
+ bt.root().begin(),
+ boost::lambda::bind(&std::list<int>::push_back, &l, boost::lambda::_1)
+ );
+ test_subtree_traversal(preorder(), l.begin(), l.end(), 1);
+ BOOST_CHECK_EQUAL(l.size(), 5);
+}
+
BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy, Order, orders)
{
boost::tree::copy(Order(), bt.root(), o);
test_traversal(Order(), l.begin(), l.end());
}
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_trees, Order, orders)
+{
+ BOOST_CHECK(bt != bt2);
+ boost::tree::copy(Order(), bt.root(), bt2.root());
+ BOOST_CHECK(bt == bt2);
+ validate_test_dataset1_tree(bt2);
+}
+
BOOST_AUTO_TEST_CASE_TEMPLATE ( test_desc_copy_using_insert_cursor, Order, orders )
{
bt2.clear();
@@ -62,7 +81,7 @@
, boost::bidirectional_traversal_tag());
validate_test_dataset1_tree(bt2);
- BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
+ BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
}
BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform, Order, orders)
@@ -75,4 +94,12 @@
test_traversal(Order(), l.begin(), l.end());
}
-BOOST_AUTO_TEST_SUITE_END()
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform_trees, Order, orders)
+{
+ BOOST_CHECK(bt != bt2);
+ boost::tree::transform(Order(), bt.root(), bt2.root()
+ , std::bind2nd(std::minus<int>(),1));
+ validate_test_dataset1_minus_1_tree(bt2);
+}
+
+BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/forest_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/forest_tree_test.cpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -23,91 +23,173 @@
using namespace boost::tree;
-typedef boost::mpl::list< boost::mpl::pair<preorder, preorder>
- /*, boost::mpl::pair<postorder, inorder>*/ > corresponding_orders;
+BOOST_AUTO_TEST_SUITE( basic_forest_test )
-BOOST_FIXTURE_TEST_SUITE(forest_algorithms_test, test_binary_tree_with_list_fixture<int>)
+BOOST_AUTO_TEST_CASE( constructors_test )
+{
+ forest_tree<int> ft0;
+ BOOST_CHECK_EQUAL(*ft0.root(), 0);
+ BOOST_CHECK(ft0.root().empty());
+}
-BOOST_AUTO_TEST_CASE( forest_tree_test )
+BOOST_AUTO_TEST_CASE( insert_value_test )
{
using namespace boost::tree;
+
+// forest_tree<int> mytree;
+//
+// forest_tree<int>::cursor c = mytree.root();
+// c = mytree.insert(c, 6);
+// BOOST_CHECK_EQUAL(*c, 6);
+//
+// c = mytree.insert(c, 5);
+// BOOST_CHECK_EQUAL(*c, 5);
+//
+// c = mytree.insert(c, 4);
+// BOOST_CHECK_EQUAL(*c, 4);
+// BOOST_CHECK(c == mytree.root().begin());
+//
+// ++c;
+// BOOST_CHECK_EQUAL(*c, 5);
+// ++c;
+// BOOST_CHECK_EQUAL(*c, 6);
- typedef forest_tree<int> tree_type;
- tree_type mytree;
+ forest_tree<int> ft0;
+
+ forest_tree<int>::cursor c = ft0.insert(ft0.root().end(), 8);
+
+ BOOST_CHECK_EQUAL(*c, 8);
+ BOOST_CHECK(c == ft0.root().begin());
+ BOOST_CHECK(++c == ft0.root().end());
+ BOOST_CHECK(ft0.root().begin().parent() == ft0.root());
+ BOOST_CHECK(!ft0.root().empty());
+ BOOST_CHECK(ft0.root().begin().empty());
- tree_type::cursor c = mytree.root();
- c = mytree.insert(c, 6);
+ c = ft0.insert(ft0.root().end(), 6);
BOOST_CHECK_EQUAL(*c, 6);
+ BOOST_CHECK(ft0.root().begin() != ft0.root().end());
+ BOOST_CHECK(c != ft0.root().end());
+ BOOST_CHECK(c.base() == ft0.root().base().begin().end());
+ BOOST_CHECK(c.parent() == ft0.root());
+ BOOST_CHECK(!ft0.root().empty());
+ BOOST_CHECK(++c == ft0.root().end());
+ ----c;
+ BOOST_CHECK(c == ft0.root().begin());
+ BOOST_CHECK_EQUAL(*c, 8);
- c = mytree.insert(c, 5);
- BOOST_CHECK_EQUAL(*c, 5);
-
- c = mytree.insert(c, 4);
- BOOST_CHECK_EQUAL(*c, 4);
- BOOST_CHECK(c == mytree.root().begin());
-
- ++c;
- BOOST_CHECK_EQUAL(*c, 5);
- ++c;
+ c = ft0.insert(ft0.root().end(), 7);
+ BOOST_CHECK_EQUAL(*c, 7);
+ BOOST_CHECK(c.parent() == ft0.root());
+ BOOST_CHECK(!ft0.root().empty());
+ BOOST_CHECK(++c == ft0.root().end());
+ ----c;
BOOST_CHECK_EQUAL(*c, 6);
-
- tree_type forest;
- //create_test_dataset1_tree(forest);
- c = forest.insert(forest.root(), 8);
- BOOST_CHECK(c == forest.root().begin());
+ BOOST_CHECK(c.parent() == ft0.root());
+ --c;
+ BOOST_CHECK(c == ft0.root().begin());
+ BOOST_CHECK(c.parent() == ft0.root());
BOOST_CHECK_EQUAL(*c, 8);
- c = forest.insert(c, 3);
+ c = ft0.root().begin().begin();
+ BOOST_CHECK(c.parent() == ft0.root().begin());
+
+ c = ft0.insert(ft0.root().begin().begin(), 3);
BOOST_CHECK_EQUAL(*c, 3);
- BOOST_CHECK_EQUAL(*++c, 8);
-// BOOST_CHECK_EQUAL(*forest.root().begin().begin(), 3);
+ BOOST_CHECK(c == ft0.root().begin().begin());
+ BOOST_CHECK(ft0.root().begin().begin().parent() == ft0.root().begin());
+
+ // Need more checks after this line...
+ c = ft0.insert(ft0.root().begin().begin().begin(), 1);
+ c = ft0.root().begin();
+ (++c).to_end();
+
+ c = ft0.insert(c, 4);
+ BOOST_CHECK_EQUAL(*c, 4);
+ BOOST_CHECK(--(c.to_parent()) == ft0.root().begin());
+ c = ft0.root().begin();
+ BOOST_CHECK_EQUAL(*c, 8);
+ BOOST_CHECK_EQUAL(*c.to_begin(), 3);
+ BOOST_CHECK_EQUAL(*c.to_begin(), 1);
+ BOOST_CHECK(c.empty());
+
+ //validate_corresponding_forest_tree(ft0);
}
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence, Order
+BOOST_AUTO_TEST_SUITE_END()
+
+BOOST_FIXTURE_TEST_SUITE(forest_algorithms_test, test_binary_tree_with_list_fixture<int>)
+
+// Test *order correspondence:
+// forest binary
+// pre pre
+// post in
+typedef boost::mpl::list< boost::mpl::pair<preorder, preorder>
+ , boost::mpl::pair<postorder, inorder> > corresponding_orders;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence_for_each, Order
, corresponding_orders )
{
using namespace boost::tree;
- typedef forest_tree<int> forest_tree_type;
- forest_tree_type ft(bt);
+ forest_tree<int> ft(bt);
- validate_corresponding_forest_tree(ft);
+ //validate_corresponding_forest_tree(ft);
- // Now test *order correspondence:
- // forest binary
- // pre pre
- // post in
std::list<int> test_list;
typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
- typedef output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
+ typedef output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
boost::tree::for_each(
- typename Order::first(),
- ft.root(),
- boost::lambda::bind(&std::list<int>::push_back, &test_list, boost::lambda::_1)
+ typename Order::first()
+ , ft.root()
+ , boost::lambda::bind(&std::list<int>::push_back, &test_list, boost::lambda::_1)
);
test_traversal(typename Order::second(), test_list.begin(), test_list.end());
BOOST_CHECK_EQUAL(test_list.size(), 11);
- test_list.clear();
- boost::tree::copy(typename Order::first(), ft.root(), oc_test_list);
- test_traversal(typename Order::second(), test_list.begin(), test_list.end());
- BOOST_CHECK_EQUAL(test_list.size(), 11);
- test_list.clear();
-
- boost::tree::transform(typename Order::first(), ft.root(), oc_test_list, std::bind2nd(std::plus<int>(),0));
- test_traversal(typename Order::second(), test_list.begin(), test_list.end());
- BOOST_CHECK_EQUAL(test_list.size(), 11);
- test_list.clear();
+}
- //test::preorder::algorithms(ft.root(), ft.root()); // FIXME: Fix algorithms for use in here.
-
+//BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence_copy, Order
+// , corresponding_orders )
+//{
+// using namespace boost::tree;
+//
+// forest_tree<int> ft(bt);
+//
+// //validate_corresponding_forest_tree(ft);
+//
+// std::list<int> test_list;
+// typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
+// typedef output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
+// back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
+// oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
+//
// boost::tree::copy(typename Order::first(), ft.root(), oc_test_list);
// test_traversal(typename Order::second(), test_list.begin(), test_list.end());
// BOOST_CHECK_EQUAL(test_list.size(), 11);
-}
+// test_list.clear();
+//}
+//BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence_transform, Order
+// , corresponding_orders )
+//{
+// using namespace boost::tree;
+//
+// forest_tree<int> ft(bt);
+//
+// //validate_corresponding_forest_tree(ft);
+//
+// std::list<int> test_list;
+// typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
+// typedef output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
+// back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
+// oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
+// boost::tree::transform(typename Order::first(), ft.root(), oc_test_list
+// , std::bind2nd(std::plus<int>(),0));
+// test_traversal(typename Order::second(), test_list.begin(), test_list.end());
+// BOOST_CHECK_EQUAL(test_list.size(), 11);
+//}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/graph_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/graph_test.cpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/graph_test.cpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -114,7 +114,7 @@
// BOOST_CHECK_EQUAL(*ci, 8);
// BOOST_CHECK_EQUAL(*++ci, 10); //FIXME
-// test::preorder::traversal(test_list.begin(), test_list.end());
+// test::traversal(preorder(), test_list.begin(), test_list.end());
// Output bt using write_graphviz. This might require copying
// the IncidenceGraph to a VertexListGraph (using copy_component)
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/iterator_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/iterator_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/iterator_algorithm_test.cpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -25,180 +25,93 @@
BOOST_FIXTURE_TEST_SUITE( iterator_algorithms_test, test_binary_tree_with_list_fixture<int> )
-template <class Order, class Cursor>
-void compare_cursor_to_iterator_traversal(Order, Cursor cur) {
- std::list<int> test_list;
- typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
- typedef output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
- back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
- oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
-
- boost::tree::copy(Order(), cur, oc_test_list);
-
- // Are the elements accessed in the correct order?
- BOOST_CHECK(std::equal( boost::tree::begin(Order(), cur),
- boost::tree::end(Order(), cur),
- test_list.begin()
- ));
-
- // Does end() mark the right element?
- BOOST_CHECK(std::distance(boost::tree::begin(Order(), cur),
- boost::tree::end(Order(), cur)) ==
- std::distance(test_list.begin(), test_list.end()));
-
- // Reverse order.
- BOOST_CHECK(std::equal( boost::tree::rbegin(Order(), cur),
- boost::tree::rend(Order(), cur),
- test_list.rbegin()
- ));
-
- BOOST_CHECK(std::distance(boost::tree::rbegin(Order(), cur),
- boost::tree::rend(Order(), cur)) ==
- std::distance(test_list.rbegin(), test_list.rend()));
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_iterator_algorithms, Order, orders )
+{
+ test_traversal(Order(), begin(Order(), bt.root())
+ , end(Order(), bt.root()));
-}
+ test_reverse_traversal(Order(), end(Order(), bt.root())
+ , begin(Order(), bt.root()));
+
+ BOOST_CHECK_EQUAL(std::distance(begin(Order(), bt.root())
+ , end(Order(), bt.root())), 11);
-template <class Cursor, class Op>
-void underefed_for_each_recursive(Cursor s, Op& f)
-{
- Cursor t = s.end();
- f(s); // Caution: f(s) comes before s.to_begin(), as opposed to
- s.to_begin(); // "normal" preorder for_each
- do
- if (!s.empty())
- underefed_for_each_recursive(s, f);
- while (s++ != t);
-}
+ // TODO: Also check with binary_tree-specialized inorder begin()!
-template <class Cursor, class Op>
-Op underefed_for_each(Cursor s, Op f)
-{
- Cursor t = s.end();
- f(s); // Caution: f(s) comes before s.to_begin(), as opposed to
- s.to_begin(); // "normal" preorder for_each
- do
- if (!s.empty())
- underefed_for_each_recursive(s, f);
- while (s++ != t);
+ // Now the iterators based on stack-based cursors (that don't use cursor.to_parent())
- return f;
+ test_traversal(Order(), begin(Order(), make_ascending_cursor(bt.root()))
+ , end(Order(), make_ascending_cursor(bt.root())));
+ test_reverse_traversal(Order(), end(Order(), make_ascending_cursor(bt.root()))
+ , begin(Order(), make_ascending_cursor(bt.root())));
+ BOOST_CHECK_EQUAL(std::distance(
+ begin(Order(), make_ascending_cursor(bt.root()))
+ , end(Order(), make_ascending_cursor(bt.root()))), 11);
}
-template <class Order>
-void comparisons_using_ac(binary_tree<int>::cursor c) {
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(c)));
+BOOST_AUTO_TEST_CASE( test_subtree3_iterator_algorithms )
+{
+ test_subtree_traversal(preorder(), begin(preorder(), bt.root().begin())
+ , end(preorder(), bt.root().begin()), 1);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), bt.root().begin())
+ , end(preorder(), bt.root().begin())), 5);
+
+ test_subtree_traversal(inorder(), begin(inorder(), bt.root().begin())
+ , end(inorder(), bt.root().begin()), 0);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), bt.root().begin())
+ , end(inorder(), bt.root().begin())), 5);
+
+ test_subtree_traversal(postorder(), begin(postorder(), bt.root().begin())
+ , end(postorder(), bt.root().begin()), 0);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), bt.root().begin())
+ , end(postorder(), bt.root().begin())), 5);
}
-template <class Order>
-void comparisons_using_rtc(binary_tree<int>::cursor c) {
- compare_cursor_to_iterator_traversal(Order(), track_root(c));
+BOOST_AUTO_TEST_CASE( test_subtree6_iterator_algorithms )
+{
+ test_subtree_traversal(preorder(), begin(preorder(), bt.root().begin().end())
+ , end(preorder(), bt.root().begin().end()), 3);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), bt.root().begin().end())
+ , end(preorder(), bt.root().begin().end())), 3);
+
+ test_subtree_traversal(inorder(), begin(inorder(), bt.root().begin().end())
+ , end(inorder(), bt.root().begin().end()), 2);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), bt.root().begin().end())
+ , end(inorder(), bt.root().begin().end())), 3);
+
+ test_subtree_traversal(postorder(), begin(postorder(), bt.root().begin().end())
+ , end(postorder(), bt.root().begin().end()), 1);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), bt.root().begin().end())
+ , end(postorder(), bt.root().begin().end())), 3);
}
-/**
- * Check all iterator traversals by comparing them to a recursive cursor
- * algorithm output. Do that at different stages of the tree while adding
- * elements to it, so different tree shapes are checked to be catered for
- * by the iterator algorithms.
- *
- * Afterwards, do all that using iterators wrapped around
- * "explicit stack"-based cursors also.
- */
-//void compare_cursor_to_iterator_traversal() {
-BOOST_AUTO_TEST_CASE_TEMPLATE( compare_cursor_to_iterator_traversal_test, Order, orders )
+BOOST_AUTO_TEST_CASE( test_subtree10_iterator_algorithms )
{
- binary_tree<int> test_tree2;
- //test::compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-
- binary_tree<int>::cursor c = test_tree2.insert(test_tree2.root(), 8);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- c = test_tree2.insert(c, 3);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- test_tree2.insert(c, 1);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- c = test_tree2.insert(++c, 6);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- test_tree2.insert(c, 4);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- test_tree2.insert(++c, 7);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- c = test_tree2.insert(test_tree2.root().end(), 10);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- c = test_tree2.insert(test_tree2.root().end().end(), 14);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- c = test_tree2.insert(c, 13);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- c = test_tree2.insert(c, 11);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- c = test_tree2.insert(++c, 12);
- compare_cursor_to_iterator_traversal(Order(), track_root(test_tree2.root()));
- compare_cursor_to_iterator_traversal(Order(), track_root(make_ascending_cursor(test_tree2.root())));
-
- underefed_for_each(test_tree2.root(), comparisons_using_ac<Order>);
- underefed_for_each(test_tree2.root(), comparisons_using_rtc<Order>);
+ test_subtree_traversal(preorder(), begin(preorder(), bt.root().end())
+ , end(preorder(), bt.root().end()), 6);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), bt.root().end())
+ , end(preorder(), bt.root().end())), 5);
+
+ test_subtree_traversal(inorder(), begin(inorder(), bt.root().end())
+ , end(inorder(), bt.root().end()), 6);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), bt.root().end())
+ , end(inorder(), bt.root().end())), 5);
+
+ test_subtree_traversal(postorder(), begin(postorder(), bt.root().end())
+ , end(postorder(), bt.root().end()), 5);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), bt.root().end())
+ , end(postorder(), bt.root().end())), 5);
}
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_algorithms, Order, orders )
+BOOST_AUTO_TEST_CASE( test_ascending_iterator_algorithms )
{
- typedef boost::tree::binary_tree<int>::cursor cursor;
-
-// std::list<int> test_list;
-//
-// // TODO: Put this into a better testing context.
-// boost::tree::preorder::for_each(
-// test_tree.root(),
-// boost::lambda::bind(&std::list<int>::push_back, &test_list, boost::lambda::_1)
-// );
-// BOOST_CHECK(test_list.empty());
-
- //Preorder
- test_traversal(Order(), begin(Order(), track_root(bt.root())),
- end(Order(), track_root(bt.root())));
-
- test_reverse_traversal(Order(), end(Order(), track_root(bt.root())),
- begin(Order(), track_root(bt.root())));
-
- BOOST_CHECK(std::distance(begin(Order(), track_root(bt.root())),
- end(Order(), track_root(bt.root()))) == 11);
-
- // TODO: Also check with binary_tree-specialized inorder begin()!
-
- // Now the iterators based on stack-based cursors (that don't use cursor.to_parent())
-
- test_traversal(Order(), begin(Order(), track_root(make_ascending_cursor(bt.root()))),
- end(Order(), track_root(make_ascending_cursor(bt.root()))));
- test_reverse_traversal(Order(), end(Order(), track_root(make_ascending_cursor(bt.root()))),
- begin(Order(), track_root(make_ascending_cursor(bt.root()))));
-
-// TODO: Move to other unit
- //Ascending iterator.
-// binary_tree<int>::cursor c = test_tree.root();
-// boost::tree::iterator<ascending, binary_tree<int>::cursor> ai_root(c);
-// c = c.begin().end().begin().begin();
-// BOOST_CHECK_EQUAL(*c, 4);
-//
-// boost::tree::iterator<ascending, binary_tree<int>::cursor> ais(c);
-// test_traversal_from_leaf4(ais, ai_root);
+ binary_tree<int>::cursor c = bt.root();
+ typedef boost::tree::root_tracking_cursor<binary_tree<int>::cursor> rtc;
+ typedef boost::tree::iterator<ascending, rtc> ai;
+ c.to_begin().to_end().to_begin().to_begin();
+ BOOST_CHECK_EQUAL(*c, 4);
+ test_traversal_from_leaf4(ai(rtc(c)), ai(rtc(bt.root())));
}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/test_tree_traversal_data.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/libs/tree/test/test_tree_traversal_data.hpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -25,8 +25,8 @@
// Just to make sure we won't be getting any false positives when
// copying test_tree1 to test_tree2, we'll change one of test_tree2's
// values.
-// d = d.begin().end().begin().begin();
-// ++*d;
+ d = d.begin().end().begin().begin();
+ *d = T(29);
}
// Test data from http://en.wikipedia.org/wiki/Image:Binary_search_tree.svg
@@ -39,16 +39,16 @@
typedef typename boost::tree::binary_tree<T>::value_type value_type;
typename boost::tree::binary_tree<T>::cursor cur = ret.insert(ret.root(), value_type(8));
- cur = ret.insert(cur, value_type(3));
- ret.insert(cur, value_type(1));
+ cur = ret.insert(cur.to_begin(), value_type(3));
+ ret.insert(cur.to_begin(), value_type(1));
cur = ret.insert(++cur, value_type(6));
- ret.insert(cur, value_type(4));
+ ret.insert(cur.to_begin(), value_type(4));
ret.insert(++cur, value_type(7));
cur = ret.insert(ret.root().end(), value_type(10));
cur = ret.insert(ret.root().end().end(), value_type(14));
- cur = ret.insert(cur, value_type(13));
- cur = ret.insert(cur, value_type(11));
- cur = ret.insert(++cur, value_type(12));
+ cur = ret.insert(cur.to_begin(), value_type(13));
+ cur = ret.insert(cur.to_begin(), value_type(11));
+ cur = ret.insert(++cur.to_begin(), value_type(12));
}
static void validate_test_dataset1_tree(boost::tree::binary_tree<T>& ret)
@@ -66,6 +66,22 @@
BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().begin(), 11);
BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().end().begin(), 12); //Leaf
}
+
+ static void validate_test_dataset1_minus_1_tree(boost::tree::binary_tree<T>& ret)
+ {
+ BOOST_CHECK_EQUAL(*ret.root().begin(), 7);
+ BOOST_CHECK_EQUAL(*ret.root().begin().begin(), 2);
+ BOOST_CHECK_EQUAL(*ret.root().begin().begin().begin(), 0); //Leaf
+ BOOST_CHECK_EQUAL(*ret.root().begin().end().begin(), 5);
+ BOOST_CHECK_EQUAL(*ret.root().begin().end().begin().begin(), 3); //Leaf
+ BOOST_CHECK_EQUAL(*ret.root().begin().end().end().begin(), 6); //Leaf
+
+ BOOST_CHECK_EQUAL(*ret.root().end().begin(), 9);
+ BOOST_CHECK_EQUAL(*ret.root().end().end().begin(), 13);
+ BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin(), 12);
+ BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().begin(), 10);
+ BOOST_CHECK_EQUAL(*ret.root().end().end().begin().begin().end().begin(), 11); //Leaf
+ }
boost::tree::binary_tree<T> bt, bt2;
};
@@ -74,7 +90,7 @@
struct test_binary_tree_with_list_fixture
: public test_binary_tree_fixture<T> {
typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
- typedef boost::tree::output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
+ typedef boost::tree::output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
test_binary_tree_with_list_fixture()
: test_binary_tree_fixture<T>(), l(), i(l), o(i) { }
@@ -146,16 +162,36 @@
}
template <class Iterator>
-void test_subtree_traversal(boost::tree::preorder, Iterator a, Iterator b)
+void test_subtree_traversal(boost::tree::preorder, Iterator a, Iterator b
+ , std::vector<int>::difference_type x = 0)
{
- BOOST_CHECK_EQUAL(*a++, 3);
- BOOST_CHECK_EQUAL(*a++, 1);
- BOOST_CHECK_EQUAL(*a++, 6);
- BOOST_CHECK_EQUAL(*a++, 4);
- BOOST_CHECK_EQUAL(*a++, 7);
- BOOST_CHECK(a == b);
+ std::vector<int> preorder(11);
+ preorder[0] = 8;
+ preorder[1] = 3;
+ preorder[2] = 1;
+ preorder[3] = 6;
+ preorder[4] = 4;
+ preorder[5] = 7;
+ preorder[6] = 10;
+ preorder[7] = 14;
+ preorder[8] = 13;
+ preorder[9] = 11;
+ preorder[10] = 12;
+
+ BOOST_CHECK(std::equal(a, b, preorder.begin() + x));
}
+//template <class Iterator>
+//void test_subtree_traversal(boost::tree::preorder, Iterator a, Iterator b)
+//{
+// BOOST_CHECK_EQUAL(*a++, 3);
+// BOOST_CHECK_EQUAL(*a++, 1);
+// BOOST_CHECK_EQUAL(*a++, 6);
+// BOOST_CHECK_EQUAL(*a++, 4);
+// BOOST_CHECK_EQUAL(*a++, 7);
+// BOOST_CHECK(a == b);
+//}
+
template <class Iterator>
void test_traversal(boost::tree::inorder, Iterator a, Iterator b)
{
@@ -190,6 +226,25 @@
BOOST_CHECK(a == b);
}
+template <class Iterator>
+void test_subtree_traversal(boost::tree::inorder, Iterator a, Iterator b
+ , std::vector<int>::difference_type x = 0)
+{
+ std::vector<int> inorder(11);
+ inorder[0] = 1;
+ inorder[1] = 3;
+ inorder[2] = 4;
+ inorder[3] = 6;
+ inorder[4] = 7;
+ inorder[5] = 8;
+ inorder[6] = 10;
+ inorder[7] = 11;
+ inorder[8] = 12;
+ inorder[9] = 13;
+ inorder[10] = 14;
+
+ BOOST_CHECK(std::equal(a, b, inorder.begin() + x));
+}
template <class Iterator>
void test_traversal(boost::tree::postorder, Iterator a, Iterator b)
@@ -226,6 +281,26 @@
}
template <class Iterator>
+void test_subtree_traversal(boost::tree::postorder, Iterator a, Iterator b
+ , std::vector<int>::difference_type x = 0)
+{
+ std::vector<int> postorder(11);
+ postorder[0] = 1;
+ postorder[1] = 4;
+ postorder[2] = 7;
+ postorder[3] = 6;
+ postorder[4] = 3;
+ postorder[5] = 12;
+ postorder[6] = 11;
+ postorder[7] = 13;
+ postorder[8] = 14;
+ postorder[9] = 10;
+ postorder[10] = 8;
+
+ BOOST_CHECK(std::equal(a, b, postorder.begin() + x));
+}
+
+template <class Iterator>
void test_traversal_from_leaf4(Iterator a, Iterator b)
{
BOOST_CHECK_EQUAL(*a, 4);
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -20,7 +20,7 @@
* Make Order the last (instead of first) parameter in algorithms? That way, we could
assume reasonable defaults while offering explicit choice (eg for size(), find(),
maybe even copy(): default to preorder).
-* Rename node -> ascending_node; implement descending_node; and corresponding cursors.
+* Implement descending_node; and corresponding cursor.
* Fix freestanding index() and members (esp. wrt cursor facade and adaptor!)
* Redo all that balance(==balanced_tree)/searcher stuff. Avoid redundancy, that is, make them both use
balanceRs for whatever they're up to, but don't make searcher depend on balance.
@@ -118,6 +118,7 @@
the STL's linear algorithms should there be a hierarchical version?
Pre-release:
+* Make directory structure reflect namespaces and vice versa.
* Cleanup headers/ #include dependencies.
* Run Boost Inspect.
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-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -31,7 +31,7 @@
namespace boost {
namespace tree {
-using detail::node;
+using detail::ascending_node;
using detail::ascending_nary_cursor;
using detail::augmented_iterator;
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-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -24,7 +24,7 @@
namespace boost {
namespace tree {
-using detail::node;
+using detail::ascending_node;
using detail::ascending_nary_cursor;
// TODO: Remove shoot() remains (was m_header->m_parent)
@@ -43,7 +43,7 @@
typedef typename Alloc::template rebind<value_type>::other allocator_type;
private:
- typedef node<value_type> node_type;
+ typedef ascending_node<value_type> node_type;
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -218,11 +218,11 @@
};
template <typename T>
-class node : public node_base {
+class ascending_node : public node_base {
public:
typedef T value_type;
- typedef node<value_type> node_type;
+ typedef ascending_node<value_type> node_type;
typedef node_type* node_pointer;
typedef node_type& node_reference;
@@ -243,9 +243,9 @@
const_reference operator*() const { return *m_data; }
- node(pointer data) : base_type(), m_data(data) {}
+ ascending_node(pointer data) : base_type(), m_data(data) {}
- node(pointer data, base_pointer p) : base_type(p), m_data(data) {}
+ ascending_node(pointer data, base_pointer p) : base_type(p), m_data(data) {}
pointer data()
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -44,7 +44,7 @@
typedef T value_type;
typedef Hierarchy hierarchy_type;
-// typedef node<2, T, typename augmentor::metadata_type, typename balancer::metadata_type> node_type;
+// typedef ascending_node<2, T, typename augmentor::metadata_type, typename balancer::metadata_type> node_type;
typedef typename hierarchy_type::cursor base_cursor;
typedef typename hierarchy_type::const_cursor base_const_cursor;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp 2008-12-29 09:02:37 EST (Mon, 29 Dec 2008)
@@ -25,7 +25,7 @@
namespace boost {
namespace tree {
-using detail::node;
+using detail::ascending_node;
using detail::ascending_nary_cursor;
/**
@@ -62,7 +62,7 @@
{}
};
- typedef node<value_type/*, mycontainer*/> node_type;
+ typedef ascending_node<value_type/*, mycontainer*/> node_type;
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
typedef typename node_traits<node_type>::node_base_type node_base_type;
