|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r49044 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/algorithm boost/tree/detail/algorithm/cursor boost/tree/detail/cursor boost/tree/detail/iterator libs/tree/test
From: ockham_at_[hidden]
Date: 2008-09-29 17:33:56
Author: bernhard.reiter
Date: 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
New Revision: 49044
URL: http://svn.boost.org/trac/boost/changeset/49044
Log:
Some ascending_cursor related cleanup.
Removed:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/iterator.hpp
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 10 ++++
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 20 +++++-----
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp | 21 +---------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/iterator.hpp | 79 ++++++++++++++++++++++++++++++++++-----
sandbox/SOC/2006/tree/trunk/boost/tree/searcher.hpp | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp | 4 +-
11 files changed, 102 insertions(+), 50 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -15,8 +15,16 @@
General:
+* Redo testing. Right now, it's just chaotic.
+* Fix recursive algorithms for use with forest.
+* Implement a real output cursor (if possible) and use preorder::copy to build a new tree.
+ Then, do some performance measurements comparing
+ * Different *orders;
+ * BOOST_RECURSIVE_ORDER_ALGORITHMS on and off;
+ * cursor and iterator based algorithms (from Boost.Tree and the STL, respectively)
+ Do these measurements also with algorithms other than copy.
* Test cursor adaptors wrapped around output cursors!
-* Add tests for *order::copy involving a seond tree cursor (not just a cursor adaptor).
+* Add tests for *order::copy involving a second tree cursor (not just a cursor adaptor).
* Think of a couple good examples (draw inspiration eg from Wikipedia: Tree traversal
or CRLS) and include them in the docs. Maybe move some files from libs/test to
example.
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 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -17,7 +17,7 @@
#include <boost/tree/cursor_facade.hpp>
#include <boost/tree/root_tracking_cursor.hpp>
-#include <boost/tree/detail/iterator/ascending.hpp>
+#include <boost/tree/detail/algorithm/cursor/ascending.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
@@ -34,9 +34,9 @@
class ascending_cursor;
template <class Cursor>
-typename ascending::iterator< ascending_cursor<Cursor> >::difference_type
-distance(ascending::iterator< ascending_cursor<Cursor> > iter1
- , ascending::iterator< ascending_cursor<Cursor> > iter2);
+typename iterator< ascending, ascending_cursor<Cursor> >::difference_type
+distance(iterator< ascending, ascending_cursor<Cursor> > iter1
+ , iterator< ascending, ascending_cursor<Cursor> > iter2);
template <class DescendingCursor>
class ascending_cursor
@@ -111,10 +111,10 @@
friend class root_tracking_cursor<self_type>;
// friend
-// typename ascending::iterator<self_type>::difference_type
+// typename iterator<ascending, self_type>::difference_type
// boost::tree::distance<>(
-// boost::tree::ascending::iterator<self_type>
-// , boost::tree::ascending::iterator<self_type>);
+// boost::tree::iterator<ascending, self_type>
+// , boost::tree::iterator<ascending, self_type>);
std::stack<DescendingCursor> m_s; // pimpl?
@@ -195,9 +195,9 @@
/// Specialization
template <class Cursor>
-typename ascending::iterator< ascending_cursor<Cursor> >::difference_type
-distance(ascending::iterator< ascending_cursor<Cursor> > iter1
- , ascending::iterator< ascending_cursor<Cursor> > iter2)
+typename iterator< ascending, ascending_cursor<Cursor> >::difference_type
+distance(iterator< ascending, ascending_cursor<Cursor> > iter1
+ , iterator< ascending, ascending_cursor<Cursor> > iter2)
{
return ascending_cursor<Cursor>(iter2).m_s.size()
- ascending_cursor<Cursor>(iter1).m_s.size();
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/ascending.hpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -19,40 +19,25 @@
namespace boost {
namespace tree {
-namespace ascending {
-
/** \addtogroup traversal */
/*\@{*/
+struct ascending {};
+
/**
* @brief Ascending successor
* @param c MultiwayCursor to be set to its ascending successor
* @ingroup traversal
*/
template <class MultiwayCursor>
-inline void forward(MultiwayCursor& c)
+inline void forward(ascending, MultiwayCursor& c)
{
c.to_parent();
return;
}
-/**
- * @brief Ascending successor
- * @param c A cursor
- * @return Ascending successor of @a c
- * @ingroup traversal
- */
-template <class MultiwayCursor>
-inline MultiwayCursor next(MultiwayCursor c)
-{
- forward(c);
- return c;
-}
-
/*\@}*/
-} // namespace ascending
-
} // namespace tree
} // namespace boost
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -20,11 +20,11 @@
namespace boost {
namespace tree {
-struct inorder {};
-
/** \addtogroup traversal */
/*\@{*/
+struct inorder {};
+
/**
* @brief Inorder successor
* @param c MultiwayCursor to be set to its inorder successor
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -18,11 +18,11 @@
namespace boost {
namespace tree {
-struct postorder {};
-
/** \addtogroup traversal */
/*\@{*/
+struct postorder {};
+
/**
* @brief Postorder successor
* @param c Cursor to be set to its postorder successor
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -20,11 +20,11 @@
namespace boost {
namespace tree {
-struct preorder {};
-
/** \addtogroup traversal */
/*\@{*/
+struct preorder {};
+
/**
* @brief Preorder successor
* @param c Cursor to be set to its preorder successor
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator.hpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -14,7 +14,7 @@
#ifndef BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_HPP
#define BOOST_TREE_DETAIL_ALGORITHM_ITERATOR_HPP
-#include <boost/tree/detail/iterator/iterator.hpp>
+#include <boost/tree/iterator.hpp>
#include <boost/tree/detail/algorithm/cursor.hpp>
namespace boost {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -15,7 +15,7 @@
#include <boost/tree/cursor_facade.hpp>
#include <boost/tree/detail/node/nary.hpp>
-#include <boost/tree/detail/iterator/iterator.hpp>
+//#include <boost/tree/iterator.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/ascending.hpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
+++ (empty file)
@@ -1,79 +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 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/detail/algorithm/cursor/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
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/iterator.hpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
+++ (empty file)
@@ -1,81 +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 iterator.hpp
- *
- * Some definitions 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_ITERATOR_ITERATOR_HPP
-#define BOOST_TREE_DETAIL_ITERATOR_ITERATOR_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 {
-
-/**
- * @brief Traversal order iterator adaptor
- *
- * Only works with ascending cursors.
- */
-template <class Order, class Cursor>
-class iterator
- : public boost::iterator_adaptor<iterator<Order, Cursor>
- , Cursor
- , boost::use_default
- , bidirectional_traversal_tag
- > {
- private:
- struct enabler {};
-
- public:
- iterator()
- : iterator::iterator_adaptor_() {}
-
- explicit iterator(Cursor p)
- : iterator::iterator_adaptor_(p) {}
-
- template <class OtherCursor>
- iterator(
- iterator<Order, 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(Order(), this->base_reference());
- //BOOST_ASSERT(!this->base_reference().parity() || this->base_reference().is_root());
- }
-
- void decrement()
- {
- back(Order(), this->base_reference());
- //BOOST_ASSERT(!this->base_reference().parity() || this->base_reference().is_root());
- }
-};
-
-} // namespace tree
-} // namespace boost
-
-#endif //BOOST_TREE_DETAIL_ITERATOR_ITERATOR_HPP
\ No newline at end of file
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-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -4,19 +4,78 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-/**
- * @file iterators.hpp
- * Iterator wrappers around cursors using the provided
- * traversal methods for:
- * Pre-, in- and postorder; ascending traversal.
+/** @file iterator.hpp
+ *
+ * Some definitions 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_ITERATOR_HPP
+#define BOOST_TREE_ITERATOR_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>
-#ifndef BOOST_TREE_ITERATORS_HPP
-#define BOOST_TREE_ITERATORS_HPP
+namespace boost {
+namespace tree {
-#include <boost/tree/detail/iterator/ascending.hpp>
+/**
+ * @brief Traversal order iterator adaptor
+ *
+ * Only works with ascending cursors.
+ */
+template <class Order, class Cursor>
+class iterator
+ : public boost::iterator_adaptor<iterator<Order, Cursor>
+ , Cursor
+ , boost::use_default
+ , bidirectional_traversal_tag
+ > {
+ private:
+ struct enabler {};
+
+ public:
+ iterator()
+ : iterator::iterator_adaptor_() {}
+
+ explicit iterator(Cursor p)
+ : iterator::iterator_adaptor_(p) {}
+
+ template <class OtherCursor>
+ iterator(
+ iterator<Order, 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(Order(), this->base_reference());
+ //BOOST_ASSERT(!this->base_reference().parity() || this->base_reference().is_root());
+ }
+
+ void decrement()
+ {
+ back(Order(), this->base_reference());
+ //BOOST_ASSERT(!this->base_reference().parity() || this->base_reference().is_root());
+ }
+};
-#include <boost/tree/detail/iterator/iterator.hpp>
+} // namespace tree
+} // namespace boost
-#endif // BOOST_TREE_ITERATORS_HPP
+#endif //BOOST_TREE_ITERATOR_HPP
\ No newline at end of file
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-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -17,7 +17,7 @@
#ifndef BOOST_TREE_SEARCHER_HPP
#define BOOST_TREE_SEARCHER_HPP
-#include <boost/tree/detail/iterator/iterator.hpp>
+#include <boost/tree/iterator.hpp>
#include <boost/bind.hpp>
#include <boost/multi_index/identity.hpp>
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp 2008-09-29 17:33:55 EDT (Mon, 29 Sep 2008)
@@ -205,11 +205,11 @@
//Ascending iterator.
binary_tree<int>::cursor c = test_tree.root();
- boost::tree::ascending::iterator<binary_tree<int>::cursor> ai_root(c);
+ boost::tree::iterator<ascending, binary_tree<int>::cursor> ai_root(c);
c = c.begin().end().begin().begin();
BOOST_CHECK(*c == 4);
- boost::tree::ascending::iterator<binary_tree<int>::cursor> ais(c);
+ boost::tree::iterator<ascending, binary_tree<int>::cursor> ais(c);
test_traversal_from_leaf4(ais, ai_root);
//Now the advanced stuff
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