Subject: [Boost-commit] svn:boost r55575 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail boost/tree/detail/balancers libs/tree/test
From: ockham_at_[hidden]
Date: 2009-08-13 18:41:09
Author: bernhard.reiter
Date: 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
New Revision: 55575
URL: http://svn.boost.org/trac/boost/changeset/55575
Log:
Some work on balance (and related).
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp | 111 +++++++++------------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp | 5 -
sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmented_iterator.hpp | 6 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp | 5 -
sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp | 9 +-
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 4
sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp | 19 ++++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 18 ++++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp | 11 +--
sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp | 40 ++++++++-----
10 files changed, 106 insertions(+), 122 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -31,9 +31,6 @@
namespace boost {
namespace tree {
-using detail::ascending_node;
-using detail::ascending_nary_cursor;
-
using detail::augmented_iterator;
using boost::multi_index::member;
@@ -80,68 +77,23 @@
typedef typename augmented_type<Val,Meta,Meta2>::metadata_type type;
};
-
-template <class Cursor>
+template <class Cursor>
class is_on_top_cursor
-: public Cursor {
+: public cursor_adaptor<is_on_top_cursor<Cursor>, Cursor>
+{
public:
is_on_top_cursor()
- : Cursor() {}
+ : is_on_top_cursor::cursor_adaptor_() {}
is_on_top_cursor(Cursor p)
- : Cursor(p) {}
+ : is_on_top_cursor::cursor_adaptor_(p) {}
bool is_root() const
{
- return this->is_on_top();
+ return this->base_reference().is_on_top();
}
};
-//template <class Cursor>
-//class is_on_top_cursor
-//: public cursor_adaptor<is_on_top_cursor<Cursor>
-// , Cursor
-// , boost::use_default
-// , bidirectional_traversal_tag
-// , bidirectional_traversal_tag
-// > {
-//private:
-// struct enabler {};
-//
-//public:
-// //TODO: Tidy up typedefs
-//
-// typedef Cursor base_cursor;
-//
-// typedef is_on_top_cursor<Cursor> cursor;
-// typedef is_on_top_cursor<Cursor const> const_cursor; //FIXME (?)
-//
-// //typedef typename cursor_size<base_cursor>::type size_type;
-//
-// //typedef bidirectional_traversal_tag cursor_category;
-//
-// // Container-specific:
-// typedef cursor iterator; // For (range) concepts' sake, mainly
-//// typedef const_cursor const_iterator;
-//
-// // Common iterator facade stuff
-// is_on_top_cursor()
-// : is_on_top_cursor::cursor_adaptor_() {}
-//
-// explicit is_on_top_cursor(base_cursor p)
-// : is_on_top_cursor::cursor_adaptor_(p) {}
-//
-//private:
-// friend class cursor_core_access;
-// friend class iterator_core_access;
-//
-//public:
-// bool is_root() const
-// {
-// return this->base_reference().is_on_top();
-// }
-//};
-
template <class Cursor>
typename is_on_top_cursor<Cursor>::size_type
index(is_on_top_cursor<Cursor> const& cur)
@@ -149,22 +101,6 @@
return cur.index();
}
-template <class Cursor>
-class balance_iterator
-: public iterator<inorder, is_on_top_cursor<Cursor> > {
-public:
- balance_iterator()
- : iterator<inorder, is_on_top_cursor<Cursor> >() {}
-
- explicit balance_iterator(Cursor p)
- : iterator<inorder, is_on_top_cursor<Cursor> >(p) {}
-
- operator Cursor()
- {
- return Cursor(this->base());
- }
-};
-
/**
* @brief A %balance.
* This class models the hierarchy concept, the container concept and the
@@ -192,9 +128,9 @@
typedef typename hierarchy_type::cursor cursor;
typedef typename hierarchy_type::const_cursor const_cursor;
- public:
- typedef augmented_iterator<balance_iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
- typedef augmented_iterator<balance_iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
+public:
+ typedef augmented_iterator<boost::tree::iterator<inorder, is_on_top_cursor<cursor> >, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
+ typedef augmented_iterator<boost::tree::iterator<inorder, is_on_top_cursor<const_cursor> >, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
@@ -211,14 +147,17 @@
// TODO: 3rd arg...?
explicit balance (size_type n, value_type const& value = value_type(),
- hierarchy_type const& hier = hierarchy_type())
+ hierarchy_type const& hier = hierarchy_type())
: h(hier)
- {}
+ {
+ for (n; n!=0; --n)
+ this->insert(this->end(), value);
+ }
template <class InputIterator>
- balance (InputIterator first, InputIterator last,
- hierarchy_type const& hier = hierarchy_type())
- : h(hier)
+ balance (InputIterator first, InputIterator last,
+ hierarchy_type const& hier = hierarchy_type())
+ : h(hier)
{
while (first++ != last)
this->insert(this->end(), *first);
@@ -243,8 +182,10 @@
*/
iterator begin()
{
- return iterator(first(inorder(), h.root()));
-
+ cursor c = h.root();
+ to_first(inorder(), c);
+ return iterator(c);
+ //return iterator(first(inorder(), h.root()));
}
/**
@@ -260,7 +201,10 @@
*/
const_iterator cbegin() const
{
- return const_iterator(h.inorder_cfirst());
+ const_cursor c = h.root();
+ to_first(inorder(), c);
+ return const_iterator(c);
+ //return const_iterator(h.inorder_cfirst());
}
/**
@@ -492,9 +436,8 @@
// Do balancers have to work for non-leaf newly inserted elements?
// If yes, we could just insert at pos.
- cursor c = pos.base().base();
- while (!c.is_leaf())
- c = c.end();
+ cursor c = pos.base().base().base();
+ to_rightmost(c);
c = h.insert(c, data_type(val));
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -139,10 +139,9 @@
typedef typename cursor_facade_::difference_type difference_type;
typedef typename cursor_facade_::size_type size_type;
-// cursor_adaptor() {}
+ cursor_adaptor() {}
- explicit cursor_adaptor(Base const& cur) : m_cursor(cur)
- { }
+ explicit cursor_adaptor(Base const& cur) : m_cursor(cur) {}
Base const& base() const
{ return m_cursor; }
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmented_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmented_iterator.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmented_iterator.hpp 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -47,13 +47,13 @@
struct enabler {};
public:
augmented_iterator()
- : augmented_iterator::iterator_adaptor_() {}
+ : augmented_iterator::iterator_adaptor_() {}
explicit augmented_iterator(InorderIter p)
- : augmented_iterator::iterator_adaptor_(p) {}
+ : augmented_iterator::iterator_adaptor_(p) {}
explicit augmented_iterator(typename InorderIter::base_type c)
- : augmented_iterator::iterator_adaptor_(InorderIter(c)) {}
+ : augmented_iterator::iterator_adaptor_(InorderIter(c)) {}
template <class OtherInorderIter>
augmented_iterator(
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -40,7 +40,6 @@
int m_priority;
};
-
class treap {
public:
typedef treap_metadata metadata_type;
@@ -50,12 +49,12 @@
{
int priority = x->metadata().get_priority();
- x = x.parent();
+ x.to_parent();
while ((x != t.root()) && (priority > x->metadata().get_priority())) {
t.rotate(x);
priority = x->metadata().get_priority();
}
- x = x.begin();
+ x.to_begin();
}
template <class Tree>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -92,7 +92,7 @@
ascending_nary_cursor(
ascending_nary_cursor<OtherNode> const& other
, typename boost::enable_if<
- boost::is_convertible<OtherNode*, node_type*>
+ boost::is_convertible<typename OtherNode::value_type*, value_type*>
, enabler
>::type = enabler()
)
@@ -190,17 +190,18 @@
//this->base_reference() = this->base_reference()->parent();
}
-protected:
+//protected:
+public:
bool is_on_top() const
{
node_base_type* parent_begin_node =
+ static_cast<node_base_type*>(
static_cast<node_base_type*>(this->base_reference()->parent())
- ->m_children[this->base_reference()->get_index()];
+ ->m_children[this->base_reference()->get_index()]);
return (!m_pos && (this->base_reference() != parent_begin_node));
// (*this != this->parent().begin())
}
-public:
node_base_type* const& parent_node() const
{
return this->base_reference();
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-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -44,10 +44,10 @@
[ run cursor_algorithm_test.cpp ]
[ run iterator_algorithm_test.cpp ]
# [ run red_black_tree_test.cpp ]
-# [ run treap_test.cpp ]
+ [ run treap_test.cpp ]
[ run forest_test.cpp ]
# [ run nary_tree_test.cpp ]
[ run multiway_tree_test.cpp ]
-# [ run unbalanced_binary_tree_test.cpp ]
+ [ run unbalanced_binary_tree_test.cpp ]
[ run graph_test.cpp ]
;
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -15,6 +15,25 @@
BOOST_FIXTURE_TEST_SUITE( ascending_cursor_test, fake_binary_tree_fixture<int> )
+BOOST_AUTO_TEST_CASE( test_ascending_cursor_constructors )
+{
+ typedef fake_binary_tree<int>::descending_cursor dc_t;
+ typedef fake_binary_tree<int>::const_descending_cursor cdc_t;
+
+ ascending_cursor<dc_t> ac1;
+ ascending_cursor<dc_t> ac2(ac1);
+
+ BOOST_CHECK(ac1 == ac2);
+
+ ascending_cursor<cdc_t> cac1;
+ ascending_cursor<cdc_t> cac2(cac1);
+
+ BOOST_CHECK(cac1 == cac2);
+
+ ascending_cursor<cdc_t> cac3(ac1);
+ BOOST_CHECK(cac3 == ac1);
+}
+
BOOST_AUTO_TEST_CASE( test_ascending_cursor )
{
typedef fake_binary_tree<int>::descending_cursor dc_t;
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-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -22,7 +22,7 @@
{
binary_tree<int> bt0;
BOOST_CHECK(bt0.root().is_leaf());
-
+
// binary_tree<int>::node_base_type::descending_node_base** x = bt0.m_header.m_children.data();
// BOOST_CHECK_EQUAL(++x, &bt0.m_header.m_children.data()[1]);
@@ -30,6 +30,22 @@
// test with allocator?
}
+BOOST_AUTO_TEST_CASE( cursor_test )
+{
+ binary_tree<int>::cursor c1;
+ binary_tree<int>::cursor c2(c1);
+
+ BOOST_CHECK(c1 == c2);
+
+ binary_tree<int>::const_cursor cc1;
+ binary_tree<int>::const_cursor cc2(cc1);
+
+ BOOST_CHECK(cc1 == cc2);
+
+ //binary_tree<int>::const_cursor cc3(c1);
+ //BOOST_CHECK(cc3 == c1);
+}
+
BOOST_AUTO_TEST_CASE( insert_value_test )
{
binary_tree<int> bt0;
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -16,8 +16,7 @@
//#define BOOST_TEST_DYN_LINK
#include <boost/test/included/unit_test.hpp>
-//TODO: Make this a test suite.
-
+//TODO: Use a mock_binary_tree
BOOST_AUTO_TEST_CASE( treap_test )
{
using namespace boost::tree;
@@ -28,19 +27,19 @@
typedef balance<binary_tree<int>, balancers::treap> treap_t;
//searcher_t my_searcher;
- treap_t my_balancer;
+ treap_t my_balance;
//tree_t my_tree;
//create_test_data_searcher(my_searcher);
- create_test_data_sequence(my_balancer);
+ //create_test_data_sequence(my_balancer);
//create_test_data_sequence(my_vector);
// Segfaults:
// BOOST_CHECK(std::equal(my_balancer.begin(), my_balancer.end(), my_vector.begin()));
//TODO: More tests?
- for (treap_t::iterator ci = my_balancer.begin(); ci != my_balancer.end(); ++ci) {
- treap_t::hierarchy_type::cursor c = ci.base().base();
+ for (treap_t::iterator ci = my_balance.begin(); ci != my_balance.end(); ++ci) {
+ treap_t::hierarchy_type::cursor c = ci.base().base().base();
// int priority = c->metadata().get_priority(); // FIXME: Segfaults!
// if (!c.is_leaf()) {
// BOOST_CHECK(priority
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -8,21 +8,40 @@
#include <boost/tree/detail/balancers/unbalanced.hpp>
#include <boost/tree/binary_tree.hpp>
-
-
#define BOOST_TEST_MODULE unbalanced_binary_tree test
//#define BOOST_TEST_DYN_LINK
#include <boost/test/included/unit_test.hpp>
+// TODO: Use a mock_binary_tree.
+BOOST_AUTO_TEST_CASE( unbalanced_binary_tree_constructors_test )
+{
+ using namespace boost::tree;
+ typedef binary_tree<int> tree_t;
+ typedef balance<tree_t, balancers::unbalanced> balance_t;
+ balance_t t1;
+
+ balance_t t2(t1);
+}
+
+BOOST_AUTO_TEST_CASE( unbalanced_binary_tree_iterator_test )
+{
+ using namespace boost::tree;
+ typedef binary_tree<int> tree_t;
+ typedef balance<tree_t, balancers::unbalanced> balance_t;
+
+ balance_t::iterator it1;
+ balance_t::iterator it2(it1);
+}
+
BOOST_AUTO_TEST_CASE( unbalanced_binary_tree_test )
{
using namespace boost::tree;
typedef binary_tree<int> tree_t;
- typedef balance<tree_t, balancers::unbalanced> balancer_t;
- balancer_t my_tree;
+ typedef balance<tree_t, balancers::unbalanced> balance_t;
+ balance_t my_tree;
- balancer_t::iterator c, c1, c2, c3, c4, c5;
+ balance_t::iterator c, c1, c2, c3, c4, c5;
c = my_tree.end();
BOOST_CHECK(c == my_tree.end());
@@ -66,14 +85,3 @@
BOOST_CHECK_EQUAL(*c, 7);
}
-
-//boost::unit_test::test_suite*
-//init_unit_test_suite( int argc, char* argv[] )
-//{
-// boost::unit_test::test_suite* key_search_test =
-// BOOST_TEST_SUITE( "Key search binary vector test" );
-//
-// key_search_test->add( BOOST_TEST_CASE( &key_search_binary_balancer_test ) );
-//
-// return key_search_test;
-//}