Subject: [Boost-commit] svn:boost r50395 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/example libs/tree/test
From: ockham_at_[hidden]
Date: 2008-12-28 17:49:08
Author: bernhard.reiter
Date: 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
New Revision: 50395
URL: http://svn.boost.org/trac/boost/changeset/50395
Log:
Introduce fake_binary_cursor (for testing purposes).
Added:
sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 5
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 3
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp | 4
sandbox/SOC/2006/tree/trunk/libs/tree/example/Jamfile.v2 | 11 ++
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp | 5
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 4
sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp | 80 ++++++++++--------
sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp | 4
sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp | 175 ++++++++++++++++++++++-----------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp | 130 ++++++++++++++++-------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 95 ++-------------------
12 files changed, 247 insertions(+), 271 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -15,12 +15,11 @@
General:
* Rename node -> ascending_node; implement descending_node; and corresponding cursors.
-* Fix freestanding parity().
+* 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.
* Add a congruence check algorithm (compare shapes of subtrees; call it "similar()"?).
-* I'd like to make algorithm checks more independent of the sanity of binary_tree; so a mock object
- would be really useful. Maybe something like a map of maps or a property_tree?
+* Finish moving algorithm checks etc. to fake_binary_tree.
* Revisit binary_tree . Can it be usable for both balanced and forest trees and still be
"light-weight" at the same time? Solution: Introduce an "inorder_optimised_binary_tree"
(with O(1) inorder first and last cursors, and possibly
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -62,6 +62,7 @@
typedef ascending_cursor<DescendingCursor> self_type;
public:
typedef typename DescendingCursor::value_type value_type;
+ typedef typename DescendingCursor::reference reference;
// Container-specific:
typedef typename DescendingCursor::size_type size_type;
@@ -111,7 +112,7 @@
std::stack<DescendingCursor> m_s; // pimpl?
- value_type& dereference() const
+ reference dereference() const
{
return *m_s.top();
}
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-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -240,7 +240,7 @@
template <class InputCursor>
cursor insert(cursor pos, InputCursor subtree)
{
-// // Optimise insert_cursor before using this
+// // Optimise insert_cursor (or introduce another class) before using this
// return cursor(boost::tree::copy(boost::tree::preorder()
// , subtree
// , boost::tree::tree_inserter(*this, pos)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -59,7 +59,7 @@
}
template <class Facade>
- static typename Facade::size_type par(Facade const& f)
+ static typename Facade::size_type idx(Facade const& f)
{
return f.idx();
}
@@ -158,7 +158,7 @@
size_type const index() const
{
- return cursor_core_access::par(this->derived());
+ return cursor_core_access::idx(this->derived());
}
Derived& to_begin()
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/example/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/example/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/example/Jamfile.v2 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -50,4 +50,13 @@
return $(all_rules) ;
}
-test-suite test_example : [ test_all r ] ;
\ No newline at end of file
+test-suite test_example : [ test_all r ] ;
+
+#install dist
+# :
+# test_example
+# :
+# <location>./doc
+# :
+# release
+# ;
\ No newline at end of file
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_search_test.cpp 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -26,9 +26,10 @@
BOOST_FIXTURE_TEST_SUITE(binary_tree_search_test, test_binary_tree_with_list_fixture<int>)
-void search_single_element(binary_tree<int>::const_cursor r, int v)
+template <class Cursor>
+void search_single_element(Cursor r, int v)
{
- binary_tree<int>::const_cursor c, d;
+ Cursor c, d;
c = lower_bound(r, v);
d = upper_bound(r, v);
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-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -12,11 +12,13 @@
//#define BOOST_TEST_DYN_LINK
#include <boost/test/included/unit_test.hpp>
-#include "helpers.hpp"
+//#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
BOOST_AUTO_TEST_SUITE( basic_binary_tree_test )
+using boost::tree::binary_tree;
+
BOOST_AUTO_TEST_CASE( constructors_test )
{
binary_tree<int> bt0;
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-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -23,25 +23,33 @@
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
+#include "fake_binary_tree.hpp"
+
using namespace boost::tree;
-BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, test_binary_tree_with_list_fixture<int>)
+BOOST_FIXTURE_TEST_SUITE(cursor_algorithms, fake_binary_tree_fixture<int>)
BOOST_AUTO_TEST_CASE_TEMPLATE( test_foreach, Order, orders)
{
+ fake_binary_tree<int> mt = generate_fake_binary_tree();
+ std::list<int> l;
boost::tree::for_each(
Order(),
- bt.root(),
+ mbt1.root(),
boost::lambda::bind(&std::list<int>::push_back, &l, boost::lambda::_1)
);
test_traversal(Order(), l.begin(), l.end());
}
+BOOST_AUTO_TEST_SUITE_END()
+
+BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_with_list_fixture<int>)
+
BOOST_AUTO_TEST_CASE( test_foreach_subtree3 )
{
boost::tree::for_each(
preorder(),
- bt.root().begin(),
+ mbt1.root().begin(),
boost::lambda::bind(&std::list<int>::push_back, &l, boost::lambda::_1)
);
test_subtree_traversal(preorder(), l.begin(), l.end(), 1);
@@ -50,56 +58,56 @@
BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy, Order, orders)
{
- boost::tree::copy(Order(), bt.root(), o);
+ boost::tree::copy(Order(), mbt1.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.root());
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE ( test_desc_copy_using_insert_cursor, Order, orders )
-{
- bt2.clear();
-
- boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
- , boost::forward_traversal_tag());
-
- validate_test_dataset1_tree(bt2.root());
- BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
-}
-
-BOOST_AUTO_TEST_CASE_TEMPLATE ( test_asc_copy_using_insert_cursor, Order, orders )
-{
- bt2.clear();
-
- boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
- , boost::bidirectional_traversal_tag());
-
- validate_test_dataset1_tree(bt2.root());
- BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
-}
+ BOOST_CHECK(mbt1 != mbt2);
+ boost::tree::copy(Order(), mbt1.root(), mbt2.root());
+ BOOST_CHECK(mbt1 == mbt2);
+ validate_test_dataset1_tree(mbt2.root());
+}
+
+//BOOST_AUTO_TEST_CASE_TEMPLATE ( test_desc_copy_using_insert_cursor, Order, orders )
+//{
+// bt2.clear();
+//
+// boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
+// , boost::forward_traversal_tag());
+//
+// validate_test_dataset1_tree(bt2.root());
+// BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
+//}
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE ( test_asc_copy_using_insert_cursor, Order, orders )
+//{
+// bt2.clear();
+//
+// boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
+// , boost::bidirectional_traversal_tag());
+//
+// validate_test_dataset1_tree(bt2.root());
+// BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
+//}
BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform, Order, orders)
{
// First copy test_tree to test_tree2, by adding 1 to each element,
// then copy test_tree2 to test_list, by subtracting 1 - so
// test_list should hold test_tree's original elements in ORDER.
- boost::tree::transform(Order(), bt.root(), bt2.root(), std::bind2nd(std::plus<int>(),1));
- boost::tree::transform(Order(), bt2.root(), o, std::bind2nd(std::minus<int>(),1));
+ boost::tree::transform(Order(), mbt1.root(), mbt2.root(), std::bind2nd(std::plus<int>(),1));
+ boost::tree::transform(Order(), mbt2.root(), o, std::bind2nd(std::minus<int>(),1));
test_traversal(Order(), l.begin(), l.end());
}
BOOST_AUTO_TEST_CASE_TEMPLATE( test_transform_trees, Order, orders)
{
- BOOST_CHECK(bt != bt2);
- boost::tree::transform(Order(), bt.root(), bt2.root()
+ BOOST_CHECK(mbt1 != mbt2);
+ boost::tree::transform(Order(), mbt1.root(), mbt2.root()
, std::bind2nd(std::minus<int>(),1));
- validate_test_dataset1_minus_1_tree(bt2.root());
+ validate_test_dataset1_minus_1_tree(mbt2.root());
}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
Added: sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -0,0 +1,273 @@
+// Copyright (c) 2006-2008, Bernhard Reiter
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef LIBS_TREE_TEST_FAKE_BINARY_TREE_HPP
+#define LIBS_TREE_TEST_FAKE_BINARY_TREE_HPP
+
+#include <boost/tree/cursor_adaptor.hpp>
+
+#include <vector>
+
+#include "helpers.hpp"
+
+template <class T>
+struct fake_binary_tree_cursor;
+
+/// See http://en.wikipedia.org/wiki/Binary_Tree#Methods_for_storing_binary_trees
+template <class T>
+struct fake_binary_tree {
+ typedef fake_binary_tree_cursor<T> cursor;
+ typedef fake_binary_tree_cursor<T const> const_cursor;
+
+ fake_binary_tree(typename std::vector<T>::size_type s) : m_data(s)
+ { }
+
+ cursor root()
+ {
+ return cursor(*this, 0);
+ }
+
+ typedef std::vector<T> children_type;
+ typedef typename children_type::size_type size_type;
+ typedef typename children_type::value_type value_type;
+ typedef typename children_type::difference_type difference_type;
+ typedef typename children_type::pointer pointer;
+ typedef typename children_type::reference reference;
+
+ children_type m_data;
+};
+
+template <class T>
+bool operator==(fake_binary_tree<T> const& x, fake_binary_tree<T> const& y)
+{
+ return (x.m_data == y.m_data);
+}
+
+template <class T>
+bool operator!=(fake_binary_tree<T> const& x, fake_binary_tree<T> const& y)
+{
+ return !(x == y);
+}
+
+// Make this use cursor_adaptor. Yes, even if that means relying on it.
+template <class T>
+struct fake_binary_tree_cursor {
+ typedef boost::forward_traversal_tag vertical_traversal;
+ typedef boost::bidirectional_traversal_tag horizontal_traversal;
+ typedef horizontal_traversal iterator_category;
+ typedef typename fake_binary_tree<T>::value_type value_type;
+ typedef typename fake_binary_tree<T>::difference_type difference_type;
+ typedef typename fake_binary_tree<T>::pointer pointer;
+ typedef typename fake_binary_tree<T>::reference reference;
+
+ typedef typename fake_binary_tree<T>::size_type size_type;
+
+ typedef fake_binary_tree_cursor<T> cursor;
+ typedef fake_binary_tree_cursor<T const> const_cursor;
+
+
+ //typedef typename fake_binary_tree<T>::children_type::value_type cur;
+ //cur c;
+ fake_binary_tree<T>& m_tree;
+ typename fake_binary_tree<T>::size_type m_pos;
+
+ explicit fake_binary_tree_cursor(fake_binary_tree<T>& t, size_type p = 0) : m_tree(t), m_pos(p) {}
+ //fake_binary_tree_cursor(fake_binary_tree_cursor const& mtc) : c(mtc.c), bgn(false) {}
+
+ T const& operator*() const
+ {
+ return m_tree.m_data[m_pos];
+ }
+
+ T& operator*()
+ {
+ return m_tree.m_data[(m_pos-1)/2];
+ }
+
+ fake_binary_tree_cursor& to_begin()
+ {
+ m_pos <<= 1;
+ ++m_pos;
+ return *this;
+ }
+
+ fake_binary_tree_cursor begin()
+ {
+ fake_binary_tree_cursor tmp(*this);
+ tmp.to_begin();
+ return tmp;
+ }
+
+ fake_binary_tree_cursor& to_end()
+ {
+ ++m_pos;
+ m_pos <<= 1;
+ return *this;
+ }
+
+ fake_binary_tree_cursor end()
+ {
+ fake_binary_tree_cursor tmp(*this);
+ tmp.to_end();
+ return tmp;
+ }
+
+ fake_binary_tree_cursor& operator++()
+ {
+ ++m_pos;
+ return *this;
+ }
+
+ fake_binary_tree_cursor& operator--()
+ {
+ --m_pos;
+ return *this;
+ }
+
+ bool empty() const
+ {
+ if (m_pos >= m_tree.m_data.size())
+ return true;
+ if (m_pos == 0)
+ return false;
+ return (m_tree.m_data[m_pos] == 0);
+ }
+
+ size_type index() const
+ {
+ return (m_pos + 1) % 2;
+ }
+};
+
+template <class T>
+bool operator==(fake_binary_tree_cursor<T> const& x, fake_binary_tree_cursor<T> const& y)
+{
+ return (x.m_tree == y.m_tree) && (x.m_pos == y.m_pos);
+}
+
+template <class T>
+bool operator!=(fake_binary_tree_cursor<T> const& x, fake_binary_tree_cursor<T> const& y)
+{
+ return !(x==y);
+}
+
+template <class T>
+struct fake_ascending_binary_tree_cursor;
+
+template <class T>
+struct fake_ascending_binary_tree_cursor
+: public boost::tree::cursor_adaptor<fake_ascending_binary_tree_cursor<T>
+ , fake_binary_tree_cursor<T> >
+{
+ typedef fake_ascending_binary_tree_cursor<T> cursor;
+ typedef fake_ascending_binary_tree_cursor<T const> const_cursor;
+
+ fake_ascending_binary_tree_cursor(fake_binary_tree<T>& t
+ , typename fake_binary_tree<T>::size_type p)
+ : fake_ascending_binary_tree_cursor::cursor_adaptor_(fake_binary_tree_cursor<T>(t, p)) {}
+
+private:
+ friend class boost::iterator_core_access;
+ friend class boost::tree::cursor_core_access;
+
+ void up()
+ {
+ --this->base_reference().m_pos;
+ this->base_reference().m_pos >>= 1;
+ }
+};
+
+//template <class T>
+//struct fake_ascending_binary_tree_cursor
+//: public fake_binary_tree_cursor<T> {
+// fake_ascending_binary_tree_cursor(fake_binary_tree<T>& t
+// , typename fake_binary_tree<T>::size_type p)
+// : fake_binary_tree_cursor<T>(t, p) {}
+//
+// fake_ascending_binary_tree_cursor& to_parent()
+// {
+// --fake_binary_tree_cursor<T>::m_pos;
+// fake_binary_tree_cursor<T>::m_pos >>= 1;
+// return *this;
+// }
+//
+// fake_ascending_binary_tree_cursor parent()
+// {
+// fake_ascending_binary_tree_cursor tmp(*this);
+// tmp.to_parent();
+// return tmp;
+// }
+//};
+
+fake_binary_tree<int> generate_fake_binary_tree()
+{
+ fake_binary_tree<int> mt(57);
+
+ 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;
+
+ return mt;
+}
+
+template <class T = int>
+struct fake_binary_tree_fixture {
+ fake_binary_tree_fixture() : mbt1(generate_fake_binary_tree()), mbt2(57) {}
+
+ 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); //Leaf
+ BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 6);
+ BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4); //Leaf
+ BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7); //Leaf
+ BOOST_CHECK_EQUAL(*cur.end().begin(), 10);
+ BOOST_CHECK_EQUAL(*cur.end().end().begin(), 14);
+ BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 13);
+ BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 11);
+ BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 12); //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
+ }
+
+ fake_binary_tree<T> mbt1, mbt2;
+};
+
+template <class T = int>
+struct fake_binary_tree_with_list_fixture
+: public fake_binary_tree_fixture<T>
+, public test_with_list_fixture {
+ fake_binary_tree_with_list_fixture()
+ : fake_binary_tree_fixture<T>()
+ , test_with_list_fixture() {}
+};
+
+#endif // LIBS_TREE_TEST_FAKE_BINARY_TREE_HPP
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/graph_test.cpp 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -16,10 +16,12 @@
#include <list>
#include <iterator>
+#include <boost/tree/balanced_tree.hpp>
+
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
-typedef augmented_type< int, boost::default_color_type > data_type;
+typedef boost::tree::augmented_type< int, boost::default_color_type > data_type;
BOOST_FIXTURE_TEST_SUITE(graph_algorithms_test, test_binary_tree_with_list_fixture<data_type>)
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp 2008-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -7,90 +7,111 @@
#ifndef LIBS_TREE_TEST_HELPERS_HPP
#define LIBS_TREE_TEST_HELPERS_HPP
-#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/balanced_tree.hpp>
-#include <boost/tree/searcher.hpp>
+//#include <boost/tree/binary_tree.hpp>
+//#include <boost/tree/balanced_tree.hpp>
+//#include <boost/tree/searcher.hpp>
+//
+//#include <boost/multi_index/identity.hpp>
-#include <boost/multi_index/identity.hpp>
-#include <boost/mpl/list.hpp>
+#include <boost/tree/output_iterator_cursor.hpp>
-using namespace boost::tree;
+#include <boost/mpl/list.hpp>
-using boost::multi_index::identity;
+#include <list>
-typedef boost::mpl::list<preorder,inorder,postorder> orders;
+struct test_with_list_fixture
+{
+ typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
+ typedef boost::tree::output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
-/**
- * @brief test_balancer (exposes underlying hierarchy for test purposes)
- */
-// TODO: Ctor, dtors
-template <class Hier, class Balance>
-struct test_balancer
- : public balanced_tree<Hier, Balance> {
-
- typedef typename balanced_tree<Hier, Balance>::hierarchy_type hierarchy_type;
-
- explicit test_balancer(hierarchy_type const& hier = hierarchy_type())
- : balanced_tree<Hier, Balance>(hier)
- {}
-
- hierarchy_type& hierarchy()
- {
- return this->h;
- }
-};
+ test_with_list_fixture()
+ : l(), i(l), o(i) {}
-/**
- * @brief test_searcher (exposes underlying container for test purposes)
- */
-// TODO: Ctor, dtors
-template <bool Multi, class Sortable, class Extract =
- boost::multi_index::identity<typename Sortable::value_type>,
- class Compare = std::less<typename Extract::result_type> >
-struct test_searcher
- : public searcher<Multi, Sortable, Extract, Compare> {
-// Sortable&
- typename Sortable::hierarchy_type::template rebind<typename Sortable::value_type>::other&
-
- container()
- {
- return this->c;
- }
+ std::list<int> l;
+ back_insert_iter_list_int i;
+ oc_bi_lst_type o;
};
-
-template <class Searcher>
-void create_test_data_searcher(Searcher& my_tree)
-{
- my_tree.insert(8);
- my_tree.insert(10);
- my_tree.insert(14);
- my_tree.insert(13);
- my_tree.insert(11);
- my_tree.insert(12);
-
- my_tree.insert(3);
- my_tree.insert(1);
- my_tree.insert(6);
- my_tree.insert(4);
- my_tree.insert(7);
-}
-
-template <class Searcher>
-void create_test_data_sequence(Searcher& my_tree)
-{
- my_tree.push_back(8);
- my_tree.push_back(10);
- my_tree.push_back(14);
- my_tree.push_back(13);
- my_tree.push_back(11);
- my_tree.push_back(12);
-
- my_tree.push_back(3);
- my_tree.push_back(1);
- my_tree.push_back(6);
- my_tree.push_back(4);
- my_tree.push_back(7);
-}
+typedef boost::mpl::list<boost::tree::preorder
+ ,boost::tree::inorder
+ ,boost::tree::postorder> orders;
+
+//using namespace boost::tree;
+//
+//using boost::multi_index::identity;
+//
+//
+///**
+// * @brief test_balancer (exposes underlying hierarchy for test purposes)
+// */
+//// TODO: Ctor, dtors
+//template <class Hier, class Balance>
+//struct test_balancer
+// : public balanced_tree<Hier, Balance> {
+//
+// typedef typename balanced_tree<Hier, Balance>::hierarchy_type hierarchy_type;
+//
+// explicit test_balancer(hierarchy_type const& hier = hierarchy_type())
+// : balanced_tree<Hier, Balance>(hier)
+// {}
+//
+// hierarchy_type& hierarchy()
+// {
+// return this->h;
+// }
+//};
+//
+///**
+// * @brief test_searcher (exposes underlying container for test purposes)
+// */
+//// TODO: Ctor, dtors
+//template <bool Multi, class Sortable, class Extract =
+// boost::multi_index::identity<typename Sortable::value_type>,
+// class Compare = std::less<typename Extract::result_type> >
+//struct test_searcher
+// : public searcher<Multi, Sortable, Extract, Compare> {
+//// Sortable&
+// typename Sortable::hierarchy_type::template rebind<typename Sortable::value_type>::other&
+//
+// container()
+// {
+// return this->c;
+// }
+//};
+//
+//
+//template <class Searcher>
+//void create_test_data_searcher(Searcher& my_tree)
+//{
+// my_tree.insert(8);
+// my_tree.insert(10);
+// my_tree.insert(14);
+// my_tree.insert(13);
+// my_tree.insert(11);
+// my_tree.insert(12);
+//
+// my_tree.insert(3);
+// my_tree.insert(1);
+// my_tree.insert(6);
+// my_tree.insert(4);
+// my_tree.insert(7);
+//}
+//
+//template <class Searcher>
+//void create_test_data_sequence(Searcher& my_tree)
+//{
+// my_tree.push_back(8);
+// my_tree.push_back(10);
+// my_tree.push_back(14);
+// my_tree.push_back(13);
+// my_tree.push_back(11);
+// my_tree.push_back(12);
+//
+// my_tree.push_back(3);
+// my_tree.push_back(1);
+// my_tree.push_back(6);
+// my_tree.push_back(4);
+// my_tree.push_back(7);
+//}
#endif // LIBS_TREE_TEST_HELPERS_HPP
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-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -18,100 +18,110 @@
#include <boost/test/test_case_template.hpp>
#include <boost/mpl/list.hpp>
-#include "helpers.hpp"
+#include "fake_binary_tree.hpp"
#include "test_tree_traversal_data.hpp"
using namespace boost::tree;
-BOOST_FIXTURE_TEST_SUITE( iterator_algorithms_test, test_binary_tree_with_list_fixture<int> )
+BOOST_FIXTURE_TEST_SUITE( iterator_algorithms_test, fake_binary_tree_with_list_fixture<int> )
BOOST_AUTO_TEST_CASE_TEMPLATE( test_iterator_algorithms, Order, orders )
{
- test_traversal(Order(), begin(Order(), bt.root())
- , end(Order(), bt.root()));
+ fake_ascending_binary_tree_cursor<int> ambtc1(mbt1, 0);
- test_reverse_traversal(Order(), end(Order(), bt.root())
- , begin(Order(), bt.root()));
+ test_traversal(Order(), begin(Order(), ambtc1)
+ , end(Order(), ambtc1));
+
+ test_reverse_traversal(Order(), end(Order(), ambtc1)
+ , begin(Order(), ambtc1));
- BOOST_CHECK_EQUAL(std::distance(begin(Order(), bt.root())
- , end(Order(), bt.root())), 11);
+ BOOST_CHECK_EQUAL(std::distance(begin(Order(), ambtc1)
+ , end(Order(), ambtc1)), 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(), 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);
+// FIXME
+// test_traversal(Order(), begin(Order(), make_ascending_cursor(mbt1.root()))
+// , end(Order(), make_ascending_cursor(mbt1.root())));
+// test_reverse_traversal(Order(), end(Order(), make_ascending_cursor(mbt1.root()))
+// , begin(Order(), make_ascending_cursor(mbt1.root())));
+// BOOST_CHECK_EQUAL(std::distance(
+// begin(Order(), make_ascending_cursor(mbt1.root()))
+// , end(Order(), make_ascending_cursor(mbt1.root()))), 11);
}
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);
+ fake_ascending_binary_tree_cursor<int> ambtc1(mbt1, 0);
+
+ test_subtree_traversal(preorder(), begin(preorder(), ambtc1.begin())
+ , end(preorder(), ambtc1.begin()), 1);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), ambtc1.begin())
+ , end(preorder(), ambtc1.begin())), 5);
+
+ test_subtree_traversal(inorder(), begin(inorder(), ambtc1.begin())
+ , end(inorder(), ambtc1.begin()), 0);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), ambtc1.begin())
+ , end(inorder(), ambtc1.begin())), 5);
+
+ test_subtree_traversal(postorder(), begin(postorder(), ambtc1.begin())
+ , end(postorder(), ambtc1.begin()), 0);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), ambtc1.begin())
+ , end(postorder(), ambtc1.begin())), 5);
}
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);
+ fake_ascending_binary_tree_cursor<int> ambtc1(mbt1, 0);
+
+ test_subtree_traversal(preorder(), begin(preorder(), ambtc1.begin().end())
+ , end(preorder(), ambtc1.begin().end()), 3);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), ambtc1.begin().end())
+ , end(preorder(), ambtc1.begin().end())), 3);
+
+ test_subtree_traversal(inorder(), begin(inorder(), ambtc1.begin().end())
+ , end(inorder(), ambtc1.begin().end()), 2);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), ambtc1.begin().end())
+ , end(inorder(), ambtc1.begin().end())), 3);
+
+ test_subtree_traversal(postorder(), begin(postorder(), ambtc1.begin().end())
+ , end(postorder(), ambtc1.begin().end()), 1);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), ambtc1.begin().end())
+ , end(postorder(), ambtc1.begin().end())), 3);
}
BOOST_AUTO_TEST_CASE( test_subtree10_iterator_algorithms )
{
- 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);
+ fake_ascending_binary_tree_cursor<int> ambtc1(mbt1, 0);
+
+ test_subtree_traversal(preorder(), begin(preorder(), ambtc1.end())
+ , end(preorder(), ambtc1.end()), 6);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), ambtc1.end())
+ , end(preorder(), ambtc1.end())), 5);
+
+ test_subtree_traversal(inorder(), begin(inorder(), ambtc1.end())
+ , end(inorder(), ambtc1.end()), 6);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), ambtc1.end())
+ , end(inorder(), ambtc1.end())), 5);
+
+ test_subtree_traversal(postorder(), begin(postorder(), ambtc1.end())
+ , end(postorder(), ambtc1.end()), 5);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), ambtc1.end())
+ , end(postorder(), ambtc1.end())), 5);
}
BOOST_AUTO_TEST_CASE( test_ascending_iterator_algorithms )
{
- binary_tree<int>::cursor c = bt.root();
- typedef boost::tree::root_tracking_cursor<binary_tree<int>::cursor> rtc;
+ typedef fake_ascending_binary_tree_cursor<int> cursor;
+ cursor c(mbt1, 0);
+ typedef boost::tree::root_tracking_cursor<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())));
+ test_traversal_from_leaf4(ai(rtc(c)), ai(rtc(cursor(mbt1,0))));
}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
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-12-28 17:49:06 EST (Sun, 28 Dec 2008)
@@ -9,82 +9,10 @@
#include <boost/tree/binary_tree.hpp>
#include <boost/tree/algorithm.hpp>
-#include <boost/tree/output_iterator_cursor.hpp>
-
-//#include <boost/array.hpp>
#include <list>
-#include <vector>
-
-template <class T>
-struct mock_tree;
-
-template <class T>
-struct mock_tree {
- mock_tree(T const& v = T()) : value(v), m(2) {}
- typedef std::vector< mock_tree<T> > children_type;
-
- T value;
- children_type m;
-};
-
-template <class T>
-struct mock_tree_cursor {
- typedef typename mock_tree<T>::children_type cur;
- cur c;
- //bool pos;
-
- T const& operator*() const
- {
- return c->value;
- }
-
- T& operator*()
- {
- return c->value;
- }
-
- void to_begin()
- {
- c = c->m.begin();
- }
-
- void to_end()
- {
- c = c->m.end();
- }
-
- mock_tree_cursor& operator++()
- {
- ++c;
- }
-
- mock_tree_cursor& operator--()
- {
- --c;
- }
-};
-
-mock_tree<int> mock_tree_data()
-{
- mock_tree<int> mt;
-
- mt.m[0] = 8;
- mt.m[0].m[0] = 3;
- mt.m[0].m[0].m[0] = 1;
- mt.m[0].m[1] = 6;
- mt.m[0].m[1].m[0] = 4;
- mt.m[0].m[1].m[1] = 7;
-
- mt.m[0].m[1] = 10;
- mt.m[0].m[1].m[1] = 14;
- mt.m[0].m[1].m[1].m[0] = 13;
- mt.m[0].m[1].m[1].m[0].m[0] = 11;
- mt.m[0].m[1].m[1].m[0].m[0].m[1] = 12;
-
- return mt;
-}
+#include "helpers.hpp"
template <class T = int>
struct test_binary_tree_fixture {
@@ -124,15 +52,15 @@
cur = ret.insert(++cur.to_begin(), value_type(12));
}
- static void validate_test_dataset1_tree(typename boost::tree::binary_tree<T>::const_cursor cur)
+ 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(), 3);
BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 1); //Leaf
- BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 6);
+ BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 6);
BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4); //Leaf
BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7); //Leaf
-
BOOST_CHECK_EQUAL(*cur.end().begin(), 10);
BOOST_CHECK_EQUAL(*cur.end().end().begin(), 14);
BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 13);
@@ -161,16 +89,11 @@
template <class T = int>
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_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
-
+: public test_binary_tree_fixture<T>
+, public test_with_list_fixture {
test_binary_tree_with_list_fixture()
- : test_binary_tree_fixture<T>(), l(), i(l), o(i) { }
-
- std::list<int> l;
- back_insert_iter_list_int i;
- oc_bi_lst_type o;
+ : test_binary_tree_fixture<T>()
+ , test_with_list_fixture() {}
};
template <class Tree>