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