|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-06-10 16:31:08
Author: bernhard.reiter
Date: 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
New Revision: 46307
URL: http://svn.boost.org/trac/boost/changeset/46307
Log:
* Eradicate shoot()
* Some forest_tree related fixes.
* Add *order::for_each(cursor) tests
* plus some minor fixes
Added:
sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
- copied, changed from r46033, /sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp (contents, props changed)
Removed:
sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 7 +
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 48 +++++++---
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 81 ++++++-----------
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp | 8 -
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp | 178 ++++++++++++++++++++-------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 29 +++++
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp | 47 +++-------
sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp | 27 ------
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 31 ------
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 2
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 8
sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp | 4
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp | 51 +++++++----
sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp | 54 ++++++++---
16 files changed, 285 insertions(+), 294 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -14,6 +14,10 @@
[section TODO]
General:
+* Change recursive *order algorithms such that their argument is root() instead of
+ root().begin() (as is now).
+* Rename parity() (which looks somewhat binary-related) to index (more general for forest
+ trees etc)?
* _Possibly_ move detail/algorithm/cursor/ to detail/cursor/algorithm/ or even just
detail/cursor/ (same for iterator).
* Make *order iterators work with empty subtrees.
@@ -23,6 +27,9 @@
the current depth. (Which, in turn, would make the free-standing forward/back/next/prior
algorithms etc. more or less useless without that piece of extra information and would
only leave us with the iterators to store it.)
+ -> This is going to be done by the RootTracker object, which I personally hate,
+ but I don't see much of a choice for iterative traversal of subtrees other than that
+ (and haven't found any on the Web, either).
* Deprecate shoot()? It's main use was for inorder::end(), which is now root().
Would (binary tree) lower_bound() be possible without shoot()? What would it have to be
like? What would be the implications for balanced_trees? (Especially the lower_bound
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -12,23 +12,25 @@
#ifndef BOOST_TREE_ASCENDING_CURSOR_HPP
#define BOOST_TREE_ASCENDING_CURSOR_HPP
+
+#include <boost/tree/cursor.hpp>
+#include <boost/tree/cursor_helpers.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>
-
#include <stack>
namespace boost {
namespace tree {
-template <class Cursor>
+template <class DescendingCursor>
class ascending_cursor
- : public cursor_facade<ascending_cursor<Cursor>
- , typename Cursor::value_type
+ : public cursor_facade<ascending_cursor<DescendingCursor>
+ , typename cursor_value<DescendingCursor>::type
, random_access_traversal_tag
, bidirectional_traversal_tag
> {
@@ -36,14 +38,14 @@
struct enabler {};
public:
- typedef typename Cursor::value_type value_type;
+ typedef typename DescendingCursor::value_type value_type;
// Container-specific:
- typedef typename Cursor::size_type size_type;
+ typedef typename DescendingCursor::size_type size_type;
- // Cursor-specific
- typedef ascending_cursor<Cursor> cursor;
- typedef ascending_cursor<typename Cursor::const_cursor> const_cursor;
+ // DescendingCursor-specific
+ typedef ascending_cursor<DescendingCursor> cursor;
+ typedef ascending_cursor<typename DescendingCursor::const_cursor> const_cursor;
// Container-specific:
typedef cursor iterator;
@@ -57,7 +59,7 @@
ascending_cursor()
: m_s() {}
- explicit ascending_cursor(Cursor c)
+ explicit ascending_cursor(DescendingCursor c)
{
m_s.push(c); // Subtree root.
}
@@ -66,18 +68,36 @@
ascending_cursor(
ascending_cursor<OtherCursor> const& other
, typename boost::enable_if<
- boost::is_convertible<OtherCursor*, Cursor*>
+ boost::is_convertible<OtherCursor*, DescendingCursor*>
, enabler
>::type = enabler()
)
: m_s(other.m_s) {}
+ struct root_tracker {
+ root_tracker() {}
+ root_tracker& operator++()
+ {
+ return *this;
+ }
+
+ root_tracker& operator--()
+ {
+ return *this;
+ }
+
+ bool is_root(cursor c)
+ {
+ return (c.is_root());
+ }
+ };
+
private:
friend class boost::iterator_core_access;
friend class boost::tree::cursor_core_access;
- std::stack<Cursor> m_s; // pimpl?
+ std::stack<DescendingCursor> m_s; // pimpl?
value_type& dereference() const
{
@@ -141,7 +161,7 @@
m_s.push(m_s.top().end());
}
- // Cursor stuff
+ // DescendingCursor stuff
void up()
{
m_s.pop();
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-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -29,6 +29,8 @@
using detail::node;
using detail::nary_tree_cursor;
+// TODO: Remove shoot() remains (was m_header->m_parent)
+
/**
* @brief A %binary_tree.
* This class models the hierarchy concept, the container concept and the
@@ -164,35 +166,6 @@
}
/**
- * Returns a read/write ("mutable") cursor to the %binary_tree's shoot, i.e.
- * one position past the last (inorder) value.
- */
- cursor shoot()
- {
- return cursor(static_cast<node_base_pointer>(m_header.m_parent),
- m_header.m_parent == &m_header ? 0 : 1);
- }
-
- /**
- * Returns a read-only const_cursor to the %binary_tree's shoot, i.e. one
- * position past the last (inorder) value.
- */
- const_cursor shoot() const
- {
- return cshoot;
- }
-
- /**
- * Returns a read-only const_cursor to the %binary_tree's shoot, i.e. one
- * position past the last (inorder) value.
- */
- const_cursor cshoot() const
- {
- return const_cursor(static_cast<node_base_pointer>(m_header.m_parent),
- m_header.m_parent == &m_header ? 0 : 1);
- }
-
- /**
* Returns a read/write ("mutable") cursor to the first (inorder) value.
*/
cursor inorder_first()
@@ -217,12 +190,11 @@
}
/**
- * Returns true if the %binary_tree is empty. (Thus root() would
- * equal shoot().)
+ * Returns true if the %binary_tree is empty.
*/
bool empty() const
{
- return m_header.m_parent == &m_header;
+ return m_header[1] == &m_header;
}
// Hierarchy-specific
@@ -254,10 +226,6 @@
// Readjust begin
if ((pos == this->inorder_first()))
m_header[1] = p_node;
-
- // Readjust shoot
- if (pos == this->shoot())
- m_header.m_parent = p_node;
return pos.begin();
}
@@ -338,7 +306,7 @@
void rotate(cursor& pos)
{
- //TODO: Take care of shoot/inorder_first pointers!
+ //TODO: Take care of inorder_first pointer!
pos.m_pos = pos.m_node->rotate(pos.m_pos);
pos.m_node = static_cast<node_base_pointer>(pos.m_node->m_parent->m_parent);
}
@@ -361,11 +329,11 @@
m_header[0]->m_parent = &m_header;
m_header[1] = other.m_header[1];
- m_header.m_parent = other.m_header.m_parent;
+ //m_header.m_parent = other.m_header.m_parent;
other.m_header[0] = node_base_type::nil();
other.m_header[1] = &other.m_header;
- other.m_header.m_parent = &other.m_header;
+ //other.m_header.m_parent = &other.m_header;
return;
}
@@ -375,11 +343,11 @@
other.m_header[0]->m_parent = &other.m_header;
other.m_header[1] = m_header[1];
- other.m_header.m_parent = m_header.m_parent;
+ //other.m_header.m_parent = m_header.m_parent;
m_header[0] = node_base_type::nil();
m_header[1] = &m_header;
- m_header.m_parent = &m_header;
+ //m_header.m_parent = &m_header;
return;
}
@@ -419,8 +387,6 @@
void splice(cursor position, binary_tree& x)
{
if (!x.empty()) {
- if (position == shoot()) // Readjust shoot to x's
- m_header.m_parent = x.m_header.m_parent;
if (position == inorder_first()) // Readjust inorder_first to x's
m_header[1] = x.m_header[1];
@@ -433,7 +399,7 @@
}
// Does this splice *p or the subtree?
- // Maybe only *p, as the subtree would require knowledge about of shoot and
+ // Maybe only *p, as the subtree would require knowledge about
// inorder_first in order to remain O(1)
// But what if p has children?... Then this would require some defined
// re-linking (splicing-out, actually) in turn!
@@ -442,15 +408,11 @@
// }
void splice(cursor position, binary_tree& x,
- cursor root, cursor shoot, cursor inorder_first)
+ cursor root, cursor inorder_first)
{
if (!x.empty()) {
- if (shoot == x.shoot())
- x.m_header.m_parent = root.m_node;
if (inorder_first == x.inorder_first())
x.m_header[1] = inorder_first.m_node;
- if (position == shoot()) // Readjust shoot to x's
- m_header.m_parent = shoot.m_node;
if (position == inorder_first()) // Readjust inorder_first to x's
m_header[1] = inorder_first.m_node;
@@ -515,8 +477,6 @@
while (position.parity())
position = position.parent();
- if (position == root())
- position = shoot();
} else {
position = position.begin();
position.m_node->m_parent = p_node->m_parent;
@@ -591,6 +551,25 @@
x.swap(y);
}
+template <class Cursor>
+class binary_tree_root_tracker {
+
+ public:
+ binary_tree_root_tracker() {}
+ binary_tree_root_tracker& operator++()
+ {
+ return *this;
+ }
+ binary_tree_root_tracker& operator--()
+ {
+ return *this;
+ }
+
+ bool is_root(Cursor c)
+ {
+ return (!c.parity() && (c != c.parent().begin()));
+ }
+};
namespace inorder {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_helpers.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -14,16 +14,14 @@
#ifndef BOOST_TREE_CURSOR_HELPERS_HPP
#define BOOST_TREE_CURSOR_HELPERS_HPP
-#include <boost/tree/detail/node/nary.hpp>
-#include <boost/type_traits/integral_constant.hpp>
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/type_traits/integral_constant.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
-#include <boost/iterator/iterator_facade.hpp>
-#include <boost/iterator/iterator_adaptor.hpp>
-
#include <iterator>
#include <utility>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -16,9 +16,10 @@
#ifndef BOOST_TREE_DETAIL_CURSOR_FOREST_HPP
#define BOOST_TREE_DETAIL_CURSOR_FOREST_HPP
-#include <boost/tree/detail/cursor/nary.hpp>
+//#include <boost/tree/detail/cursor/nary.hpp>
#include <boost/tree/cursor.hpp>
+#include <boost/tree/cursor_helpers.hpp>
//#include <boost/type_traits/integral_constant.hpp>
//
@@ -35,75 +36,78 @@
namespace tree {
namespace detail {
-template <class Cursor>
-class forest_cursor;
+using boost::tree::cursor_core_access;
+using boost::iterator_core_access;
-template<class Cursor>
-class const_forest_cursor
- : public cursor_adaptor<const_forest_cursor<Cursor>
- , Cursor const
- , boost::use_default
- , bidirectional_traversal_tag
- , forward_traversal_tag
- > {
- private:
- struct enabler {};
-
- public:
- //TODO: Tidy up typedefs
-
- typedef Cursor base_cursor;
-
- typedef forest_cursor<Cursor> cursor;
- typedef const_forest_cursor<Cursor> const_cursor;
-
- typedef typename cursor_size<base_cursor>::type size_type;
-
- typedef bidirectional_traversal_tag cursor_category;
-
- typedef typename Cursor::metadata_type metadata_type;
-
- // Container-specific:
- typedef cursor iterator; // For (range) concepts' sake, mainly
- typedef const_cursor const_iterator;
-
- // Common iterator facade stuff
- const_forest_cursor()
- : const_forest_cursor::cursor_adaptor_() {}
-
- explicit const_forest_cursor(base_cursor p)
- : const_forest_cursor::cursor_adaptor_(p) {}
-
- template <class OtherCursor>
- const_forest_cursor(
- const_forest_cursor<OtherCursor> const& other
- , typename boost::enable_if<
- boost::is_convertible<OtherCursor*,
- typename Cursor::base_pointer> // is that correct?
- , enabler
- >::type = enabler()
- )
- : const_forest_cursor::cursor_adaptor_(other.base()) {}
-
- operator base_cursor()
- {
- return this->base();
- }
- private:
-
- friend class boost::iterator_core_access;
-
- void increment()
- {
- this->base_reference() = (++this->base_reference()).begin();
- }
-
- void decrement()
- {
- this->base_reference() = --this->base_reference().parent();
- }
-
-};
+//template <class Cursor>
+//class forest_cursor;
+//
+//template<class Cursor>
+//class const_forest_cursor
+// : public cursor_adaptor<const_forest_cursor<Cursor>
+// , Cursor const
+// , boost::use_default
+// , bidirectional_traversal_tag
+// , forward_traversal_tag
+// > {
+// private:
+// struct enabler {};
+//
+// public:
+// //TODO: Tidy up typedefs
+//
+// typedef Cursor base_cursor;
+//
+// typedef forest_cursor<Cursor> cursor;
+// typedef const_forest_cursor<Cursor> const_cursor;
+//
+// typedef typename cursor_size<base_cursor>::type size_type;
+//
+// typedef bidirectional_traversal_tag cursor_category;
+//
+// typedef typename Cursor::metadata_type metadata_type;
+//
+// // Container-specific:
+// typedef cursor iterator; // For (range) concepts' sake, mainly
+// typedef const_cursor const_iterator;
+//
+// // Common iterator facade stuff
+// const_forest_cursor()
+// : const_forest_cursor::cursor_adaptor_() {}
+//
+// explicit const_forest_cursor(base_cursor p)
+// : const_forest_cursor::cursor_adaptor_(p) {}
+//
+// template <class OtherCursor>
+// const_forest_cursor(
+// const_forest_cursor<OtherCursor> const& other
+// , typename boost::enable_if<
+// boost::is_convertible<OtherCursor*,
+// typename Cursor::base_pointer> // is that correct?
+// , enabler
+// >::type = enabler()
+// )
+// : const_forest_cursor::cursor_adaptor_(other.base()) {}
+//
+// operator base_cursor()
+// {
+// return this->base();
+// }
+// private:
+//
+// friend class boost::iterator_core_access;
+//
+// void increment()
+// {
+// (++this->base_reference()).to_begin();
+// }
+//
+// void decrement()
+// {
+// --this->base_reference().to_parent();
+// }
+//
+//};
template <class Cursor>
class forest_cursor
@@ -115,14 +119,14 @@
> {
private:
struct enabler {};
- friend class cursor_core_access;
+
public:
//TODO: Tidy up typedefs
typedef Cursor base_cursor;
typedef forest_cursor<Cursor> cursor;
- typedef const_forest_cursor<Cursor> const_cursor;
+ //typedef const_forest_cursor<Cursor> const_cursor;
//typedef typename cursor_size<base_cursor>::type size_type;
@@ -130,7 +134,7 @@
// Container-specific:
typedef cursor iterator; // For (range) concepts' sake, mainly
- typedef const_cursor const_iterator;
+// typedef const_cursor const_iterator;
// Common iterator facade stuff
forest_cursor()
@@ -157,36 +161,38 @@
private:
- friend class boost::iterator_core_access;
-
+ friend class cursor_core_access;
+ friend class iterator_core_access;
+
void increment()
{
- this->base_reference()= (++this->base_reference()).begin();
+ (++this->base_reference()).to_begin();
}
void decrement()
{
- this->base_reference() = --this->base_reference().parent();
+ --this->base_reference().to_parent();
}
-public:
// Range stuff.
-// cursor begin()
-// {
-// return cursor(this->base_reference().begin());
-// }
+ // left() remains unchanged.
-// const_cursor begin() const
+// void left()
// {
-// return const_cursor(this->base_reference().begin());
-// }
+// this->base_reference().to_begin();
+// }
+ void right()
+ {
+ while (!this->base_reference().to_end().empty());
+ }
+
// Cursor stuff.
- const_cursor parent() const
+ void up()
{
if (!this->base_reference().parity()) {
- return this->base_reference().parent();
+ this->base_reference().to_parent();
}
}
};
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-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -12,15 +12,16 @@
#ifndef BOOST_TREE_DETAIL_CURSOR_NARY_HPP
#define BOOST_TREE_DETAIL_CURSOR_NARY_HPP
+
+#include <boost/tree/cursor_helpers.hpp>
+#include <boost/tree/detail/node/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>
-
-
namespace boost {
namespace tree {
namespace detail {
@@ -97,6 +98,28 @@
base_pointer m_node;
size_type m_pos;
+ class root_tracker {
+ public:
+ root_tracker() : depth(0) {}
+ root_tracker& operator++()
+ {
+ ++depth;
+ return *this;
+ }
+
+ root_tracker& operator--()
+ {
+ --depth;
+ return *this;
+ }
+
+ bool is_root(cursor)
+ {
+ return !depth;
+ }
+ private:
+ int depth;
+ };
private:
friend class iterator_core_access;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -22,7 +22,7 @@
*
* Only works with ascending cursors.
*/
-template <class Cursor>
+template <class Cursor, class RootTracker = typename Cursor::root_tracker>
class iterator
: public boost::iterator_adaptor<iterator<Cursor>
, Cursor
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -20,7 +20,7 @@
namespace boost {
namespace tree {
-
+
namespace inorder {
#include <boost/tree/detail/iterator/_order.hpp>
Deleted: sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
+++ (empty file)
@@ -1,136 +0,0 @@
-// Copyright (c) 2006-2008, Bernhard Reiter
-//
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-/**
- * @file forest.hpp
- * Binary tree based forest implementation
- */
-
-
-#ifndef BOOST_TREE_FOREST_HPP
-#define BOOST_TREE_FOREST_HPP
-
-//#include <boost/tree/cursor.hpp>
-#include <boost/tree/binary_tree.hpp>
-
-#include <boost/tree/detail/cursor/forest.hpp>
-
-#include <boost/test/minimal.hpp>
-
-//#include <memory>
-
-namespace boost {
-namespace tree {
-
-using detail::const_forest_cursor;
-using detail::forest_cursor;
-
-
-/**
- * @brief A %forest.
- * This class models the hierarchy concept, the container concept and the
- * sequence concept. TODO: complete this...
- *
-*/
-template <class T, class Hierarchy = binary_tree<T> >
-class forest {
- typedef forest<T, Hierarchy> self_type;
- public:
- typedef T value_type;
- typedef Hierarchy hierarchy_type;
-
-// typedef node<2, T, typename augmentor::metadata_type, typename balancer::metadata_type> node_type;
-
- typedef typename hierarchy_type::cursor base_cursor;
- typedef typename hierarchy_type::const_cursor base_const_cursor;
-
- typedef forest_cursor<base_cursor> cursor;
- typedef const_forest_cursor<base_const_cursor> const_cursor;
-
-// typedef inorder::iterator<cursor> iterator;
-// typedef inorder::iterator<const_cursor> const_iterator;
-//
-// typedef std::reverse_iterator<iterator> reverse_iterator;
-// typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-
- typedef typename cursor_pointer<cursor>::type pointer;
- typedef typename cursor_reference<cursor>::type reference;
- typedef typename cursor_size<cursor>::type size_type;
- typedef typename cursor_difference<cursor>::type difference_type;
-
-// typedef typename node_traits<node_type>::node_base_type node_base_type;
-// typedef typename node_traits<node_type>::node_pointer node_pointer;
-
-// typedef typename ValAlloc::template rebind<value_type>::other
-// value_allocator_type;
-// typedef typename NodeAlloc::template rebind<node_type>::other
-// node_allocator_type;
-
-// forest()
-// {
-// h.insert(h.root(), );
-// }
-
- explicit forest(Hierarchy const& hier = Hierarchy()) : h(hier)
- { }
-
- bool empty()
- {
- return h.empty();
- }
-
- size_type size() const
- {
- return h.size();
- }
-
-
-
- /**
- * Returns a read/write ("mutable") cursor to the %binary_tree's root.
- */
- cursor root()
- {
- return cursor(h.root());
- }
-
- /**
- * Returns a read-only const_cursor to the %binary_tree's root.
- */
- const_cursor root() const
- {
- return croot();
- }
-
- /**
- * Returns a read-only const_cursor to the %binary_tree's root.
- */
- const_cursor croot() const
- {
- return const_cursor(h.croot());
- }
-
- cursor insert(cursor pos, value_type const& val)
- {
- // TODO: Could we remove the root-checking part if root.parent()
- // returned root? Or don't we even want root?
- base_cursor bc = base_cursor(pos);
- if (bc != h.root())
- bc = bc.parent();
- //if (bc.parity())
- return cursor(h.insert(bc, val));
- }
-
- protected:
- hierarchy_type h;
-
-};
-
-
-} // namespace tree
-} // namespace boost
-
-#endif // BOOST_TREE_FOREST_HPP
Copied: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp (from r46033, /sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp)
==============================================================================
--- /sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -5,18 +5,17 @@
// http://www.boost.org/LICENSE_1_0.txt)
/**
- * @file forest.hpp
+ * @file forest_tree.hpp
* Binary tree based forest implementation
*/
-#ifndef BOOST_TREE_FOREST_HPP
-#define BOOST_TREE_FOREST_HPP
+#ifndef BOOST_TREE_FOREST_TREE_HPP
+#define BOOST_TREE_FOREST_TREE_HPP
-//#include <boost/tree/cursor.hpp>
-#include <boost/tree/binary_tree.hpp>
#include <boost/tree/detail/cursor/forest.hpp>
+#include <boost/tree/binary_tree.hpp>
#include <boost/test/minimal.hpp>
@@ -25,56 +24,40 @@
namespace boost {
namespace tree {
-using detail::const_forest_cursor;
using detail::forest_cursor;
/**
- * @brief A %forest.
- * This class models the hierarchy concept, the container concept and the
- * sequence concept. TODO: complete this...
+ * @brief A %forest_tree.
+ * This class models the hierarchy concept. It is a (binary) tree adaptor,
+ * and a (forest) tree of its own right.
+ * TODO: complete this..
*
*/
template <class T, class Hierarchy = binary_tree<T> >
-class forest {
- typedef forest<T, Hierarchy> self_type;
+class forest_tree {
+ typedef forest_tree<T, Hierarchy> self_type;
public:
typedef T value_type;
typedef Hierarchy hierarchy_type;
-// typedef node<2, T, typename augmentor::metadata_type, typename balancer::metadata_type> node_type;
-
typedef typename hierarchy_type::cursor base_cursor;
typedef typename hierarchy_type::const_cursor base_const_cursor;
typedef forest_cursor<base_cursor> cursor;
- typedef const_forest_cursor<base_const_cursor> const_cursor;
-
-// typedef inorder::iterator<cursor> iterator;
-// typedef inorder::iterator<const_cursor> const_iterator;
-//
-// typedef std::reverse_iterator<iterator> reverse_iterator;
-// typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+ typedef forest_cursor<base_const_cursor> const_cursor;
typedef typename cursor_pointer<cursor>::type pointer;
typedef typename cursor_reference<cursor>::type reference;
typedef typename cursor_size<cursor>::type size_type;
typedef typename cursor_difference<cursor>::type difference_type;
-
-// typedef typename node_traits<node_type>::node_base_type node_base_type;
-// typedef typename node_traits<node_type>::node_pointer node_pointer;
-
-// typedef typename ValAlloc::template rebind<value_type>::other
-// value_allocator_type;
-// typedef typename NodeAlloc::template rebind<node_type>::other
-// node_allocator_type;
-// forest()
+// forest_tree()
// {
// h.insert(h.root(), );
// }
- explicit forest(Hierarchy const& hier = Hierarchy()) : h(hier)
+ explicit forest_tree(Hierarchy const& hier = Hierarchy()) : h(hier)
{ }
bool empty()
@@ -87,8 +70,6 @@
return h.size();
}
-
-
/**
* Returns a read/write ("mutable") cursor to the %binary_tree's root.
*/
@@ -133,4 +114,4 @@
} // namespace tree
} // namespace boost
-#endif // BOOST_TREE_FOREST_HPP
+#endif // BOOST_TREE_FOREST_TREE_HPP
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -114,33 +114,6 @@
{
return const_cursor(h.croot());
}
-
- /**
- * Returns a read/write ("mutable") cursor to the %nary_tree's shoot, i.e.
- * one position past the last (inorder) value.
- */
- cursor shoot()
- {
- return cursor(h.shoot());
- }
-
- /**
- * Returns a read-only const_cursor to the %nary_tree's shoot, i.e.
- * one position past the last (inorder) value.
- */
- const_cursor shoot() const
- {
- return cshoot();
- }
-
- /**
- * Returns a read-only const_cursor to the %nary_tree's shoot, i.e.
- * one position past the last (inorder) value.
- */
- const_cursor cshoot() const
- {
- return const_cursor(h.cshoot());
- }
cursor insert(cursor pos, value_type const& val)
{
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-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -14,7 +14,6 @@
#define BOOST_TREE_NARY_TREE_HPP
#include <boost/tree/cursor.hpp>
-//#include <boost/tree/iterator.hpp>
#include <boost/tree/detail/node/traits.hpp>
#include <boost/tree/detail/cursor/nary.hpp>
@@ -27,7 +26,6 @@
namespace tree {
using detail::node;
-//using detail::const_nary_tree_cursor;
using detail::nary_tree_cursor;
/**
@@ -152,35 +150,6 @@
}
/**
- * Returns a read/write ("mutable") cursor to the %nary_tree's shoot, i.e.
- * one position past the last (inorder) value.
- */
- cursor shoot()
- {
- return cursor(static_cast<node_base_pointer>(m_header.m_parent),
- m_header.m_parent == &m_header ? 0 : 1);
- }
-
- /**
- * Returns a read-only const_cursor to the %nary_tree's shoot, i.e. one
- * position past the last (inorder) value.
- */
- const_cursor shoot() const
- {
- return cshoot;
- }
-
- /**
- * Returns a read-only const_cursor to the %nary_tree's shoot, i.e. one
- * position past the last (inorder) value.
- */
- const_cursor cshoot() const
- {
- return const_cursor(static_cast<node_base_pointer>(m_header.m_parent),
- m_header.m_parent == &m_header ? 0 : 1);
- }
-
- /**
* Returns a read/write ("mutable") cursor to the first (inorder) value.
*/
cursor inorder_first()
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-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -31,7 +31,7 @@
# [ run search_ordered_vector_test.cpp ]
# [ run red_black_tree_test.cpp ]
# [ run treap_test.cpp ]
- [ run forest_test.cpp ]
+ [ run forest_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/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 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -82,8 +82,8 @@
template <class Tree>
void inorder_erase_test_data_tree(Tree& mytree)
{
- typename Tree::cursor c = mytree.shoot();
- --c;
+ typename Tree::cursor c = mytree.root();
+ inorder::back(c);
BOOST_CHECK(*c == 14);
c = c.parent().parent();
@@ -178,8 +178,8 @@
validate_test_data_tree(tree3);
c = tree3.inorder_first();
BOOST_CHECK(*c == 1);
- c = tree3.shoot();
- --c;
+ c = tree3.root();
+ inorder::back(c);
BOOST_CHECK(*c == 14);
destroy_binary_tree(tree2);
Deleted: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
+++ (empty file)
@@ -1,76 +0,0 @@
-// Copyright (c) 2006-2008, Bernhard Reiter
-//
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-#include <boost/tree/forest.hpp>
-
-#include <boost/test/minimal.hpp>
-
-//TODO: Make this a test suite.
-
-void test_forest()
-{
- using namespace boost::tree;
-
- typedef forest<int> tree_type;
- tree_type mytree;
-
- tree_type::cursor c = mytree.root();
- tree_type::base_cursor cur = tree_type::base_cursor(c);
- BOOST_CHECK(!cur.parity());
- cur = cur.parent();
- BOOST_CHECK(cur.parity());
-
- c = mytree.insert(c, 6);
- BOOST_CHECK(*c == 6);
- cur = tree_type::base_cursor(c);
- BOOST_CHECK(*cur == 6);
-
-// BOOST_CHECK(cur == mytree.h.root().begin());
-
- c = mytree.insert(c, 5);
- BOOST_CHECK(*c == 5);
- cur = tree_type::base_cursor(c);
-// BOOST_CHECK(cur == mytree.h.root().begin());
-
- c = mytree.insert(c, 4);
- BOOST_CHECK(*c == 4);
- BOOST_CHECK(c == mytree.root().begin());
-
- cur = tree_type::base_cursor(c);
-// BOOST_CHECK(cur == mytree.h.root().begin());
-
-// ++cur;
-// cur = cur.begin();
-// BOOST_CHECK(*cur == 5);
-// cur = cur.parent();
-// --cur;
-
- ++c;
- BOOST_CHECK(*c == 5);
- ++c;
- BOOST_CHECK(*c == 6);
-// --c;
-// BOOST_CHECK(*c == 5);
-// --c;
-// BOOST_CHECK(*c == 4);
-
-
-// cur = tree_type::base_cursor(c);
-// BOOST_CHECK(*cur == 4);
-// //cur = cur.parent().parent().parent().begin();
-// BOOST_CHECK(*cur == 4);
-
- //BOOST_CHECK(*++c == 5);
-
-}
-
-
-
-int test_main(int, char* [])
-{
- test_forest();
- return 0;
-}
Added: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -0,0 +1,88 @@
+// Copyright (c) 2006-2008, Bernhard Reiter
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#include <boost/tree/forest_tree.hpp>
+
+#include <boost/test/minimal.hpp>
+
+#include "test_tree_traversal_data.hpp"
+
+//TODO: Make this a test suite.
+
+void test_forest_tree()
+{
+ using namespace boost::tree;
+
+ typedef forest_tree<int> tree_type;
+ tree_type mytree;
+
+ tree_type::cursor c = mytree.root();
+ tree_type::base_cursor cur = tree_type::base_cursor(c);
+ BOOST_CHECK(!cur.parity());
+ cur = cur.parent();
+ BOOST_CHECK(cur.parity());
+
+ c = mytree.insert(c, 6);
+ BOOST_CHECK(*c == 6);
+ cur = tree_type::base_cursor(c);
+ BOOST_CHECK(*cur == 6);
+
+// BOOST_CHECK(cur == mytree.h.root().begin());
+
+ c = mytree.insert(c, 5);
+ BOOST_CHECK(*c == 5);
+ cur = tree_type::base_cursor(c);
+// BOOST_CHECK(cur == mytree.h.root().begin());
+
+ c = mytree.insert(c, 4);
+ BOOST_CHECK(*c == 4);
+ BOOST_CHECK(c == mytree.root().begin());
+
+ cur = tree_type::base_cursor(c);
+// BOOST_CHECK(cur == mytree.h.root().begin());
+
+// ++cur;
+// cur = cur.begin();
+// BOOST_CHECK(*cur == 5);
+// cur = cur.parent();
+// --cur;
+
+ ++c;
+ BOOST_CHECK(*c == 5);
+ ++c;
+ BOOST_CHECK(*c == 6);
+// --c;
+// BOOST_CHECK(*c == 5);
+// --c;
+// BOOST_CHECK(*c == 4);
+
+
+// cur = tree_type::base_cursor(c);
+// BOOST_CHECK(*cur == 4);
+// //cur = cur.parent().parent().parent().begin();
+// BOOST_CHECK(*cur == 4);
+
+ //BOOST_CHECK(*++c == 5);
+
+ tree_type forest;
+ //create_test_data_tree(forest);
+ c = forest.insert(forest.root(), 8);
+ BOOST_CHECK(c == forest.root().begin());
+ BOOST_CHECK(*c == 8);
+ c = forest.insert(c, 3);
+ BOOST_CHECK(*c == 3);
+ BOOST_CHECK(*++c == 8);
+// BOOST_CHECK(*forest.root().begin().begin() == 3);
+
+}
+
+
+
+int test_main(int, char* [])
+{
+ test_forest_tree();
+ return 0;
+}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -48,10 +48,6 @@
//
// cur = cur.parent(); //header-cursor(,1) (root)
// BOOST_CHECK(!cur.parity());
-//
-// cur = cur.parent(); //header-parent, should be: ,1: shoot!
-// BOOST_CHECK(cur.parity());
-//
// BOOST_CHECK(searcher_t::iterator(cur) == my_tree.end());
BOOST_CHECK(*c1 = 8);
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -9,6 +9,8 @@
#include <boost/tree/ascending_cursor.hpp>
+#include <boost/lambda/bind.hpp>
+
#include <list>
#include <algorithm>
#include <iterator>
@@ -21,6 +23,16 @@
namespace test {
namespace ORDER {
+template <class Cursor, class Container>
+void test_for_each(Cursor c, Container& cont)
+{
+ boost::tree::ORDER::for_each(
+ c.begin(),
+ boost::lambda::bind(&Container::push_back, &cont, boost::lambda::_1)
+ );
+ test::ORDER::traversal(cont.begin(), cont.end());
+}
+
template <class Cursor, class OutCursor, class Container>
void test_copy(Cursor c, OutCursor& o, Container& cont)
{
@@ -50,13 +62,16 @@
back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
+ test_for_each(c, test_list);
+
+ test_list.clear();
test_copy(c, oc_test_list, test_list);
test_list.clear();
test_transform(c, d, oc_test_list, test_list);
}
-void compare_cursor_to_iterator_traversal(boost::tree::binary_tree<int> const& t) {
+void compare_cursor_to_iterator_traversal(boost::tree::binary_tree<int>::const_cursor cur) {
using boost::tree::ascending_cursor;
@@ -68,46 +83,46 @@
back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
- boost::tree::ORDER::copy(t.croot().begin(), oc_test_list);
+ boost::tree::ORDER::copy(cur.begin(), oc_test_list);
// Are the elements accessed in the correct order?
- BOOST_CHECK(std::equal( boost::tree::ORDER::begin(t.root()),
- boost::tree::ORDER::end(t.root()),
+ BOOST_CHECK(std::equal( boost::tree::ORDER::begin(cur),
+ boost::tree::ORDER::end(cur),
test_list.begin()
));
// Does end() mark the right element?
- BOOST_CHECK(std::distance(boost::tree::ORDER::begin(t.root()),
- boost::tree::ORDER::end(t.root())) ==
+ BOOST_CHECK(std::distance(boost::tree::ORDER::begin(cur),
+ boost::tree::ORDER::end(cur)) ==
std::distance(test_list.begin(), test_list.end()));
// Reverse order.
- BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(t.root()),
- boost::tree::ORDER::rend(t.root()),
+ BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(cur),
+ boost::tree::ORDER::rend(cur),
test_list.rbegin()
));
- BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(t.root()),
- boost::tree::ORDER::rend(t.root())) ==
+ BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(cur),
+ boost::tree::ORDER::rend(cur)) ==
std::distance(test_list.rbegin(), test_list.rend()));
//Now same for iterators wrapped around "explicit stack"-based cursors
- BOOST_CHECK(std::equal( boost::tree::ORDER::begin(ascending_cursor<cursor>(t.root())),
- boost::tree::ORDER::end(ascending_cursor<cursor>(t.root())),
+ BOOST_CHECK(std::equal( boost::tree::ORDER::begin(ascending_cursor<cursor>(cur)),
+ boost::tree::ORDER::end(ascending_cursor<cursor>(cur)),
test_list.begin()
));
- BOOST_CHECK(std::distance(boost::tree::ORDER::begin(ascending_cursor<cursor>(t.root())),
- boost::tree::ORDER::end(ascending_cursor<cursor>(t.root()))) ==
+ BOOST_CHECK(std::distance(boost::tree::ORDER::begin(ascending_cursor<cursor>(cur)),
+ boost::tree::ORDER::end(ascending_cursor<cursor>(cur))) ==
std::distance(test_list.begin(), test_list.end()));
- BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(ascending_cursor<cursor>(t.root())),
- boost::tree::ORDER::rend(ascending_cursor<cursor>(t.root())),
+ BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(ascending_cursor<cursor>(cur)),
+ boost::tree::ORDER::rend(ascending_cursor<cursor>(cur)),
test_list.rbegin()
));
- BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(ascending_cursor<cursor>(t.root())),
- boost::tree::ORDER::rend(ascending_cursor<cursor>(t.root()))) ==
+ BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(ascending_cursor<cursor>(cur)),
+ boost::tree::ORDER::rend(ascending_cursor<cursor>(cur))) ==
std::distance(test_list.rbegin(), test_list.rend()));
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp 2008-06-10 16:31:06 EDT (Tue, 10 Jun 2008)
@@ -42,10 +42,31 @@
#undef ORDER
-void comparisons(binary_tree<int> const& test_tree) {
- test::preorder::compare_cursor_to_iterator_traversal(test_tree);
- test::inorder::compare_cursor_to_iterator_traversal(test_tree);
- test::postorder::compare_cursor_to_iterator_traversal(test_tree);
+template <class Cursor, class Op>
+void underefed_for_each_recursive(Cursor s, Op& f)
+{
+ f(s);
+ if (!s.empty())
+ underefed_for_each_recursive(s.begin(), f);
+ if (!(++s).empty())
+ underefed_for_each_recursive(s.begin(), f);
+}
+
+template <class Cursor, class Op>
+Op underefed_for_each(Cursor s, Op f)
+{
+ f(s);
+ if (!s.empty())
+ underefed_for_each_recursive(s.begin(), f);
+ if (!(++s).empty())
+ underefed_for_each_recursive(s.begin(), f);
+ return f;
+}
+
+void comparisons(binary_tree<int>::const_cursor c) {
+ test::preorder::compare_cursor_to_iterator_traversal(c);
+ test::inorder::compare_cursor_to_iterator_traversal(c);
+ test::postorder::compare_cursor_to_iterator_traversal(c);
return;
}
@@ -59,37 +80,40 @@
binary_tree<int> test_tree2;
binary_tree<int>::cursor c = test_tree2.insert(test_tree2.root(), 8);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
c = test_tree2.insert(c, 3);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
test_tree2.insert(c, 1);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
c = test_tree2.insert(++c, 6);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
test_tree2.insert(c, 4);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
test_tree2.insert(++c, 7);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
c = test_tree2.insert(test_tree2.root().end(), 10);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
c = test_tree2.insert(test_tree2.root().end().end(), 14);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
c = test_tree2.insert(c, 13);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
c = test_tree2.insert(c, 11);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
c = test_tree2.insert(++c, 12);
- comparisons(test_tree2);
+ comparisons(test_tree2.root());
+ //underefed_for_each(test_tree2.root().begin(), comparisons);
+
+ //comparisons(test_tree2.root().begin());
}
int test_main(int, char* [])
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