|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49350 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/algorithm boost/tree/detail/cursor
From: ockham_at_[hidden]
Date: 2008-10-15 20:52:09
Author: bernhard.reiter
Date: 2008-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
New Revision: 49350
URL: http://svn.boost.org/trac/boost/changeset/49350
Log:
Use recursive *order algorithms for non-ascending cursors.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 1
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp | 9 ++++++-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp | 18 ++++++++--------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp | 42 +++++++++++++++++++++++++++++++--------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp | 18 ++++++++--------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp | 18 ++++++++--------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp | 2
8 files changed, 71 insertions(+), 41 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
@@ -14,6 +14,7 @@
[section TODO]
General:
+* Caution: Iterative algorithms require ascending cursors!
* Move some of the secondary stuff to a util/ dir? Is that what they're used for?
* Redo testing. Right now, it's just chaotic.
* Fix recursive algorithms for use with forest.
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-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
@@ -19,9 +19,9 @@
#include <boost/tree/detail/algorithm/inorder.hpp>
#include <boost/tree/detail/algorithm/postorder.hpp>
-#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
#include <boost/tree/detail/algorithm/iterative.hpp>
-#endif
+//#endif
namespace boost {
namespace tree {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp 2008-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
@@ -28,6 +28,11 @@
using boost::iterator_core_access;
+class dummy {
+private:
+dummy() {}
+};
+
// We'll abuse iterator_adaptor to determine our types.
template <
class Derived
@@ -46,7 +51,7 @@
, HorizontalTraversalOrCategory
, Reference
, Difference>
-, private iterator_adaptor<Derived
+, private iterator_adaptor<dummy
, Base
, Value
, VerticalTraversalOrCategory
@@ -59,7 +64,7 @@
typedef typename iterator_adaptor<Derived, Base, Value
, HorizontalTraversalOrCategory, Reference
, Difference>::super_t h_super_t;
- typedef typename iterator_adaptor<Derived, Base, Value
+ typedef typename iterator_adaptor<dummy, Base, Value
, VerticalTraversalOrCategory, Reference
, Difference>::super_t v_super_t;
public:
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp 2008-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
@@ -89,7 +89,7 @@
/*\@}*/
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
/**
* @if maint
@@ -126,7 +126,7 @@
*/
//[ inorder_for_each
template <class MultiwayCursor, class Op>
-Op for_each(inorder, MultiwayCursor s, Op f)
+Op for_each(inorder, MultiwayCursor s, Op f, forward_traversal_tag)
//]
{
MultiwayCursor t = s.end();
@@ -150,7 +150,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, forward_traversal_tag)
{
InCursor r = s.end();
@@ -159,13 +159,13 @@
for (; s != r; ++s, ++t) {
if (!s.empty())
- copy(inorder(), s, t);
+ copy(inorder(), s, t, forward_traversal_tag());
*t=*s;
}
// Multiway cursor
if (!r.empty())
- copy(inorder(), r, t);
+ copy(inorder(), r, t, forward_traversal_tag());
return t;
}
@@ -183,7 +183,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, forward_traversal_tag)
{
InCursor r = s.end();
@@ -192,17 +192,17 @@
for (; s != r; ++s, ++t) {
if (!s.empty())
- transform(inorder(), s, t, op);
+ transform(inorder(), s, t, op, forward_traversal_tag());
*t=op(*s);
}
// Multiway cursor
if (!r.empty())
- transform(inorder(), r, t, op);
+ transform(inorder(), r, t, op, forward_traversal_tag());
return t;
}
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
/// Search
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp 2008-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
@@ -34,6 +34,12 @@
return f;
}
+template <class Order, class Cursor, class Op>
+Op for_each(Order, Cursor s, Op f, bidirectional_traversal_tag)
+{
+ return for_each(Order(), root_tracking_cursor<Cursor>(s), f);
+}
+
/**
* @brief Apply a function to every element of a subtree,
* in the order specified by the first parameter.
@@ -50,7 +56,8 @@
Op for_each(Order, Cursor s, Op f)
//]
{
- return for_each(Order(), root_tracking_cursor<Cursor>(s), f);
+ return for_each(Order(), s, f
+ , typename cursor_vertical_traversal<Cursor>::type());
}
template <class Order, class InCursor, class OutCursor>
@@ -69,6 +76,15 @@
return t;
}
+template <class Order, class InCursor, class OutCursor>
+OutCursor copy (Order, InCursor s, OutCursor t, bidirectional_traversal_tag)
+{
+ root_tracking_cursor<OutCursor> u
+ = copy(Order(), root_tracking_cursor<InCursor>(s)
+ , root_tracking_cursor<OutCursor>(t));
+ return u.base();
+}
+
/**
* @brief Copies the subtree s into t, by traversing s
* in the order specified by the first parameter.
@@ -79,10 +95,9 @@
template <class Order, class InCursor, class OutCursor>
OutCursor copy (Order, InCursor s, OutCursor t)
{
- root_tracking_cursor<OutCursor> u
- = copy(Order(), root_tracking_cursor<InCursor>(s)
- , root_tracking_cursor<OutCursor>(t));
- return u.base();
+ return copy(Order(), s, t
+ , typename cursor_vertical_traversal<InCursor>::type());
+ // What about OutCursor?
}
template <class Order, class InCursor, class OutCursor, class Op>
@@ -103,6 +118,16 @@
return t;
}
+template <class Order, class InCursor, class OutCursor, class Op>
+OutCursor transform (Order, InCursor s, OutCursor t, Op op
+ , bidirectional_traversal_tag)
+{
+ root_tracking_cursor<OutCursor> u
+ = transform(Order(), root_tracking_cursor<InCursor>(s)
+ , root_tracking_cursor<OutCursor>(t), op);
+ return u.base();
+}
+
/**
* @brief Performs an operation on a subtree, by traversing it
* in the order specified by the first parameter.
@@ -120,10 +145,9 @@
template <class Order, class InCursor, class OutCursor, class 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);
- return u.base();
+ return transform(Order(), s, t, op
+ , typename cursor_vertical_traversal<InCursor>::type());
+ // What about OutCursor?
}
} // namespace tree
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp 2008-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
@@ -119,7 +119,7 @@
/*\@}*/
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
/**
* @if maint
@@ -154,7 +154,7 @@
*/
//[ postorder_for_each
template <class Cursor, class Op>
-Op for_each(postorder, Cursor s, Op f)
+Op for_each(postorder, Cursor s, Op f, forward_traversal_tag)
//]
{
Cursor t = s;
@@ -178,7 +178,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, forward_traversal_tag)
{
InCursor r = s;
s.to_begin();
@@ -186,14 +186,14 @@
for (; s != r.end(); ++s, ++t) {
if (!s.empty())
- copy(postorder(), s, t);
+ copy(postorder(), s, t, forward_traversal_tag());
// else
// *t = *s;
}
// Multiway cursor
if (!s.empty())
- copy(postorder(), s, t);
+ copy(postorder(), s, t, forward_traversal_tag());
*t = *r.to_begin();
return t;
@@ -213,7 +213,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, forward_traversal_tag)
{
InCursor r = s;
s.to_begin();
@@ -221,17 +221,17 @@
for (; s != r.end(); ++s, ++t)
if (!s.empty())
- transform(postorder(), s, t, op);
+ transform(postorder(), s, t, op, forward_traversal_tag());
// Multiway cursor
if (!s.empty())
- transform(postorder(), s, t, op);
+ transform(postorder(), s, t, op, forward_traversal_tag());
*t = op(*r.to_begin());
return t;
}
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
} // namespace tree
} // namespace boost
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp 2008-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
@@ -116,7 +116,7 @@
/*\@}*/
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
/**
* @if maint
@@ -151,7 +151,7 @@
*/
//[ preorder_for_each
template <class Cursor, class Op>
-Op for_each(preorder, Cursor s, Op f)
+Op for_each(preorder, Cursor s, Op f, forward_traversal_tag)
//]
{
Cursor t = s.end();
@@ -177,7 +177,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, forward_traversal_tag)
{
InCursor r = s.end();
s.to_begin();
@@ -186,12 +186,12 @@
for (; s != r; ++s, ++t) {
*t = *s;
if (!s.empty())
- copy(preorder(), s, t);
+ copy(preorder(), s, t, forward_traversal_tag());
}
// Multiway cursor
if (!r.empty())
- copy(preorder(), r, t);
+ copy(preorder(), r, t, forward_traversal_tag());
return t;
}
@@ -210,7 +210,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, forward_traversal_tag)
{
InCursor r = s.end();
s.to_begin();
@@ -218,17 +218,17 @@
for (; s != r; ++s, ++t) {
*t = op(*s);
if (!s.empty())
- transform(preorder(), s, t, op);
+ transform(preorder(), s, t, op, forward_traversal_tag());
}
// Multiway cursor
if (!s.empty())
- transform(preorder(), s, t, op);
+ transform(preorder(), s, t, op, forward_traversal_tag());
return t;
}
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
} // namespace tree
} // namespace boost
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp 2008-10-15 20:52:08 EDT (Wed, 15 Oct 2008)
@@ -38,7 +38,7 @@
, Cursor
, boost::use_default
, bidirectional_traversal_tag
- , forward_traversal_tag
+ , bidirectional_traversal_tag
> {
private:
struct enabler {};
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