Subject: [Boost-commit] svn:boost r49066 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2008-09-30 10:58:15
Author: bernhard.reiter
Date: 2008-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
New Revision: 49066
URL: http://svn.boost.org/trac/boost/changeset/49066
Log:
Start migrating to a unit-based test approach.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 7 -
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 8 +-
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 4 +
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 19 ++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp | 17 ++--
sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp | 149 +++++++++++++++------------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 2
8 files changed, 93 insertions(+), 115 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
@@ -14,7 +14,7 @@
[section TODO]
General:
-
+* Move some of the secondary stuff to a util/ dir? Is that what they're used for?
* Redo testing. Right now, it's just chaotic.
* Fix recursive algorithms for use with forest.
* Implement a real output cursor (if possible) and use preorder::copy to build a new tree.
@@ -35,10 +35,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()?
-* Remove the word "recursive" from *order subtree algorithms context, as we might
- implement these using iterative versions. Rename *_recursive algorithms to
- *_with_references or so; and use something like #ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS.
- Overload then for root_tracking_cursor.
+* 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()!
* Revisit binary_tree (inorder::)iterator functions
* Possibly sort out some more concepts, like trees with "downwards" or "upwards" insertion
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-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
@@ -72,10 +72,10 @@
m_header[1] = &m_header;
}
- explicit binary_tree (size_type n, value_type const& value = value_type(),
- allocator_type const& alloc = allocator_type())
- : m_header(), m_value_alloc(alloc)
- {}
+// explicit binary_tree (size_type n, value_type const& value = value_type(),
+// allocator_type const& alloc = allocator_type())
+// : m_header(), m_value_alloc(alloc)
+// {}
template <class InputCursor>
binary_tree (InputCursor subtree,
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 2008-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
@@ -15,6 +15,10 @@
: requirements
<include>$(BOOST_ROOT)
<include>../../../
+# <define>BOOST_TEST_DYN_LINK
+# <define>BOOST_TEST_MAIN
+# <link>shared
+# <runtime-link>shared
;
test-suite tree :
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-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
@@ -8,7 +8,9 @@
#include <boost/tree/algorithm.hpp>
-#include <boost/test/minimal.hpp>
+#define BOOST_TEST_MODULE binary_tree test
+//#define BOOST_TEST_DYN_LINK
+#include <boost/test/included/unit_test.hpp>
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
@@ -143,7 +145,18 @@
swap(one, two);
}
-int test_main(int, char* [])
+BOOST_AUTO_TEST_CASE( constructors_test )
+{
+ typedef binary_tree<int> tree_t;
+ tree_t bt;
+ BOOST_CHECK(bt.root().empty());
+ //BOOST_CHECK_EQUAL(0, 1);
+
+ // test with allocator
+}
+
+//int test_main(int, char* [])
+BOOST_AUTO_TEST_CASE( old_test )
{
typedef binary_tree<int> tree_t;
tree_t tree1, tree2;
@@ -211,5 +224,5 @@
inorder_erase_test_data_tree(tree2);
- return 0;
+ //return 0;
}
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-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
@@ -10,12 +10,15 @@
#include <boost/tree/iterator.hpp>
#include <boost/tree/algorithm.hpp>
-#include <boost/test/minimal.hpp>
-
#include <list>
#include <algorithm>
#include <iterator>
+#define BOOST_TEST_MODULE cursor_algorithm test
+#include <boost/test/included/unit_test.hpp>
+#include <boost/test/test_case_template.hpp>
+#include <boost/mpl/list.hpp>
+
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
@@ -26,7 +29,9 @@
#include "subtree_algorithms_checks.hpp"
-int test_main(int, char* [])
+typedef boost::mpl::list<preorder,inorder,postorder> orders;
+
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_algorithms, Order, orders )
{
using boost::forward_traversal_tag;
@@ -45,9 +50,5 @@
BOOST_CHECK(test_tree != test_tree2);
d = test_tree2.root();
- test::algorithms(preorder(), test_tree.root(), test_tree2.root());
- test::algorithms(inorder(), test_tree.root(), test_tree2.root());
- test::algorithms(postorder(), test_tree.root(), test_tree2.root());
-
- return 0;
+ test::algorithms(Order(), test_tree.root(), test_tree2.root());
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp 2008-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
@@ -19,11 +19,14 @@
#include <boost/tree/ascending_cursor.hpp>
#include <boost/tree/root_tracking_cursor.hpp>
-#include <boost/test/minimal.hpp>
-
#include <list>
#include <iterator>
+#define BOOST_TEST_MODULE iterator_algorithm test
+#include <boost/test/included/unit_test.hpp>
+#include <boost/test/test_case_template.hpp>
+#include <boost/mpl/list.hpp>
+
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
@@ -60,24 +63,18 @@
return f;
}
-template <class Cursor>
-void comparisons(Cursor c) {
- test::compare_cursor_to_iterator_traversal(preorder(), c);
- test::compare_cursor_to_iterator_traversal(inorder(), c);
- test::compare_cursor_to_iterator_traversal(postorder(), c);
- return;
-}
-
+template <class Order>
void comparisons_using_ac(binary_tree<int>::cursor c) {
- comparisons(make_root_tracking_cursor(make_ascending_cursor(c)));
- return;
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(c)));
}
+template <class Order>
void comparisons_using_rtc(binary_tree<int>::cursor c) {
- comparisons(make_root_tracking_cursor(c));
- return;
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(c));
}
+typedef boost::mpl::list<preorder,inorder,postorder> orders;
+
/**
* Check all iterator traversals by comparing them to a recursive cursor
* algorithm output. Do that at different stages of the tree while adding
@@ -87,59 +84,61 @@
* Afterwards, do all that using iterators wrapped around
* "explicit stack"-based cursors also.
*/
-void compare_cursor_to_iterator_traversal() {
+//void compare_cursor_to_iterator_traversal() {
+BOOST_AUTO_TEST_CASE_TEMPLATE( compare_cursor_to_iterator_traversal, Order, orders )
+{
binary_tree<int> test_tree2;
- //comparisons(test_tree2.root());
+ //test::compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
binary_tree<int>::cursor c = test_tree2.insert(test_tree2.root(), 8);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
c = test_tree2.insert(c, 3);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
test_tree2.insert(c, 1);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
c = test_tree2.insert(++c, 6);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
test_tree2.insert(c, 4);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
test_tree2.insert(++c, 7);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
c = test_tree2.insert(test_tree2.root().end(), 10);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
c = test_tree2.insert(test_tree2.root().end().end(), 14);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
c = test_tree2.insert(c, 13);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
c = test_tree2.insert(c, 11);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
c = test_tree2.insert(++c, 12);
- comparisons(make_root_tracking_cursor(test_tree2.root()));
- comparisons(make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(test_tree2.root()));
+ test::compare_cursor_to_iterator_traversal(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree2.root())));
- underefed_for_each(test_tree2.root(), comparisons_using_ac);
- underefed_for_each(test_tree2.root(), comparisons_using_rtc);
+ underefed_for_each(test_tree2.root(), comparisons_using_ac<Order>);
+ underefed_for_each(test_tree2.root(), comparisons_using_rtc<Order>);
}
-int test_main(int, char* [])
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_algorithms, Order, orders )
{
typedef boost::tree::binary_tree<int>::cursor cursor;
@@ -156,66 +155,34 @@
create_test_data_tree(test_tree);
//Preorder
- test_traversal(preorder(), begin(preorder(), make_root_tracking_cursor(test_tree.root())),
- end(preorder(), make_root_tracking_cursor(test_tree.root())));
+ test_traversal(Order(), begin(Order(), make_root_tracking_cursor(test_tree.root())),
+ end(Order(), make_root_tracking_cursor(test_tree.root())));
- test_reverse_traversal(preorder(), end(preorder(), make_root_tracking_cursor(test_tree.root())),
- begin(preorder(), make_root_tracking_cursor(test_tree.root())));
+ test_reverse_traversal(Order(), end(Order(), make_root_tracking_cursor(test_tree.root())),
+ begin(Order(), make_root_tracking_cursor(test_tree.root())));
- BOOST_CHECK(std::distance(begin(preorder(), make_root_tracking_cursor(test_tree.root())),
- end(preorder(), make_root_tracking_cursor(test_tree.root()))) == 11);
-
- // Inorder
- test_traversal(inorder(), begin(inorder(), make_root_tracking_cursor(test_tree.root())),
- end(inorder(), make_root_tracking_cursor(test_tree.root())));
+ BOOST_CHECK(std::distance(begin(Order(), make_root_tracking_cursor(test_tree.root())),
+ end(Order(), make_root_tracking_cursor(test_tree.root()))) == 11);
- test_reverse_traversal(inorder(), end(inorder(), make_root_tracking_cursor(test_tree.root())),
- begin(inorder(), make_root_tracking_cursor(test_tree.root())));
-
// TODO: Also check with binary_tree-specialized inorder begin()!
- BOOST_CHECK(std::distance(begin(inorder(), make_root_tracking_cursor(test_tree.root())),
- end(inorder(), make_root_tracking_cursor(test_tree.root()))) == 11);
-
- //Postorder
- test_traversal(postorder(), begin(postorder(), make_root_tracking_cursor(test_tree.root())),
- end(postorder(), make_root_tracking_cursor(test_tree.root())));
- test_reverse_traversal(postorder(), end(postorder(), make_root_tracking_cursor(test_tree.root())),
- begin(postorder(), make_root_tracking_cursor(test_tree.root())));
-
- BOOST_CHECK(std::distance(begin(postorder(), make_root_tracking_cursor(test_tree.root())),
- end(postorder(), make_root_tracking_cursor(test_tree.root()))) == 11);
-
// Now the iterators based on stack-based cursors (that don't use cursor.to_parent())
- test_traversal(preorder(), begin(preorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- end(preorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
- test_reverse_traversal(preorder(), end(preorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- begin(preorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
-
- test_traversal(inorder(), begin(inorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- end(inorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
- test_reverse_traversal(inorder(), end(inorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- begin(inorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
-
- test_traversal(postorder(), begin(postorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- end(postorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
- test_reverse_traversal(postorder(), end(postorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- begin(postorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
+ test_traversal(Order(), begin(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
+ end(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
+ test_reverse_traversal(Order(), end(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
+ begin(Order(), make_root_tracking_cursor(make_ascending_cursor(test_tree.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(*c == 4);
-
- boost::tree::iterator<ascending, binary_tree<int>::cursor> ais(c);
- test_traversal_from_leaf4(ais, ai_root);
+// 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(*c == 4);
+//
+// boost::tree::iterator<ascending, binary_tree<int>::cursor> ais(c);
+// test_traversal_from_leaf4(ais, ai_root);
- //Now the advanced stuff
- compare_cursor_to_iterator_traversal();
-
- return 0;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp 2008-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
@@ -13,8 +13,6 @@
#include <algorithm>
#include <iterator>
-#include <boost/test/minimal.hpp>
-
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
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-09-30 10:58:14 EDT (Tue, 30 Sep 2008)
@@ -11,8 +11,6 @@
#include <list>
-#include <boost/test/minimal.hpp>
-
// Test data from http://en.wikipedia.org/wiki/Image:Binary_search_tree.svg
// (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
