|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50649 - in sandbox/SOC/2006/tree: branches/optimise-binary-tree-cursor/boost/tree branches/optimise-binary-tree-cursor/boost/tree/detail/balancers branches/optimise-binary-tree-cursor/boost/tree/detail/cursor trunk trunk/boost/tree trunk/libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-16 20:40:08
Author: bernhard.reiter
Date: 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
New Revision: 50649
URL: http://svn.boost.org/trac/boost/changeset/50649
Log:
More tests. Plus proof-of-concept introduction of mock_cursor (that needs a header of its own).
Added:
sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp
- copied, changed from r50613, /sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp
Text files modified:
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/binary_tree.hpp | 2
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/red_black.hpp | 2
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/treap.hpp | 2
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/unbalanced.hpp | 2
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/cursor/multiway.hpp | 2
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/multiway_tree.hpp | 2
sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/nary_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/TODO | 4 ++
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 13 ++----
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 1
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 16 ++++++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp | 20 ++++++++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp | 9 +++-
sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp | 64 ++++++++++++++++++++++++++++++++-
sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp | 66 ++++++++++++++++++++++++++++++++++-
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 74 +++++++++++++++++++++++++++++++++++++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp | 27 ++++++++------
17 files changed, 270 insertions(+), 38 deletions(-)
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/binary_tree.hpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -18,7 +18,7 @@
#include <boost/tree/insert_cursor.hpp>
#include <boost/tree/detail/node/traits.hpp>
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <memory>
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/red_black.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/red_black.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/red_black.hpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -11,7 +11,7 @@
//TODO: lots.
//templatize with bool add_data?
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
namespace boost {
namespace tree {
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/treap.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/treap.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/treap.hpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -13,7 +13,7 @@
#ifndef BOOST_TREE_BALANCERS_TREAP_HPP
#define BOOST_TREE_BALANCERS_TREAP_HPP
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <limits.h>
#include <stdlib.h>
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/unbalanced.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/unbalanced.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/balancers/unbalanced.hpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -7,7 +7,7 @@
#ifndef BOOST_TREE_BALANCERS_UNBALANCED_HPP
#define BOOST_TREE_BALANCERS_UNBALANCED_HPP
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <boost/tree/detail/algorithm/inorder.hpp>
namespace boost {
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/cursor/multiway.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/cursor/multiway.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/detail/cursor/multiway.hpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -9,7 +9,7 @@
#ifndef BOOST_TREE_DETAIL_CURSOR_MULTIWAY_HPP
#define BOOST_TREE_DETAIL_CURSOR_MULTIWAY_HPP
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <boost/tree/cursor.hpp>
#include <boost/tree/cursor_adaptor.hpp>
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/multiway_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/multiway_tree.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/multiway_tree.hpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -16,7 +16,7 @@
//#include <boost/tree/cursor.hpp>
//#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/detail/cursor/multiway.hpp>
+#include <boost/tree/detail/multiway_cursor.hpp>
#include <boost/tree/nary_tree.hpp>
Modified: sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/nary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/branches/optimise-binary-tree-cursor/boost/tree/nary_tree.hpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -16,7 +16,7 @@
#include <boost/tree/cursor.hpp>
#include <boost/tree/detail/node/traits.hpp>
-#include <boost/tree/detail/cursor/nary.hpp>
+#include <boost/tree/detail/nary_cursor.hpp>
#include <memory>
#include <vector>
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -14,6 +14,10 @@
[section TODO]
General:
+* Build output_iterator_cursor around cursor_facade (like mock_cursor)
+* Get rid of lists used for order checking. Use mock cursor instead.
+* Clean up binary_tree_test
+* binary_tree_search_test -> lower_bound_test
* preorder_insert_cursor: hopefully easy to implement...
* Add checks for correspondence of concepts and archetypes!
* Re-do forest (again!).
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 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -24,9 +24,6 @@
namespace boost {
namespace tree {
-using detail::ascending_node;
-using detail::ascending_nary_cursor;
-
// TODO: Remove shoot() remains (was m_header->m_parent)
/**
@@ -43,7 +40,7 @@
typedef typename Alloc::template rebind<value_type>::other allocator_type;
private:
- typedef ascending_node<value_type> node_type;
+ typedef detail::ascending_node<value_type> node_type;
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
@@ -51,9 +48,9 @@
typedef node_base_type* node_base_pointer;
typedef typename detail::node_traits<node_type>::node_pointer node_pointer;
- public:
- typedef ascending_nary_cursor<node_type> cursor;
- typedef ascending_nary_cursor<node_type const> const_cursor;
+public:
+ typedef detail::ascending_nary_cursor<node_type> cursor;
+ typedef detail::ascending_nary_cursor<node_type const> const_cursor;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::reference reference;
@@ -112,7 +109,7 @@
}
template <class InputCursor>
- void assign(InputCursor subtree)
+ void assign(InputCursor subtree)
{
clear();
insert(this->root(), subtree);
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -24,6 +24,7 @@
test-suite tree :
# Algorithms
[ run to_first_test.cpp ]
+ [ run to_last_test.cpp ]
[ run successor_test.cpp ]
[ run predecessor_test.cpp ]
[ run for_each_test.cpp ]
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -74,7 +74,14 @@
BOOST_AUTO_TEST_CASE( insert_subtree_test )
{
binary_tree<int> bt0;
- binary_tree<int>::cursor c = bt0.insert(bt0.root(), fbt1.root());
+ bt0.insert(bt0.root(), fbt1.root());
+ validate_test_dataset1_tree(bt0.root());
+}
+
+BOOST_AUTO_TEST_CASE( assign_subtree_test )
+{
+ binary_tree<int> bt0;
+ bt0.assign(fbt1.root());
validate_test_dataset1_tree(bt0.root());
}
@@ -233,6 +240,13 @@
validate_test_dataset1_tree(bt0.root());
}
+BOOST_AUTO_TEST_CASE( assignment_operator_test )
+{
+ binary_tree<int> bt0;
+ bt0 = bt;
+ validate_test_dataset1_tree(bt0.root());
+}
+
BOOST_AUTO_TEST_CASE( comparison_operator_test )
{
*bt2.root().begin().end().begin().begin()
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/copy_test.cpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -26,6 +26,26 @@
test_traversal(Order(), l.begin(), l.end());
}
+BOOST_AUTO_TEST_CASE( alternate_test_copy_descending )
+{
+ std::vector<int> po(11);
+ po[0] = 8;
+ po[1] = 3;
+ po[2] = 1;
+ po[3] = 6;
+ po[4] = 4;
+ po[5] = 7;
+ po[6] = 10;
+ po[7] = 14;
+ po[8] = 13;
+ po[9] = 11;
+ po[10] = 12;
+ std::vector<int>::const_iterator ci = po.begin();
+ mock_cursor< std::vector<int>::const_iterator > mc(ci);
+
+ boost::tree::copy(preorder(), fbt1.descending_root(), mc);
+}
+
BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy_ascending, Order, orders)
{
boost::tree::copy(Order(), fbt1.ascending_root(), o);
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -118,7 +118,7 @@
>
{
public:
- typedef fake_descending_binary_cursor<T>cursor;
+ typedef fake_descending_binary_cursor<T> cursor;
typedef fake_descending_binary_cursor<T/* const*/> const_cursor;
typedef typename fake_descending_binary_cursor<T>::cursor_facade_::size_type size_type;
@@ -134,7 +134,6 @@
m_pos = other.m_pos;
return *this;
}
-
fake_binary_tree<T>& m_tree;
typename fake_binary_tree<T>::size_type m_pos;
@@ -143,6 +142,10 @@
friend class boost::iterator_core_access;
friend class boost::tree::cursor_core_access;
+ static const
+ typename fake_descending_binary_cursor<T>::cursor_facade_::value_type def_val
+ = typename fake_descending_binary_cursor<T>::cursor_facade_::value_type();
+
typename fake_descending_binary_cursor<T>::cursor_facade_::reference
dereference() const
{
@@ -183,7 +186,7 @@
return true;
if (m_pos == 0)
return false;
- return (m_tree.m_data[m_pos] == 0);
+ return (m_tree.m_data[m_pos] == def_val);
}
size_type const idx() const
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-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -21,22 +21,80 @@
BOOST_AUTO_TEST_CASE( test_predecessor_preorder )
{
- fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root().begin().begin();
+ fake_binary_tree<int>::root_tracking_cursor c
+ = fbt1.root_tracking_root().end().end().begin().begin().end().begin();
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 11);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 13);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 14);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 10);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 7);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 4);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 6);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 1);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 3);
boost::tree::predecessor(preorder(), c);
BOOST_CHECK_EQUAL(*c, 8);
}
BOOST_AUTO_TEST_CASE( test_predecessor_inorder )
{
- fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root().begin().begin();
+ fake_binary_tree<int>::root_tracking_cursor c
+ = fbt1.root_tracking_root().end().end().begin();
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 13);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 12);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 11);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 10);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 8);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 7);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 6);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 4);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 3);
boost::tree::predecessor(inorder(), c);
BOOST_CHECK_EQUAL(*c, 1);
}
BOOST_AUTO_TEST_CASE( test_predecessor_postorder )
{
- fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root().begin().begin();
+ fake_binary_tree<int>::root_tracking_cursor c
+ = fbt1.root_tracking_root().begin();
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 10);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 14);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 13);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 11);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 12);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 3);
boost::tree::predecessor(postorder(), c);
BOOST_CHECK_EQUAL(*c, 6);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 7);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 4);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 1);
}
+
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-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -26,20 +26,80 @@
fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root().begin();
boost::tree::successor(preorder(), c);
BOOST_CHECK_EQUAL(*c, 3);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 1);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 6);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 4);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 7);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 10);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 14);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 13);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 11);
+ boost::tree::successor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 12);
}
BOOST_AUTO_TEST_CASE( test_successor_inorder )
{
- fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root().begin();
+ fake_binary_tree<int>::root_tracking_cursor c
+ = fbt1.root_tracking_root().begin().begin().begin().begin();
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 1);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 3);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 4);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 6);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 7);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 8);
boost::tree::successor(inorder(), c);
BOOST_CHECK_EQUAL(*c, 10);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 11);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 12);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 13);
+ boost::tree::successor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 14);
}
BOOST_AUTO_TEST_CASE( test_successor_postorder )
{
- fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root().begin();
+ fake_binary_tree<int>::root_tracking_cursor c
+ = fbt1.root_tracking_root().begin().begin().begin().begin();
boost::tree::successor(postorder(), c);
- BOOST_CHECK(c == fbt1.root_tracking_root());
+ BOOST_CHECK_EQUAL(*c, 1);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 4);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 7);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 6);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 3);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 12);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 11);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 13);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 14);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 10);
+ boost::tree::successor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 8);
}
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-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -141,6 +141,78 @@
BOOST_CHECK_EQUAL(*++c, 12);
}
+template <class Iter>
+class mock_cursor;
+
+template <class Iter>
+class mock_cursor
+: public boost::tree::cursor_facade<
+ mock_cursor<Iter>
+ , mock_cursor<Iter>
+ , boost::bidirectional_traversal_tag
+ , boost::tree::descending_vertical_traversal_tag
+ >
+{
+private:
+ Iter& m_iter;
+public:
+ typedef mock_cursor<Iter> cursor;
+ typedef mock_cursor<Iter/* const*/> const_cursor;
+
+ typedef typename mock_cursor<Iter>::cursor_facade_::size_type size_type;
+
+ mock_cursor(Iter& iter)
+ : m_iter(iter)
+ {
+ }
+
+ void operator=(typename Iter::value_type const& val)
+ {
+ BOOST_CHECK_EQUAL(val, *m_iter++);
+ }
+
+private:
+ friend class boost::iterator_core_access;
+ friend class boost::tree::cursor_core_access;
+
+ typename mock_cursor<Iter>::cursor_facade_::reference
+ dereference() const
+ {
+ return const_cast< mock_cursor<Iter>& >(*this);
+ }
+
+ bool equal(mock_cursor<Iter> const& other) const
+ {
+ return false;
+ }
+
+ void increment()
+ {
+ }
+
+ void decrement()
+ {
+ }
+
+ void left()
+ {
+ }
+
+ void right()
+ {
+ }
+
+ bool const empty_() const
+ {
+ return true;
+ }
+
+ size_type const idx() const
+ {
+ return 0;
+ }
+};
+
template <class Iterator>
void test_traversal(boost::tree::preorder, Iterator a, Iterator b)
{
@@ -263,7 +335,7 @@
template <class Iterator>
void test_traversal(boost::tree::postorder, Iterator a, Iterator b)
{
- BOOST_CHECK_EQUAL(*a++, 1);
+ BOOST_CHECK_EQUAL(*a++, 1);
BOOST_CHECK_EQUAL(*a++, 4);
BOOST_CHECK_EQUAL(*a++, 7);
BOOST_CHECK_EQUAL(*a++, 6);
Copied: sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp (from r50613, /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_last_test.cpp 2009-01-16 20:40:06 EST (Fri, 16 Jan 2009)
@@ -19,25 +19,28 @@
BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
-BOOST_AUTO_TEST_CASE( test_to_first_preorder )
+BOOST_AUTO_TEST_CASE( test_to_last_preorder )
{
- fake_binary_tree<int>::descending_cursor c = fbt1.descending_root();
- boost::tree::to_first(preorder(), c);
- BOOST_CHECK_EQUAL(*c, 8);
+ fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root();
+ boost::tree::to_last(preorder(), c);
+ boost::tree::predecessor(preorder(), c);
+ BOOST_CHECK_EQUAL(*c, 12);
}
-BOOST_AUTO_TEST_CASE( test_to_first_inorder )
+BOOST_AUTO_TEST_CASE( test_to_last_inorder )
{
- fake_binary_tree<int>::descending_cursor c = fbt1.descending_root();
- boost::tree::to_first(inorder(), c);
- BOOST_CHECK_EQUAL(*c, 1);
+ fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root();
+ boost::tree::to_last(inorder(), c);
+ boost::tree::predecessor(inorder(), c);
+ BOOST_CHECK_EQUAL(*c, 14);
}
-BOOST_AUTO_TEST_CASE( test_to_first_postorder )
+BOOST_AUTO_TEST_CASE( test_to_last_postorder )
{
- fake_binary_tree<int>::descending_cursor c = fbt1.descending_root();
- boost::tree::to_first(postorder(), c);
- BOOST_CHECK_EQUAL(*c, 1);
+ fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root();
+ boost::tree::to_last(postorder(), c);
+ boost::tree::predecessor(postorder(), c);
+ BOOST_CHECK_EQUAL(*c, 8);
}
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