|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49038 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail/algorithm boost/tree/detail/algorithm/cursor boost/tree/detail/balancers boost/tree/detail/cursor boost/tree/detail/iterator libs/tree/test
From: ockham_at_[hidden]
Date: 2008-09-29 16:50:10
Author: bernhard.reiter
Date: 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
New Revision: 49038
URL: http://svn.boost.org/trac/boost/changeset/49038
Log:
Re-arrange *order algorithms from namespaces to a policy(=template)-based mechanism, part 12.
This should do the trick mostly. Documentation is not up-to-date yet!
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 5 -
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 8 +-
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 46 +++++++++-----------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp | 36 +++++++++-------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp | 51 ++++++++++++----------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp | 36 +++++++++-------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp | 40 ++++++++++--------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator.hpp | 29 +++++-------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp | 4
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/iterator.hpp | 4
sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp | 4 -
sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp | 16 +-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp | 19 ++++----
sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp | 87 +++++++++++++++++----------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp | 64 ++++++++++++++--------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 42 ++++++------------
18 files changed, 232 insertions(+), 263 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -16,10 +16,7 @@
#include <boost/tree/detail/algorithm/cursor/ascending.hpp>
-#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
-#include <boost/tree/detail/algorithm/cursor/preorder.hpp>
-#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
-
+#include <boost/tree/detail/algorithm/cursor.hpp>
#include <boost/tree/detail/algorithm/iterator.hpp>
#include <algorithm>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -97,13 +97,13 @@
template <class Cursor>
class balanced_tree_iterator
-: public iterator<inorder, , is_on_top_cursor<Cursor> > {
+: public iterator<inorder, is_on_top_cursor<Cursor> > {
public:
balanced_tree_iterator()
- : iterator<inorder, , is_on_top_cursor<Cursor> >() {}
+ : iterator<inorder, is_on_top_cursor<Cursor> >() {}
explicit balanced_tree_iterator(Cursor p)
- : iterator<inorder, , is_on_top_cursor<Cursor> >(p) {}
+ : iterator<inorder, is_on_top_cursor<Cursor> >(p) {}
operator Cursor()
{
@@ -513,7 +513,7 @@
void rotate(iterator& i)
{
- cursor c = cursor(iterator<inorder, , cursor>(i));
+ cursor c = cursor(boost::tree::iterator<inorder, cursor>(i));
h.rotate(c);
}
};
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -574,8 +574,6 @@
return (!(x == y));
}
-namespace inorder {
-
/**
* @brief First element of a MultiwayTree in inorder traversal
* (equivalent to postorder::first()) - O(1) overload for binary_tree
@@ -584,7 +582,7 @@
*/
template <class T, class Alloc>
typename binary_tree<T, Alloc>::cursor
-first_cursor(binary_tree<T, Alloc>& t)
+first_cursor(inorder, binary_tree<T, Alloc>& t)
{
return t.inorder_first();
}
@@ -598,7 +596,7 @@
*/
template <class T, class Alloc>
typename binary_tree<T, Alloc>::const_cursor
-first_cursor(binary_tree<T, Alloc> const& t)
+first_cursor(inorder, binary_tree<T, Alloc> const& t)
{
return t.inorder_first();
}
@@ -611,7 +609,7 @@
*/
template <class T, class Alloc>
typename binary_tree<T, Alloc>::const_cursor
-cfirst_cursor(binary_tree<T, Alloc> const& t)
+cfirst_cursor(inorder, binary_tree<T, Alloc> const& t)
{
return t.inorder_first();
}
@@ -623,10 +621,10 @@
* @return Mutable inorder iterator to the first element of @a t
*/
template <class T, class Alloc>
-iterator<typename binary_tree<T, Alloc>::cursor>
-begin(binary_tree<T, Alloc>& t)
+iterator<inorder, typename binary_tree<T, Alloc>::cursor>
+begin(inorder, binary_tree<T, Alloc>& t)
{
- return iterator<typename binary_tree<T, Alloc>::cursor>(first_cursor(t));
+ return iterator<inorder, typename binary_tree<T, Alloc>::cursor>(first_cursor(inorder(), t));
}
/**
@@ -636,10 +634,10 @@
* @return Read-only inorder iterator to the first element of @a t
*/
template <class T, class Alloc>
-iterator<typename binary_tree<T, Alloc>::const_cursor>
-begin(binary_tree<T, Alloc> const& t)
+iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>
+begin(inorder, binary_tree<T, Alloc> const& t)
{
- return iterator<typename binary_tree<T, Alloc>::const_cursor>(first_cursor(t));
+ return iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>(first_cursor(inorder(), t));
}
/**
@@ -649,14 +647,14 @@
* @return Read-only inorder iterator to the first element of @a t
*/
template <class T, class Alloc>
-iterator<typename binary_tree<T, Alloc>::const_cursor>
-cbegin(binary_tree<T, Alloc> const& t)
+iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>
+cbegin(inorder, binary_tree<T, Alloc> const& t)
{
// typedef
// typename cursor_vertical_traversal<
// typename binary_tree<T, Alloc>::const_cursor
// >::type traversal;
- return iterator<typename binary_tree<T, Alloc>::const_cursor>(first_cursor(t));
+ return iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>(first_cursor(inorder(), t));
}
@@ -667,10 +665,10 @@
* @return Mutable inorder iterator to the first element of @a t
*/
template <class T, class Alloc>
-iterator<typename binary_tree<T, Alloc>::cursor>
-end(binary_tree<T, Alloc>& t)
+iterator<inorder, typename binary_tree<T, Alloc>::cursor>
+end(inorder, binary_tree<T, Alloc>& t)
{
- return iterator<typename binary_tree<T, Alloc>::cursor>(last(t.root()));
+ return iterator<inorder, typename binary_tree<T, Alloc>::cursor>(last(inorder(), t.root()));
}
/**
@@ -680,10 +678,10 @@
* @return Read-only inorder iterator to the first element of @a t
*/
template <class T, class Alloc>
-iterator<typename binary_tree<T, Alloc>::const_cursor>
-end(binary_tree<T, Alloc> const& t)
+iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>
+end(inorder, binary_tree<T, Alloc> const& t)
{
- return iterator<typename binary_tree<T, Alloc>::const_cursor>(last(t.root()));
+ return iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>(last(inorder(), t.root()));
}
/**
@@ -693,14 +691,12 @@
* @return Read-only inorder iterator to the first element of @a t
*/
template <class T, class Alloc>
-iterator<typename binary_tree<T, Alloc>::const_cursor>
-cend(binary_tree<T, Alloc> const& t)
+iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>
+cend(inorder, binary_tree<T, Alloc> const& t)
{
- return iterator<typename binary_tree<T, Alloc>::const_cursor>(last(t.root()));
+ return iterator<inorder, typename binary_tree<T, Alloc>::const_cursor>(last(inorder(), t.root()));
}
-} // namespace inorder
-
} // namespace tree
} // namespace boost
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -14,6 +14,10 @@
#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
+//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+#include <boost/tree/detail/algorithm/cursor/common.hpp>
+//#endif
+
#include <boost/tree/root_tracking_cursor.hpp>
#include <boost/tree/ascending_cursor.hpp>
@@ -33,7 +37,7 @@
* @ingroup traversal
*/
template <class MultiwayCursor>
-inline void forward<inorder>(MultiwayCursor& c)
+inline void forward(inorder, MultiwayCursor& c)
{
if (!(++c).empty()) {
while (!c.to_begin().empty());
@@ -50,7 +54,7 @@
* @param c MultiwayCursor to be set to its inorder predecessor
*/
template <class MultiwayCursor>
-inline void back<inorder>(MultiwayCursor& c)
+inline void back(inorder, MultiwayCursor& c)
{
if (!c.empty()) {
while (!c.to_end().empty());
@@ -71,7 +75,7 @@
* position in the subtree.
*/
template <class Cursor>
-void to_first<inorder>(Cursor& c)
+void to_first(inorder, Cursor& c)
{
while (!c.empty())
c.to_begin();
@@ -84,7 +88,7 @@
* position in the subtree.
*/
template <class Cursor>
-void to_last<inorder>(Cursor& c)
+void to_last(inorder, Cursor& c)
{ }
/*\@}*/
@@ -98,19 +102,19 @@
* @endif
*/
template <class MultiwayCursor, class Op>
-void for_each_recursive<inorder>(MultiwayCursor s, Op& f)
+void for_each_recursive(inorder, MultiwayCursor s, Op& f)
{
MultiwayCursor t = s.end();
for (s.to_begin(); s!=t; ++s) {
if (!s.empty())
- for_each_recursive(s, f);
+ for_each_recursive(inorder(), s, f);
f(*s);
}
// Multiway cursor
if (!t.empty())
- for_each_recursive(t, f);
+ for_each_recursive(inorder(), t, f);
}
/**
@@ -126,20 +130,20 @@
*/
//[ inorder_for_each
template <class MultiwayCursor, class Op>
-Op for_each<inorder>(MultiwayCursor s, Op f)
+Op for_each(inorder, MultiwayCursor s, Op f)
//]
{
MultiwayCursor t = s.end();
for (s.to_begin(); s!=t; ++s) {
if (!s.empty())
- for_each_recursive<inorder>(s, f);
+ for_each_recursive(inorder(), s, f);
f(*s);
}
// Multiway cursor
if (!t.empty())
- for_each_recursive<inorder>(t, f);
+ for_each_recursive(inorder(), t, f);
return f;
}
@@ -150,7 +154,7 @@
* @result A cursor past t's inorder end, after the copying operation.
*/
template <class InCursor, class OutCursor>
-OutCursor copy<inorder>(InCursor s, OutCursor t)
+OutCursor copy(inorder, InCursor s, OutCursor t)
{
InCursor r = s.end();
@@ -159,13 +163,13 @@
for (; s != r; ++s, ++t) {
if (!s.empty())
- copy<inorder>(s, t);
+ copy(inorder(), s, t);
*t=*s;
}
// Multiway cursor
if (!r.empty())
- copy<inorder>(r, t);
+ copy(inorder(), r, t);
return t;
}
@@ -183,7 +187,7 @@
* op must not change its argument.
*/
template <class InCursor, class OutCursor, class Op>
-OutCursor transform<inorder>(InCursor s, OutCursor t, Op op)
+OutCursor transform(inorder, InCursor s, OutCursor t, Op op)
{
InCursor r = s.end();
@@ -192,13 +196,13 @@
for (; s != r; ++s, ++t) {
if (!s.empty())
- transform<inorder>(s, t, op);
+ transform(inorder(), s, t, op);
*t=op(*s);
}
// Multiway cursor
if (!r.empty())
- transform<inorder>(r, t, op);
+ transform(inorder(), r, t, op);
return t;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -14,18 +14,22 @@
#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_ITERATIVE_HPP
#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_ITERATIVE_HPP
+#include <boost/tree/detail/algorithm/cursor/preorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/postorder.hpp>
+
namespace boost {
namespace tree {
template <class Order, class Cursor, class Op>
-Op for_each(root_tracking_cursor<Cursor> s, Op f)
+Op for_each(Order, root_tracking_cursor<Cursor> s, Op f)
{
root_tracking_cursor<Cursor> s2(s);
- to_first<Order>(s);
- to_last<Order>(s2);
+ to_first(Order(), s);
+ to_last(Order(), s2);
while (s!=s2) {
f(*s);
- forward<Order>(s);
+ forward(Order(), s);
}
return f;
}
@@ -42,24 +46,24 @@
*/
//[ for_each
template <class Order, class Cursor, class Op>
-Op for_each(Cursor s, Op f)
+Op for_each(Order, Cursor s, Op f)
//]
{
- return for_each<Order>(root_tracking_cursor<Cursor>(s), f);
+ return for_each(Order(), root_tracking_cursor<Cursor>(s), f);
}
template <class Order, class InCursor, class OutCursor>
-root_tracking_cursor<OutCursor> copy (root_tracking_cursor<InCursor> s
+root_tracking_cursor<OutCursor> copy (Order, root_tracking_cursor<InCursor> s
, root_tracking_cursor<OutCursor> t)
{
root_tracking_cursor<InCursor> s2(s);
- to_first<Order>(s);
- to_last<Order>(s2);
- to_first<Order>(t);
+ to_first(Order(), s);
+ to_last(Order(), s2);
+ to_first(Order(), t);
while (s!=s2) {
*t = *s;
- forward<Order>(s);
- forward<Order>(t);
+ forward(Order(), s);
+ forward(Order(), t);
}
return t;
}
@@ -71,27 +75,28 @@
* @result A cursor past t's *order end, after the copying operation.
*/
template <class Order, class InCursor, class OutCursor>
-OutCursor copy (InCursor s, OutCursor t)
+OutCursor copy (Order, InCursor s, OutCursor t)
{
root_tracking_cursor<OutCursor> u
- = copy<Order>(root_tracking_cursor<InCursor>(s)
+ = copy(Order(), root_tracking_cursor<InCursor>(s)
, root_tracking_cursor<OutCursor>(t));
return u.base();
}
template <class Order, class InCursor, class OutCursor, class Op>
-root_tracking_cursor<OutCursor> transform (root_tracking_cursor<InCursor> s
+root_tracking_cursor<OutCursor> transform (Order
+ , root_tracking_cursor<InCursor> s
, root_tracking_cursor<OutCursor> t
, Op op)
{
root_tracking_cursor<InCursor> s2(s);
- to_first<Order>(s);
- to_last<Order>(s2);
- to_first<Order>(t);
+ to_first(Order(), s);
+ to_last(Order(), s2);
+ to_first(Order(), t);
while (s!=s2) {
*t = op(*s);
- forward<Order>(s);
- forward<Order>(t);
+ forward(Order(), s);
+ forward(Order(), t);
}
return t;
}
@@ -111,11 +116,11 @@
* op must not change its argument.
*/
template <class Order, class InCursor, class OutCursor, class Op>
-OutCursor transform (InCursor s, OutCursor t, Op op)
+OutCursor transform (Order, InCursor s, OutCursor t, Op op)
{
root_tracking_cursor<OutCursor> u
- = transform<Order>(root_tracking_cursor<InCursor>(s)
- , root_tracking_cursor<OutCursor>(t), op);
+ = transform(Order(), root_tracking_cursor<InCursor>(s)
+ , root_tracking_cursor<OutCursor>(t), op);
return u.base();
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -14,6 +14,10 @@
#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
+//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+#include <boost/tree/detail/algorithm/cursor/common.hpp>
+//#endif
+
#include <boost/tree/root_tracking_cursor.hpp>
#include <boost/tree/ascending_cursor.hpp>
@@ -30,7 +34,7 @@
* @param c Cursor to be set to its postorder successor
*/
template <class Cursor>
-inline void forward<postorder>(Cursor& c)
+inline void forward(postorder, Cursor& c)
{
c.to_parent();
@@ -59,7 +63,7 @@
* @param c Cursor to be set to its postorder predecessor
*/
template <class Cursor>
-inline void back<postorder>(Cursor& c)
+inline void back(postorder, Cursor& c)
{
if (c.is_root()) { // Root?
c.to_begin();
@@ -94,7 +98,7 @@
* position in the subtree.
*/
template <class Cursor>
-void to_first<postorder>(Cursor& c)
+void to_first(postorder, Cursor& c)
{
while (true)
if (!c.empty())
@@ -114,7 +118,7 @@
* position in the subtree.
*/
template <class Cursor>
-void to_last<postorder>(Cursor& c)
+void to_last(postorder, Cursor& c)
{ }
/*\@}*/
@@ -128,16 +132,16 @@
* @endif
*/
template <class Cursor, class Op>
-void for_each_recursive<postorder>(Cursor s, Op& f)
+void for_each_recursive(postorder(), Cursor s, Op& f)
{
Cursor t = s;
for (s.to_begin(); s != t.end(); ++s)
if (!s.empty())
- for_each_recursive<postorder>(s, f);
+ for_each_recursive(postorder(), s, f);
// Multiway cursor
if (!s.empty())
- for_each_recursive<postorder>(s, f);
+ for_each_recursive(postorder(), s, f);
f(*t.to_begin());
}
@@ -154,17 +158,17 @@
*/
//[ postorder_for_each
template <class Cursor, class Op>
-Op for_each<postorder>(Cursor s, Op f)
+Op for_each(postorder(), Cursor s, Op f)
//]
{
Cursor t = s;
for (s.to_begin(); s != t.end(); ++s)
if (!s.empty())
- for_each_recursive<postorder>(s, f);
+ for_each_recursive(postorder(), s, f);
// Multiway cursor
if (!s.empty())
- for_each_recursive<postorder>(s, f);
+ for_each_recursive(postorder(), s, f);
f(*t.to_begin());
@@ -178,7 +182,7 @@
* @result A cursor past t's postorder end, after the copying operation.
*/
template <class InCursor, class OutCursor>
-OutCursor copy<postorder>(InCursor s, OutCursor t)
+OutCursor copy(postorder(), InCursor s, OutCursor t)
{
InCursor r = s;
s.to_begin();
@@ -186,14 +190,14 @@
for (; s != r.end(); ++s, ++t) {
if (!s.empty())
- copy<postorder>(s, t);
+ copy(postorder(), s, t);
// else
// *t = *s;
}
// Multiway cursor
if (!s.empty())
- copy<postorder>(s, t);
+ copy(postorder(), s, t);
*t = *r.to_begin();
return t;
@@ -213,7 +217,7 @@
* op must not change its argument.
*/
template <class InCursor, class OutCursor, class Op>
-OutCursor transform<postorder>(InCursor s, OutCursor t, Op op)
+OutCursor transform(postorder(), InCursor s, OutCursor t, Op op)
{
InCursor r = s;
s.to_begin();
@@ -221,11 +225,11 @@
for (; s != r.end(); ++s, ++t)
if (!s.empty())
- transform<postorder>(s, t, op);
+ transform(postorder(), s, t, op);
// Multiway cursor
if (!s.empty())
- transform<postorder>(s, t, op);
+ transform(postorder(), s, t, op);
*t = op(*r.to_begin());
return t;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -14,14 +14,18 @@
#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
+//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+#include <boost/tree/detail/algorithm/cursor/common.hpp>
+//#endif
+
#include <boost/tree/root_tracking_cursor.hpp>
#include <boost/tree/ascending_cursor.hpp>
-struct preorder {};
-
namespace boost {
namespace tree {
+struct preorder {};
+
/** \addtogroup traversal */
/*\@{*/
@@ -30,7 +34,7 @@
* @param c Cursor to be set to its preorder successor
*/
template <class Cursor>
-inline void forward<preorder>(Cursor& c)
+inline void forward(preorder, Cursor& c)
{
// If we have a left child, go there.
if (!c.empty()) {
@@ -66,7 +70,7 @@
* @param c Cursor to be set to its preorder predecessor
*/
template <class Cursor>
-inline void back<preorder>(Cursor& c)
+inline void back(preorder, Cursor& c)
{
if (!c.is_root()) {
c.to_parent();
@@ -97,7 +101,7 @@
* position in the subtree.
*/
template <class Cursor>
-void to_first<preorder>(Cursor& c)
+void to_first(preorder, Cursor& c)
{
c.to_begin();
}
@@ -109,7 +113,7 @@
* position in the subtree.
*/
template <class Cursor>
-void to_last<preorder>(Cursor& c)
+void to_last(preorder, Cursor& c)
{ }
/*\@}*/
@@ -123,18 +127,18 @@
* @endif
*/
template <class Cursor, class Op>
-void for_each_recursive<preorder>(Cursor s, Op& f)
+void for_each_recursive(preorder, Cursor s, Op& f)
{
Cursor t = s.end();
for (s.to_begin(); s != t; ++s) {
f(*s);
if (!s.empty())
- for_each_recursive<preorder>(s, f);
+ for_each_recursive(preorder(), s, f);
}
// Multiway cursor
if (!s.empty())
- for_each_recursive<preorder>(s, f);
+ for_each_recursive(preorder(), s, f);
}
/**
@@ -149,19 +153,19 @@
*/
//[ preorder_for_each
template <class Cursor, class Op>
-Op for_each<preorder>(Cursor s, Op f)
+Op for_each(preorder, Cursor s, Op f)
//]
{
Cursor t = s.end();
for (s.to_begin(); s != t; ++s) {
f(*s);
if (!s.empty())
- for_each_recursive<preorder>(s, f);
+ for_each_recursive(preorder(), s, f);
}
// Multiway cursor
if (!s.empty())
- for_each_recursive<preorder>(s, f);
+ for_each_recursive(preorder(), s, f);
return f;
}
@@ -175,7 +179,7 @@
* @result A cursor past t's preorder end, after the copying operation.
*/
template <class InCursor, class OutCursor>
-OutCursor copy<preorder>(InCursor s, OutCursor t)
+OutCursor copy(preorder, InCursor s, OutCursor t)
{
InCursor r = s.end();
s.to_begin();
@@ -184,12 +188,12 @@
for (; s != r; ++s, ++t) {
*t = *s;
if (!s.empty())
- copy<preorder>(s, t);
+ copy(preorder(), s, t);
}
// Multiway cursor
if (!r.empty())
- copy<preorder>(r, t);
+ copy(preorder(), r, t);
return t;
}
@@ -208,7 +212,7 @@
* op must not change its argument.
*/
template <class InCursor, class OutCursor, class Op>
-OutCursor transform<preorder>(InCursor s, OutCursor t, Op op)
+OutCursor transform(preorder, InCursor s, OutCursor t, Op op)
{
InCursor r = s.end();
s.to_begin();
@@ -216,12 +220,12 @@
for (; s != r; ++s, ++t) {
*t = op(*s);
if (!s.empty())
- transform<preorder>(s, t, op);
+ transform(preorder(), s, t, op);
}
// Multiway cursor
if (!s.empty())
- transform<preorder>(s, t, op);
+ transform(preorder(), s, t, op);
return t;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -14,15 +14,12 @@
#ifndef BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_HPP
#define BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_HPP
-#include <boost/tree/detail/algorithm/cursor/preorder.hpp>
-#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
-#include <boost/tree/detail/algorithm/cursor/postorder.hpp>
-
-#include <boost/iterator/iterator_adaptor.hpp>
-#include <boost/type_traits/is_convertible.hpp>
-#include <boost/utility/enable_if.hpp>
+#include <boost/tree/detail/iterator/iterator.hpp>
+#include <boost/tree/detail/algorithm/cursor.hpp>
-// TODO: concept checks.
+//#include <boost/iterator/iterator_adaptor.hpp>
+//#include <boost/type_traits/is_convertible.hpp>
+//#include <boost/utility/enable_if.hpp>
namespace boost {
namespace tree {
@@ -35,9 +32,9 @@
*/
template <class Order, class Cursor>
iterator<Order, Cursor>
-begin(Cursor c)
+begin(Order, Cursor c)
{
- to_first(c);
+ to_first(Order(), c);
return iterator<Order, Cursor>(c);
}
@@ -49,9 +46,9 @@
*/
template <class Order, class Cursor>
iterator<Order, Cursor>
-end(Cursor c)
+end(Order, Cursor c)
{
- to_last(c);
+ to_last(Order(), c);
return iterator<Order, Cursor>(c);
}
@@ -59,16 +56,16 @@
template <class Order, class Cursor>
std::reverse_iterator< iterator<Order, Cursor> >
-rbegin(Cursor c)
+rbegin(Order, Cursor c)
{
- return std::reverse_iterator< iterator<Order, Cursor> >(end(c));
+ return std::reverse_iterator< iterator<Order, Cursor> >(end(Order(), c));
}
template <class Order, class Cursor>
std::reverse_iterator< iterator<Order, Cursor> >
-rend(Cursor c)
+rend(Order, Cursor c)
{
- return std::reverse_iterator< iterator<Order, Cursor> >(begin(c));
+ return std::reverse_iterator< iterator<Order, Cursor> >(begin(Order(), c));
}
} // namespace tree
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -32,8 +32,8 @@
//typename Tree::cursor y = x;
if (x.begin().empty() || x.end().empty())
return x;
- //inorder::forward(x);
- return inorder::next(x);
+ //forward(inorder, x);
+ return next(inorder(), x);
}
template <class Tree>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -15,7 +15,7 @@
#include <boost/tree/cursor_facade.hpp>
#include <boost/tree/detail/node/nary.hpp>
-#include <boost/tree/detail/iterator/inorder.hpp>
+#include <boost/tree/detail/iterator/iterator.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/iterator.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -64,13 +64,13 @@
void increment()
{
- forward(this->base_reference());
+ forward(Order(), this->base_reference());
//BOOST_ASSERT(!this->base_reference().parity() || this->base_reference().is_root());
}
void decrement()
{
- back(this->base_reference());
+ back(Order(), this->base_reference());
//BOOST_ASSERT(!this->base_reference().parity() || this->base_reference().is_root());
}
};
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -17,8 +17,6 @@
#include <boost/tree/detail/iterator/ascending.hpp>
-#include <boost/tree/detail/iterator/inorder.hpp>
-#include <boost/tree/detail/iterator/preorder.hpp>
-#include <boost/tree/detail/iterator/postorder.hpp>
+#include <boost/tree/detail/iterator/iterator.hpp>
#endif // BOOST_TREE_ITERATORS_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -17,7 +17,7 @@
#ifndef BOOST_TREE_SEARCHER_HPP
#define BOOST_TREE_SEARCHER_HPP
-#include <boost/tree/detail/iterator/inorder.hpp>
+#include <boost/tree/detail/iterator/iterator.hpp>
#include <boost/bind.hpp>
#include <boost/multi_index/identity.hpp>
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -24,17 +24,7 @@
// Some macro magic, to save us from all too tedious redundant calls
// to each of the three types of order algorithms and checks.
-#define ORDER preorder
#include "subtree_algorithms_checks.hpp"
-#undef ORDER
-
-#define ORDER inorder
-#include "subtree_algorithms_checks.hpp"
-#undef ORDER
-
-#define ORDER postorder
-#include "subtree_algorithms_checks.hpp"
-#undef ORDER
int test_main(int, char* [])
{
@@ -55,9 +45,9 @@
BOOST_CHECK(test_tree != test_tree2);
d = test_tree2.root();
- test::preorder::algorithms (test_tree.root(), test_tree2.root());
- test::inorder::algorithms (test_tree.root(), test_tree2.root());
- test::postorder::algorithms(test_tree.root(), test_tree2.root());
+ test::algorithms(preorder(), test_tree.root(), test_tree2.root());
+ test::algorithms(inorder(), test_tree.root(), test_tree2.root());
+ test::algorithms(postorder(), test_tree.root(), test_tree2.root());
return 0;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -15,9 +15,7 @@
#include "test_tree_traversal_data.hpp"
-#define ORDER preorder
#include "subtree_algorithms_checks.hpp"
-#undef ORDER
//TODO: Make this a test suite.
@@ -79,28 +77,29 @@
back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
- boost::tree::preorder::for_each(
+ boost::tree::for_each(
+ preorder(),
ft.root(),
boost::lambda::bind(&std::list<int>::push_back, &test_list, boost::lambda::_1)
);
- test::preorder::traversal(test_list.begin(), test_list.end());
+ test_traversal(preorder(), test_list.begin(), test_list.end());
BOOST_CHECK(test_list.size() == 11);
test_list.clear();
- boost::tree::preorder::copy(ft.root(), oc_test_list);
- test::preorder::traversal(test_list.begin(), test_list.end());
+ boost::tree::copy(preorder(), ft.root(), oc_test_list);
+ test_traversal(preorder(), test_list.begin(), test_list.end());
BOOST_CHECK(test_list.size() == 11);
test_list.clear();
- boost::tree::preorder::transform(ft.root(), oc_test_list, std::bind2nd(std::plus<int>(),0));
- test::preorder::traversal(test_list.begin(), test_list.end());
+ boost::tree::transform(preorder(), ft.root(), oc_test_list, std::bind2nd(std::plus<int>(),0));
+ test_traversal(preorder(), test_list.begin(), test_list.end());
BOOST_CHECK(test_list.size() == 11);
test_list.clear();
//test::preorder::algorithms(ft.root(), ft.root()); // FIXME: Fix algorithms for use in here.
- boost::tree::postorder::copy(ft.root(), oc_test_list);
- test::inorder::traversal(test_list.begin(), test_list.end());
+ boost::tree::copy(postorder(), ft.root(), oc_test_list);
+ test_traversal(inorder(), test_list.begin(), test_list.end());
BOOST_CHECK(test_list.size() == 11);
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -32,19 +32,8 @@
// Some macro magic, to save us from all too tedious redundant calls
// to each of the three types of order algorithms and checks.
-#define ORDER preorder
#include "subtree_algorithms_checks.hpp"
-#undef ORDER
-#define ORDER inorder
-#include "subtree_algorithms_checks.hpp"
-
-#undef ORDER
-#define ORDER postorder
-#include "subtree_algorithms_checks.hpp"
-
-#undef ORDER
-
template <class Cursor, class Op>
void underefed_for_each_recursive(Cursor s, Op& f)
{
@@ -73,9 +62,9 @@
template <class Cursor>
void comparisons(Cursor c) {
- test::preorder::compare_cursor_to_iterator_traversal(c);
- test::inorder::compare_cursor_to_iterator_traversal(c);
- test::postorder::compare_cursor_to_iterator_traversal(c);
+ test::compare_cursor_to_iterator_traversal(preorder(), c);
+ test::compare_cursor_to_iterator_traversal(inorder(), c);
+ test::compare_cursor_to_iterator_traversal(postorder(), c);
return;
}
@@ -167,61 +156,61 @@
create_test_data_tree(test_tree);
//Preorder
- test::preorder::traversal(preorder::begin(make_root_tracking_cursor(test_tree.root())),
- preorder::end(make_root_tracking_cursor(test_tree.root())));
+ test_traversal(preorder(), begin(preorder(), make_root_tracking_cursor(test_tree.root())),
+ end(preorder(), make_root_tracking_cursor(test_tree.root())));
- test::preorder::reverse_traversal(preorder::end(make_root_tracking_cursor(test_tree.root())),
- preorder::begin(make_root_tracking_cursor(test_tree.root())));
+ test_reverse_traversal(preorder(), end(preorder(), make_root_tracking_cursor(test_tree.root())),
+ begin(preorder(), make_root_tracking_cursor(test_tree.root())));
- BOOST_CHECK(std::distance(preorder::begin(make_root_tracking_cursor(test_tree.root())),
- preorder::end(make_root_tracking_cursor(test_tree.root()))) == 11);
+ BOOST_CHECK(std::distance(begin(preorder(), make_root_tracking_cursor(test_tree.root())),
+ end(preorder(), make_root_tracking_cursor(test_tree.root()))) == 11);
// Inorder
- test::inorder::traversal(inorder::begin(make_root_tracking_cursor(test_tree.root())),
- inorder::end(make_root_tracking_cursor(test_tree.root())));
+ test_traversal(inorder(), begin(inorder(), make_root_tracking_cursor(test_tree.root())),
+ end(inorder(), make_root_tracking_cursor(test_tree.root())));
- test::inorder::reverse_traversal(inorder::end(make_root_tracking_cursor(test_tree.root())),
- inorder::begin(make_root_tracking_cursor(test_tree.root())));
+ test_reverse_traversal(inorder(), end(inorder(), make_root_tracking_cursor(test_tree.root())),
+ begin(inorder(), make_root_tracking_cursor(test_tree.root())));
// TODO: Also check with binary_tree-specialized inorder begin()!
- BOOST_CHECK(std::distance(inorder::begin(make_root_tracking_cursor(test_tree.root())),
- inorder::end(make_root_tracking_cursor(test_tree.root()))) == 11);
+ BOOST_CHECK(std::distance(begin(inorder(), make_root_tracking_cursor(test_tree.root())),
+ end(inorder(), make_root_tracking_cursor(test_tree.root()))) == 11);
//Postorder
- test::postorder::traversal(postorder::begin(make_root_tracking_cursor(test_tree.root())),
- postorder::end(make_root_tracking_cursor(test_tree.root())));
- test::postorder::reverse_traversal(postorder::end(make_root_tracking_cursor(test_tree.root())),
- postorder::begin(make_root_tracking_cursor(test_tree.root())));
+ test_traversal(postorder(), begin(postorder(), make_root_tracking_cursor(test_tree.root())),
+ end(postorder(), make_root_tracking_cursor(test_tree.root())));
+ test_reverse_traversal(postorder(), end(postorder(), make_root_tracking_cursor(test_tree.root())),
+ begin(postorder(), make_root_tracking_cursor(test_tree.root())));
- BOOST_CHECK(std::distance(postorder::begin(make_root_tracking_cursor(test_tree.root())),
- postorder::end(make_root_tracking_cursor(test_tree.root()))) == 11);
+ BOOST_CHECK(std::distance(begin(postorder(), make_root_tracking_cursor(test_tree.root())),
+ end(postorder(), make_root_tracking_cursor(test_tree.root()))) == 11);
// Now the iterators based on stack-based cursors (that don't use cursor.to_parent())
- test::preorder::traversal(preorder::begin(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- preorder::end(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
- test::preorder::reverse_traversal(preorder::end(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- preorder::begin(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
-
- test::inorder::traversal(inorder::begin(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- inorder::end(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
- test::inorder::reverse_traversal(inorder::end(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- inorder::begin(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
-
- test::postorder::traversal(postorder::begin(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- postorder::end(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
- test::postorder::reverse_traversal(postorder::end(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
- postorder::begin(make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
+ test_traversal(preorder(), begin(preorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
+ end(preorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
+ test_reverse_traversal(preorder(), end(preorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
+ begin(preorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
+
+ test_traversal(inorder(), begin(inorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
+ end(inorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
+ test_reverse_traversal(inorder(), end(inorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
+ begin(inorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
+
+ test_traversal(postorder(), begin(postorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
+ end(postorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
+ test_reverse_traversal(postorder(), end(postorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))),
+ begin(postorder(), make_root_tracking_cursor(make_ascending_cursor(test_tree.root()))));
//Ascending iterator.
binary_tree<int>::cursor c = test_tree.root();
- ascending::iterator<binary_tree<int>::cursor> ai_root(c);
+ boost::tree::ascending::iterator<binary_tree<int>::cursor> ai_root(c);
c = c.begin().end().begin().begin();
BOOST_CHECK(*c == 4);
- ascending::iterator<binary_tree<int>::cursor> ais(c);
- test::ascending::traversal_from_leaf4(ais, ai_root);
+ boost::tree::ascending::iterator<binary_tree<int>::cursor> ais(c);
+ test_traversal_from_leaf4(ais, ai_root);
//Now the advanced stuff
compare_cursor_to_iterator_traversal();
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -13,44 +13,46 @@
#include <algorithm>
#include <iterator>
+#include <boost/test/minimal.hpp>
+
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
using namespace boost::tree;
namespace test {
-namespace ORDER {
-template <class Cursor, class Container>
-void test_for_each(Cursor c, Container& cont)
+template <class Order, class Cursor, class Container>
+void test_for_each(Order, Cursor c, Container& cont)
{
- boost::tree::ORDER::for_each(
+ boost::tree::for_each(
+ Order(),
c,
boost::lambda::bind(&Container::push_back, &cont, boost::lambda::_1)
);
- test::ORDER::traversal(cont.begin(), cont.end());
+ test_traversal(Order(), cont.begin(), cont.end());
}
-template <class Cursor, class OutCursor, class Container>
-void test_copy(Cursor c, OutCursor& o, Container& cont)
+template <class Order, class Cursor, class OutCursor, class Container>
+void test_copy(Order, Cursor c, OutCursor& o, Container& cont)
{
- boost::tree::ORDER::copy(c, o);
- test::ORDER::traversal(cont.begin(), cont.end());
+ boost::tree::copy(Order(), c, o);
+ test_traversal(Order(), cont.begin(), cont.end());
}
-template <class Cursor, class OutCursor, class Container>
-void test_transform(Cursor c, Cursor d, OutCursor& o, Container& cont)
+template <class Order, class Cursor, class OutCursor, class Container>
+void test_transform(Order, Cursor c, Cursor d, OutCursor& o, Container& cont)
{
// 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::ORDER::transform(c, d, std::bind2nd(std::plus<int>(),1));
- boost::tree::ORDER::transform(d, o, std::bind2nd(std::minus<int>(),1));
- test::ORDER::traversal(cont.begin(), cont.end());
+ boost::tree::transform(Order(), c, d, std::bind2nd(std::plus<int>(),1));
+ boost::tree::transform(Order(), d, o, std::bind2nd(std::minus<int>(),1));
+ test_traversal(Order(), cont.begin(), cont.end());
}
-template <class Cursor>
-void algorithms(Cursor c, Cursor d)
+template <class Order, class Cursor>
+void algorithms(Order, Cursor c, Cursor d)
{
std::list<int> test_list;
typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
@@ -58,48 +60,46 @@
back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
- test_for_each(c, test_list);
+ test_for_each(Order(), c, test_list);
test_list.clear();
- test_copy(c, oc_test_list, test_list);
+ test_copy(Order(), c, oc_test_list, test_list);
test_list.clear();
- test_transform(c, d, oc_test_list, test_list);
+ test_transform(Order(), c, d, oc_test_list, test_list);
}
-template <class Cursor>
-void compare_cursor_to_iterator_traversal(Cursor cur) {
+template <class Order, class Cursor>
+void compare_cursor_to_iterator_traversal(Order, Cursor cur) {
std::list<int> test_list;
typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
typedef output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
- boost::tree::ORDER::copy(cur, oc_test_list);
+ boost::tree::copy(Order(), cur, oc_test_list);
// Are the elements accessed in the correct order?
- BOOST_CHECK(std::equal( boost::tree::ORDER::begin(cur),
- boost::tree::ORDER::end(cur),
+ BOOST_CHECK(std::equal( boost::tree::begin(Order(), cur),
+ boost::tree::end(Order(), cur),
test_list.begin()
));
// Does end() mark the right element?
- BOOST_CHECK(std::distance(boost::tree::ORDER::begin(cur),
- boost::tree::ORDER::end(cur)) ==
+ BOOST_CHECK(std::distance(boost::tree::begin(Order(), cur),
+ boost::tree::end(Order(), cur)) ==
std::distance(test_list.begin(), test_list.end()));
// Reverse order.
- BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(cur),
- boost::tree::ORDER::rend(cur),
+ BOOST_CHECK(std::equal( boost::tree::rbegin(Order(), cur),
+ boost::tree::rend(Order(), cur),
test_list.rbegin()
));
- BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(cur),
- boost::tree::ORDER::rend(cur)) ==
+ BOOST_CHECK(std::distance(boost::tree::rbegin(Order(), cur),
+ boost::tree::rend(Order(), cur)) ==
std::distance(test_list.rbegin(), test_list.rend()));
}
-
-} // namespace ORDER
} // namespace test
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp 2008-09-29 16:50:08 EDT (Mon, 29 Sep 2008)
@@ -7,8 +7,12 @@
#ifndef LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
#define LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
+#include <boost/tree/algorithm.hpp>
+
#include <list>
+#include <boost/test/minimal.hpp>
+
// Test data from http://en.wikipedia.org/wiki/Image:Binary_search_tree.svg
// (With two additional nodes: 11 inserted left of 13; 12 right of 11)
// and in combination with http://en.wikipedia.org/wiki/Tree_traversal#Examples
@@ -76,12 +80,8 @@
BOOST_CHECK(*++c == 12);
}
-namespace test {
-
-namespace preorder {
-
template <class Iterator>
-void traversal(Iterator a, Iterator b)
+void test_traversal(boost::tree::preorder, Iterator a, Iterator b)
{
BOOST_CHECK(*a++ == 8);
BOOST_CHECK(*a++ == 3);
@@ -98,7 +98,7 @@
}
template <class Iterator>
-void reverse_traversal(Iterator a, Iterator b)
+void test_reverse_traversal(boost::tree::preorder, Iterator a, Iterator b)
{
BOOST_CHECK(*--a == 12);
BOOST_CHECK(*--a == 11);
@@ -115,7 +115,7 @@
}
template <class Iterator>
-void subtree_traversal(Iterator a, Iterator b)
+void test_subtree_traversal(boost::tree::preorder, Iterator a, Iterator b)
{
BOOST_CHECK(*a++ == 3);
BOOST_CHECK(*a++ == 1);
@@ -125,12 +125,8 @@
BOOST_CHECK(a == b);
}
-} // namespace preorder
-
-namespace inorder {
-
template <class Iterator>
-void traversal(Iterator a, Iterator b)
+void test_traversal(boost::tree::inorder, Iterator a, Iterator b)
{
BOOST_CHECK(*a++ == 1);
BOOST_CHECK(*a++ == 3);
@@ -147,8 +143,8 @@
}
template <class Iterator>
-void reverse_traversal(Iterator a, Iterator b)
-{
+void test_reverse_traversal(boost::tree::inorder, Iterator a, Iterator b)
+{
BOOST_CHECK(*--a == 14);
BOOST_CHECK(*--a == 13);
BOOST_CHECK(*--a == 12);
@@ -163,12 +159,9 @@
BOOST_CHECK(a == b);
}
-} // namespace inorder
-
-namespace postorder {
template <class Iterator>
-void traversal(Iterator a, Iterator b)
+void test_traversal(boost::tree::postorder, Iterator a, Iterator b)
{
BOOST_CHECK(*a++ == 1);
BOOST_CHECK(*a++ == 4);
@@ -185,9 +178,9 @@
}
template <class Iterator>
-void reverse_traversal(Iterator a, Iterator b)
+void test_reverse_traversal(boost::tree::postorder, Iterator a, Iterator b)
{
- BOOST_CHECK(*--a == 8);
+ BOOST_CHECK(*--a == 8);
BOOST_CHECK(*--a == 10);
BOOST_CHECK(*--a == 14);
BOOST_CHECK(*--a == 13);
@@ -201,23 +194,16 @@
BOOST_CHECK(a == b);
}
-} // namespace postorder
-
-namespace ascending {
-
template <class Iterator>
-void traversal_from_leaf4(Iterator a, Iterator b)
+void test_traversal_from_leaf4(Iterator a, Iterator b)
{
BOOST_CHECK(*a == 4);
BOOST_CHECK(*++a == 6);
BOOST_CHECK(*++a == 3);
BOOST_CHECK(*++a == 8);
BOOST_CHECK(++a == b);
-}
} // namespace ascending
-} // namespace test
-
#endif // LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk
