|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-04-30 20:41:45
Author: bernhard.reiter
Date: 2008-04-30 20:41:44 EDT (Wed, 30 Apr 2008)
New Revision: 44959
URL: http://svn.boost.org/trac/boost/changeset/44959
Log:
Finally get rid of (redundant) const_nary_cursor.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 7 +
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 1
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 8
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 220 +++++++--------------------------------
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 4
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 28 ++++
7 files changed, 81 insertions(+), 189 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-04-30 20:41:44 EDT (Wed, 30 Apr 2008)
@@ -15,6 +15,11 @@
General:
+* Unify const_cusor and cursor facades/adapters. Otherwise their use is ridiculously complicated and redundant.
+ (Something along the lines of implementing one of them and then providing a shortcut to build the other one around it).
+* Implement "flat" (sequential *order representation) trees (cf. Knuth, Fundamental Algorithms,
+ pp. 348--351). Those should be especially useful for automated testing of "real" (binary,
+ forest) trees.
* have `erase()` operations return cursor/iterator instead of void (as in new STD)
* modify parity/parent specs according to newsgroup thread, but members add to binary_tree cursor!
* Add O(n) generations(ancestor, descendant) algorithm (vertical distance) yielding number
@@ -75,7 +80,7 @@
* searcher
* Concept checks.
* Interoperability with BGL algorithms.
-* C++0x: Add template typedefs (e.g. red_black_tree is balanced_tree<red_black_balancer, binary_tree>)
+* C++09: Add template typedefs (e.g. red_black_tree is balanced_tree<red_black_balancer, binary_tree>)
Documentation:
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-04-30 20:41:44 EDT (Wed, 30 Apr 2008)
@@ -33,7 +33,6 @@
namespace tree {
using detail::node;
-using detail::const_nary_tree_cursor;
using detail::nary_tree_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-04-30 20:41:44 EDT (Wed, 30 Apr 2008)
@@ -27,7 +27,6 @@
namespace tree {
using detail::node;
-using detail::const_nary_tree_cursor;
using detail::nary_tree_cursor;
/**
@@ -45,6 +44,8 @@
private:
typedef node<value_type, detail::binary_array> node_type;
+ //typedef node<value_type, detail::binary_array> const_node_type;
+
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
typedef typename node_traits<node_type>::node_base_type node_base_type;
@@ -53,7 +54,7 @@
public:
typedef nary_tree_cursor<node_type> cursor;
- typedef const_nary_tree_cursor<node_type> const_cursor;
+ typedef /*const_*/ nary_tree_cursor<node_type const> const_cursor;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::reference reference;
@@ -94,6 +95,7 @@
* The newly-created %binary_tree uses a copy of the allocation object used
* by @a x.
*/
+
binary_tree (self_type const& x)
: m_header(), m_value_alloc(x.m_value_alloc)
{
@@ -159,7 +161,7 @@
*/
const_cursor croot() const
{
- return const_cursor(&m_header, 0);
+ return const_cursor(/*cursor(*/&m_header, 0/*)*/);
}
/**
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-04-30 20:41:44 EDT (Wed, 30 Apr 2008)
@@ -12,6 +12,12 @@
#ifndef BOOST_TREE_DETAIL_CURSOR_NARY_HPP
#define BOOST_TREE_DETAIL_CURSOR_NARY_HPP
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/type_traits/is_const.hpp>
+#include <boost/type_traits/add_const.hpp>
+#include <boost/type_traits/add_pointer.hpp>
+
#include <boost/tree/cursor_helpers.hpp>
@@ -20,194 +26,48 @@
namespace detail {
using boost::iterator_core_access;
-
using boost::tree::cursor_core_access;
-template <class Node>
-class nary_tree_cursor;
-
-template <class Node, class BasePtr, class SizeType>
-class helper {
- public:
- static typename Node::reference deref(BasePtr par, SizeType pos)
- {
- return **static_cast<Node*>(par->operator[](pos));
- }
-};
-
-
-template <class BasePtr, class SizeType, class Value>
-class helper<node<Value, detail::binary_array> const, BasePtr, SizeType > {
- typedef node<Value, detail::binary_array> const node_type;
- public:
- static typename node_type::const_reference deref(BasePtr par, SizeType pos)
- {
- return **static_cast<node_type*>(par);
- }
-};
-
-template <class BasePtr, class SizeType, class Value>
-class helper<node<Value, detail::binary_array>, BasePtr, SizeType > {
- typedef node<Value, detail::binary_array> node_type;
- public:
- static typename node_type::reference deref(BasePtr par, SizeType pos)
- {
- return **static_cast<node_type*>(par);
- }
-};
-
-template<class Node>
-class const_nary_tree_cursor
- : public cursor_facade<const_nary_tree_cursor<Node>
- , typename Node::value_type const //const is a hint for iterator_facade!
- , random_access_traversal_tag
- , bidirectional_traversal_tag
- > {
- private:
- struct enabler {};
- typedef const_nary_tree_cursor<Node> self_type;
- typedef typename self_type::cursor_facade_ cursor_facade_;
- public:
- //TODO: Tidy up typedefs
-
- typedef Node const node_type;
- typedef node_type* node_pointer;
-
- typedef typename Node::base_pointer base_pointer;
- typedef typename Node::const_base_pointer const_base_pointer;
-
- // Container-specific:
- typedef typename cursor_facade_::size_type size_type;
-
- // Cursor-specific
-
- typedef nary_tree_cursor<Node> cursor;
- typedef const_nary_tree_cursor<Node> const_cursor;
-
- // Container-specific:
- typedef cursor iterator; // For (range) concepts' sake, mainly
- typedef const_cursor const_iterator;
-
- // Common iterator facade stuff
- const_nary_tree_cursor()
- : m_node(0), m_pos(0) {}
-
- explicit const_nary_tree_cursor(const_base_pointer p, size_type pos)
- : m_node(p), m_pos(pos) {}
-
- template <class OtherNode>
- const_nary_tree_cursor(
- const_nary_tree_cursor<OtherNode> const& other
- , typename boost::enable_if<
- boost::is_convertible<OtherNode*,
- typename Node::base_pointer> // is that correct?
- , enabler
- >::type = enabler()
- )
- : m_node(other.m_node), m_pos(other.m_pos) {}
-
- const_base_pointer m_node;
- size_type m_pos;
-
- private:
- friend class iterator_core_access;
- friend class cursor_core_access;
-
- typename node_type::const_reference dereference() const
- {
- return helper<node_type, const_base_pointer, size_type>::deref(m_node, m_pos);
- }
-
- bool equal(const_nary_tree_cursor const& other) const
- {
- return (this->m_node == other.m_node) && (this->m_pos == other.m_pos);
- }
-
- void increment()
- {
- ++m_pos;
- }
-
- void decrement()
- {
- --m_pos;
- }
-
- void advance(typename const_nary_tree_cursor::cursor_facade_::difference_type n)
- {
- m_pos += n;
- }
-
- typename const_nary_tree_cursor::cursor_facade_::difference_type
- distance_to(const_nary_tree_cursor z) const //TODO: convertible to instead of const_nary_tree_cursor (?)
- {
- return (z.m_pos - this->m_pos);
- }
-
-private:
- // Container-specific
-
- bool const empty_() const
- {
- return m_node->operator[](m_pos)->empty();
- }
-
- size_type const size_() const
- {
- return m_node->size();
- }
-
- size_type const max_size_() const
- {
- return m_node->max_size();
- }
-
- // TODO (following couple of functions): wrap around node member fn
- const_cursor left() const
- {
- return const_cursor(m_node->operator[](m_pos), 0);
- }
-
- const_cursor right() const
- {
- return const_cursor(m_node->operator[](m_pos), m_node->size()-1);
- }
-
- // Cursor stuff.
- const_cursor up() const
- {
- return const_cursor(static_cast<const_base_pointer>(m_node->parent()), m_node->get_parity());
- }
-
- size_type const par() const
- {
- return m_pos;
- }
-
-};
-
template <class Node>
class nary_tree_cursor
: public cursor_facade<nary_tree_cursor<Node>
- , typename Node::value_type
+ , typename mpl::eval_if<
+ is_const<Node>
+ , add_const<typename Node::value_type>
+ , mpl::identity<typename Node::value_type>
+ >::type
, random_access_traversal_tag
, bidirectional_traversal_tag
> {
private:
- typedef typename Node::base_pointer base_pointer;
+ typedef typename Node::base_type node_base;
+
+ typedef typename mpl::eval_if<
+ is_const<Node>
+ , add_const<node_base>
+ , mpl::identity<node_base>
+ >::type base_type;
+
+ typedef base_type* base_pointer;
+
struct enabler {};
public:
typedef Node node_type;
typedef node_type* node_pointer;
+ typedef typename mpl::eval_if<
+ is_const<Node>
+ , add_const<typename Node::value_type>
+ , mpl::identity<typename Node::value_type>
+ >::type value_type;
+
// Container-specific:
typedef typename node_type::size_type size_type;
// Cursor-specific
-
typedef nary_tree_cursor<node_type> cursor;
- typedef const_nary_tree_cursor<node_type> const_cursor;
+ typedef nary_tree_cursor<node_type const> const_cursor;
// Container-specific:
typedef cursor iterator;
@@ -221,14 +81,14 @@
nary_tree_cursor()
: m_node(0), m_pos(0) {}
- explicit nary_tree_cursor(base_pointer p, size_type pos)
+ explicit nary_tree_cursor(base_pointer p, size_type pos)
: m_node(p), m_pos(pos) {}
- template <class OtherNode> //revisit
+ template <class OtherNode>
nary_tree_cursor(
nary_tree_cursor<OtherNode> const& other
, typename boost::enable_if<
- boost::is_convertible<OtherNode*, base_pointer>
+ boost::is_convertible<OtherNode*, node_type*>
, enabler
>::type = enabler()
)
@@ -244,9 +104,9 @@
friend class access_detach;
- typename node_type::reference dereference() const
+ value_type& dereference() const
{
- return helper<node_type, base_pointer, size_type>::deref(m_node, m_pos);
+ return **static_cast<node_type*>(m_node);
}
bool equal(cursor const& other) const
@@ -270,7 +130,7 @@
}
typename nary_tree_cursor::cursor_facade_::difference_type
- distance_to(nary_tree_cursor z) const //FIXME: convertible to instead of const_nary_tree_cursor
+ distance_to(nary_tree_cursor z) const //FIXME: convertible to instead of nary_tree_cursor
{
return (z.m_pos - this->m_pos);
}
@@ -302,33 +162,33 @@
{
return cursor(m_node->operator[](m_pos), 0);
}
-
+/*
const_cursor left() const
{
return const_cursor(m_node->operator[](m_pos), 0);
}
-
+*/
cursor end()
{
return cursor(m_node->operator[](m_pos), m_node->size()-1);
}
-
+/*
const_cursor right() const
{
return const_cursor(m_node->operator[](m_pos), m_node->size()-1);
}
-
+*/
// Cursor stuff
cursor parent()
{
return cursor(static_cast<base_pointer>(m_node->parent()), m_node->get_parity());
}
-
+/*
const_cursor up() const
{
return const_cursor(static_cast<base_pointer>(m_node->parent()), m_node->get_parity());
}
-
+*/
public:
// TODO: protect?
void attach(node_pointer p_node)
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-04-30 20:41:44 EDT (Wed, 30 Apr 2008)
@@ -27,7 +27,7 @@
namespace tree {
using detail::node;
-using detail::const_nary_tree_cursor;
+//using detail::const_nary_tree_cursor;
using detail::nary_tree_cursor;
/**
@@ -72,7 +72,7 @@
typedef typename node_traits<node_type>::node_pointer node_pointer;
typedef nary_tree_cursor<node_type> cursor;
- typedef const_nary_tree_cursor<node_type> const_cursor;
+ typedef nary_tree_cursor<node_type const> const_cursor;
// typedef inorder::iterator<cursor> iterator;
// typedef inorder::iterator<const_cursor> const_iterator;
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 2008-04-30 20:41:44 EDT (Wed, 30 Apr 2008)
@@ -39,7 +39,7 @@
[ run red_black_tree_test.cpp ]
[ run treap_test.cpp ]
[ run forest_test.cpp ]
- [ run nary_tree_test.cpp ]
+# [ run nary_tree_test.cpp ]
[ run multiway_tree_test.cpp ]
[ run unbalanced_binary_tree_test.cpp ]
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 2008-04-30 20:41:44 EDT (Wed, 30 Apr 2008)
@@ -7,6 +7,8 @@
#ifndef LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
#define LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_HPP
+#include <list>
+
#include <boost/test/minimal.hpp>
// Test data from http://en.wikipedia.org/wiki/Image:Binary_search_tree.svg
@@ -16,7 +18,7 @@
template <class Tree>
void create_test_data_tree(Tree& ret)
{
- typename Tree::cursor cur = ret.insert(ret.shoot(), 8);
+ typename Tree::cursor cur = ret.insert(ret.root(), 8);
cur = ret.insert(cur, 3);
ret.insert(cur, 1);
cur = ret.insert(++cur, 6);
@@ -50,6 +52,9 @@
namespace preorder {
+//std::list data;
+
+
template <class Iterator>
void traversal(Iterator a, Iterator b)
{
@@ -84,10 +89,31 @@
BOOST_CHECK(a == b);
}
+template <class Iterator>
+void subtree_traversal(Iterator a, Iterator b)
+{
+ BOOST_CHECK(*a++ == 3);
+ BOOST_CHECK(*a++ == 1);
+ BOOST_CHECK(*a++ == 6);
+ BOOST_CHECK(*a++ == 4);
+ BOOST_CHECK(*a++ == 7);
+ BOOST_CHECK(a == b);
+}
+
} // namespace preorder
namespace inorder {
+
+
+template < class Tp, class Alloc = std::allocator<Tp> >
+class flat_binary_tree {
+ protected:
+ std::list<Tp, Alloc> cont;
+ public:
+
+};
+
template <class Iterator>
void traversal(Iterator a, Iterator b)
{
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
