|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-06-08 10:29:53
Author: bernhard.reiter
Date: 2008-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
New Revision: 46238
URL: http://svn.boost.org/trac/boost/changeset/46238
Log:
Introduce ascending_adaptor.
Remove *order iterator specializations.
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 8 +-
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 | 6 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/bidirectional.hpp | 47 ++--------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/inorder.hpp | 22 -------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/postorder.hpp | 28 ---------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/preorder.hpp | 21 -------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 14 ++++
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp | 8 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp | 81 ----------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp | 105 ------------------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp | 114 ----------------------------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp | 30 +++++++---
sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp | 30 +++++-----
14 files changed, 67 insertions(+), 451 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -14,11 +14,10 @@
[section TODO]
General:
-* Include all *order iterator headers from a "iterator_algorithm.hpp" (or whatever) file.
+* _Possibly_ move detail/algorithm/cursor/ to detail/cursor/algorithm/ or even just
+ detail/cursor/ (same for iterator).
* Make *order iterators work with empty subtrees.
-* Possibly further abstract stack-based iterators by introducing a cursor adaptor
- that uses a stack of descending cursors to implement an ascending one.
-* Get rid of checks for/assignments to root and shoot in pre/post/inorder algorithms,
+* 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
@@ -54,6 +53,7 @@
Proposal:
+* Write a cursor_facade, cursor_adaptor and ascending_adaptor proposal.
* Add a revision log:
* Add to_parent() (replaces operator!()), to_begin() and to_end() descending cursor members.
* Add (subtree) cursor algorithms.
Added: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp 2008-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,162 @@
+// 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.hpp
+ * Ascending cursor adaptor implementation
+ */
+
+#ifndef BOOST_TREE_ASCENDING_CURSOR_HPP
+#define BOOST_TREE_ASCENDING_CURSOR_HPP
+
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/type_traits/is_const.hpp>
+#include <boost/type_traits/add_const.hpp>
+#include <boost/type_traits/add_pointer.hpp>
+
+#include <boost/tree/cursor_helpers.hpp>
+
+#include <stack>
+
+namespace boost {
+namespace tree {
+
+template <class Cursor>
+class ascending_cursor
+ : public cursor_facade<ascending_cursor<Cursor>
+ , typename Cursor::value_type
+ , random_access_traversal_tag
+ , bidirectional_traversal_tag
+ > {
+ private:
+ struct enabler {};
+
+ public:
+ typedef typename Cursor::value_type value_type;
+
+ // Container-specific:
+ typedef typename Cursor::size_type size_type;
+
+ // Cursor-specific
+ typedef ascending_cursor<Cursor> cursor;
+ typedef ascending_cursor<Cursor const> const_cursor; // FIXME
+
+ // Container-specific:
+ typedef cursor iterator;
+ typedef const_cursor const_iterator;
+
+ template <class OtherValue>
+ struct rebind {
+ typedef ascending_cursor<OtherValue> other;
+ };
+
+ ascending_cursor()
+ : m_s() {}
+
+ explicit ascending_cursor(Cursor c)
+ {
+ m_s.push(c); // Subtree root.
+ }
+
+ template <class OtherCursor>
+ ascending_cursor(
+ ascending_cursor<OtherCursor> const& other
+ , typename boost::enable_if<
+ boost::is_convertible<OtherCursor*, Cursor*>
+ , enabler
+ >::type = enabler()
+ )
+ : m_s(other.m_s) {}
+
+ private:
+
+ friend class boost::iterator_core_access;
+ friend class boost::tree::cursor_core_access;
+
+ std::stack<Cursor> m_s; // pimpl?
+
+ value_type& dereference() const
+ {
+ return *m_s.top();
+ }
+
+ bool equal(cursor const& other) const
+ {
+ return (this->m_s == other.m_s);
+ }
+
+ void increment()
+ {
+ ++m_s.top();
+ }
+
+ void decrement()
+ {
+ --m_s.top();
+ }
+
+ void advance(typename ascending_cursor::cursor_facade_::difference_type n)
+ {
+ m_s.top() += n;
+ }
+
+ typename ascending_cursor::cursor_facade_::difference_type
+ distance_to(ascending_cursor z) const //FIXME: convertible to instead of ascending_cursor
+ {
+ return (z.m_s.top() - this->m_s.top());
+ }
+
+ // Container specific
+ bool const empty_() const
+ {
+ return m_s.top().empty();
+ }
+
+ size_type size_()
+ {
+ return m_s.top().size();
+ }
+
+ size_type max_size_()
+ {
+ return m_s.top().max_size();
+ }
+
+ size_type const par() const
+ {
+ return m_s.top().parity();
+ }
+
+ void left()
+ {
+ m_s.push(m_s.top().begin());
+ }
+
+ void right()
+ {
+ m_s.push(m_s.top().end());
+ }
+
+ // Cursor stuff
+ void up()
+ {
+ m_s.pop();
+ }
+
+public:
+ bool is_root() const
+ {
+ return (m_s.size() == 1);
+ }
+};
+
+
+} // namespace tree
+} // namespace boost
+
+
+#endif // BOOST_TREE_ASCENDING_CURSOR_HPP
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-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -38,7 +38,7 @@
return;
}
- if (c.parent().begin() != c) // Root?
+ if (c.is_root()) // Root?
return;
// Left child.
@@ -72,7 +72,7 @@
template <class Cursor>
inline void back(Cursor& c)
{
- if (!c.parity() && (c.parent().begin() != c)) { // Root?
+ if (c.is_root()) { // Root?
c.to_begin();
return;
}
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-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -49,12 +49,12 @@
// 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
+ if (c.is_root())
return;
c.to_parent();
if (!c.parity()) {
- if (c != c.parent().begin()) // Root?
+ if (c.is_root())
return;
if (!(++c).empty()) {
c.to_begin();
@@ -84,7 +84,7 @@
template <class Cursor>
inline void back(Cursor& c)
{
- if (!(!c.parity() && (c != c.parent().begin()))) { // Not root
+ if (!c.is_root()) { // Not root
c.to_parent();
// If this is a left child, just move to its parent.
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 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -20,13 +20,6 @@
* respective *order.hpp files).
*/
-template <class Cursor>
-iterator<Cursor>
-begin(Cursor c, bidirectional_traversal_tag)
-{
- return iterator<Cursor>(first(c));
-}
-
/**
* @brief First element of a subtree in traversal
* (equivalent to postorder::begin())
@@ -34,20 +27,10 @@
* @return Iterator to the first element of @a c
*/
template <class Cursor>
-iterator<Cursor> begin(Cursor c)
-{
- typedef
- typename cursor_vertical_traversal<Cursor>::type
- traversal;
- return begin(c, traversal());
-}
-
-
-template <class Cursor>
-iterator<Cursor, bidirectional_traversal_tag>
-end(Cursor c, bidirectional_traversal_tag)
+iterator<Cursor>
+begin(Cursor c)
{
- return iterator<Cursor>(last(c));
+ return iterator<Cursor>(first(c));
}
/**
@@ -57,15 +40,12 @@
* @return Iterator one position past the last element of @a c
*/
template <class Cursor>
-iterator<Cursor> end(Cursor c)
+iterator<Cursor>
+end(Cursor c)
{
- typedef
- typename cursor_vertical_traversal<Cursor>::type
- traversal;
- return end(c, traversal());
+ return iterator<Cursor>(last(c));
}
-
/// Reverse iterators
template <class Cursor>
@@ -81,18 +61,3 @@
{
return std::reverse_iterator< iterator<Cursor> >(begin(c));
}
-
-template <class Cursor, class Traversal>
-std::reverse_iterator< iterator<Cursor, Traversal> >
-rbegin(Cursor c, Traversal t)
-{
- return std::reverse_iterator< iterator<Cursor, Traversal> >(end(c, t));
-}
-
-template <class Cursor, class Traversal>
-std::reverse_iterator< iterator<Cursor, Traversal> >
-rend(Cursor c, Traversal t)
-{
- return std::reverse_iterator< iterator<Cursor, Traversal> >(begin(c, t));
-}
-
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/inorder.hpp 2008-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -22,28 +22,6 @@
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
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/postorder.hpp 2008-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -22,34 +22,6 @@
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
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/iterator/preorder.hpp 2008-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -22,27 +22,6 @@
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
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-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -175,8 +175,18 @@
m_pos = m_node->get_parity();
m_node = static_cast<base_pointer>(m_node->parent());
}
-
-public:
+
+public:
+ // TODO This isn't really a permanently public thing.
+ bool is_root() const
+ {
+ base_pointer parent_begin_node =
+ static_cast<base_pointer>(m_node->parent())
+ ->operator[](m_node->get_parity());
+ return (!m_pos && (m_node != parent_begin_node));
+ // (*this != this->parent().begin())
+ }
+
// TODO: protect?
void attach(node_pointer p_node)
{
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 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -41,8 +41,8 @@
* @brief Specialisation for ascending cursors.
*/
template <class Cursor>
-class iterator<Cursor, bidirectional_traversal_tag>
- : public boost::iterator_adaptor<iterator<Cursor, bidirectional_traversal_tag>
+class iterator
+ : public boost::iterator_adaptor<iterator<Cursor>
, Cursor
, boost::use_default
, bidirectional_traversal_tag
@@ -61,7 +61,7 @@
iterator(
iterator<OtherCursor> const& other
, typename boost::enable_if<
- boost::is_convertible<OtherCursor,Cursor >
+ boost::is_convertible<OtherCursor, Cursor>
, enabler
>::type = enabler()
)
@@ -81,7 +81,7 @@
void decrement()
{
- back(this->base_reference());
+ back(this->base_reference());
}
};
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 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -29,89 +29,8 @@
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
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 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -25,113 +25,8 @@
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
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 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -25,122 +25,8 @@
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
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp 2008-06-08 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -5,13 +5,14 @@
// http://www.boost.org/LICENSE_1_0.txt)
#include <boost/tree/algorithm.hpp>
+#include <boost/tree/binary_tree.hpp>
+
+#include <boost/tree/ascending_cursor.hpp>
#include <list>
#include <algorithm>
#include <iterator>
-#include <boost/tree/binary_tree.hpp>
-
#include "helpers.hpp"
#include "test_tree_traversal_data.hpp"
@@ -57,7 +58,9 @@
void compare_cursor_to_iterator_traversal(boost::tree::binary_tree<int> const& t) {
- using boost::forward_traversal_tag;
+ using boost::tree::ascending_cursor;
+
+ typedef boost::tree::binary_tree<int>::const_cursor cursor;
std::list<int> test_list;
typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
@@ -88,19 +91,28 @@
boost::tree::ORDER::rend(t.root())) ==
std::distance(test_list.rbegin(), test_list.rend()));
- //Now same for "explicit stack"-based iterators
+ //Now same for iterators wrapped around "explicit stack"-based cursors
// TODO: Only possible when there are stack-based pre- and postorder iterators
- BOOST_CHECK(std::equal( boost::tree::ORDER::begin(t.root(), forward_traversal_tag()),
- boost::tree::ORDER::end(t.root(), forward_traversal_tag()),
+// BOOST_CHECK(std::equal( boost::tree::ORDER::begin(t.root(), forward_traversal_tag()),
+// boost::tree::ORDER::end(t.root(), forward_traversal_tag()),
+// test_list.begin()
+// ));
+//
+// BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(t.root(), forward_traversal_tag()),
+// boost::tree::ORDER::rend(t.root(), forward_traversal_tag()),
+// test_list.rbegin()
+// ));
+
+ BOOST_CHECK(std::equal( boost::tree::ORDER::begin(ascending_cursor<cursor>(t.root())),
+ boost::tree::ORDER::end(ascending_cursor<cursor>(t.root())),
test_list.begin()
));
- BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(t.root(), forward_traversal_tag()),
- boost::tree::ORDER::rend(t.root(), forward_traversal_tag()),
+ BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(ascending_cursor<cursor>(t.root())),
+ boost::tree::ORDER::rend(ascending_cursor<cursor>(t.root())),
test_list.rbegin()
));
-
}
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 10:29:51 EDT (Sun, 08 Jun 2008)
@@ -94,7 +94,7 @@
int test_main(int, char* [])
{
- using boost::forward_traversal_tag;
+ typedef boost::tree::binary_tree<int>::cursor cursor;
binary_tree<int> test_tree;
create_test_data_tree(test_tree);
@@ -130,22 +130,22 @@
BOOST_CHECK(std::distance(postorder::begin(test_tree.root()),
postorder::end(test_tree.root())) == 11);
- // Now the stack-based iterators (that don't use cursor.to_parent())
+ // Now the iterators based on stack-based cursors (that don't use cursor.to_parent())
- test::preorder::traversal(preorder::begin(test_tree.root(), forward_traversal_tag()),
- preorder::end(test_tree.root(), forward_traversal_tag()));
- test::preorder::reverse_traversal(preorder::end(test_tree.root(), forward_traversal_tag()),
- preorder::begin(test_tree.root(), forward_traversal_tag()));
+ test::preorder::traversal(preorder::begin(ascending_cursor<cursor>(test_tree.root())),
+ preorder::end(ascending_cursor<cursor>(test_tree.root())));
+ test::preorder::reverse_traversal(preorder::end(ascending_cursor<cursor>(test_tree.root())),
+ preorder::begin(ascending_cursor<cursor>(test_tree.root())));
- test::inorder::traversal(inorder::begin(test_tree.root(), forward_traversal_tag()),
- inorder::end(test_tree.root(), forward_traversal_tag()));
- test::inorder::reverse_traversal(inorder::end(test_tree.root(), forward_traversal_tag()),
- inorder::begin(test_tree.root(), forward_traversal_tag()));
-
- test::postorder::traversal(postorder::begin(test_tree.root(), forward_traversal_tag()),
- postorder::end(test_tree.root(), forward_traversal_tag()));
- test::postorder::reverse_traversal(postorder::end(test_tree.root(), forward_traversal_tag()),
- postorder::begin(test_tree.root(), forward_traversal_tag()));
+ test::inorder::traversal(inorder::begin(ascending_cursor<cursor>(test_tree.root())),
+ inorder::end(ascending_cursor<cursor>(test_tree.root())));
+ test::inorder::reverse_traversal(inorder::end(ascending_cursor<cursor>(test_tree.root())),
+ inorder::begin(ascending_cursor<cursor>(test_tree.root())));
+
+ test::postorder::traversal(postorder::begin(ascending_cursor<cursor>(test_tree.root())),
+ postorder::end(ascending_cursor<cursor>(test_tree.root())));
+ test::postorder::reverse_traversal(postorder::end(ascending_cursor<cursor>(test_tree.root())),
+ postorder::begin(ascending_cursor<cursor>(test_tree.root())));
//Ascending iterator.
binary_tree<int>::cursor c = test_tree.root();
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