|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-06-08 07:44:36
Author: bernhard.reiter
Date: 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
New Revision: 46232
URL: http://svn.boost.org/trac/boost/changeset/46232
Log:
Directory and file cleanup, part 4. How will I get rid of that damn /boost/tree/algorithm directory?
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/inorder.hpp
- copied, changed from r46229, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/postorder.hpp
- copied, changed from r46229, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/preorder.hpp
- copied, changed from r46229, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
Removed:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 9 ++++++++-
sandbox/SOC/2006/tree/trunk/boost/tree/balancers/unbalanced.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/bidirectional.hpp | 2 --
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/inorder.hpp | 7 ++++---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/postorder.hpp | 7 ++++---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/preorder.hpp | 7 ++++---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp | 3 ---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp | 2 --
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp | 2 --
sandbox/SOC/2006/tree/trunk/boost/tree/traversal.hpp | 12 ++++++------
sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp | 1 -
12 files changed, 28 insertions(+), 28 deletions(-)
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 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -14,7 +14,14 @@
#include <boost/tree/search.hpp>
-#include <boost/tree/traversal.hpp>
+
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/preorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
+
+#include <boost/tree/detail/algorithm/iterator/inorder.hpp>
+#include <boost/tree/detail/algorithm/iterator/preorder.hpp>
+#include <boost/tree/detail/algorithm/iterator/postorder.hpp>
#include <algorithm>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balancers/unbalanced.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balancers/unbalanced.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balancers/unbalanced.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -8,7 +8,7 @@
#define BOOST_TREE_BALANCERS_UNBALANCED_HPP
#include <boost/tree/detail/cursor/nary.hpp>
-#include <boost/tree/detail/cursor/inorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
namespace boost {
namespace tree {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -14,7 +14,7 @@
#define BOOST_TREE_BINARY_TREE_HPP
#include <boost/tree/cursor.hpp>
-#include <boost/tree/detail/algorithm/inorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
#include <boost/tree/detail/node/traits.hpp>
#include <boost/tree/detail/cursor/nary.hpp>
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,200 @@
+// 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
+ * Non-modifying hierarchy inorder range algorithms
+ */
+
+// TODO: concept checks.
+
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
+
+#include <boost/tree/detail/iterator/inorder.hpp>
+
+namespace boost {
+namespace tree {
+
+namespace inorder {
+
+/** \addtogroup traversal */
+/*\@{*/
+
+/**
+ * @brief Inorder successor
+ * @param c MultiwayCursor to be set to its inorder successor
+ * @ingroup traversal
+ */
+template <class MultiwayCursor>
+inline void forward(MultiwayCursor& c)
+{
+ if (!(++c).empty()) {
+ while (!c.to_begin().empty());
+ return;
+ }
+
+ while (c.parity()) // Doesn't work with subtrees whose root's parity != 0
+ c.to_parent();
+ return;
+}
+
+/**
+ * @brief Inorder successor
+ * @param c A cursor
+ * @return Inorder successor of @a c
+ * @ingroup traversal
+ */
+template <class MultiwayCursor>
+inline MultiwayCursor next(MultiwayCursor c)
+{
+ forward(c);
+ return c;
+}
+
+/**
+ * @brief Inorder predecessor
+ * @param c MultiwayCursor to be set to its inorder predecessor
+ */
+template <class MultiwayCursor>
+inline void back(MultiwayCursor& c)
+{
+ if (!c.empty()) {
+ while (!c.to_end().empty());
+ --c;
+ return;
+ }
+ while (!c.parity())
+ c.to_parent();
+ --c;
+ return;
+}
+
+/**
+ * @brief Inorder predecessor
+ * @param c MultiwayCursor
+ * @return Inorder predecessor of @a c
+ */
+template <class MultiwayCursor>
+inline MultiwayCursor prior(MultiwayCursor c)
+{
+ back(c);
+ return c;
+}
+
+/**
+ * @brief First element of a Multiway subtree in inorder traversal
+ * @param c A MultiwayCursor
+ * @return Cursor to the first element of @a c in inorder traversal
+ */
+template <class MultiwayCursor>
+MultiwayCursor first(MultiwayCursor c)
+{
+ while (!c.empty())
+ c.to_begin();
+ return c;
+}
+
+/**
+ * @brief One position past the last element of a Multiway subtree in
+ * inorder traversal
+ * @param c A MultiwayCursor
+ * @return Cursor one position past the last element of @a c in inorder
+ * traversal
+ */
+template <class MultiwayCursor>
+MultiwayCursor last(MultiwayCursor c)
+{
+ return c;
+}
+
+/*\@}*/
+
+/**
+ * @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(MultiwayCursor s, Op& f)
+{
+ if (!s.empty())
+ for_each_recursive(s.begin(), f);
+ f(*s);
+ if (!(++s).empty())
+ for_each_recursive(s.begin(), 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.
+ */
+template <class MultiwayCursor, class Op>
+Op for_each(MultiwayCursor s, Op f)
+{
+ if (!s.empty())
+ for_each_recursive(s.begin(), f);
+ f(*s);
+ if (!(++s).empty())
+ for_each_recursive(s.begin(), 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 (InCursor s, OutCursor t)
+{
+ if (!s.empty())
+ copy(s.begin(), t.begin());
+ *t = *s;
+ if (!(++s).empty())
+ copy(s.begin(), (++t).begin());
+ 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 (InCursor s, OutCursor t, Op op)
+{
+ if (!s.empty())
+ transform(s.begin(), t.begin(), op);
+ *t = op(*s);
+ if (!(++s).empty())
+ transform(s.begin(), (++t).begin(), op);
+ return t;
+}
+
+} // namespace inorder
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_ALGORITHM_CURSOR_INORDER_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,239 @@
+// 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
+ * Non-modifying hierarchy postorder range algorithms
+ */
+
+// TODO: concept checks.
+
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
+
+#include <boost/tree/detail/iterator/postorder.hpp>
+
+namespace boost {
+namespace tree {
+
+namespace postorder {
+
+/** \addtogroup traversal */
+/*\@{*/
+
+/**
+ * @brief Postorder successor
+ * @param c Cursor to be set to its postorder successor
+ */
+template <class Cursor>
+inline void forward(Cursor& c)
+{
+ c.to_parent();
+
+ if (c.parity()) { // Right child? Return parent.
+ --c;
+ return;
+ }
+
+ if (c.parent().begin() != c) // Root?
+ return;
+
+ // Left child.
+ ++c;
+ while (!c.empty()) {
+ c.to_begin();
+ if (c.empty())
+ ++c;
+ }
+ if (c.parity())
+ --c;
+ return;
+}
+
+/**
+ * @brief Postorder successor
+ * @param c A cursor
+ * @return Postorder successor of @a c
+ */
+template <class Cursor>
+inline Cursor next(Cursor c)
+{
+ forward(c);
+ return c;
+}
+
+/**
+ * @brief Postorder predecessor
+ * @param c Cursor to be set to its postorder predecessor
+ */
+template <class Cursor>
+inline void back(Cursor& c)
+{
+ if (!c.parity() && (c.parent().begin() != c)) { // 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 (true) { // revisit
+ c.to_parent();
+ if (c.parity())
+ if (!(--c).empty()) {
+ c.to_begin();
+ return;
+ }
+ }
+ return;
+}
+
+/**
+ * @brief Postorder predecessor
+ * @param c A cursor
+ * @return Postorder predecessor of @a c
+ */
+template <class Cursor>
+inline Cursor prior(Cursor c)
+{
+ back(c);
+ return c;
+}
+
+/**
+ * @brief First element of a subtree in postorder traversal
+ * @param c A cursor
+ * @return Cursor to the first element of @a c in postorder traversal
+ */
+template <class Cursor>
+Cursor first(Cursor c)
+{
+ while (true)
+ if (!c.empty())
+ c.to_begin();
+ else if (!(++c).empty())
+ c.to_begin();
+ else
+ return --c;
+}
+
+/**
+ * @brief One position past the last element of a subtree in postorder
+ * traversal
+ * @param c A cursor
+ * @return Cursor one position past the last element of @a c in
+ * postorder traversal
+ */
+template <class Cursor>
+Cursor last(Cursor c)
+{
+ return c;
+}
+
+/*\@}*/
+
+/**
+ * @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(Cursor s, Op& f)
+{
+ if (!s.empty())
+ for_each_recursive(s.begin(), f);
+ Cursor subtree = s;
+ if (!(++s).empty())
+ for_each_recursive(s.begin(), f);
+ f(*subtree);
+}
+
+/**
+ * @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(Cursor s, Op f)
+{
+ if (!s.empty())
+ for_each_recursive(s.begin(), f);
+ Cursor subtree = s;
+ if (!(++s).empty())
+ for_each_recursive(s.begin(), f);
+ f(*subtree);
+ 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 (InCursor s, OutCursor t)
+{
+ InCursor insubtree = s;
+ OutCursor outsubtree = t;
+ if (!s.empty())
+ copy(s.begin(), t.begin());
+ if (!(++s).empty()) {
+ copy(s.begin(), (++t).begin());
+ }
+ *outsubtree = *insubtree;
+ return outsubtree;
+}
+
+/**
+ * @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 (InCursor s, OutCursor t, Op op)
+{
+ InCursor insubtree = s;
+ OutCursor outsubtree = t;
+ if (!s.empty())
+ transform(s.begin(), t.begin(), op);
+ if (!(++s).empty()) {
+ transform(s.begin(), (++t).begin(), op);
+ }
+ *outsubtree = op(*insubtree);
+ return outsubtree;
+}
+
+} // namespace postorder
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_ALGORITHM_CURSOR_POSTORDER_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,234 @@
+// 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
+ * Non-modifying hierarchy preorder range algorithms
+ */
+
+// TODO: concept checks.
+
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
+
+#include <boost/tree/detail/iterator/preorder.hpp>
+
+namespace boost {
+namespace tree {
+
+namespace preorder {
+
+/** \addtogroup traversal */
+/*\@{*/
+
+/**
+ * @brief Preorder successor
+ * @param c Cursor to be set to its preorder successor
+ */
+template <class Cursor>
+inline void forward(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 (true) { // Doesn't work with subtrees!
+ if (!c.parity() && (c != c.parent().begin())) // Root
+ return;
+
+ c.to_parent();
+ if (!c.parity()) {
+ if (c != c.parent().begin()) // Root?
+ return;
+ if (!(++c).empty()) {
+ c.to_begin();
+ return;
+ }
+ }
+ }
+ return;
+}
+
+/**
+ * @brief Preorder successor
+ * @param c A cursor
+ * @return Preorder successor of @a c
+ */
+template <class Cursor>
+inline Cursor next(Cursor c)
+{
+ forward(c);
+ return c;
+}
+
+/**
+ * @brief Preorder predecessor
+ * @param c Cursor to be set to its preorder predecessor
+ */
+template <class Cursor>
+inline void back(Cursor& c)
+{
+ if (!(!c.parity() && (c != c.parent().begin()))) { // Not root
+ c.to_parent();
+
+ // If this is a left child, just move to its parent.
+ if (!c.parity()) {
+ c.to_parent();
+ c.to_begin();
+ return;
+ }
+
+ // So this is a right child.
+ --c;
+ }
+
+ // Same for root (=end) and right children:
+ if (!c.empty())
+ while (!c.empty())
+ if (!c.end().empty())
+ c.to_end();
+ else
+ c.to_begin();
+ return;
+}
+
+/**
+ * @brief Preorder predecessor
+ * @param c A cursor
+ * @return Preorder predecessor of @a c
+ */
+template <class Cursor>
+inline Cursor prior(Cursor c)
+{
+ back(c);
+ return c;
+}
+
+/**
+ * @brief First element of a subtree in preorder traversal
+ * @param c A cursor
+ * @return Cursor to the first element of @a c in preorder traversal
+ */
+template <class Cursor>
+Cursor first(Cursor c)
+{
+ return c.begin();
+}
+
+/**
+ * @brief One position past the last element of a subtree in preorder
+ * traversal
+ * @param c A cursor
+ * @return Cursor one position past the last element of @a c in preorder
+ * traversal
+ */
+template <class Cursor>
+Cursor last(Cursor c)
+{
+ return c;
+}
+
+/*\@}*/
+
+/**
+ * @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(Cursor s, Op& f)
+{
+ f(*s);
+ if (!s.empty())
+ for_each_recursive(s.begin(), f);
+ if (!(++s).empty())
+ for_each_recursive(s.begin(), 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.
+ */
+template <class Cursor, class Op>
+Op for_each(Cursor s, Op f)
+{
+ f(*s);
+ if (!s.empty())
+ for_each_recursive(s.begin(), f);
+ if (!(++s).empty())
+ for_each_recursive(s.begin(), f);
+ return f;
+}
+
+/**
+ * @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.
+ */
+// TODO: Should work with root() instead of root().begin() (same for in- and postorder, )
+// plus a couple of other algorithms
+template <class InCursor, class OutCursor>
+OutCursor copy (InCursor s, OutCursor t)
+{
+ *t = *s;
+ if (!s.empty())
+ copy(s.begin(), t.begin());
+ if (!(++s).empty())
+ copy(s.begin(), (++t).begin());
+ 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 (InCursor s, OutCursor t, Op op)
+{
+ *t = op(*s);
+ if (!s.empty())
+ transform(s.begin(), t.begin(), op);
+ if (!(++s).empty())
+ transform(s.begin(), (++t).begin(), op);
+ return t;
+}
+
+} // namespace preorder
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_ALGORITHM_CURSOR_PREORDER_HPP
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,53 +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
- * Non-modifying hierarchy inorder range algorithms
- */
-
-// TODO: concept checks.
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
-
-#include <boost/tree/detail/iterator/inorder.hpp>
-
-namespace boost {
-namespace tree {
-
-namespace inorder {
-
-template <class MultiwayCursor>
-iterator<MultiwayCursor, forward_traversal_tag>
-begin(MultiwayCursor c, forward_traversal_tag)
-{
- std::stack<MultiwayCursor> s;
-
- s.push(c);
- while (!s.top().empty())
- s.push(s.top().begin());
- return iterator<MultiwayCursor, forward_traversal_tag>(s);
-}
-
-template <class MultiwayCursor>
-iterator<MultiwayCursor, forward_traversal_tag>
-end(MultiwayCursor c, forward_traversal_tag)
-{
- std::stack<MultiwayCursor> s;
-
- s.push(c);
- return iterator<MultiwayCursor, forward_traversal_tag>(s);
-}
-
-#include <boost/tree/detail/algorithm/iterator/bidirectional.hpp>
-
-} // namespace inorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/bidirectional.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/bidirectional.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/bidirectional.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -13,8 +13,6 @@
// NO guards, as this is context-included!
-#include <boost/tree/cursor.hpp>
-
/** @file bidirectional.hpp
*
* Some definitions that are identical for all *order cursors (as we are just
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/inorder.hpp (from r46229, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/inorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -11,10 +11,11 @@
// TODO: concept checks.
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_INORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_INORDER_HPP
#include <boost/tree/detail/iterator/inorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
namespace boost {
namespace tree {
@@ -50,4 +51,4 @@
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
+#endif // BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_INORDER_HPP
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/postorder.hpp (from r46229, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/postorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -11,10 +11,11 @@
// TODO: concept checks.
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_POSTORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_POSTORDER_HPP
#include <boost/tree/detail/iterator/postorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/postorder.hpp>
namespace boost {
namespace tree {
@@ -56,4 +57,4 @@
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
+#endif // BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_POSTORDER_HPP
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/preorder.hpp (from r46229, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/preorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -11,10 +11,11 @@
// TODO: concept checks.
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_PREORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_PREORDER_HPP
#include <boost/tree/detail/iterator/preorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/preorder.hpp>
namespace boost {
namespace tree {
@@ -49,4 +50,4 @@
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
+#endif // BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_PREORDER_HPP
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,59 +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
- * Non-modifying hierarchy postorder range algorithms
- */
-
-// TODO: concept checks.
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
-
-#include <boost/tree/detail/iterator/postorder.hpp>
-
-namespace boost {
-namespace tree {
-
-namespace postorder {
-
-template <class Cursor>
-iterator<Cursor, forward_traversal_tag>
-begin(Cursor c, forward_traversal_tag)
-{
- std::stack<Cursor> s;
-
- s.push(c);
- while (true)
- if (!s.top().empty())
- s.push(s.top().begin());
- else if (!(++s.top()).empty())
- s.push(s.top().begin());
- else {
- --s.top();
- return iterator<Cursor, forward_traversal_tag>(s);
- }
-}
-
-template <class Cursor>
-iterator<Cursor, forward_traversal_tag>
-end(Cursor c, forward_traversal_tag)
-{
- std::stack<Cursor> s;
-
- s.push(c);
- return iterator<Cursor, forward_traversal_tag>(s);
-}
-
-#include <boost/tree/detail/algorithm/iterator/bidirectional.hpp>
-
-} // namespace postorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
+++ (empty file)
@@ -1,52 +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
- * Non-modifying hierarchy preorder range algorithms
- */
-
-// TODO: concept checks.
-
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
-
-#include <boost/tree/detail/iterator/preorder.hpp>
-
-namespace boost {
-namespace tree {
-
-namespace preorder {
-
-template <class Cursor>
-iterator<Cursor, forward_traversal_tag>
-begin(Cursor c, forward_traversal_tag)
-{
- std::stack<Cursor> s;
-
- s.push(c);
- s.push(c.begin());
- return iterator<Cursor, forward_traversal_tag>(s);
-}
-
-template <class Cursor>
-iterator<Cursor, forward_traversal_tag>
-end(Cursor c, forward_traversal_tag)
-{
- std::stack<Cursor> s;
-
- s.push(c);
- return iterator<Cursor, forward_traversal_tag>(s);
-}
-
-#include <boost/tree/detail/algorithm/iterator/bidirectional.hpp>
-
-} // namespace preorder
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -15,9 +15,6 @@
#define BOOST_TREE_DETAIL_ITERATOR_INORDER_HPP
-#include <boost/tree/detail/cursor/inorder.hpp>
-#include <boost/tree/cursor.hpp>
-
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -15,8 +15,6 @@
#define BOOST_TREE_DETAIL_ITERATOR_POSTORDER_HPP
-#include <boost/tree/detail/cursor/inorder.hpp>
-
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -15,8 +15,6 @@
#define BOOST_TREE_DETAIL_ITERATOR_PREORDER_HPP
-#include <boost/tree/detail/cursor/preorder.hpp>
-
#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/traversal.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/traversal.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/traversal.hpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -12,12 +12,12 @@
#ifndef BOOST_TREE_TRAVERSAL_HPP
#define BOOST_TREE_TRAVERSAL_HPP
-#include <boost/tree/detail/cursor/inorder.hpp>
-#include <boost/tree/detail/cursor/preorder.hpp>
-#include <boost/tree/detail/cursor/inorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/preorder.hpp>
+#include <boost/tree/detail/algorithm/cursor/inorder.hpp>
-#include <boost/tree/detail/algorithm/inorder.hpp>
-#include <boost/tree/detail/algorithm/preorder.hpp>
-#include <boost/tree/detail/algorithm/postorder.hpp>
+#include <boost/tree/detail/algorithm/iterator/inorder.hpp>
+#include <boost/tree/detail/algorithm/iterator/preorder.hpp>
+#include <boost/tree/detail/algorithm/iterator/postorder.hpp>
#endif // BOOST_TREE_TRAVERSAL_HPP
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp 2008-06-08 07:44:35 EDT (Sun, 08 Jun 2008)
@@ -4,7 +4,6 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-//#include <boost/test/unit_test.hpp>
#include <boost/test/minimal.hpp>
#include <boost/tree/balanced_tree.hpp>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk