|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-06-08 06:42:04
Author: bernhard.reiter
Date: 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
New Revision: 46228
URL: http://svn.boost.org/trac/boost/changeset/46228
Log:
Implement (stack-based) pre- and postorder iterator adaptors for descending cursors.
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/iterator/
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/iterator/bidirectional.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 5 +-
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp | 23 ++++-------
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp | 25 ++++++++++--
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp | 17 ++++++--
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/bidirectional.hpp | 65 --------------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp | 53 +++++++++-----------------
sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp | 14 +++++--
sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp | 69 +++++++++++++++++++++++++++++++---
sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp | 5 +-
sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp | 79 ++++++++++++++++++++++++++++++++++++---
sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html | 10 ++--
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp | 33 +++++++++++-----
13 files changed, 238 insertions(+), 164 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -14,8 +14,9 @@
[section TODO]
General:
-* Actually implement stack-based pre- and postorder iterators for forward cursors.
- (For now, they're only dummies.)
+* 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,
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
Modified: 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/algorithm/inorder.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -107,32 +107,25 @@
iterator<MultiwayCursor, forward_traversal_tag>
begin(MultiwayCursor c, forward_traversal_tag)
{
- typedef MultiwayCursor cursor;
- std::stack<cursor> s;
- typename cursor_size<cursor>::type branch = 0;
- typename cursor_size<cursor>::type i = 0;
+ std::stack<MultiwayCursor> s;
+
s.push(c);
- while (!s.top().empty()) {
- ++i;
- if (!branch && !s.top().end().empty())
- branch = i;
+ while (!s.top().empty())
s.push(s.top().begin());
- }
- return iterator<cursor, forward_traversal_tag>(s, branch);
+ return iterator<MultiwayCursor, forward_traversal_tag>(s);
}
template <class MultiwayCursor>
iterator<MultiwayCursor, forward_traversal_tag>
end(MultiwayCursor c, forward_traversal_tag)
{
- typedef MultiwayCursor cursor;
- std::stack<cursor> s;
+ std::stack<MultiwayCursor> s;
+
s.push(c);
- while (!s.top().empty())
- s.push(s.top().end());
- return iterator<cursor, forward_traversal_tag>(s, s.size());
+ return iterator<MultiwayCursor, forward_traversal_tag>(s);
}
+#include <boost/tree/algorithm/iterator/bidirectional.hpp>
} // namespace inorder
Added: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/iterator/bidirectional.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/iterator/bidirectional.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -0,0 +1,109 @@
+// 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.
+
+// 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
+ * calling the appropriate traversal function that are defined in the
+ * 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())
+ * @param c A cursor
+ * @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)
+{
+ return iterator<Cursor>(last(c));
+}
+
+/**
+ * @brief One position past the last element of a subtree
+ * in traversal (Alias of cend())
+ * @param c A cursor
+ * @return Iterator one position past the last element of @a c
+ */
+template <class Cursor>
+iterator<Cursor> end(Cursor c)
+{
+ typedef
+ typename cursor_vertical_traversal<Cursor>::type
+ traversal;
+ return end(c, traversal());
+}
+
+
+/// Reverse iterators
+
+template <class Cursor>
+std::reverse_iterator< iterator<Cursor> >
+rbegin(Cursor c)
+{
+ return std::reverse_iterator< iterator<Cursor> >(end(c));
+}
+
+template <class Cursor>
+std::reverse_iterator< iterator<Cursor> >
+rend(Cursor c)
+{
+ 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));
+}
+
+//#endif // BOOST_TREE_DETAIL_ITERATOR_BIDIRECTIONAL_HPP
Modified: 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/algorithm/postorder.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -109,24 +109,39 @@
return outsubtree;
}
-///Iterators
+
+/// Iterators
template <class Cursor>
iterator<Cursor, forward_traversal_tag>
begin(Cursor c, forward_traversal_tag)
{
- // TODO: Only a (bidirectional) dummy!
- return iterator<Cursor, forward_traversal_tag>(first(c));
+ 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)
{
- // TODO: Only a (bidirectional) dummy!
- return iterator<Cursor, forward_traversal_tag>(last(c));
+ std::stack<Cursor> s;
+
+ s.push(c);
+ return iterator<Cursor, forward_traversal_tag>(s);
}
+#include <boost/tree/algorithm/iterator/bidirectional.hpp>
+
} // namespace postorder
} // namespace tree
Modified: 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/algorithm/preorder.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -101,22 +101,31 @@
return t;
}
+/// Iterators
+
template <class Cursor>
iterator<Cursor, forward_traversal_tag>
begin(Cursor c, forward_traversal_tag)
{
- // TODO: Only a (bidirectional) dummy!
- return iterator<Cursor, forward_traversal_tag>(first(c));
+ 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)
{
- // TODO: Only a (bidirectional) dummy!
- return iterator<Cursor, forward_traversal_tag>(last(c));
+ std::stack<Cursor> s;
+
+ s.push(c);
+ return iterator<Cursor, forward_traversal_tag>(s);
}
+#include <boost/tree/algorithm/iterator/bidirectional.hpp>
+
} // namespace preorder
} // namespace tree
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 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -85,69 +85,4 @@
}
};
-
-/// Iterators
-
-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())
- * @param c A cursor
- * @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)
-{
- return iterator<Cursor>(last(c));
-}
-
-/**
- * @brief One position past the last element of a subtree
- * in traversal (Alias of cend())
- * @param c A cursor
- * @return Iterator one position past the last element of @a c
- */
-template <class Cursor>
-iterator<Cursor> end(Cursor c)
-{
- typedef
- typename cursor_vertical_traversal<Cursor>::type
- traversal;
- return end(c, traversal());
-}
-
-
-/// Reverse iterators
-
-template <class Cursor>
-std::reverse_iterator< iterator<Cursor> >
-rbegin(Cursor c)
-{
- return std::reverse_iterator< iterator<Cursor> >(end(c));
-}
-
-template <class Cursor>
-std::reverse_iterator< iterator<Cursor> >
-rend(Cursor c)
-{
- return std::reverse_iterator< iterator<Cursor> >(begin(c));
-}
-
//#endif // BOOST_TREE_DETAIL_ITERATOR_BIDIRECTIONAL_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_iterator.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -32,14 +32,14 @@
namespace inorder {
-template <class Cursor,
- class Tag = typename cursor_vertical_traversal<Cursor>::type>
+template <class MultiwayCursor,
+ class Tag = typename cursor_vertical_traversal<MultiwayCursor>::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
+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:
@@ -49,63 +49,50 @@
iterator() {}
// : iterator::iterator_adaptor_() {}
- explicit iterator(stack<Cursor> s)
- : m_s(s), m_branch() {}
+ explicit iterator(stack<MultiwayCursor> s)
+ : m_s(s) {}
// : iterator::iterator_adaptor_(p) {}
- explicit iterator(stack<Cursor> s, typename cursor_size<Cursor>::type branch)
- : m_s(s), m_branch(branch) {}
-
-// template <class OtherCursor>
+// template <class OtherMultiwayCursor>
// iterator(
-// iterator<OtherCursor> const& other
+// iterator<OtherMultiwayCursor> const& other
// , typename boost::enable_if<
-// boost::is_convertible<OtherCursor,Cursor >
+// boost::is_convertible<OtherMultiwayCursor,MultiwayCursor >
// , enabler
// >::type = enabler()
// )
// : iterator::iterator_adaptor_(other.base()) {}
- operator Cursor()
+ operator MultiwayCursor()
{
return m_s.top();
}
private:
friend class boost::iterator_core_access;
- stack<Cursor> m_s;
- typename cursor_size<Cursor>::type m_branch;
+ stack<MultiwayCursor> m_s;
- typename Cursor::value_type& dereference() const
+ typename MultiwayCursor::value_type& dereference() const
{
return *m_s.top();
}
- bool equal(iterator<Cursor, forward_traversal_tag> const& other) const
+ bool equal(iterator<MultiwayCursor, forward_traversal_tag> const& other) const
{
- return (this->m_s == other.m_s) && (this->m_branch == other.m_branch);
+ return (this->m_s == other.m_s);
}
void increment()
{
if (!(++m_s.top()).empty()) {
- while (!m_s.top().begin().empty() && !m_s.top().end().empty())
- m_s.push(m_s.top().begin());
- if (!m_s.top().begin().empty() && m_s.top().end().empty())
- m_branch = m_s.size();
while (!m_s.top().begin().empty())
- m_s.push(m_s.top().begin());
+ m_s.push(m_s.top().begin());
m_s.push(m_s.top().begin());
return;
}
- if (++m_branch == m_s.size())
- return;
-
- while (m_s.top().parity())
+ while (m_s.top().parity() && !m_s.empty())
m_s.pop();
- if (--m_branch > m_s.size())
- m_branch = m_s.size();
return;
}
@@ -117,11 +104,9 @@
m_s.push(m_s.top().begin());
return;
}
+
while (!m_s.top().parity())
m_s.pop();
- if (++m_branch > m_s.size())
- m_branch = m_s.size();
- --m_branch;
--m_s.top();
return;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -77,6 +77,7 @@
c.to_begin();
return;
}
+
if (!(++c).empty()) { // Right
c.to_begin();
return;
@@ -86,6 +87,8 @@
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) { // revisit
c.to_parent();
if (c.parity())
@@ -111,16 +114,19 @@
/**
* @brief First element of a subtree in postorder traversal
- * (equivalent to inorder::first())
* @param c A cursor
* @return Cursor to the first element of @a c in postorder traversal
*/
template <class Cursor>
Cursor first(Cursor c)
{
- while (!c.empty())
- c.to_begin();
- return c;
+ while (true)
+ if (!c.empty())
+ c.to_begin();
+ else if (!(++c).empty())
+ c.to_begin();
+ else
+ return --c;
}
/**
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder_iterator.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -31,21 +31,21 @@
class Tag = typename cursor_vertical_traversal<Cursor>::type>
class iterator;
-// TODO. For now, it's only a (bidirectional) dummy
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 {};
+// private:
+// struct enabler {};
public:
iterator() {}
// : iterator::iterator_adaptor_() {}
- explicit iterator(Cursor p) {}
+ explicit iterator(stack<Cursor> s)
+ : m_s(s) {}
// : iterator::iterator_adaptor_(p) {}
// template <class OtherCursor>
@@ -60,19 +60,74 @@
operator Cursor()
{
- return this->base();
+ 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()
{
- forward(this->base_reference()); //Dummy
+ 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()
{
- back(this->base_reference()); //Dummy
+ 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;
}
};
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -50,10 +50,9 @@
// 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
- c.to_parent();
+ if (!c.parity() && (c != c.parent().begin())) // Root
return;
- }
+
c.to_parent();
if (!c.parity()) {
if (c != c.parent().begin()) // Root?
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder_iterator.hpp 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -37,14 +37,15 @@
, typename Cursor::value_type
, bidirectional_traversal_tag
> {
- private:
- struct enabler {};
+// private:
+// struct enabler {};
public:
iterator() {}
// : iterator::iterator_adaptor_() {}
- explicit iterator(Cursor p) {}
+ explicit iterator(stack<Cursor> s)
+ : m_s(s) {}
// : iterator::iterator_adaptor_(p) {}
// template <class OtherCursor>
@@ -59,19 +60,83 @@
operator Cursor()
{
- return this->base();
+ return m_s.top();
}
private:
friend class boost::iterator_core_access;
+
+ stack<Cursor> m_s;
- void increment()
+ typename Cursor::value_type& dereference() const
+ {
+ return *m_s.top();
+ }
+
+ bool equal(iterator<Cursor, forward_traversal_tag> const& other) const
{
- forward(this->base_reference()); //Dummy
+ 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()
{
- back(this->base_reference()); //Dummy
+ 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;
}
};
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html 2008-06-08 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -2836,15 +2836,15 @@
</li>
<li>
- <p>If exactly one application of the expression <tt>i =
- i.begin()</tt>, followed by a finite sequence of applications of
- the expression <tt>++j</tt> makes <tt>i == j</tt>, <tt>j</tt> is
- a <em>child</em> (or <em>immediate descendant</em> ) of
+ <p>If exactly one application of the expression <tt>
+ i.to_begin()</tt>, followed by a finite sequence of applications of
+ the expression <tt>++j</tt> makes <tt>i == j</tt>, then <tt>j</tt> is
+ a <em>child</em> (or <em>immediate descendant</em>) of
<tt>i</tt>, and <tt>i</tt> is the <em>parent</em> (or the
<em>immediate ancestor</em>) of <tt>j</tt>. A cursor <tt>j</tt>
is another cursor <tt>i</tt>'s <tt>descendant</tt> if there is a
finite sequential combination of applications of either of the
- expressions <tt>++i</tt> and <tt>i = i.begin()</tt> that makes
+ expressions <tt>++i</tt> and <tt>i.to_begin()</tt> that makes
<tt>i == j</tt>; <tt>i</tt> is then called <tt>j</tt>'s ancestor.
If two cursors <tt>i</tt> and <tt>j</tt> share at least one
common ancestor, they refer to the same container. The descending
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 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -90,7 +90,7 @@
//Now same for "explicit stack"-based iterators
// 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()),
test_list.begin()
@@ -100,7 +100,7 @@
boost::tree::ORDER::rend(t.root(), forward_traversal_tag()),
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 06:42:02 EDT (Sun, 08 Jun 2008)
@@ -98,7 +98,17 @@
binary_tree<int> test_tree;
create_test_data_tree(test_tree);
-
+
+ //Preorder
+ test::preorder::traversal(preorder::begin(test_tree.root()),
+ preorder::end(test_tree.root()));
+
+ test::preorder::reverse_traversal(preorder::end(test_tree.root()),
+ preorder::begin(test_tree.root()));
+
+ BOOST_CHECK(std::distance(preorder::begin(test_tree.root()),
+ preorder::end(test_tree.root())) == 11);
+
// Inorder
test::inorder::traversal(inorder::begin(test_tree.root()),
inorder::end(test_tree.root()));
@@ -111,16 +121,6 @@
BOOST_CHECK(std::distance(inorder::begin(test_tree.root()),
inorder::end(test_tree.root())) == 11);
- //Preorder
- test::preorder::traversal(preorder::begin(test_tree.root()),
- preorder::end(test_tree.root()));
-
- test::preorder::reverse_traversal(preorder::end(test_tree.root()),
- preorder::begin(test_tree.root()));
-
- BOOST_CHECK(std::distance(preorder::begin(test_tree.root()),
- preorder::end(test_tree.root())) == 11);
-
//Postorder
test::postorder::traversal(postorder::begin(test_tree.root()),
postorder::end(test_tree.root()));
@@ -131,11 +131,22 @@
postorder::end(test_tree.root())) == 11);
// Now the stack-based iterators (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::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()));
+
//Ascending iterator.
binary_tree<int>::cursor c = test_tree.root();
ascending::iterator<binary_tree<int>::cursor> ai_root(c);
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