[Boost-commit] svn:boost r50440 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail boost/tree/detail/balancers

Subject: [Boost-commit] svn:boost r50440 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail boost/tree/detail/balancers
From: ockham_at_[hidden]
Date: 2009-01-02 14:06:58

Author: bernhard.reiter
Date: 2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
New Revision: 50440
URL: http://svn.boost.org/trac/boost/changeset/50440

Log:
Continue reorganising algorithms.
Added:
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending_algorithms.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp
      - copied, changed from r50432, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp
      - copied unchanged from r50433, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms
   sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp   (contents, props changed)
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp   (contents, props changed)
Removed:
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                       |     4 ++++                                    
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp                   |    33 ++++++++++++++++++++-------------       
   sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp            |     4 ++--                                    
   sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp               |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp |     2 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp |    16 +++++++++-------                        
   6 files changed, 37 insertions(+), 24 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -14,11 +14,14 @@
 [section TODO]
 
 General:
+* Add checks for correspondence of concepts and archetypes!
 * Re-do forest (again!). No root(); begin() and end() instead. No default element at
   construction time (that would really suck). Rename forest_tree to forest, 
   as it's going to be a forest, not just "one" tree.
   This seems to raise one issue, though: subtree algorithms operate on subtree root cursors,
   not ranges. (They might, however, work for "subforests".)
+  They also work for the important special case in which forest consists of only one
+  subtree!
 * Improve cursor_archetype. Currently, there's trouble eg with constructors.
 * Remove a cursor's cursor, const_cursor, iterator and const_iterator typedefs?
   The latter two only make sense in a range algorithm context, where they might actually be
@@ -185,6 +188,7 @@
 
 Documentation:
 
+* Add a rationale for binary tree cursor semantics.
 * Make docs more coherent. If we're using doxygen for API documentation, don't
   duplicate that information via quickbook!
 * Include examples output (requires some Jamfile tweaking)!

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	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -12,15 +12,19 @@
 #ifndef BOOST_TREE_ALGORITHM_HPP
 #define BOOST_TREE_ALGORITHM_HPP
 
-#include <boost/tree/detail/algorithm/general.hpp>
-#include <boost/tree/detail/algorithm/ascending.hpp>
+#include <boost/tree/general_algorithms.hpp>
+#include <boost/tree/ascending_algorithms.hpp>
 
-#include <boost/tree/detail/algorithm/preorder.hpp>
-#include <boost/tree/detail/algorithm/inorder.hpp>
-#include <boost/tree/detail/algorithm/postorder.hpp>
+#include <boost/tree/preorder_algorithms.hpp>
+#include <boost/tree/inorder_algorithms.hpp>
+#include <boost/tree/postorder_algorithms.hpp>
+
+#include <boost/tree/detail/recursive_preorder_algorithms.hpp>
+#include <boost/tree/detail/recursive_inorder_algorithms.hpp>
+#include <boost/tree/detail/recursive_postorder_algorithms.hpp>
 
 //#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
-#include <boost/tree/detail/iterative.hpp>
+#include <boost/tree/detail/iterative_algorithms.hpp>
 //#endif
 
 namespace boost {
@@ -93,7 +97,10 @@
 }
 
 template <class BinaryCursor>
-void to_forest_end(BinaryCursor& c)
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<BinaryCursor>)),
+    (void)) // return type
+to_forest_end(BinaryCursor& c)
 {
     c.to_begin();
     while (!c.empty())
@@ -129,8 +136,8 @@
 Op for_each(Order, Cursor s, Op f)
 //]
 {
-    return for_each(Order(), s, f
-                  , typename cursor_vertical_traversal<Cursor>::type());
+    return detail::for_each(Order(), s, f
+                          , typename cursor_vertical_traversal<Cursor>::type());
 }
 
 /**
@@ -152,8 +159,8 @@
 OutCursor transform (Order, InCursor s, OutCursor t, Op op)
 //]
 {
-    return transform(Order(), s, t, op
-                  , typename cursor_vertical_traversal<InCursor>::type());
+    return detail::transform(Order(), s, t, op
+                           , typename cursor_vertical_traversal<InCursor>::type());
     // What about OutCursor?
 }
 
@@ -166,8 +173,8 @@
 template <class Order, class InCursor, class OutCursor, class Traversal>
 OutCursor copy(Order, InCursor s, OutCursor t, Traversal tr)
 {
-    return transform(Order(), s, t
-                   , identity<typename cursor_value<InCursor>::type>, tr);
+    return detail::transform(Order(), s, t
+                           , identity<typename cursor_value<InCursor>::type>, tr);
 }
 
 /**

Added: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_algorithms.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_algorithms.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,52 @@
+//  Copyright (c) 2006-2009, 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_algorithms.hpp
+ * Ascending traversal algorithms for cursors
+ */
+
+#ifndef BOOST_TREE_ASCENDING_ALGORITHMS_HPP
+#define BOOST_TREE_ASCENDING_ALGORITHMS_HPP
+
+#include <boost/iterator/iterator_categories.hpp>
+
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
+
+namespace boost {
+namespace tree {
+
+/** \addtogroup traversal */
+/*\@{*/
+
+struct ascending {
+    typedef forward_traversal_tag iterator_category; 
+};
+
+/**
+ * @brief    Ascending successor
+ * @param c    MultiwayCursor to be set to its ascending successor
+ * @ingroup    traversal
+ */
+template <class MultiwayCursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((Ascendor<MultiwayCursor>)),
+    (void)) // return type
+successor(ascending, MultiwayCursor& c)
+{
+    c.to_parent();
+    return;
+}
+
+/*\@}*/
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_ASCENDING_ALGORITHMS_HPP

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	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -18,8 +18,6 @@
 #include <boost/tree/iterator.hpp>
 #include <boost/tree/root_tracking_cursor.hpp>
 
-#include <boost/tree/detail/algorithm/ascending.hpp>
-
 #include <boost/mpl/eval_if.hpp>
 #include <boost/mpl/identity.hpp>
 #include <boost/type_traits/is_const.hpp>
@@ -33,6 +31,8 @@
 
 /** \addtogroup cursor_adaptors
  *  \@{ */
+ 
+struct ascending;
 
 template <class DescendingCursor> 
 class ascending_cursor;

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -19,7 +19,7 @@
 #include <boost/tree/detail/balancers/unbalanced.hpp>
 #include <boost/tree/detail/augmentors/unaugmented.hpp>
 
-#include <boost/tree/detail/algorithm/inorder.hpp>
+#include <boost/tree/inorder_algorithms.hpp>
 #include <boost/tree/detail/augmented_iterator.hpp>
 
 #include <boost/bind.hpp>

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -8,7 +8,7 @@
 #define BOOST_TREE_BALANCERS_UNBALANCED_HPP
 
 #include <boost/tree/detail/cursor/nary.hpp>
-#include <boost/tree/detail/algorithm/inorder.hpp>
+#include <boost/tree/inorder_algorithms.hpp>
 
 namespace boost {
 namespace tree {

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
+++ (empty file)
@@ -1,76 +0,0 @@
-//  Copyright (c) 2006-2009, 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_ITERATIVE_HPP
-#define BOOST_TREE_DETAIL_ITERATIVE_HPP
-
-#include <boost/tree/coupling_cursor.hpp>
-
-#include <boost/tree/detail/algorithm/preorder.hpp>
-#include <boost/tree/detail/algorithm/inorder.hpp>
-#include <boost/tree/detail/algorithm/postorder.hpp>
-
-#include <boost/tree/cursor_concepts.hpp>
-
-#include <boost/concept/requires.hpp>
-
-namespace boost {
-namespace tree {
-
-template <class Order, class Cursor, class Op>
-BOOST_CONCEPT_REQUIRES(
-    ((Descendor<Cursor>))
-    ((Ascendor<Cursor>)),
-    (Op)) // return type
-for_each(Order, Cursor is, Op f, ascending_vertical_traversal_tag)
-{
-    root_tracking_cursor<Cursor> s(is);
-    root_tracking_cursor<Cursor> s2(s);
-    to_first(Order(), s);
-    to_last(Order(), s2);
-    while (s!=s2) {
-        f(*s);
-        successor(Order(), s);
-    }
-    return f;
-}
-
-template <class Order, class InCursor, class OutCursor, class Op>
-BOOST_CONCEPT_REQUIRES(
-    ((Descendor<InCursor>))
-    ((Ascendor<InCursor>))
-    ((Descendor<OutCursor>))
-    ((Ascendor<OutCursor>)),
-    (OutCursor)) // return type
-transform (Order, InCursor is, OutCursor t, Op op
-                   , ascending_vertical_traversal_tag)
-{
-    root_tracking_cursor<InCursor> s(is);
-    root_tracking_cursor<InCursor> s2(s);
-    
-    boost::tree::coupling_cursor< root_tracking_cursor<InCursor>, OutCursor > cc(s, t);
-
-    to_first(Order(), cc);
-    to_last(Order(), s2);
-
-    while (cc.in()!=s2) {
-        *cc.out() = op(*cc.in());
-        successor(Order(), cc);
-    }
-    return cc.out();
-}
-
-} // namespace tree
-} // namespace boost
-
-#endif //BOOST_TREE_DETAIL_ITERATIVE_HPP
\ No newline at end of file

Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp (from r50432, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -4,21 +4,21 @@
 //  (See accompanying file LICENSE_1_0.txt or copy at
 //  http://www.boost.org/LICENSE_1_0.txt)
 
-/** @file   iterative.hpp
+/** @file   iterative_algorithms.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_ITERATIVE_HPP
-#define BOOST_TREE_DETAIL_ITERATIVE_HPP
+#ifndef BOOST_TREE_DETAIL_ITERATIVE_ALGORITHMS_HPP
+#define BOOST_TREE_DETAIL_ITERATIVE_ALGORITHMS_HPP
 
 #include <boost/tree/coupling_cursor.hpp>
 
-#include <boost/tree/detail/algorithm/preorder.hpp>
-#include <boost/tree/detail/algorithm/inorder.hpp>
-#include <boost/tree/detail/algorithm/postorder.hpp>
+#include <boost/tree/preorder_algorithms.hpp>
+#include <boost/tree/inorder_algorithms.hpp>
+#include <boost/tree/postorder_algorithms.hpp>
 
 #include <boost/tree/cursor_concepts.hpp>
 
@@ -26,6 +26,7 @@
 
 namespace boost {
 namespace tree {
+namespace detail {
 
 template <class Order, class Cursor, class Op>
 BOOST_CONCEPT_REQUIRES(
@@ -70,7 +71,8 @@
     return cc.out();
 }
 
+} // namespace detail
 } // namespace tree
 } // namespace boost
 
-#endif //BOOST_TREE_DETAIL_ITERATIVE_HPP
\ No newline at end of file
+#endif //BOOST_TREE_DETAIL_ITERATIVE_ALGORITHMS_HPP
\ No newline at end of file

Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
+++ (empty file)
@@ -1,124 +0,0 @@
-//  Copyright (c) 2006-2009, 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 recursive_postorder_algorithms.hpp
- * Recursice subtree postorder traversal algorithms
- */
-
-#ifndef BOOST_TREE_DETAIL_RECURSIVE_POSTORDER_ALGORITHMS_HPP
-#define BOOST_TREE_DETAIL_RECURSIVE_POSTORDER_ALGORITHMS_HPP
-
-#include <boost/tree/cursor_concepts.hpp>
-
-#include <boost/concept/requires.hpp>
-
-namespace boost {
-namespace tree {
-namespace detail {
-
-using namespace boost_concepts;
-
-//#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>
-BOOST_CONCEPT_REQUIRES(
-    ((Descendor<Cursor>)),
-    (void)) // return type
-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.
- */
-template <class Cursor, class Op>
-BOOST_CONCEPT_REQUIRES(
-    ((Descendor<Cursor>)),
-    (Op)) // return type
-for_each(postorder, Cursor s, Op f, descending_vertical_traversal_tag)
-{
-    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     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>
-BOOST_CONCEPT_REQUIRES(
-    ((Descendor<InCursor>))
-    ((Descendor<OutCursor>)),
-    (OutCursor)) // return type
-transform(postorder, InCursor s, OutCursor t, Op op, descending_vertical_traversal_tag)
-{
-    InCursor r = s;
-    s.to_begin();
-    t.to_begin();
-    OutCursor t2 = t;
-    
-    for (; s != r.end(); ++s, ++t)
-        if (!s.empty())
-            transform(postorder(), s, t, op, descending_vertical_traversal_tag());
-
-    // Multiway cursor
-    if (!s.empty())
-        transform(postorder(), s, t, op, descending_vertical_traversal_tag());
-    
-    *t2 = op(*r.to_begin());
-    return t;
-}
-
-//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-
-} // namespace detail
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_RECURSIVE_POSTORDER_ALGORITHMS_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,137 @@
+//  Copyright (c) 2006-2009, 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_algorithms.hpp
+ * General algorithms for cursors
+ */
+
+#ifndef BOOST_TREE_GENERAL_ALGORITHMS_HPP
+#define BOOST_TREE_GENERAL_ALGORITHMS_HPP
+
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
+
+namespace boost {
+namespace tree {
+
+using namespace boost_concepts;
+
+// 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.
+ */
+//[ equal
+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.
+ */
+//[ equal_pred
+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::subtree_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.
+ */
+//[ size
+template <class InCursor>
+typename InCursor::subtree_size_type size(InCursor c)
+//]
+{
+    typename InCursor::subtree_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_GENERAL_ALGORITHMS_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,231 @@
+//  Copyright (c) 2006-2009, 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_algorithms.hpp
+ * Subtree intorder traversal and search algorithms
+ */
+
+#ifndef BOOST_TREE_INORDER_ALGORITHMS_HPP
+#define BOOST_TREE_INORDER_ALGORITHMS_HPP
+
+#include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
+
+#include <algorithm>
+
+namespace boost {
+namespace tree {
+
+using namespace boost_concepts;
+
+/** \addtogroup traversal */
+/*\@{*/
+
+struct inorder {
+    typedef bidirectional_traversal_tag iterator_category;
+};
+
+/**
+ * @brief    Inorder successor
+ * @param c    MultiwayCursor to be set to its inorder successor
+ * @ingroup    traversal
+ */
+template <class MultiwayCursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<MultiwayCursor>))
+    ((RootTracker<MultiwayCursor>)),
+    (void)) // return type
+successor(inorder, MultiwayCursor& c)
+{
+    if (!(++c).empty()) {
+        while (!c.to_begin().empty());
+        return;
+    }
+    
+    while (index(c) && !c.is_root())
+        c.to_parent();
+    return;
+}
+
+/**
+ * @brief    Inorder predecessor
+ * @param c    MultiwayCursor to be set to its inorder predecessor
+ */
+template <class MultiwayCursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<MultiwayCursor>))
+    ((RootTracker<MultiwayCursor>)),
+    (void)) // return type
+predecessor(inorder, MultiwayCursor& c)
+{
+    if (!c.empty()) {
+        while (!c.to_end().empty());
+        --c;
+        return;
+    }
+    
+    while (!index(c) && !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>
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<Cursor>)),
+    (void)) // return type
+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)
+{ }
+
+/*\@}*/
+
+/// 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.
+ */
+//[ lower_bound
+template <class MultiwayCursor, class T>
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<MultiwayCursor>)),
+    (MultiwayCursor)) // return type
+lower_bound(MultiwayCursor x, T const& val)
+//]
+{
+    MultiwayCursor y = x;
+    while (!x.empty()) {
+        x = std::lower_bound(x.begin(), x.end(), val);
+        if (index(x) == 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.
+ */
+//[ lower_bound_cmp
+template <class MultiwayCursor, class T, class Cmp>
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<MultiwayCursor>))
+    /*((LessThanComparable<Cmp>))*/, // Problem with balanced_tree
+    (MultiwayCursor)) // return type
+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 (index(x) == 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.
+ */
+//[ upper_bound
+template <class MultiwayCursor, class T>
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<MultiwayCursor>)),
+    (MultiwayCursor)) // return type
+upper_bound(MultiwayCursor x, T const& val)
+//]
+{
+    MultiwayCursor y = x;
+    while (!x.empty()) {
+        x = std::upper_bound(x.begin(), x.end(), val);
+        if (index(x) == 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.
+ */
+//[ upper_bound_cmp
+template <class MultiwayCursor, class T, class Cmp>
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<MultiwayCursor>))
+    ((LessThanComparable<Cmp>)),
+    (MultiwayCursor)) // return type
+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 (index(x) == 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_INORDER_ALGORITHMS_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,143 @@
+//  Copyright (c) 2006-2009, 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_algorithms.hpp
+ * Subtree postorder traversal algorithms
+ */
+
+#ifndef BOOST_TREE_POSTORDER_ALGORITHMS_HPP
+#define BOOST_TREE_POSTORDER_ALGORITHMS_HPP
+
+#include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
+
+namespace boost {
+namespace tree {
+
+using namespace boost_concepts;
+
+/** \addtogroup traversal */
+/*\@{*/
+
+struct postorder {
+    typedef bidirectional_traversal_tag iterator_category;
+};
+
+/**
+ * @brief    Postorder successor
+ * @param c    Cursor to be set to its postorder successor
+ */
+template <class Cursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<Cursor>))
+    ((RootTracker<Cursor>)),
+    (void)) // return type
+successor(postorder, Cursor& c)
+{
+    c.to_parent();
+
+    if (c.is_root())
+        return;
+
+    if (index(c)) { // Right child? Return parent.
+        --c;
+        return;
+    }
+        
+    // Left child.
+    ++c;
+    while (!c.empty()) {
+        c.to_begin();
+        if (c.empty())
+            ++c;
+    }
+    if (index(c))
+        --c;
+    return;
+}
+
+/**
+ * @brief    Postorder predecessor
+ * @param c    Cursor to be set to its postorder predecessor
+ */
+template <class Cursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<Cursor>))
+    ((RootTracker<Cursor>)),
+    (void)) // return type
+predecessor(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 (index(c))
+            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>
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<Cursor>)),
+    (void)) // return type
+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)
+{ }
+
+/*\@}*/
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_POSTORDER_ALGORITHMS_HPP

Added: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp	2009-01-02 14:06:54 EST (Fri, 02 Jan 2009)
@@ -0,0 +1,138 @@
+//  Copyright (c) 2006-2009, 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_algorithms.hpp
+ * Subtree preorder traversal algorithms
+ */
+
+#ifndef BOOST_TREE_PREORDER_ALGORITHMS_HPP
+#define BOOST_TREE_PREORDER_ALGORITHMS_HPP
+
+#include <boost/tree/root_tracking_cursor.hpp>
+#include <boost/tree/ascending_cursor.hpp>
+#include <boost/tree/cursor_concepts.hpp>
+
+#include <boost/concept/requires.hpp>
+
+namespace boost {
+namespace tree {
+
+using namespace boost_concepts;
+
+/** \addtogroup traversal */
+/*\@{*/
+
+struct preorder {
+    typedef bidirectional_traversal_tag iterator_category;
+};
+
+/**
+ * @brief    Preorder successor
+ * @param c    Cursor to be set to its preorder successor
+ */
+template <typename Cursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<Cursor>))
+    ((RootTracker<Cursor>)),
+    (void)) // return type
+successor(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() && !index(c)) {
+            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
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<Cursor>))
+    ((RootTracker<Cursor>)),
+    (void)) // return type
+predecessor(preorder, Cursor& c)
+{
+    if (!c.is_root()) {
+        c.to_parent();
+        
+        // If a left child was given, just move to its parent.
+        if (!index(c))
+            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 (index(c))
+        --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>
+BOOST_CONCEPT_REQUIRES(
+    ((Descendor<Cursor>)),
+    (void)) // return type
+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)
+{ }
+
+/*\@}*/
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_PREORDER_ALGORITHMS_HPP