[Boost-commit] svn:boost r49057 - in sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm: . cursor

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)
==============================================================================