From: ockham_at_[hidden]
Date: 2008-07-06 10:23:47
Author: bernhard.reiter
Date: 2008-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
New Revision: 47133
URL: http://svn.boost.org/trac/boost/changeset/47133
Log:
Introducing root_tracking_cursor.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 21 ++--------
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 75 +++++++++++++++++++++++++++++++++++++
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 20 ----------
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp | 80 ++++++++++++++++++++-------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 22 -----------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp | 1
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp | 1
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp | 1
sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp | 31 ++++++++++++---
10 files changed, 145 insertions(+), 109 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -19,6 +19,11 @@
(insert()/insert_above()), trees with values only at the leaves (makes sense in combination
with "upwards" insertion"), etc.
* === The is_root problem() and its solution ===
+ Get rid of checks for/assignments to root in pre/post/inorder algorithms,
+ as they are otherwise limited to "whole" trees and cannot be applied to subtrees.
+ In order to work for subtrees, it's probable that we need at least an int to store
+ the current depth.
+ Solution:
Introduce a root tracking cursor concept providing c.is_root(). *order::forward(), back(),
next() and prior() functions as well as *order::iterators then require this concept.
Write a root_tracking_cursor adaptor that does exactly that, with suitable specializations
@@ -26,22 +31,6 @@
(Why? Because any root_tracker object would have to be
passed along with a cursor, plus in- or decremented when going down or up in the hierarchy,
resp. This kind of naturally suggests some kind of encapsulation/adaptation.)
- (Earlier thoughts:)
- Get rid of checks for/assignments to root in pre/post/inorder algorithms,
- as they are otherwise limited to "whole" trees and cannot be applied to subtrees.
- In order to work for subtrees, it's probable that we need at least an int to store
- the current depth. (Which, in turn, would make the free-standing forward/back/next/prior
- algorithms etc. more or less useless without that piece of extra information and would
- only leave us with the iterators to store it.)
- -> This is going to be done by the RootTracker object, which I personally hate,
- but I don't see much of a choice for iterative traversal of subtrees other than that
- (and haven't found any on the Web, either).
- Our options, in more detail:
- * Saving a copy of root, obviously. (Only comparison, no later calculation of depth involved)
- * Iterators based on ascending cursor shouldn't check for size==1, but for size==root_size,
- where root_size is the size of the stack with all cursors up to the root cursor
- are pushed. (Comparison, no calculation)
- * Some color map approach? (Cf BGL, Knuth?)
* Do we want/need an O(1) inorder_begin() for binary_tree?
Does Gnu's rb_tree (used in std::map) have one?
* Is it really a good idea to use InCursor::size_type for size(Cursor)?
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-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -5,7 +5,7 @@
// http://www.boost.org/LICENSE_1_0.txt)
/**
- * @file ascending.hpp
+ * @file ascending_cursor.hpp
* Ascending cursor adaptor implementation
*/
@@ -15,6 +15,8 @@
#include <boost/tree/cursor.hpp>
#include <boost/tree/cursor_facade.hpp>
+#include <boost/tree/root_tracking_cursor.hpp>
+
#include <boost/tree/detail/iterator/ascending.hpp>
#include <boost/mpl/eval_if.hpp>
@@ -106,6 +108,8 @@
friend class boost::iterator_core_access;
friend class boost::tree::cursor_core_access;
+ friend class root_tracking_cursor<self_type>;
+
// friend
// typename ascending::iterator<self_type>::difference_type
// boost::tree::distance<>(
@@ -205,6 +209,75 @@
- ascending_cursor<Cursor>(iter1).m_s.size();
}
+template <class Cursor>
+class root_tracking_cursor< ascending_cursor<Cursor> >
+: public cursor_adaptor<root_tracking_cursor< ascending_cursor<Cursor> >
+ , ascending_cursor<Cursor>
+ , boost::use_default
+ , typename cursor_horizontal_traversal<
+ ascending_cursor<Cursor> >::type
+ , bidirectional_traversal_tag
+ > {
+ private:
+ struct enabler {};
+ typedef root_tracking_cursor< ascending_cursor<Cursor> > self_type;
+ public:
+ typedef typename ascending_cursor<Cursor>::value_type value_type;
+
+ // Container-specific:
+ typedef typename ascending_cursor<Cursor>::size_type size_type;
+
+ // Cursor-specific
+ typedef root_tracking_cursor< ascending_cursor<Cursor> > cursor;
+ typedef root_tracking_cursor<
+ typename ascending_cursor<Cursor>::const_cursor > const_cursor;
+
+ // Container-specific:
+ typedef cursor iterator;
+ typedef const_cursor const_iterator;
+
+ template <class OtherCursor>
+ struct rebind {
+ typedef root_tracking_cursor< ascending_cursor<OtherCursor> > other;
+ };
+
+ root_tracking_cursor()
+ : root_tracking_cursor::cursor_adaptor_(), m_root_depth(1) {}
+
+ explicit root_tracking_cursor(ascending_cursor<Cursor> c)
+ : root_tracking_cursor::cursor_adaptor_(c), m_root_depth(c.m_s.size()) {}
+
+ template <class OtherCursor>
+ root_tracking_cursor(
+ root_tracking_cursor< ascending_cursor<OtherCursor> > const& other
+ , typename boost::enable_if<
+ boost::is_convertible<ascending_cursor<OtherCursor>*
+ , ascending_cursor<Cursor>*>
+ , enabler
+ >::type = enabler()
+ )
+ : root_tracking_cursor::cursor_adaptor_(other.base())
+ , m_root_depth(other.base().m_s.size()) {}
+
+ private:
+
+ std::size_t m_root_depth;
+
+ friend class boost::iterator_core_access;
+ friend class boost::tree::cursor_core_access;
+
+// bool equal(cursor const& other) const
+// {
+// }
+
+public:
+ bool is_root() const
+ {
+ return this->base().m_s.size() == m_root_depth;
+ }
+};
+
+
} // namespace tree
} // namespace boost
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-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -557,26 +557,6 @@
x.swap(y);
}
-template <class Cursor>
-class binary_tree_root_tracker {
-
- public:
- binary_tree_root_tracker() {}
- binary_tree_root_tracker& operator++()
- {
- return *this;
- }
- binary_tree_root_tracker& operator--()
- {
- return *this;
- }
-
- bool is_root(Cursor c)
- {
- return (!c.parity() && (c != c.parent().begin()));
- }
-};
-
/**
* @brief Binary tree equality comparison.
* @param x A %binary_tree.
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp 2008-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -18,6 +18,8 @@
#include <boost/tree/cursor_facade.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+
#include <boost/type_traits/integral_constant.hpp>
#include <boost/type_traits/is_same.hpp>
@@ -139,46 +141,19 @@
, Difference
, Size>::size_type>
{
- friend class iterator_core_access;
- friend class cursor_core_access;
- typedef cursor_facade<Derived
- , Value
- , HorizontalTraversalOrCategory
- , VerticalTraversalOrCategory
- , Reference
- , Difference
- , Size> cursor_facade_;
-
- public:
- cursor_adaptor() {}
-
- explicit cursor_adaptor(Base const& cur) : m_cursor(cur)
- { }
-
- Base const& base() const
- { return m_cursor; }
-
- typedef typename cursor_facade_::iterator_category iterator_category;
-
- typedef typename cursor_facade_::horizontal_traversal horizontal_traversal;
- typedef typename cursor_facade_::vertical_traversal cursor_category;
-
- typedef Size size_type;
- typedef Base base_type;
-
- protected:
+protected:
typedef cursor_adaptor<Derived, Base, Value, HorizontalTraversalOrCategory,
VerticalTraversalOrCategory, Reference, Difference,
Size> cursor_adaptor_;
typedef eval_use_default<Derived
- , Base
- , Value
- , HorizontalTraversalOrCategory
- , VerticalTraversalOrCategory
- , Reference
- , Difference
- , Size> super_t;
+ , Base
+ , Value
+ , HorizontalTraversalOrCategory
+ , VerticalTraversalOrCategory
+ , Reference
+ , Difference
+ , Size> super_t;
Base const& base_reference() const
{ return m_cursor; }
@@ -186,8 +161,38 @@
Base& base_reference()
{ return m_cursor; }
- public:
+private:
+ Base m_cursor;
+
+ friend class iterator_core_access;
+ friend class cursor_core_access;
+
+ typedef cursor_facade<Derived
+ , typename super_t::value_type
+ , typename super_t::iterator_category
+ , typename super_t::vertical_traversal
+ , typename super_t::reference
+ , typename super_t::difference_type
+ , typename super_t::size_type> cursor_facade_;
+
+public:
+ typedef Base base_type;
+
+ typedef typename cursor_facade_::iterator_category iterator_category;
+
+ typedef typename cursor_facade_::horizontal_traversal horizontal_traversal;
+ typedef typename cursor_facade_::vertical_traversal cursor_category;
+
+ typedef typename cursor_facade_::size_type size_type;
+ cursor_adaptor() {}
+
+ explicit cursor_adaptor(Base const& cur) : m_cursor(cur)
+ { }
+
+ Base const& base() const
+ { return m_cursor; }
+
typename super_t::reference dereference() const
{
return *m_cursor;
@@ -253,9 +258,6 @@
{
m_cursor.to_parent();
}
-
-private:
- Base m_cursor;
};
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-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -98,28 +98,6 @@
base_pointer m_node;
size_type m_pos;
- class root_tracker {
- public:
- root_tracker() : depth(0) {}
- root_tracker& operator++()
- {
- ++depth;
- return *this;
- }
-
- root_tracker& operator--()
- {
- --depth;
- return *this;
- }
-
- bool is_root(cursor)
- {
- return !depth;
- }
- private:
- int depth;
- };
private:
friend class iterator_core_access;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp 2008-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -23,7 +23,7 @@
* Only works with ascending cursors.
*/
-template <class Cursor, class RootTracker = typename Cursor::root_tracker>
+template <class Cursor>
class iterator
: public boost::iterator_adaptor<iterator<Cursor>
, Cursor
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-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -18,7 +18,6 @@
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
-//#include <boost/test/minimal.hpp>
namespace boost {
namespace tree {
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-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -18,7 +18,6 @@
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
-//#include <boost/test/minimal.hpp>
namespace boost {
namespace tree {
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-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -19,7 +19,6 @@
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
-//#include <boost/test/minimal.hpp>
namespace boost {
namespace tree {
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-07-06 10:23:44 EDT (Sun, 06 Jul 2008)
@@ -17,6 +17,7 @@
#include <boost/tree/algorithm.hpp>
#include <boost/tree/ascending_cursor.hpp>
+#include <boost/tree/root_tracking_cursor.hpp>
#include <boost/test/minimal.hpp>
@@ -83,12 +84,19 @@
return;
}
+void comparisons_using_rtc(binary_tree<int>::cursor c) {
+ comparisons(make_root_tracking_cursor(c));
+ return;
+}
+
/**
* Check all iterator traversals by comparing them to a recursive cursor
* algorithm output. Do that at different stages of the tree while adding
* elements to it, so different tree shapes are checked to be catered for
* by the iterator algorithms.
- * Do all that also using iterators wrapped around "explicit stack"-based cursors
+ *
+ * Afterwards, do all that using iterators wrapped around
+ * "explicit stack"-based cursors also.
*/
void compare_cursor_to_iterator_traversal() {
binary_tree<int> test_tree2;
@@ -97,51 +105,60 @@
binary_tree<int>::cursor c = test_tree2.insert(test_tree2.root(), 8);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
c = test_tree2.insert(c, 3);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
-
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
+
test_tree2.insert(c, 1);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
-
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
+
c = test_tree2.insert(++c, 6);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
test_tree2.insert(c, 4);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
-
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
+
test_tree2.insert(++c, 7);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
c = test_tree2.insert(test_tree2.root().end(), 10);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
c = test_tree2.insert(test_tree2.root().end().end(), 14);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
c = test_tree2.insert(c, 13);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
c = test_tree2.insert(c, 11);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
c = test_tree2.insert(++c, 12);
comparisons(test_tree2.root());
comparisons(make_ascending_cursor(test_tree2.root()));
-
- // FIXME: This requires subtree cursors to know their root.
- //underefed_for_each(test_tree2.root(), comparisons<binary_tree<int>::cursor>);
+ comparisons(make_root_tracking_cursor(test_tree2.root()));
underefed_for_each(test_tree2.root(), comparisons_using_ac);
+ underefed_for_each(test_tree2.root(), comparisons_using_rtc);
}
int test_main(int, char* [])