Subject: [Boost-commit] svn:boost r48985 - in sandbox/SOC/2006/tree/trunk/boost/tree: . detail/algorithm/cursor
From: ockham_at_[hidden]
Date: 2008-09-27 16:57:23
Author: bernhard.reiter
Date: 2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
New Revision: 48985
URL: http://svn.boost.org/trac/boost/changeset/48985
Log:
Outsource redundant cursor algorithms.
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 24 +++++++++---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order_iterative.hpp | 75 +++++++++++++++++++++++++++++++++++++--
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp | 75 +++++++++++----------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp | 73 ++++++++++++--------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp | 67 ++++++++++-------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp | 24 ++++++------
6 files changed, 165 insertions(+), 173 deletions(-)
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-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -216,7 +216,7 @@
struct enabler {};
typedef root_tracking_cursor< ascending_cursor<Cursor> > self_type;
public:
- typedef typename ascending_cursor<Cursor>::value_type value_type;
+ typedef typename ascending_cursor<Cursor>::value_type value_type;
// Container-specific:
typedef typename ascending_cursor<Cursor>::size_type size_type;
@@ -245,18 +245,30 @@
root_tracking_cursor(
root_tracking_cursor< ascending_cursor<OtherCursor> > const& other
, typename boost::enable_if<
- boost::is_convertible<ascending_cursor<OtherCursor>*
- , ascending_cursor<Cursor>*>
+ boost::is_convertible<OtherCursor*
+ , Cursor*>
, enabler
>::type = enabler()
)
: root_tracking_cursor::cursor_adaptor_(other.base())
- , m_root_depth(other.base().m_s.size()) {}
+ , m_root_depth(other.m_root_depth) {}
+//
+// template <class OtherCursor>
+// root_tracking_cursor(
+// root_tracking_cursor<OtherCursor> const& other
+// , typename boost::enable_if<
+// boost::is_convertible<OtherCursor*
+// , ascending_cursor<Cursor>*>
+// , enabler
+// >::type = enabler()
+// )
+// : root_tracking_cursor::cursor_adaptor_(other.base())
+// , m_root_depth(other.base().m_s.size()) {}
private:
- std::size_t const m_root_depth;
+ std::size_t const m_root_depth;
- friend class boost::iterator_core_access;
+ friend class boost::iterator_core_access;
friend class boost::tree::cursor_core_access;
// bool equal(cursor const& other) const
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order.hpp 2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -0,0 +1,70 @@
+// 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)
+
+/** @file _order.hpp
+ *
+ * Some algorithm versions that are identical for all *order cursors
+ * (as we are just calling the appropriate traversal function that are
+ * defined in the respective *order.hpp files).
+ */
+
+// NO guards, as this is context-included!
+
+/**
+ * @brief Successor
+ * @param c A cursor
+ * @param n Optional parameter to indicate how many steps to move forward
+ * @return Successor of @a c
+ */
+template <class Cursor>
+inline Cursor next(Cursor c
+ , typename Cursor::difference_type n = 1)
+{
+ for (; n!=0; --n)
+ forward(c);
+ return c;
+}
+
+/**
+ * @brief Predecessor
+ * @param c A cursor
+ * @param n Optional parameter to indicate how many steps to move back
+ * @return Predecessor of @a c
+ */
+template <class Cursor>
+inline Cursor prior(Cursor c
+ , typename Cursor::difference_type n = 1)
+{
+ for (; n!=0; --n)
+ back(c);
+ return c;
+}
+
+/**
+ * @brief First element of a subtree in preorder traversal
+ * @param c A cursor
+ * @return Cursor to the first element of @a c in preorder traversal
+ */
+template <class Cursor>
+Cursor first(Cursor c)
+{
+ to_first(c);
+ return c;
+}
+
+/**
+ * @brief One position past the last element of a subtree in preorder
+ * traversal
+ * @param c A cursor
+ * @return Cursor one position past the last element of @a c in preorder
+ * traversal
+ */
+template <class Cursor>
+Cursor last(Cursor c)
+{
+ to_last(c);
+ return c;
+}
\ No newline at end of file
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order_iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order_iterative.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/_order_iterative.hpp 2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -4,7 +4,7 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-/** @file _order.hpp
+/** @file _order_iterative.hpp
*
* Some iterative algorithm versions that are identical for all *order cursors
* (as we are just calling the appropriate traversal function that are
@@ -16,18 +16,85 @@
template <class Cursor, class Op>
Op for_each(root_tracking_cursor<Cursor> s, Op f)
{
- root_tracking_cursor<Cursor> t = last(s);
+ root_tracking_cursor<Cursor> s2 = last(s);
s = first(s);
- while (s!=t) {
+ while (s!=s2) {
f(*s);
forward(s);
}
return f;
}
-
+/**
+ * @brief Apply a function to every element of a subtree, in the given order.
+ * @param s A cursor.
+ * @param f A unary function object.
+ * @return @p f
+ *
+ * Applies the function object @p f to each element in the @p subtree.
+ * @p f must not modify the order of the sequence.
+ * If @p f has a return value it is ignored.
+ */
+//[ for_each
template <class Cursor, class Op>
Op for_each(Cursor s, Op f)
+//]
{
return for_each(root_tracking_cursor<Cursor>(s), f);
+}
+
+template <class InCursor, class OutCursor>
+OutCursor copy (root_tracking_cursor<InCursor> s, OutCursor t)
+{
+ root_tracking_cursor<InCursor> s2(last(s));
+ s = first(s);
+ while (s!=s2) {
+ *t = *s;
+ forward(s);
+ }
+ return t;
+}
+
+/**
+ * @brief Copies the subtree s into t, by traversing s in the given order.
+ * @param s An input cursor.
+ * @param t An output cursor.
+ * @result A cursor past t's *order end, after the copying operation.
+ */
+template <class InCursor, class OutCursor>
+OutCursor copy (InCursor s, OutCursor t)
+{
+ return copy(root_tracking_cursor<InCursor>(s), t);
+}
+
+template <class InCursor, class OutCursor, class Op>
+OutCursor transform (root_tracking_cursor<InCursor> s, OutCursor t, Op op)
+{
+ root_tracking_cursor<InCursor> s2(last(s));
+ s = first(s);
+ while (s!=s2) {
+ *t = op(*s);
+ forward(s);
+ }
+ return t;
+}
+
+/**
+ * @brief Performs an operation on a subtree, by traversing it in
+ * the given order.
+ * @param s An input cursor.
+ * @param t An output cursor.
+ * @param op A unary operation.
+ * @result A cursor past t's preorder end, after the transforming has
+ * finished.
+ *
+ * By traversing the input subtree s, apply the operation op
+ * to each element and write the result to the output subtree t.
+ *
+ * op must not change its argument.
+ */
+template <class InCursor, class OutCursor, class Op>
+OutCursor transform (InCursor s, OutCursor t, Op op)
+{
+ return transform(root_tracking_cursor<InCursor>(s), t, op);
}
\ No newline at end of file
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-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -15,6 +15,7 @@
#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
#include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
#include <algorithm>
@@ -45,22 +46,6 @@
}
/**
- * @brief Inorder successor
- * @param c A cursor
- * @param n Optional parameter to indicate how many steps to move forward
- * @return Inorder successor of @a c
- * @ingroup traversal
- */
-template <class MultiwayCursor>
-inline MultiwayCursor next(MultiwayCursor c
- , typename MultiwayCursor::difference_type n = 1)
-{
- for (; n!=0; --n)
- forward(c);
- return c;
-}
-
-/**
* @brief Inorder predecessor
* @param c MultiwayCursor to be set to its inorder predecessor
*/
@@ -81,49 +66,35 @@
}
/**
- * @brief Inorder predecessor
- * @param c MultiwayCursor
- * @param n Optional parameter to indicate how many steps to move back
- * @return Inorder predecessor of @a c
- */
-template <class MultiwayCursor>
-inline MultiwayCursor prior(MultiwayCursor c
- , typename MultiwayCursor::difference_type n = 1)
-{
- for (; n!=0; --n)
- back(c);
- return c;
-}
-
-/**
- * @brief First element of a Multiway subtree in inorder traversal
- * @param c A MultiwayCursor
- * @return Cursor to the first element of @a c in inorder traversal
+ * @brief First element of a subtree in inorder traversal
+ * @param c Subtree root cursor that will be set to the first inorder
+ * position in the subtree.
*/
-template <class MultiwayCursor>
-MultiwayCursor first(MultiwayCursor c)
+template <class Cursor>
+void to_first(Cursor& c)
{
while (!c.empty())
c.to_begin();
- return c;
}
/**
- * @brief One position past the last element of a Multiway subtree in
- * inorder traversal
- * @param c A MultiwayCursor
- * @return Cursor one position past the last element of @a c in inorder
- * traversal
- */
-template <class MultiwayCursor>
-MultiwayCursor last(MultiwayCursor c)
-{
- return c;
-}
+ * @brief One position past the last element of a subtree in inorder
+ * traversal
+ * @param c Subtree root cursor that will be set to the last inorder
+ * position in the subtree.
+ */
+template <class Cursor>
+void to_last(Cursor& c)
+{ }
+
+#include <boost/tree/detail/algorithm/cursor/_order.hpp>
/*\@}*/
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
+//#else
+
/**
* @if maint
* Helper function for for_each, using a reference parameter in order to
@@ -176,10 +147,6 @@
return f;
}
-#else
-#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
/**
* @brief Copies the subtree s into t, by traversing s in inorder.
* @param s An input cursor.
@@ -239,6 +206,8 @@
return t;
}
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+
/// Search
/**
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-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -15,6 +15,7 @@
#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
#include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
namespace boost {
namespace tree {
@@ -54,21 +55,6 @@
}
/**
- * @brief Postorder successor
- * @param c A cursor
- * @param n Optional parameter to indicate how many steps to move forward
- * @return Postorder successor of @a c
- */
-template <class Cursor>
-inline Cursor next(Cursor c
- , typename Cursor::difference_type n = 1)
-{
- for (; n!=0; --n)
- forward(c);
- return c;
-}
-
-/**
* @brief Postorder predecessor
* @param c Cursor to be set to its postorder predecessor
*/
@@ -103,53 +89,42 @@
}
/**
- * @brief Postorder predecessor
- * @param c A cursor
- * @param n Optional parameter to indicate how many steps to move back
- * @return Postorder predecessor of @a c
- */
-template <class Cursor>
-inline Cursor prior(Cursor c
- , typename Cursor::difference_type n = 1)
-{
- for (; n!=0; --n)
- back(c);
- return c;
-}
-
-/**
- * @brief First element of a subtree in postorder traversal
- * @param c A cursor
- * @return Cursor to the first element of @a c in postorder traversal
+ * @brief First element of a subtree in postorder traversal
+ * @param c Subtree root cursor that will be set to the first postorder
+ * position in the subtree.
*/
template <class Cursor>
-Cursor first(Cursor c)
+void to_first(Cursor& c)
{
while (true)
if (!c.empty())
c.to_begin();
else if (!(++c).empty())
c.to_begin();
- else
- return --c;
+ else {
+ --c;
+ return;
+ }
}
/**
- * @brief One position past the last element of a subtree in postorder
- * traversal
- * @param c A cursor
- * @return Cursor one position past the last element of @a c in
- * postorder traversal
+ * @brief One position past the last element of a subtree in postorder
+ * traversal
+ * @param c Subtree root cursor that will be set to the last postorder
+ * position in the subtree.
*/
template <class Cursor>
-Cursor last(Cursor c)
-{
- return c;
-}
+void to_last(Cursor& c)
+{ }
+
+#include <boost/tree/detail/algorithm/cursor/_order.hpp>
/*\@}*/
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
+//#else
+
/**
* @if maint
* Helper function for for_each, using a reference parameter in order to
@@ -200,10 +175,6 @@
return f;
}
-#else
-#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
/**
* @brief Copies the subtree s into t, by traversing s in postorder.
* @param s An input cursor.
@@ -264,6 +235,8 @@
return t;
}
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+
} // namespace postorder
} // namespace tree
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-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -15,6 +15,7 @@
#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
#include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
namespace boost {
namespace tree {
@@ -61,21 +62,6 @@
}
/**
- * @brief Preorder successor
- * @param c A cursor
- * @param n Optional parameter to indicate how many steps to move forward
- * @return Preorder successor of @a c
- */
-template <class Cursor>
-inline Cursor next(Cursor c
- , typename Cursor::difference_type n = 1)
-{
- for (; n!=0; --n)
- forward(c);
- return c;
-}
-
-/**
* @brief Preorder predecessor
* @param c Cursor to be set to its preorder predecessor
*/
@@ -106,47 +92,34 @@
}
/**
- * @brief Preorder predecessor
- * @param c A cursor
- * @param n Optional parameter to indicate how many steps to move back
- * @return Preorder predecessor of @a c
+ * @brief First element of a subtree in preorder traversal
+ * @param c Subtree root cursor that will be set to the first preorder
+ * position in the subtree.
*/
template <class Cursor>
-inline Cursor prior(Cursor c
- , typename Cursor::difference_type n = 1)
+void to_first(Cursor& c)
{
- for (; n!=0; --n)
- back(c);
- return c;
+ c.to_begin();
}
/**
- * @brief First element of a subtree in preorder traversal
- * @param c A cursor
- * @return Cursor to the first element of @a c in preorder traversal
+ * @brief One position past the last element of a subtree in preorder
+ * traversal
+ * @param c Subtree root cursor that will be set to the last preorder
+ * position in the subtree.
*/
template <class Cursor>
-Cursor first(Cursor c)
-{
- return c.begin();
-}
+void to_last(Cursor& c)
+{ }
-/**
- * @brief One position past the last element of a subtree in preorder
- * traversal
- * @param c A cursor
- * @return Cursor one position past the last element of @a c in preorder
- * traversal
- */
-template <class Cursor>
-Cursor last(Cursor c)
-{
- return c;
-}
+#include <boost/tree/detail/algorithm/cursor/_order.hpp>
/*\@}*/
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
+//#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
+//#else
+
/**
* @if maint
* Helper function for for_each, using a reference parameter in order to
@@ -197,10 +170,6 @@
return f;
}
-#else
-#include <boost/tree/detail/algorithm/cursor/_order_iterative.hpp>
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
/**
* @brief Copies the subtree s into t, by traversing s in preorder.
* @param s An input cursor.
@@ -259,6 +228,8 @@
return t;
}
+//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+
} // namespace preorder
} // namespace tree
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/root_tracking_cursor.hpp 2008-09-27 16:57:23 EDT (Sat, 27 Sep 2008)
@@ -60,22 +60,22 @@
explicit root_tracking_cursor(Cursor c)
: root_tracking_cursor::cursor_adaptor_(c), m_depth(0) {}
- template <class OtherCursor>
- root_tracking_cursor(
- root_tracking_cursor<OtherCursor> const& other
- , typename boost::enable_if<
- boost::is_convertible<OtherCursor*, Cursor*>
- , enabler
- >::type = enabler()
- )
- : root_tracking_cursor::cursor_adaptor_(other.base())
- , m_depth(other.m_depth) {}
+// template <class OtherCursor>
+// root_tracking_cursor(
+// root_tracking_cursor<OtherCursor> const& other
+// , typename boost::enable_if<
+// boost::is_convertible<OtherCursor*, Cursor*>
+// , enabler
+// >::type = enabler()
+// )
+// : root_tracking_cursor::cursor_adaptor_(other.base())
+// , m_depth(other.m_depth) {}
private:
- friend class boost::iterator_core_access;
+ friend class boost::iterator_core_access;
friend class boost::tree::cursor_core_access;
- std::size_t m_depth;
+ std::size_t m_depth;
// bool equal(cursor const& other) const
// {