Subject: [Boost-commit] svn:boost r50505 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-07 15:57:06
Author: bernhard.reiter
Date: 2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
New Revision: 50505
URL: http://svn.boost.org/trac/boost/changeset/50505
Log:
Add checks for leaf nodes.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 6 ++-
sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp | 44 ++++++++++++++--------------
sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp | 9 ++---
sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp | 6 +--
sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp | 61 ++++++++++++++++++++++++++++++++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp | 33 +++++++++------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 22 +++++++++++---
7 files changed, 115 insertions(+), 66 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -15,7 +15,6 @@
General:
* preorder_insert_cursor: hopefully easy to implement...
-* Fix insert cursor (test) to work with fake_binary_tree
* Fix binary tree/node: empty() -> root.begin() == root.end() !
* Check forest/binary_tree correspondence in a hard wired fashion.
* Add checks for correspondence of concepts and archetypes!
@@ -131,8 +130,11 @@
the STL's linear algorithms should there be a hierarchical version?
Pre-release:
+* Look into
+ * boost/graph/tree_traits.hpp
+ * Matt Austern's segmented iterators paper (maybe relevant for level order algos).
* Make directory structure reflect namespaces and vice versa.
-* Cleanup headers/ #include dependencies.
+* Cleanup headers/ #include dependencies, whitespace, indentation.
* Run Boost Inspect.
Future:
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 2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -89,28 +89,28 @@
};
// Deprecate?
-struct cursor_tag {};
-
-struct descending_tag {};
-struct descending_cursor_tag
- : public cursor_tag, public descending_tag,
- public input_iterator_tag, public output_iterator_tag {};
-struct descending_forward_cursor_tag
- : public cursor_tag, public descending_tag, public forward_iterator_tag {};
-struct descending_bidirectional_cursor_tag
- : public cursor_tag, public descending_tag, public bidirectional_iterator_tag {};
-struct descending_random_access_cursor_tag
- : public cursor_tag, public descending_tag, public random_access_iterator_tag {};
-
-struct ascending_tag {};
-struct ascending_cursor_tag
- : public descending_cursor_tag, public ascending_tag {};
-struct ascending_forward_cursor_tag
- : public descending_forward_cursor_tag, public ascending_tag {};
-struct ascending_bidirectional_cursor_tag
- : public descending_bidirectional_cursor_tag, public ascending_tag {};
-struct ascending_random_access_cursor_tag
- : public descending_random_access_cursor_tag, public ascending_tag {};
+//struct cursor_tag {};
+//
+//struct descending_tag {};
+//struct descending_cursor_tag
+// : public cursor_tag, public descending_tag,
+// public input_iterator_tag, public output_iterator_tag {};
+//struct descending_forward_cursor_tag
+// : public cursor_tag, public descending_tag, public forward_iterator_tag {};
+//struct descending_bidirectional_cursor_tag
+// : public cursor_tag, public descending_tag, public bidirectional_iterator_tag {};
+//struct descending_random_access_cursor_tag
+// : public cursor_tag, public descending_tag, public random_access_iterator_tag {};
+//
+//struct ascending_tag {};
+//struct ascending_cursor_tag
+// : public descending_cursor_tag, public ascending_tag {};
+//struct ascending_forward_cursor_tag
+// : public descending_forward_cursor_tag, public ascending_tag {};
+//struct ascending_bidirectional_cursor_tag
+// : public descending_bidirectional_cursor_tag, public ascending_tag {};
+//struct ascending_random_access_cursor_tag
+// : public descending_random_access_cursor_tag, public ascending_tag {};
/*
template <class Hor, class Vert>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp 2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -41,7 +41,6 @@
* in saving keystrokes.
*/
// TODO: Complete this.
-// Shouldn't we be using cursor_facade?
template <class Tr>
class insert_cursor
: public cursor_adaptor<insert_cursor<Tr>
@@ -81,9 +80,9 @@
typename insert_cursor::cursor_adaptor_::reference dereference() const
{
- if (index(this->base_reference())) {
- const_cast<typename Tr::cursor&>(this->base_reference())
- = tree.insert(this->base_reference(), typename Tr::value_type());
+ if (this->base_reference().index()) { // FIXME: use freestanding index!
+ //const_cast<typename Tr::cursor&>(this->base_reference()) =
+ tree.insert(this->base_reference(), typename Tr::value_type());
const_cast<typename Tr::cursor&>(this->base_reference()).to_begin();
}
return *this->base_reference();
@@ -92,7 +91,7 @@
void left()
{
if (this->base_reference().empty())
- this->base_reference() =
+// this->base_reference() =
tree.insert(this->base_reference(), typename Tr::value_type());
this->base_reference().to_begin();
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp 2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -25,14 +25,12 @@
BOOST_CONCEPT_USAGE(Tree)
{
- c = t.root();
- cc = t.root();
+ cursor c = t.root();
+ const_cursor cc = t.root(); // FIXME
}
private:
X t;
- cursor c;
- const_cursor cc;
};
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-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -26,8 +26,18 @@
/// See http://en.wikipedia.org/wiki/Binary_Tree#Methods_for_storing_binary_trees
template <class T>
struct fake_binary_tree {
+ typedef std::vector<T> children_type;
+ typedef typename children_type::size_type size_type;
+ typedef typename children_type::value_type value_type;
+ typedef typename children_type::difference_type difference_type;
+ typedef typename children_type::pointer pointer;
+ typedef typename children_type::reference reference;
+
typedef fake_descending_binary_cursor<T> descending_cursor;
- typedef fake_descending_binary_cursor<T const> const_descending_cursor;
+ typedef fake_descending_binary_cursor<T/* const*/> const_descending_cursor; //FIXME
+
+ typedef descending_cursor cursor;
+ typedef const_descending_cursor const_cursor;
typedef fake_ascending_binary_cursor<T> ascending_cursor;
typedef fake_ascending_binary_cursor<T const> const_ascending_cursor;
@@ -35,7 +45,7 @@
typedef fake_root_tracking_binary_cursor<T> root_tracking_cursor;
typedef fake_root_tracking_binary_cursor<T const> const_root_tracking_cursor;
- fake_binary_tree(typename std::vector<T>::size_type s) : m_data(s)
+ fake_binary_tree(typename std::vector<T>::size_type s = 0) : m_data(s)
{ }
descending_cursor descending_root()
@@ -43,6 +53,16 @@
return descending_cursor(*this, 0);
}
+ descending_cursor root()
+ {
+ return descending_cursor(*this, 0);
+ }
+
+ const_descending_cursor root() const
+ {
+ return const_descending_cursor(*this, 0);
+ }
+
ascending_cursor ascending_root()
{
return ascending_cursor(*this, 0);
@@ -53,12 +73,23 @@
return root_tracking_cursor(*this, 0);
}
- typedef std::vector<T> children_type;
- typedef typename children_type::size_type size_type;
- typedef typename children_type::value_type value_type;
- typedef typename children_type::difference_type difference_type;
- typedef typename children_type::pointer pointer;
- typedef typename children_type::reference reference;
+ descending_cursor insert(descending_cursor c, value_type const& v)
+ {
+ m_data[c.m_pos] = v;
+ return c;
+ }
+
+// ascending_cursor insert(ascending_cursor c, value_type const& v)
+// {
+// m_data[c.m_pos] = v;
+// return c;
+// }
+//
+// root_tracking_cursor insert(root_tracking_cursor c, value_type const& v)
+// {
+// m_data[c.m_pos] = v;
+// return c;
+// }
children_type m_data;
};
@@ -86,16 +117,21 @@
{
public:
typedef fake_descending_binary_cursor<T>cursor;
- typedef fake_descending_binary_cursor<T const> const_cursor;
+ typedef fake_descending_binary_cursor<T/* const*/> const_cursor;
typedef typename fake_descending_binary_cursor<T>::cursor_facade_::size_type size_type;
explicit fake_descending_binary_cursor(fake_binary_tree<T>& t, size_type p = 0)
: m_tree(t), m_pos(p) {}
+
+// explicit fake_descending_binary_cursor(fake_binary_tree<T> const& t, size_type p = 0)
+// : m_tree(t), m_pos(p) {}
fake_descending_binary_cursor(fake_descending_binary_cursor<T> const& other)
: m_tree(other.m_tree), m_pos(other.m_pos) {}
+// fake_descending_binary_cursor<T> operator=(fake_descending_binary_cursor<T> const&)
+
fake_binary_tree<T>& m_tree;
typename fake_binary_tree<T>::size_type m_pos;
@@ -153,6 +189,13 @@
};
template <class T>
+typename fake_descending_binary_cursor<T>::size_type
+index(fake_descending_binary_cursor<T> const& cur)
+{
+ return cur.index();
+}
+
+template <class T>
struct fake_ascending_binary_cursor
: public boost::tree::cursor_adaptor<fake_ascending_binary_cursor<T>
, fake_descending_binary_cursor<T>
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp 2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -23,9 +23,6 @@
using namespace boost::tree;
-BOOST_FIXTURE_TEST_SUITE(insert_cursor_test, test_binary_tree_fixture<int>)
-
-
template <class Cursor>
void fill_subtree_with_data(Cursor cur)
{
@@ -125,47 +122,45 @@
*c8 = 8;
}
+BOOST_FIXTURE_TEST_SUITE(insert_cursor_test, fake_binary_tree_fixture<int>)
+
BOOST_AUTO_TEST_CASE ( test_desc_copy_using_insert_cursor_preorder )
{
- bt2.clear();
- fill_subtree_with_data_in_preorder(tree_inserter(bt2, bt2.root()));
+ fill_subtree_with_data_in_preorder(tree_inserter(fbt2, fbt2.descending_root()));
- validate_test_dataset1_tree(bt2.root());
+ validate_test_dataset1_tree(fbt2.descending_root());
}
BOOST_AUTO_TEST_CASE ( test_desc_copy_using_insert_cursor_inorder )
{
- bt2.clear();
- fill_subtree_with_data_in_inorder(tree_inserter(bt2, bt2.root()));
+ fill_subtree_with_data_in_inorder(tree_inserter(fbt2, fbt2.descending_root()));
- validate_test_dataset1_tree(bt2.root());
+ validate_test_dataset1_tree(fbt2.descending_root());
}
BOOST_AUTO_TEST_CASE ( test_desc_copy_using_insert_cursor_postorder )
{
- bt2.clear();
- fill_subtree_with_data_in_postorder(tree_inserter(bt2, bt2.root()));
+ fill_subtree_with_data_in_postorder(tree_inserter(fbt2, fbt2.descending_root()));
- validate_test_dataset1_tree(bt2.root());
+ validate_test_dataset1_tree(fbt2.descending_root());
}
BOOST_AUTO_TEST_CASE ( test_desc_copy_using_insert_cursor )
{
- bt2.clear();
- fill_subtree_with_data(tree_inserter(bt2, bt2.root()));
+ fill_subtree_with_data(tree_inserter(fbt2, fbt2.descending_root()));
- validate_test_dataset1_tree(bt2.root());
+ validate_test_dataset1_tree(fbt2.descending_root());
}
//BOOST_AUTO_TEST_CASE_TEMPLATE ( test_asc_copy_using_insert_cursor, Order, orders )
//{
-// bt2.clear();
+// fbt2.clear();
//
-// boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
+// boost::tree::copy(Order(), bt.root(), tree_inserter(fbt2, fbt2.root())
// , boost::tree::ascending_vertical_traversal_tag());
//
-// validate_test_dataset1_tree(bt2.root());
-// BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root()));
+// validate_test_dataset1_tree(fbt2.root());
+// BOOST_CHECK_EQUAL(size(fbt2.root()), size(bt.root()));
//}
BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
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-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -63,15 +63,27 @@
{
BOOST_CHECK_EQUAL(*cur.begin(), 8);
BOOST_CHECK_EQUAL(*cur.begin().begin(), 3);
- BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 1); //Leaf
+ BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 1);
+ BOOST_CHECK(cur.begin().begin().end().empty());
+ BOOST_CHECK(cur.begin().begin().begin().empty()); //Leaf
+
BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 6);
- BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4); //Leaf
- BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7); //Leaf
+ BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4);
+ BOOST_CHECK(cur.begin().end().begin().begin().empty()); //Leaf
+
+ BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7);
+ BOOST_CHECK(cur.begin().end().end().begin().empty()); //Leaf
+
BOOST_CHECK_EQUAL(*cur.end().begin(), 10);
+ BOOST_CHECK(cur.end().begin().empty());
BOOST_CHECK_EQUAL(*cur.end().end().begin(), 14);
+ BOOST_CHECK(cur.end().end().end().empty());
BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 13);
- BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 11);
- BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 12); //Leaf
+ BOOST_CHECK(cur.end().end().begin().end().empty());
+ BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 11);
+ BOOST_CHECK(cur.end().end().begin().begin().begin().empty());
+ BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 12);
+ BOOST_CHECK(cur.end().end().begin().begin().end().begin().empty()); //Leaf
}
static void validate_test_dataset1_minus_1_tree(typename boost::tree::binary_tree<T>::const_cursor cur)