Subject: [Boost-commit] svn:boost r52132 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-04-02 11:32:49
Author: bernhard.reiter
Date: 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
New Revision: 52132
URL: http://svn.boost.org/trac/boost/changeset/52132
Log:
* Use Boost.MultiIndex for organising mock objects to avoid redundancy.
* Some TODO cleanup
* forest.hpp: One minimal fix (use to_rightmost also in const cursor end)
Added:
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_data.hpp
- copied, changed from r52130, /sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 63 ++++++--------
sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp | 5
sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp | 33 ++++---
sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp | 29 +++---
sandbox/SOC/2006/tree/trunk/libs/tree/test/for_each_test.cpp | 36 +++++---
sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp | 8 +
sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp | 17 ++-
sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp | 15 ++-
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_data.hpp | 168 +++++++++++++--------------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 60 -------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/transform_test.cpp | 32 ++++---
11 files changed, 186 insertions(+), 280 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -17,19 +17,8 @@
* Do we need to_{left|right}most_ancestor?
* Do we need multiway and plain cursor "flavor" tags (for algorithms)?
* In case of forest cursor, is_leaf() should really be empty().
-* Further reduce test data redundancy: make mock cursor use the data from fake_binary_tree,
- and give it an Order template argument. Calculate *order positions from level order indices
- as of fake_binary_tree. Possibly change fake_binary_tree internal representation to a
- vector<bool> with indices indicating the level order position (and also the value),
- and values indicating "empty or not".
-* Re-merge algorithm tests into algorithm_test.cpp after they're all tidied up?
* Add algorithms for construction of a tree based on two ranges specifying its
pre-/in-/postorder linearization (see Knuth).
-* Use Boost.MultiIndex for organising mock objects to avoid redundancy?
- (The data pairs position--value
- are always the same, but the order in which they are accessed depends on the order of the
- algorithm acting on them).
-* Clean up binary_tree_test
* preorder_insert_cursor: hopefully easy to implement...
* Add checks for correspondence of concepts and archetypes!
* Re-do forest (again!).
@@ -62,18 +51,9 @@
* Clean up node/cursor/binary_tree implementation.
* Fix forest copy
* Fix cursor archetypes: *order copy checks don't compile
-* Test insert_cursor independently of algorithms.
* Implement forest_tree::insert_above.
* Revisit namespaces.
* 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.
-* Implement a real output cursor (if possible) and use copy(preorder(), ...) to build a new tree.
- Then, do some performance measurements comparing
- * Different *orders;
- * BOOST_RECURSIVE_ORDER_ALGORITHMS on and off;
- * cursor and iterator based algorithms (from Boost.Tree and the STL, respectively)
- Do these measurements also with algorithms other than copy.
-* Test cursor adaptors wrapped around output cursors!
* Think of a couple good examples (draw inspiration eg from Wikipedia: Tree traversal
or CRLS) and include them in the docs. Maybe move some files from libs/test to
example.
@@ -102,20 +82,7 @@
(Compare this again to container vs sequence; also look into graph concepts.)
Finally, mind the implications for internal/external adaptation; they might be
generalised, if the above assumption is true.
-* Re-organize traversal tests:
- * Verify recursive algorithms to work
- * 1. with a tree filled with given data
- * 2. with an empty tree
- * Same for iterators
- * Start with an empty tree, fill it with data. At each step, check if
- cursor and iterator algorithms yield the same result.
- (Or, alternatively, if neither is to be trusted: compare to subsets of
- the complete test data.)
- * With the tree complete, do the same recursively for all its subtrees.
-* Also test copy with two trees (not just one tree and a container/output iterator)
-* /Possibly/ move detail/algorithm/cursor/ to detail/cursor/algorithm/ or even just
- detail/cursor/ (same for iterator).
-* Make *order iterators work with empty subtrees; same for cursor algorithms.
+* Make algorithms work with empty subtrees.
(Not necessarily! If that means a check for empty(), it's better to leave it to
the user!)
* Investigate the lower_bound for search vs insert purposes problem.
@@ -127,9 +94,6 @@
Let the cursor based *order algorithms then copy its elements into linear structures
and compare these linear structures to an iterator-based *order traversal.
* Should const_cursor have cbegin(), cend() and cparent() members?
-* Implement "flat" (sequential *order representation) trees (cf. Knuth, Fundamental Algorithms,
- 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)
* We might need still more binary_tree members for more efficient functions operating on
ranges...
@@ -143,6 +107,29 @@
* Start an RFC: what subtree algorithms should there be? In particular, of which of
the STL's linear algorithms should there be a hierarchical version?
+Testing:
+* Re-merge algorithm tests into algorithm_test.cpp after they're all tidied up?
+* Clean up binary_tree_test
+* Re-organize traversal tests:
+ * Verify algorithms to work
+ * 1. with at least one tree filled with given data
+ * 2. with an empty tree
+ Minimize possible points of failure, ie always compare to pre-defined test data.
+
+Testing tools:
+* Possibly calculate *order positions from level order indices
+ as of fake_binary_tree. Possibly change fake_binary_tree internal representation to a
+ vector<bool> with indices indicating the level order position (and also the value),
+ and values indicating "empty or not".
+
+Performance tests:
+* Implement a real output cursor (if possible) and use copy(preorder(), ...) to build a new tree.
+ Then, do some performance measurements comparing
+ * Different *orders;
+ * BOOST_RECURSIVE_ORDER_ALGORITHMS on and off;
+ * cursor and iterator based algorithms (from Boost.Tree and the STL, respectively)
+ Do these measurements also with algorithms other than copy.
+
Pre-release:
* Look into
* boost/graph/tree_traits.hpp
@@ -161,6 +148,8 @@
(preorder copy; ideally, we can guarantee RAII for every single element)
and clear/dtor (postorder for_each).
* Deprecate non-preorder insert cursors.
+* Implement "flat" (sequential *order representation) trees (cf. Knuth, Fundamental Algorithms,
+ pp. 348--351). Possibly useful for automated testing of "real" (binary, forest) trees.
Ask on the mailing list:
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -94,7 +94,6 @@
*/
cursor begin()
{
- //cursor c(h.root());
return cursor(h.root());
}
@@ -113,7 +112,6 @@
*/
const_cursor cbegin() const
{
- //const_cursor c(h.croot());
return const_cursor(h.croot());
}
@@ -146,8 +144,7 @@
const_cursor cend() const
{
base_const_cursor b(h.croot());
- while (!b.is_leaf())
- b.to_end();
+ to_rightmost(b);
return const_cursor(b);
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -10,7 +10,6 @@
#include <boost/test/included/unit_test.hpp>
#include <boost/test/test_case_template.hpp>
-
#include "test_tree_traversal_data.hpp"
#include "mock_binary_cursor.hpp"
@@ -23,24 +22,30 @@
BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_descending, Order, orders )
{
- typedef std::vector< std::pair<std::size_t, int> > container_type;
- container_type po(11);
- generate_mock_cursor_data(Order(), po);
- container_type::const_iterator ci = po.begin();
- container_type::const_iterator cie = po.end();
- mock_binary_cursor< container_type::const_iterator > mc(ci, cie);
-
+ test_data_set mpo;
+ mock_cursor_data(mpo);
+
+ typedef typename test_data_set::index<Order>::type container_type;
+ const container_type& order_index = mpo.get<Order>();
+
+ typename container_type::const_iterator ci = order_index.begin();
+ typename container_type::const_iterator cie = order_index.end();
+ mock_binary_cursor< typename container_type::const_iterator > mc(ci, cie);
+
boost::tree::copy(Order(), fbt1.descending_root(), mc);
}
BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_ascending, Order, orders )
{
- typedef std::vector< std::pair<std::size_t, int> > container_type;
- container_type po(11);
- generate_mock_cursor_data(Order(), po);
- container_type::const_iterator ci = po.begin();
- container_type::const_iterator cie = po.end();
- mock_binary_cursor< container_type::const_iterator > mc(ci, cie);
+ test_data_set mpo;
+ mock_cursor_data(mpo);
+
+ typedef typename test_data_set::index<Order>::type container_type;
+ const container_type& order_index = mpo.get<Order>();
+
+ typename container_type::const_iterator ci = order_index.begin();
+ typename container_type::const_iterator cie = order_index.end();
+ mock_binary_cursor< typename container_type::const_iterator > mc(ci, cie);
boost::tree::copy(Order(), fbt1.ascending_root(), mc);
}
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-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -12,7 +12,7 @@
#include <vector>
-
+#include "test_data.hpp"
template <class T>
struct fake_descending_binary_cursor;
@@ -283,19 +283,22 @@
fake_binary_tree<int> generate_fake_binary_tree()
{
- fake_binary_tree<int> mt(57);
+ test_data_set mpo;
+ mock_cursor_data(mpo);
- mt.m_data[0] = 8;
- mt.m_data[1] = 3;
- mt.m_data[2] = 10;
- mt.m_data[3] = 1;
- mt.m_data[4] = 6;
- mt.m_data[6] = 14;
- mt.m_data[9] = 4;
- mt.m_data[10] = 7;
- mt.m_data[13] = 13;
- mt.m_data[27] = 11;
- mt.m_data[56] = 12;
+ typedef test_data_set::nth_index<0>::type container_type;
+ const container_type& order_index = mpo.get<0>();
+
+ container_type::const_iterator ci = order_index.begin();
+ container_type::const_iterator cie = order_index.end();
+
+ fake_binary_tree<int> mt(57);
+
+ for(;ci!=cie;++ci) {
+ if (ci->pos_level >= mt.m_data.size())
+ mt.m_data.resize(ci->pos_level + 1);
+ mt.m_data[ci->pos_level] = ci->val;
+ }
return mt;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/for_each_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/for_each_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/for_each_test.cpp 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -33,24 +33,28 @@
mock_unary_functor(mock_unary_functor<Iter> const& other)
: m_iter(other.m_iter), m_end(other.m_end) {}
- void operator()(typename Iter::value_type::second_type const& val)
+ void operator()(typename Iter::value_type::value_type const& val)
{
BOOST_CHECK(m_iter != m_end);
if (m_iter == m_end)
return;
- BOOST_CHECK_EQUAL(val, m_iter->second);
+ BOOST_CHECK_EQUAL(val, m_iter->val);
++m_iter;
}
};
BOOST_AUTO_TEST_CASE_TEMPLATE( test_for_each_descending, Order, orders)
{
- typedef std::vector< std::pair<std::size_t, int> > container_type;
- container_type po(11);
- generate_mock_cursor_data(Order(), po);
- container_type::const_iterator ci = po.begin();
- container_type::const_iterator cie = po.end();
- mock_unary_functor<container_type::const_iterator> muc(ci, cie);
+ test_data_set mpo;
+ mock_cursor_data(mpo);
+
+ typedef typename test_data_set::index<Order>::type container_type;
+ const container_type& order_index = mpo.get<Order>();
+
+ typename container_type::const_iterator ci = order_index.begin();
+ typename container_type::const_iterator cie = order_index.end();
+
+ mock_unary_functor<typename container_type::const_iterator> muc(ci, cie);
boost::tree::for_each(
Order(),
fbt1.descending_root(),
@@ -60,12 +64,16 @@
BOOST_AUTO_TEST_CASE_TEMPLATE( test_for_each_ascending, Order, orders)
{
- typedef std::vector< std::pair<std::size_t, int> > container_type;
- container_type po(11);
- generate_mock_cursor_data(Order(), po);
- container_type::const_iterator ci = po.begin();
- container_type::const_iterator cie = po.end();
- mock_unary_functor<container_type::const_iterator> muc(ci, cie);
+ test_data_set mpo;
+ mock_cursor_data(mpo);
+
+ typedef typename test_data_set::index<Order>::type container_type;
+ const container_type& order_index = mpo.get<Order>();
+
+ typename container_type::const_iterator ci = order_index.begin();
+ typename container_type::const_iterator cie = order_index.end();
+
+ mock_unary_functor<typename container_type::const_iterator> muc(ci, cie);
boost::tree::for_each(
Order(),
fbt1.ascending_root(),
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -7,6 +7,8 @@
#ifndef LIBS_TREE_TEST_MOCK_BINARY_CURSOR_HPP
#define LIBS_TREE_TEST_MOCK_BINARY_CURSOR_HPP
+#include "test_data.hpp"
+
template <class Iter>
class mock_binary_cursor;
@@ -40,13 +42,13 @@
mock_binary_cursor(mock_binary_cursor<Iter> const& other)
: m_iter(other.m_iter), m_end(other.m_end), m_pos(other.m_pos) {}
- void operator=(typename Iter::value_type::second_type const& val)
+ void operator=(typename Iter::value_type::value_type const& val)
{
BOOST_CHECK(m_iter != m_end);
if (m_iter == m_end)
return;
- BOOST_CHECK_EQUAL((m_pos-1)/2, m_iter->first);
- BOOST_CHECK_EQUAL(val, m_iter->second);
+ BOOST_CHECK_EQUAL((m_pos-1)/2, m_iter->pos_level);
+ BOOST_CHECK_EQUAL(val, m_iter->val);
++m_iter;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -31,20 +31,23 @@
{
fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root();
to_last(Order(), c);
- // Replace by a fake_to_first function for dependency minimization's sake?
+ // Replace by a fake_to_last function for dependency minimization's sake?
// preorder: fbt1.root_tracking_root().end().end().begin().begin().end().begin();
// inorder: fbt1.root_tracking_root().end().end().begin();
// postorder: fbt1.root_tracking_root().begin();
- typedef std::vector< std::pair<std::size_t, int> > container_type;
- container_type po(11);
- generate_mock_cursor_data(Order(), po);
- container_type::const_iterator cib = po.begin();
- container_type::const_iterator ci = po.end();
+ test_data_set mpo;
+ mock_cursor_data(mpo);
+
+ typedef typename test_data_set::index<Order>::type container_type;
+ const container_type& order_index = mpo.get<Order>();
+
+ typename container_type::const_iterator cib = order_index.begin();
+ typename container_type::const_iterator ci = order_index.end();
for (--ci; ci!=cib; --ci) {
boost::tree::predecessor(Order(), c);
- BOOST_CHECK_EQUAL(*c, ci->second);
+ BOOST_CHECK_EQUAL(*c, ci->val);
}
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -33,14 +33,17 @@
// preorder: fbt1.root_tracking_root().begin();
// in- and postorder: fbt1.root_tracking_root().begin().begin().begin();
- typedef std::vector< std::pair<std::size_t, int> > container_type;
- container_type po(11);
- generate_mock_cursor_data(Order(), po);
- container_type::const_iterator ci = po.begin();
- container_type::const_iterator cie = po.end();
+ test_data_set mpo;
+ mock_cursor_data(mpo);
+
+ typedef typename test_data_set::index<Order>::type container_type;
+ const container_type& order_index = mpo.get<Order>();
+
+ typename container_type::const_iterator ci = order_index.begin();
+ typename container_type::const_iterator cie = order_index.end();
for (; ci!=cie; ++ci) {
- BOOST_CHECK_EQUAL(*c, ci->second);
+ BOOST_CHECK_EQUAL(*c, ci->val);
boost::tree::successor(Order(), c);
}
}
Copied: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_data.hpp (from r52130, /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_data.hpp 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -4,123 +4,67 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
-#define LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
+#ifndef LIBS_TREE_TEST_TEST_DATA_HPP
+#define LIBS_TREE_TEST_TEST_DATA_HPP
#include <boost/tree/algorithm.hpp>
-#include <boost/mpl/list.hpp>
-
-typedef boost::mpl::list<boost::tree::preorder
- ,boost::tree::inorder
- ,boost::tree::postorder> orders;
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/member.hpp>
+
+struct test_data {
+ typedef std::size_t size_type;
+ typedef int value_type;
-template <class Cursor>
-static void validate_test_dataset1_tree(Cursor cur)
-{
- BOOST_CHECK_EQUAL(*cur.begin(), 8);
- BOOST_CHECK_EQUAL(*cur.begin().begin(), 3);
- BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 1);
- BOOST_CHECK(cur.begin().begin().end().is_leaf());
- BOOST_CHECK(cur.begin().begin().begin().is_leaf()); //Leaf
+ size_type pos_level;
+ size_type pre;
+ size_type in;
+ size_type post;
- BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 6);
- BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4);
- BOOST_CHECK(cur.begin().end().begin().begin().is_leaf()); //Leaf
-
- BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7);
- BOOST_CHECK(cur.begin().end().end().begin().is_leaf()); //Leaf
-
- BOOST_CHECK_EQUAL(*cur.end().begin(), 10);
- BOOST_CHECK(cur.end().begin().is_leaf());
- BOOST_CHECK_EQUAL(*cur.end().end().begin(), 14);
- BOOST_CHECK(cur.end().end().end().is_leaf());
- BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 13);
- BOOST_CHECK(cur.end().end().begin().end().is_leaf());
- BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 11);
- BOOST_CHECK(cur.end().end().begin().begin().begin().is_leaf());
- BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 12);
- BOOST_CHECK(cur.end().end().begin().begin().end().begin().is_leaf()); //Leaf
-}
-
-template <class Cursor>
-static void validate_test_dataset1_minus_1_tree(Cursor cur)
-{
- BOOST_CHECK_EQUAL(*cur.begin(), 7);
- BOOST_CHECK_EQUAL(*cur.begin().begin(), 2);
- BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 0); //Leaf
- BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 5);
- BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 3); //Leaf
- BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 6); //Leaf
-
- BOOST_CHECK_EQUAL(*cur.end().begin(), 9);
- BOOST_CHECK_EQUAL(*cur.end().end().begin(), 13);
- BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 12);
- BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 10);
- BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 11); //Leaf
-}
-
-template <class Container>
-void generate_mock_cursor_data(boost::tree::preorder, Container& data)
-{
- using std::make_pair;
- data[0] = make_pair(0, 8);
- data[1] = make_pair(1, 3);
- data[2] = make_pair(3, 1);
- data[3] = make_pair(4, 6);
- data[4] = make_pair(9, 4);
- data[5] = make_pair(10, 7);
- data[6] = make_pair(2, 10);
- data[7] = make_pair(6, 14);
- data[8] = make_pair(13, 13);
- data[9] = make_pair(27, 11);
- data[10] = make_pair(56, 12);
-}
-
-template <class Container>
-void generate_mock_cursor_data(boost::tree::inorder, Container& data)
-{
- using std::make_pair;
- data[0] = make_pair(3, 1);
- data[1] = make_pair(1, 3);
- data[2] = make_pair(9, 4);
- data[3] = make_pair(4, 6);
- data[4] = make_pair(10, 7);
- data[5] = make_pair(0, 8);
- data[6] = make_pair(2, 10);
- data[7] = make_pair(27, 11);
- data[8] = make_pair(56, 12);
- data[9] = make_pair(13, 13);
- data[10] = make_pair(6, 14);
-}
-
-template <class Container>
-void generate_mock_cursor_data(boost::tree::postorder, Container& data)
-{
- using std::make_pair;
- data[0] = make_pair(3, 1);
- data[1] = make_pair(9, 4);
- data[2] = make_pair(10, 7);
- data[3] = make_pair(4, 6);
- data[4] = make_pair(1, 3);
- data[5] = make_pair(56, 12);
- data[6] = make_pair(27, 11);
- data[7] = make_pair(13, 13);
- data[8] = make_pair(6, 14);
- data[9] = make_pair(2, 10);
- data[10] = make_pair(0, 8);
+ value_type val;
+
+ test_data(size_type lop, size_type _pre, size_type _in, size_type _post, int v)
+ : pos_level (lop)
+ , pre(_pre), in(_in), post(_post)
+ , val(v)
+ {}
+
+ size_type const& get(boost::tree::preorder) const { return pre; }
+ size_type const& get(boost::tree::inorder) const { return in; }
+ size_type const& get(boost::tree::postorder) const { return post; }
+};
+
+template <class Cont>
+void mock_cursor_data(Cont& data)
+{
+ data.insert(test_data( 0, 0, 5,10, 8));
+ data.insert(test_data( 1, 1, 1, 4, 3));
+ data.insert(test_data( 3, 2, 0, 0, 1));
+ data.insert(test_data( 4, 3, 3, 3, 6));
+ data.insert(test_data( 9, 4, 2, 1, 4));
+ data.insert(test_data(10, 5, 4, 2, 7));
+ data.insert(test_data( 2, 6, 6, 9,10));
+ data.insert(test_data( 6, 7,10, 8,14));
+ data.insert(test_data(13, 8, 9, 7,13));
+ data.insert(test_data(27, 9, 7, 6,11));
+ data.insert(test_data(56,10, 8, 5,12));
}
-template <class Iterator>
-void test_traversal_from_leaf4(Iterator a, Iterator b)
-{
- BOOST_CHECK_EQUAL(*a, 4);
- BOOST_CHECK_EQUAL(*++a, 6);
- BOOST_CHECK_EQUAL(*++a, 3);
- BOOST_CHECK_EQUAL(*++a, 8);
- BOOST_CHECK(++a == b);
-
-} // namespace ascending
-
+using boost::multi_index::indexed_by;
+using boost::multi_index::member;
+using boost::multi_index::ordered_unique;
+using boost::multi_index::tag;
+
+typedef boost::multi_index::multi_index_container<
+ test_data,
+ indexed_by<
+ ordered_unique< member<test_data,test_data::size_type,&test_data::pos_level> >,
+
+ ordered_unique<tag<boost::tree::preorder>,member<test_data,test_data::size_type,&test_data::pre> >,
+ ordered_unique<tag<boost::tree::inorder>,member<test_data,test_data::size_type,&test_data::in> >,
+ ordered_unique<tag<boost::tree::postorder>,member<test_data,test_data::size_type,&test_data::post> >
+ >
+> test_data_set;
-#endif // LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
+#endif // LIBS_TREE_TEST_TEST_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 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -4,8 +4,8 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-#ifndef LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
-#define LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
+#ifndef LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_DATA_HPP
+#define LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_DATA_HPP
#include <boost/tree/algorithm.hpp>
@@ -14,7 +14,7 @@
typedef boost::mpl::list<boost::tree::preorder
,boost::tree::inorder
,boost::tree::postorder> orders;
-
+
template <class Cursor>
static void validate_test_dataset1_tree(Cursor cur)
{
@@ -60,57 +60,6 @@
BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 11); //Leaf
}
-template <class Container>
-void generate_mock_cursor_data(boost::tree::preorder, Container& data)
-{
- using std::make_pair;
- data[0] = make_pair(0, 8);
- data[1] = make_pair(1, 3);
- data[2] = make_pair(3, 1);
- data[3] = make_pair(4, 6);
- data[4] = make_pair(9, 4);
- data[5] = make_pair(10, 7);
- data[6] = make_pair(2, 10);
- data[7] = make_pair(6, 14);
- data[8] = make_pair(13, 13);
- data[9] = make_pair(27, 11);
- data[10] = make_pair(56, 12);
-}
-
-template <class Container>
-void generate_mock_cursor_data(boost::tree::inorder, Container& data)
-{
- using std::make_pair;
- data[0] = make_pair(3, 1);
- data[1] = make_pair(1, 3);
- data[2] = make_pair(9, 4);
- data[3] = make_pair(4, 6);
- data[4] = make_pair(10, 7);
- data[5] = make_pair(0, 8);
- data[6] = make_pair(2, 10);
- data[7] = make_pair(27, 11);
- data[8] = make_pair(56, 12);
- data[9] = make_pair(13, 13);
- data[10] = make_pair(6, 14);
-}
-
-template <class Container>
-void generate_mock_cursor_data(boost::tree::postorder, Container& data)
-{
- using std::make_pair;
- data[0] = make_pair(3, 1);
- data[1] = make_pair(9, 4);
- data[2] = make_pair(10, 7);
- data[3] = make_pair(4, 6);
- data[4] = make_pair(1, 3);
- data[5] = make_pair(56, 12);
- data[6] = make_pair(27, 11);
- data[7] = make_pair(13, 13);
- data[8] = make_pair(6, 14);
- data[9] = make_pair(2, 10);
- data[10] = make_pair(0, 8);
-}
-
template <class Iterator>
void test_traversal_from_leaf4(Iterator a, Iterator b)
{
@@ -122,5 +71,4 @@
} // namespace ascending
-
-#endif // LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
+#endif // LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_DATA_HPP
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/transform_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/transform_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/transform_test.cpp 2009-04-02 11:32:48 EDT (Thu, 02 Apr 2009)
@@ -24,26 +24,30 @@
BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform_descending, Order, orders)
{
- typedef std::vector< std::pair<std::size_t, int> > container_type;
- container_type po(11);
- generate_mock_cursor_data(Order(), po);
- //std::transform(po.begin(), po.end(), po.begin(), std::bind2nd(std::plus<int>(/*second member of pair*/),0))
- container_type::const_iterator ci = po.begin();
- container_type::const_iterator cie = po.end();
- mock_binary_cursor< container_type::const_iterator > mc(ci, cie);
+ test_data_set mpo;
+ mock_cursor_data(mpo);
+
+ typedef typename test_data_set::index<Order>::type container_type;
+ const container_type& order_index = mpo.get<Order>();
+
+ typename container_type::const_iterator ci = order_index.begin();
+ typename container_type::const_iterator cie = order_index.end();
+ mock_binary_cursor< typename container_type::const_iterator > mc(ci, cie);
boost::tree::transform(Order(), fbt1.descending_root(), mc, std::bind2nd(std::plus<int>(),0));
}
BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform_ascending, Order, orders)
{
- typedef std::vector< std::pair<std::size_t, int> > container_type;
- container_type po(11);
- generate_mock_cursor_data(Order(), po);
- //std::transform(po.begin(), po.end(), po.begin(), std::bind2nd(std::plus<int>(/*second member of pair*/),0))
- container_type::const_iterator ci = po.begin();
- container_type::const_iterator cie = po.end();
- mock_binary_cursor< container_type::const_iterator > mc(ci, cie);
+ test_data_set mpo;
+ mock_cursor_data(mpo);
+
+ typedef typename test_data_set::index<Order>::type container_type;
+ const container_type& order_index = mpo.get<Order>();
+
+ typename container_type::const_iterator ci = order_index.begin();
+ typename container_type::const_iterator cie = order_index.end();
+ mock_binary_cursor< typename container_type::const_iterator > mc(ci, cie);
boost::tree::transform(Order(), fbt1.ascending_root(), mc, std::bind2nd(std::plus<int>(),0));
}