Subject: [Boost-commit] svn:boost r49057 - in sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm: . cursor
From: ockham_at_[hidden]
Date: 2008-09-29 18:09:07
Author: bernhard.reiter
Date: 2008-09-29 18:09:06 EDT (Mon, 29 Sep 2008)
New Revision: 49057
URL: http://svn.boost.org/trac/boost/changeset/49057
Log:
More cleanup.
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/ascending.hpp (contents, props changed)
- copied, changed from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/general.hpp (contents, props changed)
- copied, changed from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp (contents, props changed)
- copied, changed from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp (contents, props changed)
- copied, changed from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp (contents, props changed)
- copied, changed from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp (contents, props changed)
- copied, changed from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
Removed:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/ascending.hpp (from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp)
==============================================================================
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp 2008-09-29 18:09:06 EDT (Mon, 29 Sep 2008)
+++ (empty file)
@@ -1,42 +0,0 @@
-// 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 ascending.hpp
- * Ascending traversal algorithms for cursors
- */
-
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_ASCENDING_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_ASCENDING_HPP
-
-
-namespace boost {
-namespace tree {
-
-/** \addtogroup traversal */
-/*\@{*/
-
-struct ascending {};
-
-/**
- * @brief Ascending successor
- * @param c MultiwayCursor to be set to its ascending successor
- * @ingroup traversal
- */
-template <class MultiwayCursor>
-inline void forward(ascending, MultiwayCursor& c)
-{
- c.to_parent();
- return;
-}
-
-/*\@}*/
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_ALGORITHM_ASCENDING_HPP
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp 2008-09-29 18:09:06 EDT (Mon, 29 Sep 2008)
+++ (empty file)
@@ -1,127 +0,0 @@
-// 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 general.hpp
- * General algorithms for cursors
- */
-
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_GENERAL_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_GENERAL_HPP
-
-
-namespace boost {
-namespace tree {
-
-// These algorithms are actually mostly preorder, as it's most efficient, but I
-// think it doesn't make much sense having in- and postorder versions of them.
-// The only reason I can think of is that there might be some cases
-// where it's likely to find a mismatch or whatever faster in in- or postorder
-// than in preorder -- but for things like size() or count(), this doesn't really matter.
-
-// What about the subtree shapes?
-/**
- * @brief Checks two subtrees for element-wise equality.
- * @param c1 An input cursor.
- * @param c2 An input cursor.
- * @return A boolean true or false.
- *
- * Compares the elements of two subtrees using @c ==. Returns true if
- * all the corresponding elements of the subtrees are equal; otherwise,
- * it returns false.
- */
-template <class InCursor1, class InCursor2>
-bool equal(InCursor1 c1, InCursor2 c2)
-{
- InCursor1 d1 = c1.end();
- c1.to_begin();
- c2.to_begin();
- if (!(*c1 == *c2))
- return false;
- do {
- if (!c1.empty())
- if (!equal(c1, c2))
- return false;
- ++c2;
- } while (c1++ != d1);
-
- return true;
-}
-
-/**
- * @brief Checks two subtrees for element-wise equality.
- * @param c1 An input cursor.
- * @param c2 An input cursor.
- * @param p A binary predicate.
- * @return A boolean true or false.
- *
- * Compares the elements of two subtrees using the p parameter.
- * Returns true if all the corresponding elements of the
- * subtrees are equal; otherwise, it returns false.
- */
-template <class InCursor1, class InCursor2, class BinPred>
-bool equal(InCursor1 c1, InCursor2 c2, BinPred p)
-{
- InCursor1 d1 = c1.end();
- c1.to_begin();
- c2.to_begin();
- if (!p(*c1,*c2))
- return false;
- do {
- if (!c1.empty())
- if (!equal(c1, c2))
- return false;
- ++c2;
- } while (c1++ != d1);
-
- return true;
-}
-
-/**
- * @brief Calculates the number of elements in a subtree.
- * @param c An input cursor.
- * @param s The size type of @c c1.
- *
- * After finishing, s will have been increased by the number of elements in c.
- */
-template <class InCursor>
-void size(InCursor c, typename InCursor::size_type& s)
-{
- InCursor d = c.end();
- c.to_begin();
- ++s;
- do
- if (!c.empty())
- size(c, s);
- while (c++ != d);
-}
-
-/**
- * @brief Returns the number of elements in a subtree.
- * @param c An input cursor.
- * @return The size type of @c c1.
- */
-template <class InCursor>
-typename InCursor::size_type size(InCursor c)
-{
- typename InCursor::size_type s = 0;
- InCursor d = c.end();
- c.to_begin();
- ++s;
- do
- if (!c.empty())
- size(c, s);
- while (c++ != d);
-
- return s;
-}
-
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_ALGORITHM_GENERAL_HPP
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp 2008-09-29 18:09:06 EDT (Mon, 29 Sep 2008)
+++ (empty file)
@@ -1,304 +0,0 @@
-// 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 inorder.hpp
- * Subtree intorder traversal and search algorithms
- */
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
-
-#include <boost/tree/root_tracking_cursor.hpp>
-#include <boost/tree/ascending_cursor.hpp>
-
-#include <algorithm>
-
-namespace boost {
-namespace tree {
-
-/** \addtogroup traversal */
-/*\@{*/
-
-struct inorder {};
-
-/**
- * @brief Inorder successor
- * @param c MultiwayCursor to be set to its inorder successor
- * @ingroup traversal
- */
-template <class MultiwayCursor>
-inline void forward(inorder, MultiwayCursor& c)
-{
- if (!(++c).empty()) {
- while (!c.to_begin().empty());
- return;
- }
-
- while (c.parity() && !c.is_root())
- c.to_parent();
- return;
-}
-
-/**
- * @brief Inorder predecessor
- * @param c MultiwayCursor to be set to its inorder predecessor
- */
-template <class MultiwayCursor>
-inline void back(inorder, MultiwayCursor& c)
-{
- if (!c.empty()) {
- while (!c.to_end().empty());
- --c;
- return;
- }
-
- while (!c.parity() && !c.is_root())
- c.to_parent();
- if (!c.is_root())
- --c;
- return;
-}
-
-/**
- * @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 Cursor>
-void to_first(inorder, Cursor& c)
-{
- while (!c.empty())
- c.to_begin();
-}
-
-/**
- * @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(inorder, Cursor& c)
-{ }
-
-/*\@}*/
-
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
-
-/**
- * @if maint
- * Helper function for for_each, using a reference parameter in order to
- * require fewer copy and assignment operations.
- * @endif
- */
-template <class MultiwayCursor, class Op>
-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(inorder(), s, f);
- f(*s);
- }
-
- // Multiway cursor
- if (!t.empty())
- for_each_recursive(inorder(), t, f);
-}
-
-/**
- * @brief Apply a function to every element of a multiway subtree,
- * in inorder.
- * @param s A MultiwayTree cursor.
- * @param f A unary function object.
- * @return @p f
- *
- * Applies the function object @p f to each element in the @p subtree, using
- * inorder. @p f must not modify the order of the sequence.
- * If @p f has a return value it is ignored.
- */
- //[ inorder_for_each
-template <class MultiwayCursor, class Op>
-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);
- f(*s);
- }
-
- // Multiway cursor
- if (!t.empty())
- for_each_recursive(inorder(), t, f);
- return f;
-}
-
-/**
- * @brief Copies the subtree s into t, by traversing s in inorder.
- * @param s An input cursor.
- * @param t An output cursor.
- * @result A cursor past t's inorder end, after the copying operation.
- */
-template <class InCursor, class OutCursor>
-OutCursor copy(inorder, InCursor s, OutCursor t)
-{
- InCursor r = s.end();
-
- s.to_begin();
- t.to_begin();
-
- for (; s != r; ++s, ++t) {
- if (!s.empty())
- copy(inorder(), s, t);
- *t=*s;
- }
-
- // Multiway cursor
- if (!r.empty())
- copy(inorder(), r, t);
- return t;
-}
-
-/**
- * @brief Performs an operation on a subtree, by traversing it in inorder.
- * @param s An input cursor.
- * @param t An output cursor.
- * @param op A unary operation.
- * @result A cursor past t's inorder end, after the transforming has
- * finished.
- *
- * By traversing the input subtree s in inorder, 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(inorder, InCursor s, OutCursor t, Op op)
-{
- InCursor r = s.end();
-
- s.to_begin();
- t.to_begin();
-
- for (; s != r; ++s, ++t) {
- if (!s.empty())
- transform(inorder(), s, t, op);
- *t=op(*s);
- }
-
- // Multiway cursor
- if (!r.empty())
- transform(inorder(), r, t, op);
- return t;
-}
-
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
-/// Search
-
-/**
- * @brief Finds the first position in a multiway subtree in which @a val
- * could be inserted without changing the ordering, using < (less
- * than) for comparisons.
- * @param x The subtree's root
- * @param val The search term
- * @return A multiway cursor pointing to the first element not less than
- * @a val, or @x if every element in the subtree is less than
- * @a val.
- */
-template <class MultiwayCursor, class T>
-MultiwayCursor lower_bound(MultiwayCursor x, T const& val)
-{
- MultiwayCursor y = x;
- while (!x.empty()) {
- x = std::lower_bound(x.begin(), x.end(), val);
- if (x.parity() == 0)
- y = x;
- }
- return y;
-}
-
-/**
- * @brief Finds the first position in a multiway subtree in which @a val
- * could be inserted without changing the ordering, using @a cmp
- * for comparisons.
- * @param x The subtree's root
- * @param val The search term
- * @param cmp The comparison functor
- * @return A multiway cursor pointing to the first element not less than
- * @a val, or @x if every element in the subtree is less than
- * @a val.
- */
-template <class MultiwayCursor, class T, class Cmp>
-MultiwayCursor lower_bound(MultiwayCursor x, T const& val, Cmp cmp)
-{
- MultiwayCursor y = x;
- while (!x.empty()) {
- x = std::lower_bound(x.begin(), x.end(), val, cmp);
- if (x.parity() == 0)
- y = x;
- }
- return y;
-}
-
-/**
- * @brief Finds the last position in a multiway subtree in which @a val
- * could be inserted without changing the ordering, using < (less
- * than) for comparisons.
- * @param x The subtree's root
- * @param val The search term
- * @return A multiway cursor pointing to the first element greater than
- * @a val, or @x if no element in the subtree is greater than
- * @a val.
- */
-template <class MultiwayCursor, class T>
-MultiwayCursor upper_bound(MultiwayCursor x, T const& val)
-{
- MultiwayCursor y = x;
- while (!x.empty()) {
- x = std::upper_bound(x.begin(), x.end(), val);
- if (x.parity() == 0)
- y = x;
- }
- return y;
-}
-
-/**
- * @brief Finds the last position in a multiway subtree in which @a val
- * could be inserted without changing the ordering, using @a cmp
- * for comparisons.
- * @param x The subtree's root
- * @param val The search term
- * @param cmp The comparison functor
- * @return A multiway cursor pointing to the first element greater than
- * @a val, or @x if no element in the subtree is greater than
- * @a val.
- */
-template <class MultiwayCursor, class T, class Cmp>
-MultiwayCursor upper_bound(MultiwayCursor x, T const& val, Cmp cmp)
-{
- MultiwayCursor y = x;
- while (!x.empty()) {
- x = std::upper_bound(x.begin(), x.end(), val, cmp);
- if (x.parity() == 0)
- y = x;
- }
- return y;
-}
-
-// Implement equal_range? Maybe not, if it'd only return a pair
-// consisting of cursors calculated by calling lower_bound and upper_bound.
-// This might be a bit more subtle for non-binary multiway trees.
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp 2008-09-29 18:09:06 EDT (Mon, 29 Sep 2008)
+++ (empty file)
@@ -1,132 +0,0 @@
-// 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 iterative.hpp
- *
- * Some iterative 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).
- */
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_ITERATIVE_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_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(Order, root_tracking_cursor<Cursor> s, Op f)
-{
- root_tracking_cursor<Cursor> s2(s);
- to_first(Order(), s);
- to_last(Order(), s2);
- while (s!=s2) {
- f(*s);
- forward(Order(), s);
- }
- return f;
-}
-
-/**
- * @brief Apply a function to every element of a subtree,
- * in the order specified by the first parameter.
- * @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 Order, class Cursor, class Op>
-Op for_each(Order, Cursor s, Op f)
-//]
-{
- return for_each(Order(), root_tracking_cursor<Cursor>(s), f);
-}
-
-template <class Order, class InCursor, class OutCursor>
-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);
- while (s!=s2) {
- *t = *s;
- forward(Order(), s);
- forward(Order(), t);
- }
- return t;
-}
-
-/**
- * @brief Copies the subtree s into t, by traversing s
- * in the order specified by the first parameter.
- * @param s An input cursor.
- * @param t An output cursor.
- * @result A cursor past t's *order end, after the copying operation.
- */
-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();
-}
-
-template <class Order, class InCursor, class OutCursor, class Op>
-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);
- while (s!=s2) {
- *t = op(*s);
- forward(Order(), s);
- forward(Order(), t);
- }
- return t;
-}
-
-/**
- * @brief Performs an operation on a subtree, by traversing it
- * in the order specified by the first parameter.
- * @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 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();
-}
-
-} // namespace tree
-} // namespace boost
-
-#endif //BOOST_TREE_DETAIL_ALGORITHM_ITERATIVE_HPP
\ No newline at end of file
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp 2008-09-29 18:09:06 EDT (Mon, 29 Sep 2008)
+++ (empty file)
@@ -1,237 +0,0 @@
-// 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 postorder.hpp
- * Subtree postorder traversal algorithms
- */
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
-
-#include <boost/tree/root_tracking_cursor.hpp>
-#include <boost/tree/ascending_cursor.hpp>
-
-namespace boost {
-namespace tree {
-
-/** \addtogroup traversal */
-/*\@{*/
-
-struct postorder {};
-
-/**
- * @brief Postorder successor
- * @param c Cursor to be set to its postorder successor
- */
-template <class Cursor>
-inline void forward(postorder, Cursor& c)
-{
- c.to_parent();
-
- if (c.is_root())
- return;
-
- if (c.parity()) { // Right child? Return parent.
- --c;
- return;
- }
-
- // Left child.
- ++c;
- while (!c.empty()) {
- c.to_begin();
- if (c.empty())
- ++c;
- }
- if (c.parity())
- --c;
- return;
-}
-
-/**
- * @brief Postorder predecessor
- * @param c Cursor to be set to its postorder predecessor
- */
-template <class Cursor>
-inline void back(postorder, Cursor& c)
-{
- if (c.is_root()) { // Root?
- c.to_begin();
- return;
- }
-
- if (!(++c).empty()) { // Right
- c.to_begin();
- return;
- }
- if (!(--c).empty()) { // Left
- c.to_begin();
- return;
- }
-
- // Move up in the hierarchy until we find a descendant that has a right
- // child (which is what we'll return) or we land at root.
- while (!c.is_root()) {
- c.to_parent();
- if (c.parity())
- if (!(--c).empty()) {
- c.to_begin();
- return;
- }
- }
- return;
-}
-
-/**
- * @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>
-void to_first(postorder, Cursor& c)
-{
- while (true)
- if (!c.empty())
- c.to_begin();
- else if (!(++c).empty())
- c.to_begin();
- else {
- --c;
- return;
- }
-}
-
-/**
- * @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>
-void to_last(postorder, Cursor& c)
-{ }
-
-/*\@}*/
-
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
-
-/**
- * @if maint
- * Helper function for for_each, using a reference parameter in order to
- * require fewer copy and assignment operations.
- * @endif
- */
-template <class Cursor, class Op>
-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);
-
- // Multiway cursor
- if (!s.empty())
- for_each_recursive(postorder(), s, f);
-
- f(*t.to_begin());
-}
-
-/**
- * @brief Apply a function to every element of a subtree, in postorder.
- * @param s A cursor.
- * @param f A unary function object.
- * @return @p f
- *
- * Applies the function object @p f to each element in the subtree @p s, using
- * postorder. @p f must not modify the order of the sequence.
- * If @p f has a return value it is ignored.
- */
-//[ postorder_for_each
-template <class Cursor, class Op>
-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);
-
- // Multiway cursor
- if (!s.empty())
- for_each_recursive(postorder(), s, f);
-
- f(*t.to_begin());
-
- return f;
-}
-
-/**
- * @brief Copies the subtree s into t, by traversing s in postorder.
- * @param s An input cursor.
- * @param t An output cursor.
- * @result A cursor past t's postorder end, after the copying operation.
- */
-template <class InCursor, class OutCursor>
-OutCursor copy(postorder, InCursor s, OutCursor t)
-{
- InCursor r = s;
- s.to_begin();
- t.to_begin();
-
- for (; s != r.end(); ++s, ++t) {
- if (!s.empty())
- copy(postorder(), s, t);
-// else
-// *t = *s;
- }
-
- // Multiway cursor
- if (!s.empty())
- copy(postorder(), s, t);
-
- *t = *r.to_begin();
- return t;
-}
-
-/**
- * @brief Performs an operation on a subtree, by traversing it in postorder.
- * @param s An input cursor.
- * @param t An output cursor.
- * @param op A unary operation.
- * @result A cursor past t's postorder end, after the transforming has
- * finished.
- *
- * By traversing the input subtree s in postorder, 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(postorder, InCursor s, OutCursor t, Op op)
-{
- InCursor r = s;
- s.to_begin();
- t.to_begin();
-
- for (; s != r.end(); ++s, ++t)
- if (!s.empty())
- transform(postorder(), s, t, op);
-
- // Multiway cursor
- if (!s.empty())
- transform(postorder(), s, t, op);
-
- *t = op(*r.to_begin());
- return t;
-}
-
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp 2008-09-29 18:09:06 EDT (Mon, 29 Sep 2008)
+++ (empty file)
@@ -1,234 +0,0 @@
-// 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 preorder.hpp
- * Subtree preorder traversal algorithms
- */
-
-// TODO: concept checks.
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
-
-#include <boost/tree/root_tracking_cursor.hpp>
-#include <boost/tree/ascending_cursor.hpp>
-
-namespace boost {
-namespace tree {
-
-/** \addtogroup traversal */
-/*\@{*/
-
-struct preorder {};
-
-/**
- * @brief Preorder successor
- * @param c Cursor to be set to its preorder successor
- */
-template <class Cursor>
-inline void forward(preorder, Cursor& c)
-{
- // If we have a left child, go there.
- if (!c.empty()) {
- c.to_begin();
- return;
- }
-
- // No left child. So if we have a right child, go there.
- if (!(++c).empty()) {
- c.to_begin();
- return;
- }
-
- // (Here's where we'd need to check if this is the end().)
-
- // No children at all.
- // As we've already visited all the ancestors, we'll move upwards until
- // we find an ancestor that has a right child.
- while (!c.is_root()) { // Doesn't work with subtrees!
- c.to_parent();
- if (!c.is_root() && !c.parity()) {
- if (!(++c).empty()) {
- c.to_begin();
- return;
- }
- }
- }
- return;
-}
-
-/**
- * @brief Preorder predecessor
- * @param c Cursor to be set to its preorder predecessor
- */
-template <class Cursor>
-inline void back(preorder, Cursor& c)
-{
- if (!c.is_root()) {
- c.to_parent();
-
- // If a left child was given, just move to its parent.
- if (!c.parity())
- return;
-
- // So this is a right child.
- --c;
- }
-
- // Same for root (=end) and right children:
- while (!c.empty())
- if (!c.end().empty())
- c.to_end();
- else
- c.to_begin();
-
- if (c.parity())
- --c;
- return;
-}
-
-/**
- * @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>
-void to_first(preorder, Cursor& c)
-{
- c.to_begin();
-}
-
-/**
- * @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>
-void to_last(preorder, Cursor& c)
-{ }
-
-/*\@}*/
-
-#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
-
-/**
- * @if maint
- * Helper function for for_each, using a reference parameter in order to
- * require fewer copy and assignment operations.
- * @endif
- */
-template <class Cursor, class Op>
-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);
- }
-
- // Multiway cursor
- if (!s.empty())
- for_each_recursive(preorder(), s, f);
-}
-
-/**
- * @brief Apply a function to every element of a subtree, in preorder.
- * @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, using
- * preorder. @p f must not modify the order of the sequence.
- * If @p f has a return value it is ignored.
- */
-//[ preorder_for_each
-template <class Cursor, class Op>
-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);
- }
-
- // Multiway cursor
- if (!s.empty())
- for_each_recursive(preorder(), s, f);
-
- return f;
-}
-
-//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
-/**
- * @brief Copies the subtree s into t, by traversing s in preorder.
- * @param s An input cursor.
- * @param t An output cursor.
- * @result A cursor past t's preorder end, after the copying operation.
- */
-template <class InCursor, class OutCursor>
-OutCursor copy(preorder, InCursor s, OutCursor t)
-{
- InCursor r = s.end();
- s.to_begin();
- t.to_begin();
-
- for (; s != r; ++s, ++t) {
- *t = *s;
- if (!s.empty())
- copy(preorder(), s, t);
- }
-
- // Multiway cursor
- if (!r.empty())
- copy(preorder(), r, t);
-
- return t;
-}
-
-/**
- * @brief Performs an operation on a subtree, by traversing it in preorder.
- * @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 in preorder, 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(preorder, InCursor s, OutCursor t, Op op)
-{
- InCursor r = s.end();
- s.to_begin();
- t.to_begin();
- for (; s != r; ++s, ++t) {
- *t = op(*s);
- if (!s.empty())
- transform(preorder(), s, t, op);
- }
-
- // Multiway cursor
- if (!s.empty())
- transform(preorder(), s, t, op);
-
- return t;
-}
-
-#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/general.hpp (from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/general.hpp)
==============================================================================
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp (from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp)
==============================================================================
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterative.hpp (from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/iterative.hpp)
==============================================================================
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp (from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp)
==============================================================================
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp (from r49056, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp)
==============================================================================