Subject: [Boost-commit] svn:boost r50397 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/cursor libs/tree/test
From: ockham_at_[hidden]
Date: 2008-12-29 08:55:43
Author: bernhard.reiter
Date: 2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
New Revision: 50397
URL: http://svn.boost.org/trac/boost/changeset/50397
Log:
Rename nary_tree_cursor to ascending_nary_cursor.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 12 ++++++++++++
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 36 ++++++++++++++++++------------------
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp | 14 ++++++--------
6 files changed, 43 insertions(+), 33 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -14,6 +14,12 @@
[section TODO]
General:
+* Remove a cursor's cursor, const_cursor, iterator and const_iterator typedefs?
+ The latter two only make sense in a range algorithm context, where they might actually be
+ useful. (The former two are just aliases for completeness' sake.)
+* Make Order the last (instead of first) parameter in algorithms? That way, we could
+ assume reasonable defaults while offering explicit choice (eg for size(), find(),
+ maybe even copy(): default to preorder).
* Rename node -> ascending_node; implement descending_node; and corresponding cursors.
* Fix freestanding index() and members (esp. wrt cursor facade and adaptor!)
* Redo all that balance(==balanced_tree)/searcher stuff. Avoid redundancy, that is, make them both use
@@ -111,7 +117,13 @@
* Start an RFC: what subtree algorithms should there be? In particular, of which of
the STL's linear algorithms should there be a hierarchical version?
+Pre-release:
+* Cleanup headers/ #include dependencies.
+* Run Boost Inspect.
+
Future:
+* Exception safety?
+* Thread safety?
* Add cool constructors/assignment à la C++0x, ie (nested) parentheses or Boost.Assign.
* Do we need cursors that are not iterators, ie that provide to_begin() and to_end
(and possibly to_parent()) operations, but not operator++() and --?
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp 2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -32,7 +32,7 @@
namespace tree {
using detail::node;
-using detail::nary_tree_cursor;
+using detail::ascending_nary_cursor;
using detail::augmented_iterator;
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 2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -25,7 +25,7 @@
namespace tree {
using detail::node;
-using detail::nary_tree_cursor;
+using detail::ascending_nary_cursor;
// TODO: Remove shoot() remains (was m_header->m_parent)
@@ -52,8 +52,8 @@
typedef typename node_traits<node_type>::node_pointer node_pointer;
public:
- typedef nary_tree_cursor<node_type> cursor;
- typedef nary_tree_cursor<node_type const> const_cursor;
+ typedef ascending_nary_cursor<node_type> cursor;
+ typedef ascending_nary_cursor<node_type const> const_cursor;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::reference reference;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp 2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -29,8 +29,8 @@
using boost::tree::cursor_core_access;
template <class Node>
-class nary_tree_cursor
- : public cursor_adaptor<nary_tree_cursor<Node>
+class ascending_nary_cursor
+ : public cursor_adaptor<ascending_nary_cursor<Node>
, typename mpl::eval_if<
is_const<Node>
, add_const<typename Node::base_type>
@@ -69,11 +69,11 @@
>::type value_type;
// Container-specific:
- typedef typename nary_tree_cursor::cursor_adaptor_::size_type size_type;
+ typedef typename ascending_nary_cursor::cursor_adaptor_::size_type size_type;
// Cursor-specific
- typedef nary_tree_cursor<node_type> cursor;
- typedef nary_tree_cursor<node_type const> const_cursor;
+ typedef ascending_nary_cursor<node_type> cursor;
+ typedef ascending_nary_cursor<node_type const> const_cursor;
typedef std::size_t subtree_size_type;
// Container-specific:
@@ -82,24 +82,24 @@
template <class OtherValue>
struct rebind {
- typedef nary_tree_cursor<OtherValue> other;
+ typedef ascending_nary_cursor<OtherValue> other;
};
- nary_tree_cursor()
- : nary_tree_cursor::cursor_adaptor_(0), m_pos(0) {}
+ ascending_nary_cursor()
+ : ascending_nary_cursor::cursor_adaptor_(0), m_pos(0) {}
- explicit nary_tree_cursor(base_pointer p, size_type pos)
- : nary_tree_cursor::cursor_adaptor_(p), m_pos(pos) {}
+ explicit ascending_nary_cursor(base_pointer p, size_type pos)
+ : ascending_nary_cursor::cursor_adaptor_(p), m_pos(pos) {}
template <class OtherNode>
- nary_tree_cursor(
- nary_tree_cursor<OtherNode> const& other
+ ascending_nary_cursor(
+ ascending_nary_cursor<OtherNode> const& other
, typename boost::enable_if<
boost::is_convertible<OtherNode*, node_type*>
, enabler
>::type = enabler()
)
- : nary_tree_cursor::cursor_adaptor_(other.base()), m_pos(other.m_pos) {}
+ : ascending_nary_cursor::cursor_adaptor_(other.base()), m_pos(other.m_pos) {}
size_type m_pos;
@@ -132,14 +132,14 @@
//this->base_reference() -= sizeof(node_type);
}
- void advance(typename nary_tree_cursor::cursor_facade_::difference_type n)
+ void advance(typename ascending_nary_cursor::cursor_facade_::difference_type n)
{
m_pos += n;
//this->base_reference() += n * sizeof(node_type);
}
- typename nary_tree_cursor::cursor_facade_::difference_type
- distance_to(nary_tree_cursor z) const //FIXME: convertible to instead of nary_tree_cursor
+ typename ascending_nary_cursor::cursor_facade_::difference_type
+ distance_to(ascending_nary_cursor z) const //FIXME: convertible to instead of ascending_nary_cursor
{
return (z.m_pos - this->m_pos);
//return (z.base_reference() - this->base_reference()) / sizeof(node_type);
@@ -244,8 +244,8 @@
} // namespace detail
template <class Node>
-typename detail::nary_tree_cursor<Node>::size_type
-index(detail::nary_tree_cursor<Node> const& cur)
+typename detail::ascending_nary_cursor<Node>::size_type
+index(detail::ascending_nary_cursor<Node> const& cur)
{
return cur.index();
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp 2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -26,7 +26,7 @@
namespace tree {
using detail::node;
-using detail::nary_tree_cursor;
+using detail::ascending_nary_cursor;
/**
* @brief An %nary_tree.
@@ -69,8 +69,8 @@
typedef node_base_type* node_base_pointer;
typedef typename node_traits<node_type>::node_pointer node_pointer;
- typedef nary_tree_cursor<node_type> cursor;
- typedef nary_tree_cursor<node_type const> const_cursor;
+ typedef ascending_nary_cursor<node_type> cursor;
+ typedef ascending_nary_cursor<node_type const> const_cursor;
// typedef iterator<inorder, , cursor> iterator;
// typedef iterator<inorder, , const_cursor> const_iterator;
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 2008-12-29 08:55:42 EST (Mon, 29 Dec 2008)
@@ -5,17 +5,11 @@
// http://www.boost.org/LICENSE_1_0.txt)
#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/iterator.hpp>
-#include <boost/tree/algorithm.hpp>
+//#include <boost/tree/iterator.hpp>
+//#include <boost/tree/algorithm.hpp>
#include <boost/tree/insert_cursor.hpp>
-//#include <boost/lambda/bind.hpp>
-
-//#include <list>
-//#include <algorithm>
-//#include <iterator>
-
#define BOOST_TEST_MODULE cursor_algorithm test
#include <boost/test/included/unit_test.hpp>
#include <boost/test/test_case_template.hpp>
@@ -29,6 +23,10 @@
BOOST_FIXTURE_TEST_SUITE(insert_cursor_test, test_binary_tree_fixture<int>)
+// Maybe suffix this by "_preorder", and add
+// emulated inorder and postorder versions, so
+// we can check whether insert_cursor works in all cases
+// without relying on algorithms.
template <class Cursor>
void fill_subtree_with_data(Cursor cur)
{