|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r57007 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-10-19 18:32:35
Author: bernhard.reiter
Date: 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
New Revision: 57007
URL: http://svn.boost.org/trac/boost/changeset/57007
Log:
Fix predecessor.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 2 ++
sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp | 29 +++++++++++------------------
sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp | 40 ++++++++++++++++++++--------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp | 3 +++
sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp | 28 ++++++++++++++--------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp | 9 +++++----
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 35 ++++++++++++++++++++++++++++++++++-
sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp | 3 +++
sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp | 7 +++++--
10 files changed, 100 insertions(+), 62 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -14,6 +14,8 @@
[section TODO]
General:
+* In most algorithms, calls to index(c) appear after a c.to_parent() operation, so for
+ increased effciency, we need a to_parent_return_index(c) function.
* Fix binary_tree_test (rotate)
* Apply all binary_tree_test cchecks also to fake_binary_tree in order to check if semantics
are mapped properly.
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -69,16 +69,16 @@
(void)) // return type
predecessor(inorder, MultiwayCursor& c)
{
- if (!c.is_leaf()) {
+ if (!c.to_begin().is_leaf()) {
to_rightmost(c);
- --c;
+ c.to_parent(); //TODO: The latter two lines should probably be to_last(inorder(),c)
return;
}
while (!index(c) && !c.is_root())
c.to_parent();
if (!c.is_root())
- --c;
+ c.to_parent();
return;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -31,8 +31,10 @@
};
/**
- * @brief Postorder successor
- * @param c Cursor to be set to its postorder successor
+ * @brief Postorder successor
+ * @param c Cursor to be set to its postorder successor
+ *
+ * Note that this is the reverse preorder predecessor.
*/
template <class Cursor>
inline
@@ -62,8 +64,10 @@
}
/**
- * @brief Postorder predecessor
- * @param c Cursor to be set to its postorder predecessor
+ * @brief Postorder predecessor
+ * @param c Cursor to be set to its postorder predecessor
+ *
+ * Note that this is the reverse preorder successor.
*/
template <class Cursor>
inline
@@ -73,29 +77,18 @@
(void)) // return type
predecessor(postorder, Cursor& c)
{
- if (c.is_root()) { // Root?
- c.to_begin();
- return;
- }
-
- if (!(++c).is_leaf()) { // Right
- c.to_begin();
+ if (!c.to_end().is_leaf()) // Right
return;
- }
- if (!(--c).is_leaf()) { // Left
- c.to_begin();
+ if (!(--c).is_leaf()) // Left
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 (!c.is_root()) {
c.to_parent();
if (index(c))
- if (!(--c).is_leaf()) {
- c.to_begin();
+ if (!(--c).is_leaf())
return;
- }
}
return;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -33,6 +33,8 @@
/**
* @brief Preorder successor
* @param c Cursor to be set to its preorder successor
+ *
+ * Note that this is the reverse postorder predecessor.
*/
template <typename Cursor>
inline
@@ -66,7 +68,7 @@
/**
* @brief Preorder successor
- * @param c Cursor to be set to its preorder successor
+ * @param c Cursor to be set to its preorder successor
*/
template <typename Cursor>
inline
@@ -106,8 +108,10 @@
}
/**
- * @brief Preorder predecessor
- * @param c Cursor to be set to its preorder predecessor
+ * @brief Preorder predecessor
+ * @param c Cursor to be set to its preorder predecessor
+ *
+ * Note that this is the reverse postorder successor.
*/
template <class Cursor>
inline
@@ -117,26 +121,22 @@
(void)) // return type
predecessor(preorder, Cursor& c)
{
- if (!c.is_root()) {
+ if (c.is_root())
+ return;
+
+ if (!index(c)) { // Left child? Return parent.
c.to_parent();
+ return;
+ }
- // If a left child was given, just move to its parent.
- if (!index(c))
- return;
-
- // So this is a right child.
- --c;
+ // Right child.
+ --c;
+ while (!c.is_leaf()) {
+ c.to_end();
+ if (c.is_leaf())
+ --c;
}
-
- // Same for root (=end) and right children:
- while (!c.is_leaf())
- if (!c.end().is_leaf())
- c.to_end();
- else
- c.to_begin();
-
- if (index(c))
- --c;
+ c.to_parent();
return;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -26,11 +26,14 @@
BOOST_AUTO_TEST_CASE( test_equal )
{
BOOST_CHECK(equal(fbt1.root(), fbt1.root()));
+ BOOST_CHECK(!equal(fbt1.root(), fbt2.root()));
+ // TODO: Also check with empty trees
}
BOOST_AUTO_TEST_CASE( test_equal_pred )
{
BOOST_CHECK(boost::tree::equal(fbt1.root(), fbt1.root(), std::equal_to<int>()));
+ BOOST_CHECK(!boost::tree::equal(fbt1.root(), fbt2.root(), std::equal_to<int>()));
}
BOOST_AUTO_TEST_CASE( test_size )
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -19,24 +19,20 @@
BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
-BOOST_AUTO_TEST_CASE( test_rightmost )
-{
- fake_root_tracking_binary_tree<int> frbt1(fbt1);
- fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
- to_rightmost(c);
- BOOST_CHECK(c.is_leaf());
- BOOST_CHECK(c == frbt1.root().end().end().end());
-}
+//BOOST_AUTO_TEST_CASE( test_rightmost )
+//{
+// fake_root_tracking_binary_tree<int> frbt1(fbt1);
+// fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
+// to_rightmost(c);
+// BOOST_CHECK(c.is_leaf());
+// BOOST_CHECK(c == frbt1.root().end().end().end());
+//}
BOOST_AUTO_TEST_CASE_TEMPLATE( test_predecessor, Order, orders )
{
fake_root_tracking_binary_tree<int> frbt1(fbt1);
fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
- to_last(Order(), c);
- // Replace by a fake_to_last function for dependency minimization's sake?
- // preorder: fbt1.root_tracking_root().end().end().begin().begin().end().begin();
- // inorder: fbt1.root_tracking_root().end().end().begin();
- // postorder: fbt1.root_tracking_root().begin();
+ fake_to_last(Order(), c);
test_data_set mpo;
mock_cursor_data(mpo);
@@ -48,9 +44,13 @@
typename container_type::const_iterator ci = order_index.end();
for (--ci; ci!=cib; --ci) {
+ BOOST_CHECK_EQUAL(*c, ci->val); //Change order of statements!
boost::tree::predecessor(Order(), c);
- BOOST_CHECK_EQUAL(*c, ci->val);
+
}
+ fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
+ fake_to_first(Order(), d);
+ BOOST_CHECK(c == d);
}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -30,10 +30,7 @@
{
fake_root_tracking_binary_tree<int> frbt1(fbt1);
fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
- to_first(Order(), c);
- // Replace by a fake_to_first function for dependency minimization's sake?
- // preorder: fbt1.root_tracking_root().begin();
- // in- and postorder: fbt1.root_tracking_root().begin().begin().begin();
+ fake_to_first(Order(), c);
test_data_set mpo;
mock_cursor_data(mpo);
@@ -48,6 +45,10 @@
BOOST_CHECK_EQUAL(*c, ci->val);
boost::tree::successor(Order(), c);
}
+
+ fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
+ fake_to_last(Order(), d);
+ BOOST_CHECK(c == d);
}
BOOST_AUTO_TEST_CASE( test_successor_ascending )
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -69,6 +69,39 @@
BOOST_CHECK_EQUAL(*++a, 8);
BOOST_CHECK(++a == b);
-} // namespace ascending
+}
+
+template <class Cursor>
+void fake_to_first(boost::tree::preorder, Cursor& c)
+{}
+
+template <class Cursor>
+void fake_to_first(boost::tree::inorder, Cursor& c)
+{
+ c.to_begin().to_begin();
+}
+
+template <class Cursor>
+void fake_to_first(boost::tree::postorder, Cursor& c)
+{
+ c.to_begin().to_begin();
+}
+
+template <class Cursor>
+void fake_to_last(boost::tree::preorder, Cursor& c)
+{
+ c.to_end().to_end().to_begin().to_begin().to_end();
+}
+
+template <class Cursor>
+void fake_to_last(boost::tree::inorder, Cursor& c)
+{
+ c.to_end().to_end();
+}
+
+template <class Cursor>
+void fake_to_last(boost::tree::postorder, Cursor& c)
+{}
+
#endif // LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_DATA_HPP
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -26,7 +26,10 @@
= mpo.get<Order>().begin();
fake_binary_tree<int>::descending_cursor c = fbt1.descending_root();
+ fake_binary_tree<int>::descending_cursor d = fbt1.descending_root();
boost::tree::to_first(Order(), c);
+ fake_to_first(Order(), d);
+ BOOST_CHECK(c == d);
BOOST_CHECK_EQUAL(*c, ci->val);
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -28,9 +28,12 @@
fake_root_tracking_binary_tree<int> frbt1(fbt1);
fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
+ fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
boost::tree::to_last(Order(), c);
- boost::tree::predecessor(Order(), c);
- BOOST_CHECK_EQUAL(*c, cie->val);
+ fake_to_last(Order(), d);
+ BOOST_CHECK(c == d);
+// boost::tree::predecessor(Order(), c);
+// BOOST_CHECK_EQUAL(*c, cie->val);
}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
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