|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-06-08 07:22:45
Author: bernhard.reiter
Date: 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
New Revision: 46229
URL: http://svn.boost.org/trac/boost/changeset/46229
Log:
Directory and file cleanup, part 1.
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/
- copied from r43517, /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
- copied, changed from r46228, /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/
- copied from r46228, /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/iterator/
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
- copied, changed from r46228, /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
- copied, changed from r46228, /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp (contents, props changed)
Text files modified:
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/inorder.hpp | 92 +----------------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/bidirectional.hpp | 9 ---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp | 101 +--------------------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp | 92 +----------------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp | 8 +-
sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/traversal.hpp | 12 ++--
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp | 2
12 files changed, 31 insertions(+), 295 deletions(-)
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:22:43 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/inorder.hpp>
+#include <boost/tree/detail/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:22:43 EDT (Sun, 08 Jun 2008)
@@ -14,7 +14,7 @@
#define BOOST_TREE_BINARY_TREE_HPP
#include <boost/tree/cursor.hpp>
-#include <boost/tree/algorithm/inorder.hpp>
+#include <boost/tree/detail/algorithm/inorder.hpp>
#include <boost/tree/detail/node/traits.hpp>
#include <boost/tree/detail/cursor/nary.hpp>
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp (from r46228, /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -11,98 +11,16 @@
// TODO: concept checks.
-#ifndef BOOST_TREE_ALGORITHM_INORDER_HPP
-#define BOOST_TREE_ALGORITHM_INORDER_HPP
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
-#include <boost/tree/inorder_iterator.hpp>
+#include <boost/tree/detail/iterator/inorder.hpp>
namespace boost {
namespace tree {
namespace inorder {
-/**
- * @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;
-}
-
-
-/// Iterators
-
template <class MultiwayCursor>
iterator<MultiwayCursor, forward_traversal_tag>
begin(MultiwayCursor c, forward_traversal_tag)
@@ -125,11 +43,11 @@
return iterator<MultiwayCursor, forward_traversal_tag>(s);
}
-#include <boost/tree/algorithm/iterator/bidirectional.hpp>
+#include <boost/tree/detail/algorithm/iterator/bidirectional.hpp>
} // namespace inorder
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_ALGORITHM_INORDER_HPP
+#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/algorithm/iterator/bidirectional.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/bidirectional.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -13,16 +13,8 @@
// NO guards, as this is context-included!
-//#ifndef BOOST_TREE_DETAIL_ITERATOR_BIDIRECTIONAL_HPP
-//#define BOOST_TREE_DETAIL_ITERATOR_BIDIRECTIONAL_HPP
-
#include <boost/tree/cursor.hpp>
-//namespace boost {
-//namespace tree {
-//
-//namespace inorder {
-
/** @file bidirectional.hpp
*
* Some definitions that are identical for all *order cursors (as we are just
@@ -106,4 +98,3 @@
return std::reverse_iterator< iterator<Cursor, Traversal> >(begin(c, t));
}
-//#endif // BOOST_TREE_DETAIL_ITERATOR_BIDIRECTIONAL_HPP
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp (from r46228, /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -11,107 +11,16 @@
// TODO: concept checks.
-#ifndef BOOST_TREE_ALGORITHM_POSTORDER_HPP
-#define BOOST_TREE_ALGORITHM_POSTORDER_HPP
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
-#include <boost/tree/postorder_iterator.hpp>
+#include <boost/tree/detail/iterator/postorder.hpp>
namespace boost {
namespace tree {
namespace postorder {
-/**
- * @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;
-}
-
-
-/// Iterators
-
template <class Cursor>
iterator<Cursor, forward_traversal_tag>
begin(Cursor c, forward_traversal_tag)
@@ -140,11 +49,11 @@
return iterator<Cursor, forward_traversal_tag>(s);
}
-#include <boost/tree/algorithm/iterator/bidirectional.hpp>
+#include <boost/tree/detail/algorithm/iterator/bidirectional.hpp>
} // namespace postorder
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_ALGORITHM_POSTORDER_HPP
+#endif // BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp (from r46228, /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -11,98 +11,16 @@
// TODO: concept checks.
-#ifndef BOOST_TREE_ALGORITHM_PREORDER_HPP
-#define BOOST_TREE_ALGORITHM_PREORDER_HPP
+#ifndef BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
+#define BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
-#include <boost/tree/preorder_iterator.hpp>
+#include <boost/tree/detail/iterator/preorder.hpp>
namespace boost {
namespace tree {
namespace preorder {
-/**
- * @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;
-}
-
-/// Iterators
-
template <class Cursor>
iterator<Cursor, forward_traversal_tag>
begin(Cursor c, forward_traversal_tag)
@@ -124,11 +42,11 @@
return iterator<Cursor, forward_traversal_tag>(s);
}
-#include <boost/tree/algorithm/iterator/bidirectional.hpp>
+#include <boost/tree/detail/algorithm/iterator/bidirectional.hpp>
} // namespace preorder
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_ALGORITHM_PREORDER_HPP
+#endif // BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,79 @@
+// Copyright (c) 2006-2008, Bernhard Reiter
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+/**
+ * @file ascending_iterator.hpp
+ * Ascending iterator wrapper around cursor.
+ */
+
+// TODO: concept checks.
+
+#ifndef BOOST_TREE_DETAIL_ITERATOR_ASCENDING_HPP
+#define BOOST_TREE_DETAIL_ITERATOR_ASCENDING_HPP
+
+#include <boost/tree/ascending.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>
+
+namespace boost {
+namespace tree {
+
+namespace ascending {
+
+template <class Cursor, class Tag = typename cursor_category<Cursor>::type>
+class iterator;
+
+template <class Cursor>
+class iterator<Cursor, bidirectional_traversal_tag>
+ : public boost::iterator_adaptor<iterator<Cursor, bidirectional_traversal_tag>
+ , Cursor
+ , boost::use_default
+ , forward_traversal_tag
+ > {
+ private:
+ struct enabler {};
+
+ public:
+ iterator()
+ : iterator::iterator_adaptor_() {}
+
+ explicit iterator(Cursor p)
+ : iterator::iterator_adaptor_(p) {}
+
+ template <class OtherCursor>
+ iterator(
+ iterator<OtherCursor> const& other
+ , typename boost::enable_if<
+ boost::is_convertible<OtherCursor,Cursor >
+ , enabler
+ >::type = enabler()
+ )
+ : iterator::iterator_adaptor_(other.base()) {}
+
+ operator Cursor()
+ {
+ return this->base();
+ }
+ private:
+ friend class boost::iterator_core_access;
+
+ void increment()
+ {
+ forward(this->base_reference());
+ }
+
+};
+
+
+} // namespace ascending
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_ITERATOR_ASCENDING_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -17,7 +17,7 @@
//#define BOOST_TREE_DETAIL_ITERATOR_BIDIRECTIONAL_HPP
-//#include <boost/tree/inorder.hpp>
+//#include <boost/tree/detail/cursor/inorder.hpp>
#include <boost/tree/cursor.hpp>
#include <boost/iterator/iterator_adaptor.hpp>
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,123 @@
+// 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_iterator.hpp
+ * Inorder iterator wrapper around cursor.
+ */
+
+// TODO: concept checks.
+
+#ifndef BOOST_TREE_DETAIL_ITERATOR_INORDER_HPP
+#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>
+
+#include <stack>
+
+
+using std::stack;
+
+namespace boost {
+namespace tree {
+
+namespace inorder {
+
+template <class MultiwayCursor,
+ class Tag = typename cursor_vertical_traversal<MultiwayCursor>::type>
+class iterator;
+
+template <class MultiwayCursor>
+class iterator<MultiwayCursor, forward_traversal_tag>
+ : public boost::iterator_facade<iterator<MultiwayCursor, forward_traversal_tag>
+ , typename MultiwayCursor::value_type
+ , bidirectional_traversal_tag
+ > {
+// private:
+// struct enabler {};
+
+ public:
+ iterator() {}
+// : iterator::iterator_adaptor_() {}
+
+ explicit iterator(stack<MultiwayCursor> s)
+ : m_s(s) {}
+// : iterator::iterator_adaptor_(p) {}
+
+// template <class OtherMultiwayCursor>
+// iterator(
+// iterator<OtherMultiwayCursor> const& other
+// , typename boost::enable_if<
+// boost::is_convertible<OtherMultiwayCursor,MultiwayCursor >
+// , enabler
+// >::type = enabler()
+// )
+// : iterator::iterator_adaptor_(other.base()) {}
+
+ operator MultiwayCursor()
+ {
+ return m_s.top();
+ }
+ private:
+ friend class boost::iterator_core_access;
+
+ stack<MultiwayCursor> m_s;
+
+ typename MultiwayCursor::value_type& dereference() const
+ {
+ return *m_s.top();
+ }
+
+ bool equal(iterator<MultiwayCursor, forward_traversal_tag> const& other) const
+ {
+ return (this->m_s == other.m_s);
+ }
+
+ void increment()
+ {
+ if (!(++m_s.top()).empty()) {
+ while (!m_s.top().begin().empty())
+ m_s.push(m_s.top().begin());
+ m_s.push(m_s.top().begin());
+ return;
+ }
+
+ while (m_s.top().parity() && !m_s.empty())
+ m_s.pop();
+ return;
+ }
+
+ void decrement()
+ {
+ if (!m_s.top().empty()) {
+ while (!m_s.top().end().empty())
+ m_s.push(m_s.top().end());
+ m_s.push(m_s.top().begin());
+ return;
+ }
+
+ while (!m_s.top().parity())
+ m_s.pop();
+ --m_s.top();
+ return;
+ }
+};
+
+#include <boost/tree/detail/iterator/bidirectional.hpp>
+
+
+} // namespace inorder
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_ITERATOR_INORDER_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,142 @@
+// 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_iterator.hpp
+ * Postorder iterator wrapper around cursor.
+ */
+
+// TODO: concept checks.
+
+#ifndef BOOST_TREE_DETAIL_ITERATOR_POSTORDER_HPP
+#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>
+
+
+namespace boost {
+namespace tree {
+
+namespace postorder {
+
+template <class Cursor,
+ class Tag = typename cursor_vertical_traversal<Cursor>::type>
+class iterator;
+
+template <class Cursor>
+class iterator<Cursor, forward_traversal_tag>
+ : public boost::iterator_facade<iterator<Cursor, forward_traversal_tag>
+ , typename Cursor::value_type
+ , bidirectional_traversal_tag
+ > {
+// private:
+// struct enabler {};
+
+ public:
+ iterator() {}
+// : iterator::iterator_adaptor_() {}
+
+ explicit iterator(stack<Cursor> s)
+ : m_s(s) {}
+// : iterator::iterator_adaptor_(p) {}
+
+// template <class OtherCursor>
+// iterator(
+// iterator<OtherCursor> const& other
+// , typename boost::enable_if<
+// boost::is_convertible<OtherCursor,Cursor >
+// , enabler
+// >::type = enabler()
+// )
+// : iterator::iterator_adaptor_(other.base()) {}
+
+ operator Cursor()
+ {
+ return m_s.top();
+ }
+ private:
+ friend class boost::iterator_core_access;
+
+ stack<Cursor> m_s;
+
+ typename Cursor::value_type& dereference() const
+ {
+ return *m_s.top();
+ }
+
+ bool equal(iterator<Cursor, forward_traversal_tag> const& other) const
+ {
+ return (this->m_s == other.m_s);
+ }
+
+ void increment()
+ {
+ m_s.pop();
+
+ if (m_s.top().parity()) { // Right child? Return parent.
+ --m_s.top();
+ return;
+ }
+
+ if (m_s.size() == 1) // Root?
+ return;
+
+ // Left child.
+ ++m_s.top();
+ while (!m_s.top().empty()) {
+ m_s.push(m_s.top().begin());
+ if (m_s.top().empty())
+ ++m_s.top();
+ }
+ if (m_s.top().parity())
+ --m_s.top();
+ return;
+ }
+
+ void decrement()
+ {
+ if (m_s.size() == 1) { // Root?
+ m_s.push(m_s.top().begin());
+ return;
+ }
+
+ if (!(++m_s.top()).empty()) { // Right
+ m_s.push(m_s.top().begin());
+ return;
+ }
+ if (!(--m_s.top()).empty()) { // Left
+ m_s.push(m_s.top().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) {
+ m_s.pop();
+ if (m_s.top().parity())
+ if (!(--m_s.top()).empty()) {
+ m_s.push(m_s.top().begin());
+ return;
+ }
+ }
+ return;
+ }
+};
+
+#include <boost/tree/detail/iterator/bidirectional.hpp>
+
+
+} // namespace postorder
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_ITERATOR_POSTORDER_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,151 @@
+// 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_iterator.hpp
+ * Preorder iterator wrapper around cursor.
+ */
+
+// TODO: concept checks.
+
+#ifndef BOOST_TREE_DETAIL_ITERATOR_PREORDER_HPP
+#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>
+
+
+namespace boost {
+namespace tree {
+
+namespace preorder {
+
+template <class Cursor,
+ class Tag = typename cursor_vertical_traversal<Cursor>::type>
+class iterator;
+
+template <class Cursor>
+class iterator<Cursor, forward_traversal_tag>
+ : public boost::iterator_facade<iterator<Cursor, forward_traversal_tag>
+ , typename Cursor::value_type
+ , bidirectional_traversal_tag
+ > {
+// private:
+// struct enabler {};
+
+ public:
+ iterator() {}
+// : iterator::iterator_adaptor_() {}
+
+ explicit iterator(stack<Cursor> s)
+ : m_s(s) {}
+// : iterator::iterator_adaptor_(p) {}
+
+// template <class OtherCursor>
+// iterator(
+// iterator<OtherCursor> const& other
+// , typename boost::enable_if<
+// boost::is_convertible<OtherCursor,Cursor >
+// , enabler
+// >::type = enabler()
+// )
+// : iterator::iterator_adaptor_(other.base()) {}
+
+ operator Cursor()
+ {
+ return m_s.top();
+ }
+ private:
+ friend class boost::iterator_core_access;
+
+ stack<Cursor> m_s;
+
+ typename Cursor::value_type& dereference() const
+ {
+ return *m_s.top();
+ }
+
+ bool equal(iterator<Cursor, forward_traversal_tag> const& other) const
+ {
+ return (this->m_s == other.m_s);
+ }
+
+ void increment()
+ {
+ // If we have a left child, go there.
+ if (!m_s.top().empty()) {
+ m_s.push(m_s.top().begin());
+ return;
+ }
+
+ // No left child. So if we have a right child, go there.
+ if (!(++m_s.top()).empty()) {
+ m_s.push(m_s.top().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 (m_s.size() == 1) // Root
+ return;
+
+ m_s.pop();
+ if (!m_s.top().parity()) {
+ if (m_s.size() == 1) // Root?
+ return;
+ if (!(++m_s.top()).empty()) {
+ m_s.push(m_s.top().begin());
+ return;
+ }
+ }
+ }
+ return;
+}
+
+ void decrement()
+ {
+ if (m_s.size() != 1) { // Not root
+ m_s.pop();
+
+ // If this is a left child, just move to its parent.
+ if (!m_s.top().parity()) {
+ m_s.pop();
+ m_s.push(m_s.top().begin());
+ return;
+ }
+
+ // So this is a right child.
+ --m_s.top();
+ }
+
+ // Same for root (=end) and right children:
+ if (!m_s.top().empty())
+ while (!m_s.top().empty())
+ if (!m_s.top().end().empty())
+ m_s.push(m_s.top().end());
+ else
+ m_s.push(m_s.top().begin());
+ return;
+ }
+};
+
+#include <boost/tree/detail/iterator/bidirectional.hpp>
+
+
+} // namespace preorder
+
+} // namespace tree
+} // namespace boost
+
+#endif // BOOST_TREE_DETAIL_ITERATOR_PREORDER_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -15,10 +15,10 @@
#ifndef BOOST_TREE_ITERATORS_HPP
#define BOOST_TREE_ITERATORS_HPP
-#include <boost/tree/ascending_iterator.hpp>
+#include <boost/tree/detail/iterator/ascending.hpp>
-#include <boost/tree/inorder_iterator.hpp>
-#include <boost/tree/preorder_iterator.hpp>
-#include <boost/tree/postorder_iterator.hpp>
+#include <boost/tree/detail/iterator/inorder.hpp>
+#include <boost/tree/detail/iterator/preorder.hpp>
+#include <boost/tree/detail/iterator/postorder.hpp>
#endif // BOOST_TREE_ITERATORS_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -17,7 +17,7 @@
#ifndef BOOST_TREE_SEARCHER_HPP
#define BOOST_TREE_SEARCHER_HPP
-#include <boost/tree/inorder_iterator.hpp>
+#include <boost/tree/detail/iterator/inorder.hpp>
#include <boost/bind.hpp>
#include <boost/multi_index/identity.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:22:43 EDT (Sun, 08 Jun 2008)
@@ -12,12 +12,12 @@
#ifndef BOOST_TREE_TRAVERSAL_HPP
#define BOOST_TREE_TRAVERSAL_HPP
-#include <boost/tree/inorder.hpp>
-#include <boost/tree/preorder.hpp>
-#include <boost/tree/postorder.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/algorithm/inorder.hpp>
-#include <boost/tree/algorithm/preorder.hpp>
-#include <boost/tree/algorithm/postorder.hpp>
+#include <boost/tree/detail/algorithm/inorder.hpp>
+#include <boost/tree/detail/algorithm/preorder.hpp>
+#include <boost/tree/detail/algorithm/postorder.hpp>
#endif // BOOST_TREE_TRAVERSAL_HPP
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -14,7 +14,7 @@
#include <boost/tree/binary_tree.hpp>
#include <boost/tree/iterator.hpp>
-#include <boost/tree/traversal.hpp>
+#include <boost/tree/algorithm.hpp>
#include <boost/test/minimal.hpp>
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp 2008-06-08 07:22:43 EDT (Sun, 08 Jun 2008)
@@ -14,7 +14,7 @@
#include <boost/tree/binary_tree.hpp>
#include <boost/tree/iterator.hpp>
-#include <boost/tree/traversal.hpp>
+#include <boost/tree/algorithm.hpp>
#include <boost/test/minimal.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