[Boost-commit] svn:boost r52132 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test

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));
 }