|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50432 - in sandbox/SOC/2006/tree/trunk/boost/tree: . detail
From: ockham_at_[hidden]
Date: 2009-01-01 11:19:04
Author: bernhard.reiter
Date: 2009-01-01 11:19:04 EST (Thu, 01 Jan 2009)
New Revision: 50432
URL: http://svn.boost.org/trac/boost/changeset/50432
Log:
Start reorganising algorithms.
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/inorder.hpp
- copied, changed from r50431, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/inorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/boost/tree/detail/postorder.hpp
- copied, changed from r50431, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/postorder.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/preorder.hpp
- copied, changed from r50431, /sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/preorder.hpp
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/inorder.hpp | 216 +--------------------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/postorder.hpp | 128 +----------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/preorder.hpp | 123 +---------------------
4 files changed, 22 insertions(+), 447 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 2009-01-01 11:19:04 EST (Thu, 01 Jan 2009)
@@ -20,7 +20,7 @@
#include <boost/tree/detail/algorithm/postorder.hpp>
//#ifndef BOOST_RECURSIVE_ORDER_ALGORITHMS
-#include <boost/tree/detail/algorithm/iterative.hpp>
+#include <boost/tree/detail/iterative.hpp>
//#endif
namespace boost {
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/inorder.hpp (from r50431, /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/inorder.hpp 2009-01-01 11:19:04 EST (Thu, 01 Jan 2009)
@@ -5,108 +5,23 @@
// http://www.boost.org/LICENSE_1_0.txt)
/**
- * @file inorder.hpp
- * Subtree intorder traversal and search algorithms
+ * @file recursive_inorder_algorithms.hpp
+ * Recursive subtree inorder traversal and search algorithms.
*/
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
+#ifndef BOOST_TREE_DETAIL_RECURSIVE_INORDER_ALGORITHMS_HPP
+#define BOOST_TREE_DETAIL_RECURSIVE_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 {
+namespace detail {
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)
-{ }
-
-/*\@}*/
-
//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
/**
@@ -205,125 +120,8 @@
//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
-/// Search
-
-/**
- * @brief Finds the first position in a multiway subtree in which @a val
- * could be inserted without changing the ordering, using < (less
- * than) for comparisons.
- * @param x The subtree's root
- * @param val The search term
- * @return A multiway cursor pointing to the first element not less than
- * @a val, or @x if every element in the subtree is less than
- * @a val.
- */
-//[ 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 detail
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_DETAIL_ALGORITHM_INORDER_HPP
+#endif // BOOST_TREE_DETAIL_RECURSIVE_INORDER_ALGORITHMS_HPP
Added: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative.hpp 2009-01-01 11:19:04 EST (Thu, 01 Jan 2009)
@@ -0,0 +1,76 @@
+// 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/postorder.hpp (from r50431, /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/postorder.hpp 2009-01-01 11:19:04 EST (Thu, 01 Jan 2009)
@@ -5,138 +5,23 @@
// http://www.boost.org/LICENSE_1_0.txt)
/**
- * @file postorder.hpp
- * Subtree postorder traversal algorithms
+ * @file recursive_postorder_algorithms.hpp
+ * Recursice subtree postorder traversal algorithms
*/
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
+#ifndef BOOST_TREE_DETAIL_RECURSIVE_POSTORDER_ALGORITHMS_HPP
+#define BOOST_TREE_DETAIL_RECURSIVE_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 {
+namespace detail {
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)
-{ }
-
-/*\@}*/
-
//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
/**
@@ -232,7 +117,8 @@
//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+} // namespace detail
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_DETAIL_ALGORITHM_POSTORDER_HPP
+#endif // BOOST_TREE_DETAIL_RECURSIVE_POSTORDER_ALGORITHMS_HPP
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/detail/preorder.hpp (from r50431, /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/preorder.hpp 2009-01-01 11:19:04 EST (Thu, 01 Jan 2009)
@@ -5,133 +5,23 @@
// http://www.boost.org/LICENSE_1_0.txt)
/**
- * @file preorder.hpp
- * Subtree preorder traversal algorithms
+ * @file recursive_preorder_algorithms.hpp
+ * Recursive subtree preorder traversal algorithms
*/
-#ifndef BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
-#define BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
+#ifndef BOOST_TREE_DETAIL_RECURSIVE_PREORDER_ALGORITHMS_HPP
+#define BOOST_TREE_DETAIL_RECURSIVE_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 {
+namespace detail {
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)
-{ }
-
-/*\@}*/
-
//#ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
/**
@@ -228,7 +118,8 @@
//#endif //BOOST_RECURSIVE_ORDER_ALGORITHMS
+} // namespace detail
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_DETAIL_ALGORITHM_PREORDER_HPP
+#endif // BOOST_TREE_DETAIL_RECURSIVE_PREORDER_ALGORITHMS_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