|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-06-11 15:52:26
Author: bernhard.reiter
Date: 2008-06-11 15:52:25 EDT (Wed, 11 Jun 2008)
New Revision: 46336
URL: http://svn.boost.org/trac/boost/changeset/46336
Log:
Invocation consistency fixes to recursive *order algorithms.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 3 -
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 5 +++
sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp | 2 +
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp | 62 ++++++++++++++++++++++++++------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp | 64 +++++++++++++++++++++------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp | 50 ++++++++++++++++++------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp | 28 ++++++++--------
sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp | 24 +++++++++-----
8 files changed, 143 insertions(+), 95 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-06-11 15:52:25 EDT (Wed, 11 Jun 2008)
@@ -14,8 +14,7 @@
[section TODO]
General:
-* Change recursive *order algorithms such that their argument is root() instead of
- root().begin() (as is now).
+* Also test copy with two trees (not just one tree and a container/output iterator)
* Rename parity() (which looks somewhat binary-related) to index (more general for forest
trees etc)?
* _Possibly_ move detail/algorithm/cursor/ to detail/cursor/algorithm/ or even just
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-06-11 15:52:25 EDT (Wed, 11 Jun 2008)
@@ -174,6 +174,11 @@
}
};
+template <class Cursor>
+inline ascending_cursor<Cursor> make_ascending_cursor(Cursor c)
+{
+ return ascending_cursor<Cursor>(c);
+}
} // namespace tree
} // namespace boost
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp 2008-06-11 15:52:25 EDT (Wed, 11 Jun 2008)
@@ -126,6 +126,7 @@
* in saving keystrokes.
*/
// TODO: Complete this.
+// Shouldn't we be using cursor_facade?
template<class OutputIterator>
class output_cursor_iterator_wrapper {
protected:
@@ -168,6 +169,7 @@
output_cursor_iterator_wrapper operator++(int) { return *this; }
/// Returns *this, as this %cursor doesn't "move".
+ output_cursor_iterator_wrapper& to_begin() { return *this; }
output_cursor_iterator_wrapper& begin() { return *this; }
};
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-06-11 15:52:25 EDT (Wed, 11 Jun 2008)
@@ -122,11 +122,15 @@
template <class MultiwayCursor, class Op>
void for_each_recursive(MultiwayCursor s, Op& f)
{
- if (!s.empty())
- for_each_recursive(s.begin(), f);
- f(*s);
- if (!(++s).empty())
- for_each_recursive(s.begin(), f);
+ MultiwayCursor t = s;
+ t.to_end();
+ for (s.to_begin(); s!=t; ++s) {
+ if (!s.empty())
+ for_each_recursive(s, f);
+ f(*s);
+ }
+ if (!t.empty())
+ for_each_recursive(t, f);
}
/**
@@ -143,11 +147,15 @@
template <class MultiwayCursor, class Op>
Op for_each(MultiwayCursor s, Op f)
{
- if (!s.empty())
- for_each_recursive(s.begin(), f);
- f(*s);
- if (!(++s).empty())
- for_each_recursive(s.begin(), f);
+ MultiwayCursor t = s;
+ t.to_end();
+ for (s.to_begin(); s!=t; ++s) {
+ if (!s.empty())
+ for_each_recursive(s, f);
+ f(*s);
+ }
+ if (!t.empty())
+ for_each_recursive(t, f);
return f;
}
@@ -160,11 +168,18 @@
template <class InCursor, class OutCursor>
OutCursor copy (InCursor s, OutCursor t)
{
- if (!s.empty())
- copy(s.begin(), t.begin());
- *t = *s;
- if (!(++s).empty())
- copy(s.begin(), (++t).begin());
+ InCursor r = s;
+ r.to_end();
+ s.to_begin();
+ t.to_begin();
+
+ while (s!=r) {
+ if (!s.empty())
+ copy(s, t);
+ *++t=*++s;
+ }
+ if (!r.empty())
+ copy(r, t);
return t;
}
@@ -184,11 +199,18 @@
template <class InCursor, class OutCursor, class Op>
OutCursor transform (InCursor s, OutCursor t, Op op)
{
- if (!s.empty())
- transform(s.begin(), t.begin(), op);
- *t = op(*s);
- if (!(++s).empty())
- transform(s.begin(), (++t).begin(), op);
+ InCursor r = s;
+ r.to_end();
+ s.to_begin();
+ t.to_begin();
+
+ while (s!=r) {
+ if (!s.empty())
+ transform(s, t, op);
+ *++t=op(*++s);
+ }
+ if (!r.empty())
+ transform(r, t, op);
return t;
}
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-11 15:52:25 EDT (Wed, 11 Jun 2008)
@@ -152,12 +152,13 @@
template <class Cursor, class Op>
void for_each_recursive(Cursor s, Op& f)
{
- if (!s.empty())
- for_each_recursive(s.begin(), f);
- Cursor subtree = s;
- if (!(++s).empty())
- for_each_recursive(s.begin(), f);
- f(*subtree);
+ Cursor t = s;
+ s.to_begin();
+ do
+ if (!s.empty())
+ for_each_recursive(s, f);
+ while (s++ != t.end());
+ f(*t.to_begin());
}
/**
@@ -174,12 +175,13 @@
template <class Cursor, class Op>
Op for_each(Cursor s, Op f)
{
- if (!s.empty())
- for_each_recursive(s.begin(), f);
- Cursor subtree = s;
- if (!(++s).empty())
- for_each_recursive(s.begin(), f);
- f(*subtree);
+ Cursor t = s;
+ s.to_begin();
+ do
+ if (!s.empty())
+ for_each_recursive(s, f);
+ while (s++ != t.end());
+ f(*t.to_begin());
return f;
}
//]
@@ -193,15 +195,16 @@
template <class InCursor, class OutCursor>
OutCursor copy (InCursor s, OutCursor t)
{
- InCursor insubtree = s;
- OutCursor outsubtree = t;
- if (!s.empty())
- copy(s.begin(), t.begin());
- if (!(++s).empty()) {
- copy(s.begin(), (++t).begin());
- }
- *outsubtree = *insubtree;
- return outsubtree;
+ InCursor r = s;
+ s.to_begin();
+ t.to_begin();
+ do {
+ if (!s.empty())
+ copy(s, t);
+ ++t;
+ } while (s++ != r.end());
+ *t = *r.to_begin();
+ return t;
}
/**
@@ -220,15 +223,16 @@
template <class InCursor, class OutCursor, class Op>
OutCursor transform (InCursor s, OutCursor t, Op op)
{
- InCursor insubtree = s;
- OutCursor outsubtree = t;
- if (!s.empty())
- transform(s.begin(), t.begin(), op);
- if (!(++s).empty()) {
- transform(s.begin(), (++t).begin(), op);
- }
- *outsubtree = op(*insubtree);
- return outsubtree;
+ InCursor r = s;
+ s.to_begin();
+ t.to_begin();
+ do {
+ if (!s.empty())
+ transform(s, t, op);
+ ++t;
+ } while (s++ != r.end());
+ *t = op(*r.to_begin());
+ return t;
}
} // namespace postorder
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-11 15:52:25 EDT (Wed, 11 Jun 2008)
@@ -155,11 +155,14 @@
template <class Cursor, class Op>
void for_each_recursive(Cursor s, Op& f)
{
+ Cursor t = s;
+ t.to_end();
+ s.to_begin();
f(*s);
- if (!s.empty())
- for_each_recursive(s.begin(), f);
- if (!(++s).empty())
- for_each_recursive(s.begin(), f);
+ do
+ if (!s.empty())
+ for_each_recursive(s, f);
+ while (s++ != t);
}
/**
@@ -175,11 +178,14 @@
template <class Cursor, class Op>
Op for_each(Cursor s, Op f)
{
+ Cursor t = s.end();
+ s.to_begin();
f(*s);
- if (!s.empty())
- for_each_recursive(s.begin(), f);
- if (!(++s).empty())
- for_each_recursive(s.begin(), f);
+ do
+ if (!s.empty())
+ for_each_recursive(s, f);
+ while (s++ != t);
+
return f;
}
@@ -189,16 +195,17 @@
* @param t An output cursor.
* @result A cursor past t's preorder end, after the copying operation.
*/
-// TODO: Should work with root() instead of root().begin() (same for in- and postorder, )
-// plus a couple of other algorithms
template <class InCursor, class OutCursor>
OutCursor copy (InCursor s, OutCursor t)
{
- *t = *s;
- if (!s.empty())
- copy(s.begin(), t.begin());
- if (!(++s).empty())
- copy(s.begin(), (++t).begin());
+ InCursor r = s.end();
+ *t.to_begin() = *s.to_begin();
+ do {
+ if (!s.empty())
+ copy(s, t);
+ ++t;
+ } while (s++ != r);
+
return t;
}
@@ -218,11 +225,14 @@
template <class InCursor, class OutCursor, class Op>
OutCursor transform (InCursor s, OutCursor t, Op op)
{
- *t = op(*s);
- if (!s.empty())
- transform(s.begin(), t.begin(), op);
- if (!(++s).empty())
- transform(s.begin(), (++t).begin(), op);
+ InCursor r = s.end();
+ *t.to_begin() = op(*s.to_begin());
+ do {
+ if (!s.empty())
+ transform(s, t, op);
+ ++t;
+ } while (s++ != r);
+
return t;
}
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-11 15:52:25 EDT (Wed, 11 Jun 2008)
@@ -27,7 +27,7 @@
void test_for_each(Cursor c, Container& cont)
{
boost::tree::ORDER::for_each(
- c.begin(),
+ c,
boost::lambda::bind(&Container::push_back, &cont, boost::lambda::_1)
);
test::ORDER::traversal(cont.begin(), cont.end());
@@ -36,8 +36,8 @@
template <class Cursor, class OutCursor, class Container>
void test_copy(Cursor c, OutCursor& o, Container& cont)
{
- boost::tree::ORDER::copy(c.begin(), o);
- test::ORDER::traversal(cont.begin(), cont.end());
+ boost::tree::preorder::copy(c, o);
+ test::preorder::traversal(cont.begin(), cont.end());
}
template <class Cursor, class OutCursor, class Container>
@@ -46,9 +46,9 @@
// First copy test_tree to test_tree2, by adding 1 to each element,
// then copy test_tree2 to test_list, by subtracting 1 - so
// test_list should hold test_tree's original elements in ORDER.
- boost::tree::ORDER::transform(c.begin(), d.begin(),
+ boost::tree::ORDER::transform(c, d,
std::bind2nd(std::plus<int>(),1));
- boost::tree::ORDER::transform(d.begin(), o,
+ boost::tree::ORDER::transform(d, o,
std::bind2nd(std::minus<int>(),1));
test::ORDER::traversal(cont.begin(), cont.end());
}
@@ -83,7 +83,7 @@
back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
- boost::tree::ORDER::copy(cur.begin(), oc_test_list);
+ boost::tree::ORDER::copy(cur, oc_test_list);
// Are the elements accessed in the correct order?
BOOST_CHECK(std::equal( boost::tree::ORDER::begin(cur),
@@ -107,22 +107,22 @@
std::distance(test_list.rbegin(), test_list.rend()));
//Now same for iterators wrapped around "explicit stack"-based cursors
- BOOST_CHECK(std::equal( boost::tree::ORDER::begin(ascending_cursor<cursor>(cur)),
- boost::tree::ORDER::end(ascending_cursor<cursor>(cur)),
+ BOOST_CHECK(std::equal( boost::tree::ORDER::begin(make_ascending_cursor(cur)),
+ boost::tree::ORDER::end(make_ascending_cursor(cur)),
test_list.begin()
));
- BOOST_CHECK(std::distance(boost::tree::ORDER::begin(ascending_cursor<cursor>(cur)),
- boost::tree::ORDER::end(ascending_cursor<cursor>(cur))) ==
+ BOOST_CHECK(std::distance(boost::tree::ORDER::begin(make_ascending_cursor(cur)),
+ boost::tree::ORDER::end(make_ascending_cursor(cur))) ==
std::distance(test_list.begin(), test_list.end()));
- BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(ascending_cursor<cursor>(cur)),
- boost::tree::ORDER::rend(ascending_cursor<cursor>(cur)),
+ BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(make_ascending_cursor(cur)),
+ boost::tree::ORDER::rend(make_ascending_cursor(cur)),
test_list.rbegin()
));
- BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(ascending_cursor<cursor>(cur)),
- boost::tree::ORDER::rend(ascending_cursor<cursor>(cur))) ==
+ BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(make_ascending_cursor(cur)),
+ boost::tree::ORDER::rend(make_ascending_cursor(cur))) ==
std::distance(test_list.rbegin(), test_list.rend()));
}
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-11 15:52:25 EDT (Wed, 11 Jun 2008)
@@ -45,21 +45,27 @@
template <class Cursor, class Op>
void underefed_for_each_recursive(Cursor s, Op& f)
{
+ Cursor t = s;
+ t.to_end();
+ s.to_begin();
f(s);
- if (!s.empty())
- underefed_for_each_recursive(s.begin(), f);
- if (!(++s).empty())
- underefed_for_each_recursive(s.begin(), f);
+ do
+ if (!s.empty())
+ underefed_for_each_recursive(s, f);
+ while (s++ != t);
}
template <class Cursor, class Op>
Op underefed_for_each(Cursor s, Op f)
{
+ Cursor t = s.end();
+ s.to_begin();
f(s);
- if (!s.empty())
- underefed_for_each_recursive(s.begin(), f);
- if (!(++s).empty())
- underefed_for_each_recursive(s.begin(), f);
+ do
+ if (!s.empty())
+ underefed_for_each_recursive(s, f);
+ while (s++ != t);
+
return f;
}
@@ -111,7 +117,7 @@
c = test_tree2.insert(++c, 12);
comparisons(test_tree2.root());
- //underefed_for_each(test_tree2.root().begin(), comparisons);
+ //underefed_for_each(test_tree2.root(), comparisons);
//comparisons(test_tree2.root().begin());
}
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