Boost-Commit mailing page: [Boost-commit] svn:boost r76812 - in sandbox/tree_node/boost: detail tree

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r76812 - in sandbox/tree_node/boost: detail tree_node
From: sponage_at_[hidden]
Date: 2012-01-31 14:22:41

Next message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r76813 - sandbox/gtl/boost/polygon"
Previous message: john_at_[hidden]: "[Boost-commit] svn:boost r76811 - in sandbox/math: boost/math/special_functions libs/math/test"

Author: expaler
Date: 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
New Revision: 76812
URL: http://svn.boost.org/trac/boost/changeset/76812

Log:
Added non-virtual dtors to Boost.TreeNode base class template definitions.
Added:
   sandbox/tree_node/boost/detail/base_pointee.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/associative_node.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/base.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/binary_node.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/breadth_first_desc_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/breadth_first_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/depth_first_desc_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/depth_first_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/in_order_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/nary_node.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/post_order_desc_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/post_order_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/pre_order_desc_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/pre_order_iterator.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/traversal_state.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/typeof.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/with_depth.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/with_position.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/with_red_black_flag.hpp (contents, props changed)

Added: sandbox/tree_node/boost/detail/base_pointee.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/detail/base_pointee.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,46 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_DETAIL_BASE_POINTEE_HPP_INCLUDED
+#define BOOST_DETAIL_BASE_POINTEE_HPP_INCLUDED
+
+namespace boost { namespace detail {
+
+ template <typename Derived>
+ struct base_pointee
+ {
+ typedef Derived const* const_pointer;
+ typedef Derived* pointer;
+
+ const_pointer get_derived() const;
+
+ pointer get_derived();
+
+ protected:
+ ~base_pointee();
+ };
+
+ template <typename Derived>
+ inline typename base_pointee<Derived>::const_pointer
+ base_pointee<Derived>::get_derived() const
+ {
+ return static_cast<const_pointer>(this);
+ }
+
+ template <typename Derived>
+ inline typename base_pointee<Derived>::pointer
+ base_pointee<Derived>::get_derived()
+ {
+ return static_cast<pointer>(this);
+ }
+
+ template <typename Derived>
+ base_pointee<Derived>::~base_pointee()
+ {
+ }
+}} // namespace boost::detail
+
+#endif // BOOST_DETAIL_BASE_POINTEE_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/associative_node.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/associative_node.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,1109 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_ASSOCIATIVE_NODE_HPP_INCLUDED
+#define BOOST_TREE_NODE_ASSOCIATIVE_NODE_HPP_INCLUDED
+
+#include <utility>
+#include <boost/config.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/mpl/apply_wrap.hpp>
+#include <boost/move/move.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/utility/associative_container_gen.hpp>
+#include <boost/utility/has_stable_iters_selector.hpp>
+#ifdef BOOST_MSVC
+#include <boost/utility/is_unordered_selector.hpp>
+#else
+#include <boost/tr1/type_traits.hpp>
+#include <boost/mpl/or.hpp>
+#endif
+#include <boost/tree_node/base.hpp>
+#include <boost/tree_node/depth_first_desc_iterator.hpp>
+#include <boost/tree_node/breadth_first_desc_iterator.hpp>
+#include <boost/tree_node/algorithm/lexicographical_comp_3way.hpp>
+#include <boost/tree_node/algorithm/_detail/skew_equal.hpp>
+#include <boost/tree_node/algorithm/_detail/skew_less.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived
+ , typename Key
+ , typename Data
+ , typename AssociativeContainerSelector
+ >
+ class associative_node_base
+ : public
+ //[reference__associative_node_base__bases
+ tree_node_base<Derived>
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(associative_node_base);
+ typedef typename ::boost::mpl::apply_wrap2<
+ associative_container_gen<
+ AssociativeContainerSelector
+ >
+ , Key
+ , Derived
+ >::type
+ children;
+
+ public:
+ //[reference__associative_node_base__traits
+ struct traits
+ {
+ typedef Key key_type;
+ typedef Data data_type;
+ };
+ //]
+
+ //[reference__associative_node_base__pointer
+ typedef typename tree_node_base<Derived>::pointer
+ pointer;
+ //]
+
+ //[reference__associative_node_base__const_pointer
+ typedef typename tree_node_base<Derived>::const_pointer
+ const_pointer;
+ //]
+
+ //[reference__associative_node_base__iterator
+ typedef // implementation_defined
+ //<-
+ typename children::iterator
+ //->
+ iterator;
+ //]
+
+ //[reference__associative_node_base__const_iterator
+ typedef // implementation_defined
+ //<-
+ typename children::const_iterator
+ //->
+ const_iterator;
+ //]
+
+ private:
+ children _children;
+ pointer _parent;
+ typename traits::data_type _data;
+
+ public:
+ //[reference__associative_node_base__default_ctor
+ associative_node_base();
+ //]
+
+ //[reference__associative_node_base__data_ctor
+ explicit associative_node_base(
+ typename traits::data_type const& data
+ );
+ //]
+
+ //[reference__associative_node_base__copy_ctor
+ associative_node_base(associative_node_base const& copy);
+ //]
+
+ associative_node_base(BOOST_RV_REF(associative_node_base) source);
+
+ associative_node_base&
+ operator=(BOOST_COPY_ASSIGN_REF(associative_node_base) copy);
+
+ associative_node_base&
+ operator=(BOOST_RV_REF(associative_node_base) source);
+
+ protected:
+ ~associative_node_base();
+
+ public:
+ //[reference__associative_node_base__get_data__const
+ typename traits::data_type const& get_data() const;
+ //]
+
+ //[reference__associative_node_base__get_data
+ typename traits::data_type& get_data();
+ //]
+
+ //[reference__associative_node_base__get_parent_ptr__const
+ const_pointer get_parent_ptr() const;
+ //]
+
+ //[reference__associative_node_base__get_parent_ptr
+ pointer get_parent_ptr();
+ //]
+
+ //[reference__associative_node_base__add_child__data
+ iterator
+ add_child(
+ typename traits::key_type const& key
+ , typename traits::data_type const& data
+ );
+ //]
+
+ //[reference__associative_node_base__add_child
+ iterator add_child(typename traits::key_type const& key);
+ //]
+
+ //[reference__associative_node_base__add_child_copy
+ iterator
+ add_child_copy(
+ typename traits::key_type const& key
+ , Derived const& copy
+ );
+ //]
+
+ //[reference__associative_node_base__begin__const
+ const_iterator begin() const;
+ //]
+
+ //[reference__associative_node_base__begin
+ iterator begin();
+ //]
+
+ //[reference__associative_node_base__end__const
+ const_iterator end() const;
+ //]
+
+ //[reference__associative_node_base__end
+ iterator end();
+ //]
+
+ //[reference__associative_node_base__empty
+ bool empty() const;
+ //]
+
+ //[reference__associative_node_base__clear
+ void clear();
+ //]
+
+ //[reference__associative_node_base__find_child__const
+ const_iterator
+ find_child(typename traits::key_type const& key) const;
+ //]
+
+ //[reference__associative_node_base__find_child
+ iterator find_child(typename traits::key_type const& key);
+ //]
+
+ //[reference__associative_node_base__find_children__const
+ ::std::pair<const_iterator,const_iterator>
+ find_children(typename traits::key_type const& key) const;
+ //]
+
+ //[reference__associative_node_base__find_children
+ ::std::pair<iterator,iterator>
+ find_children(typename traits::key_type const& key);
+ //]
+
+ //[reference__associative_node_base__remove_children
+ ::std::size_t remove_children(typename traits::key_type const& key);
+ //]
+
+ private:
+ template <typename Arg>
+ iterator
+ _add_child(
+ typename traits::key_type const& key
+ , Arg const& arg
+ );
+
+ template <typename Arg>
+ iterator
+ _add_child(
+ typename traits::key_type const& key
+ , Arg const& arg
+ , ::boost::mpl::true_
+ );
+
+ template <typename Arg>
+ iterator
+ _add_child(
+ typename traits::key_type const& key
+ , Arg const& arg
+ , ::boost::mpl::false_
+ );
+
+ iterator _add_child_def(typename traits::key_type const& key);
+
+ iterator
+ _add_child_def(
+ typename traits::key_type const& key
+ , ::boost::mpl::true_
+ );
+
+ iterator
+ _add_child_def(
+ typename traits::key_type const& key
+ , ::boost::mpl::false_
+ );
+ // We shouldn't need all of the above private methods, but we do.
+
+ void _initialize(iterator& itr);
+
+ void _clone(associative_node_base const& copy);
+ };
+
+ template <typename Derived, typename K, typename D, typename A>
+ associative_node_base<Derived,K,D,A>::associative_node_base()
+ : _children(), _parent(), _data()
+ {
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ associative_node_base<Derived,K,D,A>::associative_node_base(
+ typename traits::data_type const& data
+ ) : _children(), _parent(), _data(data)
+ {
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ associative_node_base<Derived,K,D,A>::associative_node_base(
+ associative_node_base const& copy
+ ) : _children(), _parent(), _data(copy._data)
+ {
+ _clone(copy);
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ associative_node_base<Derived,K,D,A>::associative_node_base(
+ BOOST_RV_REF(associative_node_base) source
+ ) : _children(::boost::move(source._children))
+ , _parent()
+ , _data(::boost::move(source._data))
+ {
+ this->shallow_update_derived();
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ associative_node_base<Derived,K,D,A>&
+ associative_node_base<Derived,K,D,A>::operator=(
+ BOOST_COPY_ASSIGN_REF(associative_node_base) copy
+ )
+ {
+ if (this != &copy)
+ {
+ associative_node_base twin(copy);
+
+ _children = ::boost::move(twin._children);
+ _data = ::boost::move(twin._data);
+
+ for (iterator itr = begin(); itr != end(); ++itr)
+ {
+ itr->second._parent = this->get_derived();
+ }
+
+ this->shallow_update_derived();
+ }
+
+ return *this;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ associative_node_base<Derived,K,D,A>&
+ associative_node_base<Derived,K,D,A>::operator=(
+ BOOST_RV_REF(associative_node_base) source
+ )
+ {
+ if (this != &source)
+ {
+ _children = ::boost::move(source._children);
+ _data = ::boost::move(source._data);
+
+ for (iterator itr = begin(); itr != end(); ++itr)
+ {
+ itr->second._parent = this->get_derived();
+ }
+
+ this->shallow_update_derived();
+ }
+
+ return *this;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ associative_node_base<Derived,K,D,A>::~associative_node_base()
+ {
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<
+ Derived
+ , K
+ , D
+ , A
+ >::traits::data_type const&
+ associative_node_base<Derived,K,D,A>::get_data() const
+ {
+ return _data;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<
+ Derived
+ , K
+ , D
+ , A
+ >::traits::data_type&
+ associative_node_base<Derived,K,D,A>::get_data()
+ {
+ return _data;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<Derived,K,D,A>::const_pointer
+ associative_node_base<Derived,K,D,A>::get_parent_ptr() const
+ {
+ return _parent;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<Derived,K,D,A>::pointer
+ associative_node_base<Derived,K,D,A>::get_parent_ptr()
+ {
+ return _parent;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::add_child(
+ typename traits::key_type const& key
+ , typename traits::data_type const& data
+ )
+ {
+ iterator result = _add_child(key, data);
+ this->shallow_update_derived();
+ return result;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::add_child(
+ typename traits::key_type const& key
+ )
+ {
+ iterator result = _add_child_def(key);
+ this->shallow_update_derived();
+ return result;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::add_child_copy(
+ typename traits::key_type const& key
+ , Derived const& copy
+ )
+ {
+ iterator result = _add_child(key, copy);
+ this->shallow_update_derived();
+ return result;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<
+ Derived
+ , K
+ , D
+ , A
+ >::const_iterator
+ associative_node_base<Derived,K,D,A>::begin() const
+ {
+ return _children.begin();
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::begin()
+ {
+ return _children.begin();
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<
+ Derived
+ , K
+ , D
+ , A
+ >::const_iterator
+ associative_node_base<Derived,K,D,A>::end() const
+ {
+ return _children.end();
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::end()
+ {
+ return _children.end();
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline bool associative_node_base<Derived,K,D,A>::empty() const
+ {
+ return _children.empty();
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline void associative_node_base<Derived,K,D,A>::clear()
+ {
+ _children.clear();
+ this->shallow_update_derived();
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<Derived,K,D,A>::const_iterator
+ associative_node_base<Derived,K,D,A>::find_child(
+ typename traits::key_type const& key
+ ) const
+ {
+ return _children.find(key);
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::find_child(
+ typename traits::key_type const& key
+ )
+ {
+ return _children.find(key);
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline ::std::pair<
+ typename associative_node_base<Derived,K,D,A>::const_iterator
+ , typename associative_node_base<Derived,K,D,A>::const_iterator
+ >
+ associative_node_base<Derived,K,D,A>::find_children(
+ typename traits::key_type const& key
+ ) const
+ {
+ return _children.equal_range(key);
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline ::std::pair<
+ typename associative_node_base<Derived,K,D,A>::iterator
+ , typename associative_node_base<Derived,K,D,A>::iterator
+ >
+ associative_node_base<Derived,K,D,A>::find_children(
+ typename traits::key_type const& key
+ )
+ {
+ return _children.equal_range(key);
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ ::std::size_t
+ associative_node_base<Derived,K,D,A>::remove_children(
+ typename traits::key_type const& key
+ )
+ {
+ ::std::size_t result = _children.erase(key);
+
+ this->shallow_update_derived();
+ return result;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ template <typename Arg>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::_add_child(
+ typename traits::key_type const& key
+ , Arg const& arg
+ )
+ {
+#ifdef BOOST_MSVC
+ return _add_child(key, arg, ::boost::is_unordered_selector<A>());
+#else
+ return _add_child(
+ key
+ , arg
+ , ::boost::mpl::or_<
+ ::std::tr1::is_same<A,::boost::hash_setS>
+ , ::std::tr1::is_same<A,::boost::hash_mapS>
+ >()
+ );
+#endif
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ template <typename Arg>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::_add_child(
+ typename traits::key_type const& key
+ , Arg const& arg
+ , ::boost::mpl::true_
+ )
+ {
+#ifdef BOOST_MSVC
+ ::std::pair<iterator,bool> p = _children.emplace(
+ ::boost::move(::std::make_pair(key, arg))
+ );
+#else
+ ::std::pair<iterator,bool> p = _children.emplace(key, Derived(arg));
+#endif
+
+ if (p.second)
+ {
+ _initialize(p.first);
+ }
+
+ return p.first;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ template <typename Arg>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::_add_child(
+ typename traits::key_type const& key
+ , Arg const& arg
+ , ::boost::mpl::false_
+ )
+ {
+#ifdef BOOST_MSVC
+ iterator child_itr = _children.emplace(key, arg);
+#else
+ iterator child_itr = _children.emplace(key, Derived(arg));
+#endif
+ _initialize(child_itr);
+ return child_itr;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::_add_child_def(
+ typename traits::key_type const& key
+ )
+ {
+#ifdef BOOST_MSVC
+ return _add_child_def(key, ::boost::is_unordered_selector<A>());
+#else
+ return _add_child_def(
+ key
+ , ::boost::mpl::or_<
+ ::std::tr1::is_same<A,::boost::hash_setS>
+ , ::std::tr1::is_same<A,::boost::hash_mapS>
+ >()
+ );
+#endif
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::_add_child_def(
+ typename traits::key_type const& key
+ , ::boost::mpl::true_
+ )
+ {
+#ifdef BOOST_MSVC
+ ::std::pair<iterator,bool> p = _children.emplace(
+ ::boost::move(::std::make_pair(key, D()))
+ );
+#else
+ ::std::pair<iterator,bool> p = _children.emplace(key, Derived());
+#endif
+
+ if (p.second)
+ {
+ _initialize(p.first);
+ }
+
+ return p.first;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ typename associative_node_base<Derived,K,D,A>::iterator
+ associative_node_base<Derived,K,D,A>::_add_child_def(
+ typename traits::key_type const& key
+ , ::boost::mpl::false_
+ )
+ {
+#ifdef BOOST_MSVC
+ iterator child_itr = _children.emplace(key);
+#else
+ iterator child_itr = _children.emplace(key, Derived());
+#endif
+ _initialize(child_itr);
+ return child_itr;
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ inline void
+ associative_node_base<Derived,K,D,A>::_initialize(iterator& itr)
+ {
+ itr->second._parent = this->get_derived();
+ itr->second.set_position_derived(
+ itr
+ , ::boost::has_stable_iterators_selector<A>()
+ );
+ }
+
+ template <typename Derived, typename K, typename D, typename A>
+ void
+ associative_node_base<Derived,K,D,A>::_clone(
+ associative_node_base const& copy
+ )
+ {
+ pointer p = this->get_derived();
+
+ for (
+ ::boost::tree_node::depth_first_descendant_iterator<
+ Derived const
+ > copy_itr(*copy.get_derived());
+ copy_itr;
+ ++copy_itr
+ )
+ {
+ switch (::boost::tree_node::traversal_state(copy_itr))
+ {
+ case ::boost::tree_node::pre_order_traversal:
+ {
+ p = &p->_add_child(
+ copy_itr->first
+ , copy_itr->second.get_data()
+ )->second;
+ break;
+ }
+
+ case ::boost::tree_node::post_order_traversal:
+ {
+ p = p->_parent;
+ break;
+ }
+ }
+ }
+
+ this->deep_update_derived();
+ }
+}} // namespace boost::tree_node
+
+//[reference__associative_node_base__operator_equals
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ bool
+ operator==(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ bool
+ operator==(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ )
+ {
+ return (
+ (lhs.get_data() == rhs.get_data())
+ && (
+ 0 == ::boost::tree_node::lexicographical_compare_3way(
+ ::boost::tree_node::breadth_first_descendant_iterator<
+ Derived1 const
+ >(*lhs.get_derived())
+ , ::boost::tree_node::breadth_first_descendant_iterator<
+ Derived2 const
+ >(*rhs.get_derived())
+ )
+ )
+ && ::boost::tree_node::_detail::skew_equal(
+ *lhs.get_derived()
+ , *rhs.get_derived()
+ )
+ );
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__associative_node_base__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ bool
+ operator!=(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ inline bool
+ operator!=(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__associative_node_base__operator_less_than
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ bool
+ operator<(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ bool
+ operator<(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ )
+ {
+ if (lhs.get_data() < rhs.get_data())
+ {
+ return true;
+ }
+
+ if (rhs.get_data() < lhs.get_data())
+ {
+ return false;
+ }
+
+ int value = ::boost::tree_node::lexicographical_compare_3way(
+ ::boost::tree_node::breadth_first_descendant_iterator<
+ Derived1 const
+ >(*lhs.get_derived())
+ , ::boost::tree_node::breadth_first_descendant_iterator<
+ Derived2 const
+ >(*rhs.get_derived())
+ );
+
+ if (value < 0)
+ {
+ return true;
+ }
+
+ if (0 < value)
+ {
+ return false;
+ }
+
+ return ::boost::tree_node::_detail::skew_less(
+ *lhs.get_derived()
+ , *rhs.get_derived()
+ );
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__associative_node_base__operator_greater_than
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ bool
+ operator>(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ inline bool
+ operator>(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ )
+ {
+ return rhs < lhs;
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__associative_node_base__operator_less_equal
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ bool
+ operator<=(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ inline bool
+ operator<=(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ )
+ {
+ return !(rhs < lhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__associative_node_base__operator_greater_equal
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ bool
+ operator>=(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename K1
+ , typename D1
+ , typename A1
+ , typename Derived2
+ , typename K2
+ , typename D2
+ , typename A2
+ >
+ inline bool
+ operator>=(
+ associative_node_base<Derived1,K1,D1,A1> const& lhs
+ , associative_node_base<Derived2,K2,D2,A2> const& rhs
+ )
+ {
+ return !(lhs < rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename Key
+ , typename Data
+ , typename AssociativeContainerSelector = ::boost::boost_mapS
+ >
+ class associative_node
+ : public
+ //[reference__associative_node__bases
+ associative_node_base<
+ associative_node<Key,Data,AssociativeContainerSelector>
+ , Key
+ , Data
+ , AssociativeContainerSelector
+ >
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(associative_node);
+
+ //[reference__associative_node__super_t
+ typedef associative_node_base<
+ associative_node
+ , Key
+ , Data
+ , AssociativeContainerSelector
+ >
+ super_t;
+ //]
+
+ public:
+ //[reference__associative_node__traits
+ typedef typename super_t::traits
+ traits;
+ //]
+
+ //[reference__associative_node__pointer
+ typedef typename super_t::pointer
+ pointer;
+ //]
+
+ //[reference__associative_node__const_pointer
+ typedef typename super_t::const_pointer
+ const_pointer;
+ //]
+
+ //[reference__associative_node__iterator
+ typedef typename super_t::iterator
+ iterator;
+ //]
+
+ //[reference__associative_node__const_iterator
+ typedef typename super_t::const_iterator
+ const_iterator;
+ //]
+
+ //[reference__associative_node__default_ctor
+ associative_node();
+ //]
+
+ //[reference__associative_node__data_ctor
+ explicit associative_node(typename traits::data_type const& data);
+ //]
+
+ associative_node(BOOST_RV_REF(associative_node) source);
+
+ associative_node&
+ operator=(BOOST_COPY_ASSIGN_REF(associative_node) copy);
+
+ associative_node& operator=(BOOST_RV_REF(associative_node) source);
+ };
+
+ template <typename K, typename D, typename A>
+ associative_node<K,D,A>::associative_node() : super_t()
+ {
+ }
+
+ template <typename K, typename D, typename A>
+ associative_node<K,D,A>::associative_node(
+ typename traits::data_type const& data
+ ) : super_t(data)
+ {
+ }
+
+ template <typename K, typename D, typename A>
+ associative_node<K,D,A>::associative_node(
+ BOOST_RV_REF(associative_node) source
+ ) : super_t(::boost::move(static_cast<super_t&>(source)))
+ {
+ }
+
+ template <typename K, typename D, typename A>
+ inline associative_node<K,D,A>&
+ associative_node<K,D,A>::operator=(
+ BOOST_COPY_ASSIGN_REF(associative_node) copy
+ )
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ return *this;
+ }
+
+ template <typename K, typename D, typename A>
+ inline associative_node<K,D,A>&
+ associative_node<K,D,A>::operator=(
+ BOOST_RV_REF(associative_node) source
+ )
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ return *this;
+ }
+}} // namespace boost::tree_node
+
+//[reference__associative_node_gen
+namespace boost { namespace tree_node {
+
+ template <typename Selector = ::boost::boost_mapS>
+ struct associative_node_gen
+ {
+ template <typename Derived, typename Key, typename Data>
+ struct apply
+ {
+ typedef associative_node_base<Derived,Key,Data,Selector> type;
+ };
+ };
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_ASSOCIATIVE_NODE_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/base.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/base.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,125 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_BASE_HPP_INCLUDED
+#define BOOST_TREE_NODE_BASE_HPP_INCLUDED
+
+#include <boost/mpl/bool.hpp>
+#include <boost/detail/base_pointee.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <typename Derived>
+ struct tree_node_base
+ : public ::boost::detail::base_pointee<Derived>
+ {
+ typedef typename ::boost::detail::base_pointee<Derived>::pointer
+ pointer;
+ typedef typename ::boost::detail::base_pointee<Derived>::const_pointer
+ const_pointer;
+
+ protected:
+ ~tree_node_base();
+
+ //[reference__tree_node_base__shallow_update_impl
+ void shallow_update_impl();
+ //]
+
+ //[reference__tree_node_base__shallow_update_derived
+ void shallow_update_derived();
+ //]
+
+ //[reference__tree_node_base__deep_update_impl
+ void deep_update_impl();
+ //]
+
+ //[reference__tree_node_base__deep_update_derived
+ void deep_update_derived();
+ //]
+
+ //[reference__tree_node_base__set_position_impl__true
+ template <typename Iterator>
+ void set_position_impl(Iterator position, ::boost::mpl::true_);
+ //]
+
+ //[reference__tree_node_base__set_position_impl__false
+ template <typename Iterator>
+ void set_position_impl(Iterator position, ::boost::mpl::false_);
+ //]
+
+ //[reference__tree_node_base__set_position_derived
+ template <typename Iterator, typename BooleanIntegralConstant>
+ void
+ set_position_derived(
+ Iterator position
+ , BooleanIntegralConstant invalidates_sibling_positions
+ );
+ //]
+ };
+
+ template <typename Derived>
+ tree_node_base<Derived>::~tree_node_base()
+ {
+ }
+
+ template <typename Derived>
+ inline void tree_node_base<Derived>::shallow_update_impl()
+ {
+ }
+
+ template <typename Derived>
+ inline void tree_node_base<Derived>::shallow_update_derived()
+ {
+ this->get_derived()->shallow_update_impl();
+ }
+
+ template <typename Derived>
+ inline void tree_node_base<Derived>::deep_update_impl()
+ {
+ }
+
+ template <typename Derived>
+ inline void tree_node_base<Derived>::deep_update_derived()
+ {
+ this->get_derived()->deep_update_impl();
+ }
+
+ template <typename Derived>
+ template <typename Iterator>
+ inline void
+ tree_node_base<Derived>::set_position_impl(
+ Iterator position
+ , ::boost::mpl::true_
+ )
+ {
+ }
+
+ template <typename Derived>
+ template <typename Iterator>
+ inline void
+ tree_node_base<Derived>::set_position_impl(
+ Iterator position
+ , ::boost::mpl::false_
+ )
+ {
+ }
+
+ template <typename Derived>
+ template <typename Iterator, typename BooleanIntegralConstant>
+ inline void
+ tree_node_base<Derived>::set_position_derived(
+ Iterator position
+ , BooleanIntegralConstant invalidates_sibling_positions
+ )
+ {
+ this->get_derived()->set_position_impl(
+ position
+ , invalidates_sibling_positions
+ );
+ }
+}} // namespace boost::tree_node
+
+#endif // BOOST_TREE_NODE_BASE_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/binary_node.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/binary_node.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,1049 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_BINARY_NODE_HPP_INCLUDED
+#define BOOST_TREE_NODE_BINARY_NODE_HPP_INCLUDED
+
+#include <iterator>
+#include <boost/config.hpp>
+#include <boost/mpl/bool.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/move/move.hpp>
+#include <boost/tree_node/base.hpp>
+#include <boost/tree_node/depth_first_desc_iterator.hpp>
+#include <boost/tree_node/in_order_iterator.hpp>
+#include <boost/tree_node/algorithm/lexicographical_comp_3way.hpp>
+#include <boost/tree_node/algorithm/_detail/skew_equal.hpp>
+#include <boost/tree_node/algorithm/_detail/skew_less.hpp>
+
+namespace boost { namespace tree_node {
+ namespace _detail {
+
+ template <typename Node>
+ class binary_child_iterator
+ {
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public:
+ typedef ::std::bidirectional_iterator_tag iterator_category;
+ typedef Node value_type;
+ typedef ::std::ptrdiff_t difference_type;
+ typedef value_type* pointer;
+ typedef value_type& reference;
+
+// private:
+ pointer _current;
+
+ public:
+ binary_child_iterator();
+
+ binary_child_iterator(pointer const& p, bool p_is_child);
+
+ template <typename N>
+ binary_child_iterator(
+ binary_child_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+ );
+
+ reference operator*() const;
+
+ pointer operator->() const;
+
+ binary_child_iterator& operator++();
+
+ binary_child_iterator operator++(int);
+
+ binary_child_iterator& operator--();
+
+ binary_child_iterator operator--(int);
+
+ private:
+ void _iterate(pointer const& sibling);
+
+ template <typename N1, typename N2>
+ friend bool
+ operator==(
+ binary_child_iterator<N1> const& lhs
+ , binary_child_iterator<N2> const& rhs
+ );
+ };
+
+ template <typename Node>
+ binary_child_iterator<Node>::binary_child_iterator() : _current(0)
+ {
+ }
+
+ template <typename Node>
+ binary_child_iterator<Node>::binary_child_iterator(
+ pointer const& p
+ , bool p_is_child
+ ) : _current(
+ p_is_child
+ ? p
+ : p->get_left_child_ptr()
+ ? p->get_left_child_ptr()
+ : p->get_right_child_ptr()
+ )
+ {
+ }
+
+ template <typename Node>
+ template <typename N>
+ binary_child_iterator<Node>::binary_child_iterator(
+ binary_child_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : _current(other._current)
+ {
+ }
+
+ template <typename Node>
+ inline typename binary_child_iterator<Node>::reference
+ binary_child_iterator<Node>::operator*() const
+ {
+ return *_current;
+ }
+
+ template <typename Node>
+ inline typename binary_child_iterator<Node>::pointer
+ binary_child_iterator<Node>::operator->() const
+ {
+ return _current;
+ }
+
+ template <typename Node>
+ inline binary_child_iterator<Node>&
+ binary_child_iterator<Node>::operator++()
+ {
+ _iterate(_current->get_parent_ptr()->get_right_child_ptr());
+ return *this;
+ }
+
+ template <typename Node>
+ binary_child_iterator<Node> binary_child_iterator<Node>::operator++(int)
+ {
+ binary_child_iterator itr(*this);
+ ++(*this);
+ return itr;
+ }
+
+ template <typename Node>
+ inline binary_child_iterator<Node>&
+ binary_child_iterator<Node>::operator--()
+ {
+ _iterate(_current->get_parent_ptr()->get_left_child_ptr());
+ return *this;
+ }
+
+ template <typename Node>
+ binary_child_iterator<Node> binary_child_iterator<Node>::operator--(int)
+ {
+ binary_child_iterator itr(*this);
+ --(*this);
+ return itr;
+ }
+
+ template <typename Node>
+ inline void binary_child_iterator<Node>::_iterate(pointer const& sibling)
+ {
+ _current = (_current == sibling) ? 0 : sibling;
+ }
+
+ template <typename N1, typename N2>
+ inline bool
+ operator==(
+ binary_child_iterator<N1> const& lhs
+ , binary_child_iterator<N2> const& rhs
+ )
+ {
+ return lhs._current == rhs._current;
+ }
+
+ template <typename N1, typename N2>
+ inline bool
+ operator!=(
+ binary_child_iterator<N1> const& lhs
+ , binary_child_iterator<N2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ } // namespace _detail
+
+ template <typename Derived, typename T>
+ class binary_node_base
+ : public
+ //[reference__binary_node_base__bases
+ tree_node_base<Derived>
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(binary_node_base);
+
+ public:
+ //[reference__binary_node_base__traits
+ struct traits
+ {
+ typedef T data_type;
+ };
+ //]
+
+ //[reference__binary_node_base__pointer
+ typedef typename tree_node_base<Derived>::pointer
+ pointer;
+ //]
+
+ //[reference__binary_node_base__const_pointer
+ typedef typename tree_node_base<Derived>::const_pointer
+ const_pointer;
+ //]
+
+ //[reference__binary_node_base__iterator
+ typedef // implementation_defined
+ //<-
+ _detail::binary_child_iterator<Derived>
+ //->
+ iterator;
+ //]
+
+ //[reference__binary_node_base__const_iterator
+ typedef // implementation_defined
+ //<-
+ _detail::binary_child_iterator<Derived const>
+ //->
+ const_iterator;
+ //]
+
+ private:
+ pointer _left_child;
+ pointer _right_child;
+ pointer _parent;
+ typename traits::data_type _data;
+
+ public:
+ //[reference__binary_node_base__default_ctor
+ binary_node_base();
+ //]
+
+ //[reference__binary_node_base__data_ctor
+ explicit binary_node_base(typename traits::data_type const& data);
+ //]
+
+ //[reference__binary_node_base__copy_ctor
+ binary_node_base(binary_node_base const& copy);
+ //]
+
+ binary_node_base(BOOST_RV_REF(binary_node_base) source);
+
+ binary_node_base&
+ operator=(BOOST_COPY_ASSIGN_REF(binary_node_base) copy);
+
+ binary_node_base& operator=(BOOST_RV_REF(binary_node_base) source);
+
+ protected:
+ ~binary_node_base();
+
+ public:
+ //[reference__binary_node_base__get_data__const
+ typename traits::data_type const& get_data() const;
+ //]
+
+ //[reference__binary_node_base__get_data
+ typename traits::data_type& get_data();
+ //]
+
+ //[reference__binary_node_base__get_parent_ptr__const
+ const_pointer get_parent_ptr() const;
+ //]
+
+ //[reference__binary_node_base__get_parent_ptr
+ pointer get_parent_ptr();
+ //]
+
+ //[reference__binary_node_base__add_left_child__data
+ iterator add_left_child(typename traits::data_type const& data);
+ //]
+
+ //[reference__binary_node_base__add_left_child
+ iterator add_left_child();
+ //]
+
+ //[reference__binary_node_base__add_left_child_copy
+ iterator add_left_child_copy(Derived const& copy);
+ //]
+
+ //[reference__binary_node_base__add_right_child__data
+ iterator add_right_child(typename traits::data_type const& data);
+ //]
+
+ //[reference__binary_node_base__add_right_child
+ iterator add_right_child();
+ //]
+
+ //[reference__binary_node_base__add_right_child_copy
+ iterator add_right_child_copy(Derived const& copy);
+ //]
+
+ //[reference__binary_node_base__get_left_child_ptr__const
+ const_pointer get_left_child_ptr() const;
+ //]
+
+ //[reference__binary_node_base__get_left_child_ptr
+ pointer get_left_child_ptr();
+ //]
+
+ //[reference__binary_node_base__get_right_child_ptr__const
+ const_pointer get_right_child_ptr() const;
+ //]
+
+ //[reference__binary_node_base__get_right_child_ptr
+ pointer get_right_child_ptr();
+ //]
+
+ //[reference__binary_node_base__begin__const
+ const_iterator begin() const;
+ //]
+
+ //[reference__binary_node_base__begin
+ iterator begin();
+ //]
+
+ //[reference__binary_node_base__end__const
+ const_iterator end() const;
+ //]
+
+ //[reference__binary_node_base__end
+ iterator end();
+ //]
+
+ //[reference__binary_node_base__empty
+ bool empty() const;
+ //]
+
+ //[reference__binary_node_base__clear
+ void clear();
+ //]
+
+ //[reference__binary_node_base__rotate_left
+ pointer rotate_left();
+ //]
+
+ //[reference__binary_node_base__rotate_right
+ pointer rotate_right();
+ //]
+
+ //[reference__binary_node_base__remove_left_child
+ void remove_left_child();
+ //]
+
+ //[reference__binary_node_base__remove_right_child
+ void remove_right_child();
+ //]
+
+ private:
+ iterator _add_child(pointer const& child);
+
+ void _clone(binary_node_base const& copy);
+ };
+
+ template <typename Derived, typename T>
+ binary_node_base<Derived,T>::binary_node_base()
+ : _left_child(), _right_child(), _parent(), _data()
+ {
+ }
+
+ template <typename Derived, typename T>
+ binary_node_base<Derived,T>::binary_node_base(
+ typename traits::data_type const& data
+ ) : _left_child(), _right_child(), _parent(), _data(data)
+ {
+ }
+
+ template <typename Derived, typename T>
+ binary_node_base<Derived,T>::binary_node_base(
+ binary_node_base const& copy
+ ) : _left_child(), _right_child(), _parent(), _data(copy._data)
+ {
+ _clone(copy);
+ }
+
+ template <typename Derived, typename T>
+ binary_node_base<Derived,T>::binary_node_base(
+ BOOST_RV_REF(binary_node_base) source
+ ) : _left_child(source._left_child)
+ , _right_child(source._right_child)
+ , _parent()
+ , _data(::boost::move(source._data))
+ {
+ this->shallow_update_derived();
+ source._left_child = source._right_child = 0;
+ }
+
+ template <typename Derived, typename T>
+ binary_node_base<Derived,T>&
+ binary_node_base<Derived,T>::operator=(
+ BOOST_COPY_ASSIGN_REF(binary_node_base) copy
+ )
+ {
+ if (this != &copy)
+ {
+ binary_node_base twin(copy);
+
+ delete _left_child;
+ delete _right_child;
+ _left_child = twin._left_child;
+ _right_child = twin._right_child;
+ _left_child->_parent = _right_child->_parent = this->get_derived();
+ _data = ::boost::move(twin._data);
+ this->shallow_update_derived();
+ twin._left_child = twin._right_child = 0;
+ }
+
+ return *this;
+ }
+
+ template <typename Derived, typename T>
+ inline binary_node_base<Derived,T>&
+ binary_node_base<Derived,T>::operator=(
+ BOOST_RV_REF(binary_node_base) source
+ )
+ {
+ if (this != &source)
+ {
+ _left_child = source._left_child;
+ _right_child = source._right_child;
+ _left_child->_parent = _right_child->_parent = this->get_derived();
+ _data = ::boost::move(source._data);
+ this->shallow_update_derived();
+ source._left_child = source._right_child = 0;
+ }
+
+ return *this;
+ }
+
+ template <typename Derived, typename T>
+ binary_node_base<Derived,T>::~binary_node_base()
+ {
+ delete _left_child;
+ delete _right_child;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::traits::data_type const&
+ binary_node_base<Derived,T>::get_data() const
+ {
+ return _data;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::traits::data_type&
+ binary_node_base<Derived,T>::get_data()
+ {
+ return _data;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::const_pointer
+ binary_node_base<Derived,T>::get_parent_ptr() const
+ {
+ return _parent;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::pointer
+ binary_node_base<Derived,T>::get_parent_ptr()
+ {
+ return _parent;
+ }
+
+ template <typename Derived, typename T>
+ typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::add_left_child(
+ typename traits::data_type const& data
+ )
+ {
+ if (_left_child)
+ {
+ return end();
+ }
+ else
+ {
+ return _add_child(_left_child = new Derived(data));
+ }
+ }
+
+ template <typename Derived, typename T>
+ typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::add_left_child()
+ {
+ if (_left_child)
+ {
+ return end();
+ }
+ else
+ {
+ return _add_child(_left_child = new Derived());
+ }
+ }
+
+ template <typename Derived, typename T>
+ typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::add_left_child_copy(Derived const& copy)
+ {
+ if (_left_child)
+ {
+ return end();
+ }
+ else
+ {
+ return _add_child(_left_child = new Derived(copy));
+ }
+ }
+
+ template <typename Derived, typename T>
+ typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::add_right_child(
+ typename traits::data_type const& data
+ )
+ {
+ if (_right_child)
+ {
+ return end();
+ }
+ else
+ {
+ return _add_child(_right_child = new Derived(data));
+ }
+ }
+
+ template <typename Derived, typename T>
+ typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::add_right_child()
+ {
+ if (_right_child)
+ {
+ return end();
+ }
+ else
+ {
+ return _add_child(_right_child = new Derived());
+ }
+ }
+
+ template <typename Derived, typename T>
+ typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::add_right_child_copy(Derived const& copy)
+ {
+ if (_right_child)
+ {
+ return end();
+ }
+ else
+ {
+ return _add_child(_right_child = new Derived(copy));
+ }
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::const_pointer
+ binary_node_base<Derived,T>::get_left_child_ptr() const
+ {
+ return _left_child;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::pointer
+ binary_node_base<Derived,T>::get_left_child_ptr()
+ {
+ return _left_child;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::const_pointer
+ binary_node_base<Derived,T>::get_right_child_ptr() const
+ {
+ return _right_child;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::pointer
+ binary_node_base<Derived,T>::get_right_child_ptr()
+ {
+ return _right_child;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::const_iterator
+ binary_node_base<Derived,T>::begin() const
+ {
+ return const_iterator(this->get_derived(), false);
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::begin()
+ {
+ return iterator(this->get_derived(), false);
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::const_iterator
+ binary_node_base<Derived,T>::end() const
+ {
+ return const_iterator();
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::end()
+ {
+ return iterator();
+ }
+
+ template <typename Derived, typename T>
+ inline bool binary_node_base<Derived,T>::empty() const
+ {
+ return !_left_child && !_right_child;
+ }
+
+ template <typename Derived, typename T>
+ void binary_node_base<Derived,T>::clear()
+ {
+ delete _left_child;
+ delete _right_child;
+ _left_child = _right_child = 0;
+ this->shallow_update_derived();
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::pointer
+ binary_node_base<Derived,T>::rotate_left()
+ {
+ pointer pivot = _right_child;
+
+ pivot->_parent = _parent;
+ _right_child = pivot->_left_child;
+ _right_child->_parent = pivot->_left_child = this->get_derived();
+
+ if (_parent)
+ {
+ if (_parent->_left_child == this->get_derived())
+ {
+ _parent->_left_child = pivot;
+ }
+ else // if (_parent->_right_child == this->get_derived())
+ {
+ _parent->_right_child = pivot;
+ }
+ }
+
+ _parent = pivot;
+ this->shallow_update_derived();
+ return pivot;
+ }
+
+ template <typename Derived, typename T>
+ inline typename binary_node_base<Derived,T>::pointer
+ binary_node_base<Derived,T>::rotate_right()
+ {
+ pointer pivot = _left_child;
+
+ pivot->_parent = _parent;
+ _left_child = pivot->_right_child;
+ _left_child->_parent = pivot->_right_child = this->get_derived();
+
+ if (_parent)
+ {
+ if (_parent->_right_child == this->get_derived())
+ {
+ _parent->_right_child = pivot;
+ }
+ else // if (_parent->_left_child == this->get_derived())
+ {
+ _parent->_left_child = pivot;
+ }
+ }
+
+ _parent = pivot;
+ this->shallow_update_derived();
+ return pivot;
+ }
+
+ template <typename Derived, typename T>
+ void binary_node_base<Derived,T>::remove_left_child()
+ {
+ delete _left_child;
+ _left_child = 0;
+ this->shallow_update_derived();
+ }
+
+ template <typename Derived, typename T>
+ void binary_node_base<Derived,T>::remove_right_child()
+ {
+ delete _right_child;
+ _right_child = 0;
+ this->shallow_update_derived();
+ }
+
+ template <typename Derived, typename T>
+ typename binary_node_base<Derived,T>::iterator
+ binary_node_base<Derived,T>::_add_child(pointer const& child)
+ {
+ iterator result(child, true);
+
+ result->_parent = this->get_derived();
+ result->set_position_derived(result, ::boost::mpl::false_());
+ this->shallow_update_derived();
+ return result;
+ }
+
+ template <typename Derived, typename T>
+ void binary_node_base<Derived,T>::_clone(binary_node_base const& copy)
+ {
+ pointer p = this->get_derived();
+
+ for (
+ ::boost::tree_node::depth_first_descendant_iterator<
+ Derived const
+ > copy_itr(*copy.get_derived());
+ copy_itr;
+ ++copy_itr
+ )
+ {
+ switch (::boost::tree_node::traversal_state(copy_itr))
+ {
+ case ::boost::tree_node::pre_order_traversal:
+ {
+ if (copy_itr->_parent->_left_child == &*copy_itr)
+ {
+ p->_left_child = new Derived(copy_itr->get_data());
+ p->_left_child->_parent = p;
+ p = p->_left_child;
+ }
+ else // if (copy_itr->_parent->_right_child == &*copy_itr)
+ {
+ p->_right_child = new Derived(copy_itr->get_data());
+ p->_right_child->_parent = p;
+ p = p->_right_child;
+ }
+
+ p->set_position_derived(
+ iterator(p, true)
+ , ::boost::mpl::false_()
+ );
+ break;
+ }
+
+ case ::boost::tree_node::post_order_traversal:
+ {
+ p = p->_parent;
+ break;
+ }
+ }
+ }
+
+ this->deep_update_derived();
+ }
+}} // namespace boost::tree_node
+
+//[reference__binary_node_base__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ bool
+ operator==(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ );
+
+ //<-
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ inline bool
+ operator==(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ )
+ {
+ return (
+ (
+ 0 == ::boost::tree_node::lexicographical_compare_3way(
+ ::boost::tree_node::in_order_iterator<Derived1 const>(
+ *lhs.get_derived()
+ )
+ , ::boost::tree_node::in_order_iterator<Derived2 const>(
+ *rhs.get_derived()
+ )
+ )
+ )
+ && ::boost::tree_node::_detail::skew_equal(
+ *lhs.get_derived()
+ , *rhs.get_derived()
+ )
+ );
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__binary_node_base__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ bool
+ operator!=(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ );
+
+ //<-
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ inline bool
+ operator!=(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__binary_node_base__operator_less_than
+namespace boost { namespace tree_node {
+
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ bool
+ operator<(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ );
+
+ //<-
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ bool
+ operator<(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ )
+ {
+ int value = ::boost::tree_node::lexicographical_compare_3way(
+ ::boost::tree_node::in_order_iterator<Derived1 const>(
+ *lhs.get_derived()
+ )
+ , ::boost::tree_node::in_order_iterator<Derived2 const>(
+ *rhs.get_derived()
+ )
+ );
+
+ if (value < 0)
+ {
+ return true;
+ }
+
+ if (0 < value)
+ {
+ return false;
+ }
+
+ return ::boost::tree_node::_detail::skew_less(
+ *lhs.get_derived()
+ , *rhs.get_derived()
+ );
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__binary_node_base__operator_greater_than
+namespace boost { namespace tree_node {
+
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ bool
+ operator>(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ );
+
+ //<-
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ inline bool
+ operator>(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ )
+ {
+ return rhs < lhs;
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__binary_node_base__operator_less_equal
+namespace boost { namespace tree_node {
+
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ bool
+ operator<=(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ );
+
+ //<-
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ inline bool
+ operator<=(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ )
+ {
+ return !(rhs < lhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__binary_node_base__operator_greater_equal
+namespace boost { namespace tree_node {
+
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ bool
+ operator>=(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ );
+
+ //<-
+ template <typename Derived1, typename T1, typename Derived2, typename T2>
+ inline bool
+ operator>=(
+ binary_node_base<Derived1,T1> const& lhs
+ , binary_node_base<Derived2,T2> const& rhs
+ )
+ {
+ return !(lhs < rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+namespace boost { namespace tree_node {
+
+ template <typename T>
+ class binary_node
+ : public
+ //[reference__binary_node__bases
+ binary_node_base<binary_node<T>,T>
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(binary_node);
+
+ //[reference__binary_node__super_t
+ typedef binary_node_base<binary_node<T>,T> super_t;
+ //]
+
+ public:
+ //[reference__binary_node__traits
+ typedef typename super_t::traits traits;
+ //]
+
+ //[reference__binary_node__pointer
+ typedef typename super_t::pointer pointer;
+ //]
+
+ //[reference__binary_node__const_pointer
+ typedef typename super_t::const_pointer const_pointer;
+ //]
+
+ //[reference__binary_node__iterator
+ typedef typename super_t::iterator iterator;
+ //]
+
+ //[reference__binary_node__const_iterator
+ typedef typename super_t::const_iterator const_iterator;
+ //]
+
+ //[reference__binary_node__default_ctor
+ binary_node();
+ //]
+
+ //[reference__binary_node__data_ctor
+ explicit binary_node(typename traits::data_type const& data);
+ //]
+
+ binary_node(BOOST_RV_REF(binary_node) source);
+
+ binary_node& operator=(BOOST_COPY_ASSIGN_REF(binary_node) copy);
+
+ binary_node& operator=(BOOST_RV_REF(binary_node) source);
+ };
+
+ template <typename T>
+ binary_node<T>::binary_node() : super_t()
+ {
+ }
+
+ template <typename T>
+ binary_node<T>::binary_node(typename traits::data_type const& data)
+ : super_t(data)
+ {
+ }
+
+ template <typename T>
+ binary_node<T>::binary_node(BOOST_RV_REF(binary_node) source)
+ : super_t(::boost::move(static_cast<super_t&>(source)))
+ {
+ }
+
+ template <typename T>
+ inline binary_node<T>&
+ binary_node<T>::operator=(
+ BOOST_COPY_ASSIGN_REF(binary_node) copy
+ )
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ return *this;
+ }
+
+ template <typename T>
+ inline binary_node<T>&
+ binary_node<T>::operator=(BOOST_RV_REF(binary_node) source)
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ return *this;
+ }
+}} // namespace boost::tree_node
+
+//[reference__binary_node_gen
+namespace boost { namespace tree_node {
+
+ struct binary_node_gen
+ {
+ template <typename Derived, typename T>
+ struct apply
+ {
+ typedef binary_node_base<Derived,T> type;
+ };
+ };
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_BINARY_NODE_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/breadth_first_desc_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/breadth_first_desc_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,267 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_BREADTH_FIRST_DESC_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_BREADTH_FIRST_DESC_ITERATOR_HPP_INCLUDED
+
+#include <deque>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+#include <boost/detail/metafunction/container_iterator.hpp>
+
+//[reference__breadth_first_descendant_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class breadth_first_descendant_iterator
+ : public ::boost::iterator_adaptor<
+ breadth_first_descendant_iterator<Node>
+ //, typename Node::iterator or typename Node::const_iterator
+ //<-
+ , typename ::boost::detail::container_iterator<Node>::type
+ //->
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ {
+ //<-
+ typedef typename ::boost::detail::container_iterator<Node>::type
+ child_iterator;
+ typedef ::boost::iterator_adaptor<
+ breadth_first_descendant_iterator<Node>
+ , child_iterator
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ ::std::deque<child_iterator> _queue;
+ traversal_state _state;
+ //->
+
+ public:
+ breadth_first_descendant_iterator();
+
+ explicit breadth_first_descendant_iterator(Node& node);
+
+ template <typename N>
+ breadth_first_descendant_iterator(
+ breadth_first_descendant_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ private:
+ void _push_children(Node&);
+
+ void _pop();
+
+ template <typename Node1, typename Node2>
+ friend bool
+ operator==(
+ breadth_first_descendant_iterator<Node1> const& lhs
+ , breadth_first_descendant_iterator<Node2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename N>
+ breadth_first_descendant_iterator<N>::breadth_first_descendant_iterator()
+ : super_t(), _queue(), _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ breadth_first_descendant_iterator<Node>::breadth_first_descendant_iterator(
+ Node& node
+ ) : super_t(), _queue(), _state(breadth_first_traversal)
+ {
+ _push_children(node);
+ _pop();
+ }
+
+ template <typename Node>
+ template <typename N>
+ breadth_first_descendant_iterator<Node>::breadth_first_descendant_iterator(
+ breadth_first_descendant_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _queue(other._queue.begin(), other._queue.end())
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline breadth_first_descendant_iterator<Node>::operator
+ traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ inline void breadth_first_descendant_iterator<Node>::increment()
+ {
+ _push_children(dereference_iterator(this->base()));
+ _pop();
+ }
+
+ template <typename Node>
+ void breadth_first_descendant_iterator<Node>::_push_children(Node& node)
+ {
+ child_iterator itr_end = node.end();
+
+ for (child_iterator itr = node.begin(); itr != itr_end; ++itr)
+ {
+ _queue.push_back(itr);
+ }
+ }
+
+ template <typename Node>
+ inline void breadth_first_descendant_iterator<Node>::_pop()
+ {
+ if (_queue.empty())
+ {
+ _state = no_traversal;
+ }
+ else
+ {
+ this->base_reference() = _queue.front();
+ _queue.pop_front();
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__breadth_first_descendant_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator==(
+ breadth_first_descendant_iterator<Node1> const& lhs
+ , breadth_first_descendant_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator==(
+ breadth_first_descendant_iterator<Node1> const& lhs
+ , breadth_first_descendant_iterator<Node2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (lhs.base() == rhs.base()) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__breadth_first_descendant_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator!=(
+ breadth_first_descendant_iterator<Node1> const& lhs
+ , breadth_first_descendant_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator!=(
+ breadth_first_descendant_iterator<Node1> const& lhs
+ , breadth_first_descendant_iterator<Node2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_breadth_first_descendant_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ breadth_first_descendant_iterator<Node>
+ make_breadth_first_descendant_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline breadth_first_descendant_iterator<Node>
+ make_breadth_first_descendant_iterator(Node& node)
+ {
+ return breadth_first_descendant_iterator<Node>(node);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__breadth_first_iterate_descendants
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename UnaryFunction>
+ void breadth_first_iterate_descendants(Node& node, UnaryFunction function);
+
+ //<-
+ template <typename Node, typename UnaryFunction>
+ void breadth_first_iterate_descendants(Node& node, UnaryFunction function)
+ {
+ for (breadth_first_descendant_iterator<Node> itr(node); itr; ++itr)
+ {
+ function(*itr);
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_BREADTH_FIRST_DESC_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/breadth_first_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/breadth_first_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,250 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_BREADTH_FIRST_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_BREADTH_FIRST_ITERATOR_HPP_INCLUDED
+
+#include <deque>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+#include <boost/detail/metafunction/container_iterator.hpp>
+
+//[reference__breadth_first_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class breadth_first_iterator
+ : public ::boost::iterator_adaptor<
+ breadth_first_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ {
+ //<-
+ typedef ::boost::iterator_adaptor<
+ breadth_first_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ ::std::deque<Node*> _queue;
+ traversal_state _state;
+ //->
+
+ public:
+ breadth_first_iterator();
+
+ explicit breadth_first_iterator(Node& node);
+
+ template <typename N>
+ breadth_first_iterator(
+ breadth_first_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ private:
+ void _push_children(Node&);
+
+ void _pop();
+
+ template <typename Node1, typename Node2>
+ friend bool
+ operator==(
+ breadth_first_iterator<Node1> const& lhs
+ , breadth_first_iterator<Node2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename Node>
+ breadth_first_iterator<Node>::breadth_first_iterator()
+ : super_t(), _queue(), _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ breadth_first_iterator<Node>::breadth_first_iterator(Node& node)
+ : super_t(&node)
+ , _queue()
+ , _state(breadth_first_traversal)
+ {
+ }
+
+ template <typename Node>
+ template <typename N>
+ breadth_first_iterator<Node>::breadth_first_iterator(
+ breadth_first_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _queue(other._queue.begin(), other._queue.end())
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline breadth_first_iterator<Node>::operator traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ void breadth_first_iterator<Node>::increment()
+ {
+ typedef typename ::boost::detail::container_iterator<Node>::type
+ child_iterator;
+
+ child_iterator itr_end = this->base()->end();
+
+ for (child_iterator itr = this->base()->begin(); itr != itr_end; ++itr)
+ {
+ _queue.push_back(&dereference_iterator(itr));
+ }
+
+ if (_queue.empty())
+ {
+ _state = no_traversal;
+ }
+ else
+ {
+ this->base_reference() = _queue.front();
+ _queue.pop_front();
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__breadth_first_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator==(
+ breadth_first_iterator<Node1> const& lhs
+ , breadth_first_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator==(
+ breadth_first_iterator<Node1> const& lhs
+ , breadth_first_iterator<Node2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (lhs.base() == rhs.base()) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__breadth_first_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator!=(
+ breadth_first_iterator<Node1> const& lhs
+ , breadth_first_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator!=(
+ breadth_first_iterator<Node1> const& lhs
+ , breadth_first_iterator<Node2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_breadth_first_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ breadth_first_iterator<Node> make_breadth_first_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline breadth_first_iterator<Node> make_breadth_first_iterator(Node& node)
+ {
+ return breadth_first_iterator<Node>(node);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__breadth_first_iterate
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename UnaryFunction>
+ void breadth_first_iterate(Node& node, UnaryFunction function);
+
+ //<-
+ template <typename Node, typename UnaryFunction>
+ void breadth_first_iterate(Node& node, UnaryFunction function)
+ {
+ for (breadth_first_iterator<Node> itr(node); itr; ++itr)
+ {
+ function(*itr);
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_BREADTH_FIRST_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/depth_first_desc_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/depth_first_desc_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,313 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_DEPTH_FIRST_DESC_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_DEPTH_FIRST_DESC_ITERATOR_HPP_INCLUDED
+
+#include <deque>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+#include <boost/detail/metafunction/container_iterator.hpp>
+
+//[reference__depth_first_descendant_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class depth_first_descendant_iterator
+ : public ::boost::iterator_adaptor<
+ depth_first_descendant_iterator<Node>
+ //, typename Node::iterator or typename Node::const_iterator
+ //<-
+ , typename ::boost::detail::container_iterator<Node>::type
+ //->
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ {
+ //<-
+ typedef typename ::boost::detail::container_iterator<Node>::type
+ child_iterator;
+ typedef ::boost::iterator_adaptor<
+ depth_first_descendant_iterator<Node>
+ , child_iterator
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ ::std::deque<Node*> _node_stack;
+ ::std::deque<child_iterator> _itr_stack;
+ Node* _node_ptr;
+ traversal_state _state;
+ //->
+
+ public:
+ depth_first_descendant_iterator();
+
+ explicit depth_first_descendant_iterator(Node& node);
+
+ template <typename N>
+ depth_first_descendant_iterator(
+ depth_first_descendant_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ template <typename Node1, typename Node2>
+ friend bool
+ operator==(
+ depth_first_descendant_iterator<Node1> const& lhs
+ , depth_first_descendant_iterator<Node2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename Node>
+ depth_first_descendant_iterator<Node>::depth_first_descendant_iterator()
+ : super_t()
+ , _node_stack()
+ , _itr_stack()
+ , _node_ptr()
+ , _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ depth_first_descendant_iterator<Node>::depth_first_descendant_iterator(
+ Node& node
+ ) : super_t()
+ , _node_stack()
+ , _itr_stack()
+ , _node_ptr(&node)
+ , _state(pre_order_traversal)
+ {
+ _itr_stack.push_back(node.begin());
+ increment();
+ }
+
+ template <typename Node>
+ template <typename N>
+ depth_first_descendant_iterator<Node>::depth_first_descendant_iterator(
+ depth_first_descendant_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _node_stack(other._node_stack.begin(), other._node_stack.end())
+ , _itr_stack(other._itr_stack.begin(), other._itr_stack.end())
+ , _node_ptr(other._node_ptr)
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline depth_first_descendant_iterator<Node>::operator
+ traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ void depth_first_descendant_iterator<Node>::increment()
+ {
+ if (_state == post_order_traversal)
+ {
+ if (_node_stack.empty())
+ {
+ _state = no_traversal;
+ _itr_stack.clear();
+ }
+ else
+ {
+ _itr_stack.pop_back();
+ _node_ptr = _node_stack.back();
+ _node_stack.pop_back();
+
+ if (++this->base_reference() == _node_ptr->end())
+ {
+ if (_node_stack.empty())
+ {
+ _itr_stack.clear();
+ _state = no_traversal;
+ }
+ else
+ {
+ child_iterator itr = _itr_stack.back();
+
+ _itr_stack.pop_back();
+
+ if (!_itr_stack.empty())
+ {
+ this->base_reference() = _itr_stack.back();
+ }
+
+ _itr_stack.push_back(itr);
+ _state = post_order_traversal;
+ }
+ }
+ else
+ {
+ _itr_stack.pop_back();
+ _node_stack.push_back(_node_ptr);
+ _itr_stack.push_back(this->base());
+ _node_ptr = &dereference_iterator(this->base());
+ _state = pre_order_traversal;
+ _itr_stack.push_back(_node_ptr->begin());
+ }
+ }
+ }
+ else
+ {
+ child_iterator& itr = _itr_stack.back();
+
+ if (itr == _node_ptr->end())
+ {
+ _state = (
+ _node_stack.empty() ? no_traversal : post_order_traversal
+ );
+ }
+ else
+ {
+ _node_stack.push_back(_node_ptr);
+ _node_ptr = &dereference_iterator(
+ this->base_reference() = itr
+ );
+ _state = pre_order_traversal;
+ _itr_stack.push_back(_node_ptr->begin());
+ }
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__depth_first_descendant_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator==(
+ depth_first_descendant_iterator<Node1> const& lhs
+ , depth_first_descendant_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator==(
+ depth_first_descendant_iterator<Node1> const& lhs
+ , depth_first_descendant_iterator<Node2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (lhs.base() == rhs.base()) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__depth_first_descendant_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator!=(
+ depth_first_descendant_iterator<Node1> const& lhs
+ , depth_first_descendant_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator!=(
+ depth_first_descendant_iterator<Node1> const& lhs
+ , depth_first_descendant_iterator<Node2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_depth_first_descendant_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ depth_first_descendant_iterator<Node>
+ make_depth_first_descendant_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline depth_first_descendant_iterator<Node>
+ make_depth_first_descendant_iterator(Node& node)
+ {
+ return depth_first_descendant_iterator<Node>(node);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__depth_first_iterate_descendants
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename BinaryFunction>
+ void depth_first_iterate_descendants(Node& node, BinaryFunction function);
+
+ //<-
+ template <typename Node, typename BinaryFunction>
+ void depth_first_iterate_descendants(Node& node, BinaryFunction function)
+ {
+ for (depth_first_iterator<Node> itr(node); itr; ++itr)
+ {
+ function(*itr, traversal_state(itr));
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_DEPTH_FIRST_DESC_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/depth_first_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/depth_first_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,299 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_DEPTH_FIRST_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_DEPTH_FIRST_ITERATOR_HPP_INCLUDED
+
+#include <deque>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+#include <boost/detail/metafunction/container_iterator.hpp>
+
+//[reference__depth_first_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class depth_first_iterator
+ : public ::boost::iterator_adaptor<
+ depth_first_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ {
+ //<-
+ typedef typename ::boost::detail::container_iterator<Node>::type
+ child_iterator;
+ typedef ::boost::iterator_adaptor<
+ depth_first_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ ::std::deque<Node*> _node_stack;
+ ::std::deque<child_iterator> _itr_stack;
+ child_iterator _current_itr;
+ traversal_state _state;
+ //->
+
+ public:
+ depth_first_iterator();
+
+ explicit depth_first_iterator(Node& node);
+
+ template <typename N>
+ depth_first_iterator(
+ depth_first_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ template <typename Node1, typename Node2>
+ friend bool
+ operator==(
+ depth_first_iterator<Node1> const& lhs
+ , depth_first_iterator<Node2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename Node>
+ depth_first_iterator<Node>::depth_first_iterator()
+ : super_t()
+ , _node_stack()
+ , _itr_stack()
+ , _current_itr()
+ , _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ depth_first_iterator<Node>::depth_first_iterator(Node& node)
+ : super_t(&node)
+ , _node_stack()
+ , _itr_stack()
+ , _current_itr()
+ , _state(pre_order_traversal)
+ {
+ _itr_stack.push_back(node.begin());
+ }
+
+ template <typename Node>
+ template <typename N>
+ depth_first_iterator<Node>::depth_first_iterator(
+ depth_first_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _node_stack(other._node_stack.begin(), other._node_stack.end())
+ , _itr_stack(other._itr_stack.begin(), other._itr_stack.end())
+ , _current_itr(other._current_itr)
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline depth_first_iterator<Node>::operator traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ void depth_first_iterator<Node>::increment()
+ {
+ if (_state == post_order_traversal)
+ {
+ _itr_stack.pop_back();
+
+ if (_node_stack.empty())
+ {
+ _state = no_traversal;
+ _itr_stack.clear();
+ }
+ else
+ {
+ this->base_reference() = _node_stack.back();
+ _node_stack.pop_back();
+
+ if (++_current_itr == this->base()->end())
+ {
+ child_iterator itr = _itr_stack.back();
+
+ _itr_stack.pop_back();
+
+ if (!_itr_stack.empty())
+ {
+ _current_itr = _itr_stack.back();
+ }
+
+ _itr_stack.push_back(itr);
+ _state = post_order_traversal;
+ }
+ else
+ {
+ _itr_stack.pop_back();
+ _node_stack.push_back(this->base());
+ _itr_stack.push_back(_current_itr);
+ this->base_reference() = &dereference_iterator(
+ _current_itr
+ );
+ _state = pre_order_traversal;
+ _itr_stack.push_back(this->base()->begin());
+ }
+ }
+ }
+ else
+ {
+ child_iterator& itr = _itr_stack.back();
+
+ if (itr == this->base()->end())
+ {
+ _state = post_order_traversal;
+ }
+ else
+ {
+ _node_stack.push_back(this->base());
+ this->base_reference() = &dereference_iterator(
+ _current_itr = itr
+ );
+ _state = pre_order_traversal;
+ _itr_stack.push_back(this->base()->begin());
+ }
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__depth_first_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator==(
+ depth_first_iterator<Node1> const& lhs
+ , depth_first_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator==(
+ depth_first_iterator<Node1> const& lhs
+ , depth_first_iterator<Node2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (lhs.base() == rhs.base()) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__depth_first_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator!=(
+ depth_first_iterator<Node1> const& lhs
+ , depth_first_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator!=(
+ depth_first_iterator<Node1> const& lhs
+ , depth_first_iterator<Node2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_depth_first_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ depth_first_iterator<Node> make_depth_first_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline depth_first_iterator<Node> make_depth_first_iterator(Node& node)
+ {
+ return depth_first_iterator<Node>(node);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__depth_first_iterate
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename BinaryFunction>
+ void depth_first_iterate(Node& node, BinaryFunction function);
+
+ //<-
+ template <typename Node, typename BinaryFunction>
+ void depth_first_iterate(Node& node, BinaryFunction function)
+ {
+ for (depth_first_iterator<Node> itr(node); itr; ++itr)
+ {
+ function(*itr, traversal_state(itr));
+ }
+ }
+ //->
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_DEPTH_FIRST_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/in_order_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/in_order_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,346 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_IN_ORDER_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_IN_ORDER_ITERATOR_HPP_INCLUDED
+
+#include <iterator>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+
+//[reference__in_order_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class in_order_iterator
+ : public ::boost::iterator_adaptor<
+ in_order_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::bidirectional_traversal_tag
+ >
+ {
+ //<-
+ typedef ::boost::iterator_adaptor<
+ in_order_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::bidirectional_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ Node* _root_parent_ptr;
+ traversal_state _state;
+ //->
+
+ public:
+ in_order_iterator();
+
+ explicit in_order_iterator(Node& node, bool start_left = true);
+
+ template <typename N>
+ in_order_iterator(
+ in_order_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ void decrement();
+
+ template <typename N1, typename N2>
+ friend bool
+ operator==(
+ in_order_iterator<N1> const& lhs
+ , in_order_iterator<N2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename Node>
+ in_order_iterator<Node>::in_order_iterator()
+ : super_t(), _root_parent_ptr(), _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ in_order_iterator<Node>::in_order_iterator(Node& node, bool start_left)
+ : super_t(&node)
+ , _root_parent_ptr(node.get_parent_ptr())
+ , _state(in_order_traversal)
+ {
+ if (start_left)
+ {
+ while (this->base()->get_left_child_ptr())
+ {
+ this->base_reference() = this->base()->get_left_child_ptr();
+ }
+ }
+ else
+ {
+ while (this->base()->get_right_child_ptr())
+ {
+ this->base_reference() = this->base()->get_right_child_ptr();
+ }
+ }
+ }
+
+ template <typename Node>
+ template <typename N>
+ in_order_iterator<Node>::in_order_iterator(
+ in_order_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _root_parent_ptr(other._root_parent_ptr)
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline in_order_iterator<Node>::operator traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ void in_order_iterator<Node>::increment()
+ {
+ Node* node_ptr = this->base()->get_right_child_ptr();
+
+ if (node_ptr)
+ {
+ while (node_ptr->get_left_child_ptr())
+ {
+ node_ptr = node_ptr->get_left_child_ptr();
+ }
+
+ this->base_reference() = node_ptr;
+ return;
+ }
+
+ node_ptr = this->base();
+
+ for (
+ Node* next_ptr = node_ptr->get_parent_ptr();
+ next_ptr != _root_parent_ptr;
+ next_ptr = next_ptr->get_parent_ptr()
+ )
+ {
+ if (node_ptr == next_ptr->get_left_child_ptr())
+ {
+ this->base_reference() = next_ptr;
+ return;
+ }
+
+ node_ptr = next_ptr;
+ }
+
+ this->base_reference() = _root_parent_ptr = 0;
+ _state = no_traversal;
+ }
+
+ template <typename Node>
+ void in_order_iterator<Node>::decrement()
+ {
+ Node* node_ptr = this->base()->get_left_child_ptr();
+
+ if (node_ptr)
+ {
+ while (node_ptr->get_right_child_ptr())
+ {
+ node_ptr = node_ptr->get_right_child_ptr();
+ }
+
+ this->base_reference() = node_ptr;
+ return;
+ }
+
+ node_ptr = this->base();
+
+ for (
+ Node* next_ptr = node_ptr->get_parent_ptr();
+ next_ptr != _root_parent_ptr;
+ next_ptr = next_ptr->get_parent_ptr()
+ )
+ {
+ if (node_ptr == next_ptr->get_right_child_ptr())
+ {
+ this->base_reference() = next_ptr;
+ return;
+ }
+
+ node_ptr = next_ptr;
+ }
+
+ this->base_reference() = _root_parent_ptr = 0;
+ _state = no_traversal;
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__in_order_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename N1, typename N2>
+ bool
+ operator==(
+ in_order_iterator<N1> const& lhs
+ , in_order_iterator<N2> const& rhs
+ );
+
+ //<-
+ template <typename N1, typename N2>
+ inline bool
+ operator==(
+ in_order_iterator<N1> const& lhs
+ , in_order_iterator<N2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (lhs.base() == rhs.base()) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__in_order_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename N1, typename N2>
+ bool
+ operator!=(
+ in_order_iterator<N1> const& lhs
+ , in_order_iterator<N2> const& rhs
+ );
+
+ //<-
+ template <typename N1, typename N2>
+ inline bool
+ operator!=(
+ in_order_iterator<N1> const& lhs
+ , in_order_iterator<N2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_in_order_forward_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ in_order_iterator<Node> make_in_order_forward_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline in_order_iterator<Node>
+ make_in_order_forward_iterator(Node& node)
+ {
+ return in_order_iterator<Node>(node, true);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_in_order_reverse_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ in_order_iterator<Node> make_in_order_reverse_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline in_order_iterator<Node>
+ make_in_order_reverse_iterator(Node& node)
+ {
+ return in_order_iterator<Node>(node, false);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__in_order_iterate_forward
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename UnaryFunction>
+ void in_order_iterate_forward(Node& node, UnaryFunction function);
+
+ //<-
+ template <typename Node, typename UnaryFunction>
+ void in_order_iterate_forward(Node& node, UnaryFunction function)
+ {
+ for (in_order_iterator<Node> itr(node, true); itr; ++itr)
+ {
+ function(*itr);
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__in_order_iterate_reverse
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename UnaryFunction>
+ void in_order_iterate_reverse(Node& node, UnaryFunction function);
+
+ //<-
+ template <typename Node, typename UnaryFunction>
+ void in_order_iterate_reverse(Node& node, UnaryFunction function)
+ {
+ for (in_order_iterator<Node> itr(node, false); itr; --itr)
+ {
+ function(*itr);
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_IN_ORDER_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/nary_node.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/nary_node.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,907 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_NARY_NODE_HPP_INCLUDED
+#define BOOST_TREE_NODE_NARY_NODE_HPP_INCLUDED
+
+#include <utility>
+#include <boost/mpl/bool.hpp>
+#include <boost/move/move.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/utility/container_gen.hpp>
+#include <boost/utility/has_stable_iters_selector.hpp>
+#include <boost/utility/is_associative_selector.hpp>
+#include <boost/utility/is_unordered_selector.hpp>
+#include <boost/tree_node/base.hpp>
+#include <boost/tree_node/depth_first_desc_iterator.hpp>
+#include <boost/tree_node/breadth_first_iterator.hpp>
+#include <boost/tree_node/algorithm/lexicographical_comp_3way.hpp>
+#include <boost/tree_node/algorithm/_detail/skew_equal.hpp>
+#include <boost/tree_node/algorithm/_detail/skew_less.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <typename Derived, typename T, typename Selector>
+ class nary_node_base
+ : public
+ //[reference__nary_node_base__bases
+ tree_node_base<Derived>
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(nary_node_base);
+ typedef typename ::boost::container_gen<Selector,Derived>::type
+ children;
+
+ public:
+ //[reference__nary_node_base__traits
+ struct traits
+ {
+ typedef T data_type;
+ };
+ //]
+
+ //[reference__nary_node_base__pointer
+ typedef typename tree_node_base<Derived>::pointer
+ pointer;
+ //]
+
+ //[reference__nary_node_base__const_pointer
+ typedef typename tree_node_base<Derived>::const_pointer
+ const_pointer;
+ //]
+
+ //[reference__nary_node_base__iterator
+ typedef // implementation_defined
+ //<-
+ typename children::iterator
+ //->
+ iterator;
+ //]
+
+ //[reference__nary_node_base__const_iterator
+ typedef // implementation_defined
+ //<-
+ typename children::const_iterator
+ //->
+ const_iterator;
+ //]
+
+ private:
+ children _children;
+ pointer _parent;
+ typename traits::data_type _data;
+
+ public:
+ //[reference__nary_node_base__default_ctor
+ nary_node_base();
+ //]
+
+ //[reference__nary_node_base__data_ctor
+ explicit nary_node_base(typename traits::data_type const& data);
+ //]
+
+ //[reference__nary_node_base__copy_ctor
+ nary_node_base(nary_node_base const& copy);
+ //]
+
+ nary_node_base(BOOST_RV_REF(nary_node_base) source);
+
+ nary_node_base& operator=(BOOST_COPY_ASSIGN_REF(nary_node_base) copy);
+
+ nary_node_base& operator=(BOOST_RV_REF(nary_node_base) source);
+
+ protected:
+ ~nary_node_base();
+
+ public:
+ //[reference__nary_node_base__get_data__const
+ typename traits::data_type const& get_data() const;
+ //]
+
+ //[reference__nary_node_base__get_data
+ typename traits::data_type& get_data();
+ //]
+
+ //[reference__nary_node_base__get_parent_ptr__const
+ const_pointer get_parent_ptr() const;
+ //]
+
+ //[reference__nary_node_base__get_parent_ptr
+ pointer get_parent_ptr();
+ //]
+
+ //[reference__nary_node_base__add_child__data
+ iterator add_child(typename traits::data_type const& data);
+ //]
+
+ //[reference__nary_node_base__add_child
+ iterator add_child();
+ //]
+
+ //[reference__nary_node_base__add_child_copy
+ iterator add_child_copy(Derived const& copy);
+ //]
+
+ //[reference__nary_node_base__begin__const
+ const_iterator begin() const;
+ //]
+
+ //[reference__nary_node_base__begin
+ iterator begin();
+ //]
+
+ //[reference__nary_node_base__end__const
+ const_iterator end() const;
+ //]
+
+ //[reference__nary_node_base__end
+ iterator end();
+ //]
+
+ //[reference__nary_node_base__empty
+ bool empty() const;
+ //]
+
+ //[reference__nary_node_base__clear
+ void clear();
+ //]
+
+ private:
+ template <typename Arg>
+ iterator _add_child(Arg& arg);
+
+ template <typename Arg>
+ iterator _add_child(Arg& arg, ::boost::mpl::true_);
+
+ template <typename Arg>
+ iterator _add_child(Arg& arg, ::boost::mpl::false_);
+
+ template <typename Arg>
+ iterator _add_child_assoc(Arg& arg, ::boost::mpl::true_);
+
+ template <typename Arg>
+ iterator _add_child_assoc(Arg& arg, ::boost::mpl::false_);
+
+ iterator _add_child_def();
+
+ iterator _add_child_def(::boost::mpl::true_);
+
+ iterator _add_child_def(::boost::mpl::false_);
+
+ iterator _add_child_def_assoc(::boost::mpl::true_);
+
+ iterator _add_child_def_assoc(::boost::mpl::false_);
+ // We shouldn't need all of the above private methods, but we do.
+
+ void _initialize(iterator& to_child);
+
+ void _clone(nary_node_base const& copy);
+ };
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>::nary_node_base()
+ : _children(), _parent(), _data()
+ {
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>::nary_node_base(
+ typename traits::data_type const& data
+ ) : _children(), _parent(), _data(data)
+ {
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>::nary_node_base(
+ nary_node_base const& copy
+ ) : _children(), _parent(), _data(copy._data)
+ {
+ _clone(copy);
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>::nary_node_base(
+ BOOST_RV_REF(nary_node_base) source
+ ) : _children(::boost::move(source._children))
+ , _parent()
+ , _data(::boost::move(source._data))
+ {
+ this->shallow_update_derived();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>&
+ nary_node_base<Derived,T,Selector>::operator=(
+ BOOST_COPY_ASSIGN_REF(nary_node_base) copy
+ )
+ {
+ if (this != &copy)
+ {
+ nary_node_base twin(copy);
+
+ _children = ::boost::move(twin._children);
+ _data = ::boost::move(twin._data);
+
+ for (iterator itr = begin(); itr != end(); ++itr)
+ {
+ itr->_parent = this->get_derived();
+ }
+
+ this->shallow_update_derived();
+ }
+
+ return *this;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>&
+ nary_node_base<Derived,T,Selector>::operator=(
+ BOOST_RV_REF(nary_node_base) source
+ )
+ {
+ if (this != &source)
+ {
+ _children = ::boost::move(source._children);
+ _data = ::boost::move(source._data);
+
+ for (iterator itr = begin(); itr != end(); ++itr)
+ {
+ itr->_parent = this->get_derived();
+ }
+
+ this->shallow_update_derived();
+ }
+
+ return *this;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>::~nary_node_base()
+ {
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<
+ Derived
+ , T
+ , Selector
+ >::traits::data_type const&
+ nary_node_base<Derived,T,Selector>::get_data() const
+ {
+ return _data;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::traits::data_type&
+ nary_node_base<Derived,T,Selector>::get_data()
+ {
+ return _data;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::const_pointer
+ nary_node_base<Derived,T,Selector>::get_parent_ptr() const
+ {
+ return _parent;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::pointer
+ nary_node_base<Derived,T,Selector>::get_parent_ptr()
+ {
+ return _parent;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::add_child(
+ typename traits::data_type const& data
+ )
+ {
+ iterator result(_add_child(data));
+ this->shallow_update_derived();
+ return result;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::add_child()
+ {
+ iterator result(_add_child_def());
+ this->shallow_update_derived();
+ return result;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::add_child_copy(Derived const& copy)
+ {
+ iterator result(_add_child(copy));
+ this->shallow_update_derived();
+ return result;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::const_iterator
+ nary_node_base<Derived,T,Selector>::begin() const
+ {
+ return _children.begin();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::begin()
+ {
+ return _children.begin();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::const_iterator
+ nary_node_base<Derived,T,Selector>::end() const
+ {
+ return _children.end();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::end()
+ {
+ return _children.end();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline bool nary_node_base<Derived,T,Selector>::empty() const
+ {
+ return _children.empty();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline void nary_node_base<Derived,T,Selector>::clear()
+ {
+ _children.clear();
+ this->shallow_update_derived();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ template <typename Arg>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child(Arg& arg)
+ {
+ return _add_child(arg, ::boost::is_associative_selector<Selector>());
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ template <typename Arg>
+ typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child(
+ Arg& arg
+ , ::boost::mpl::true_
+ )
+ {
+ return _add_child_assoc(
+ arg
+ , ::boost::is_unordered_selector<Selector>()
+ );
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ template <typename Arg>
+ typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child(
+ Arg& arg
+ , ::boost::mpl::false_
+ )
+ {
+ iterator to_child = _children.emplace(_children.end(), arg);
+ _initialize(to_child);
+ return to_child;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ template <typename Arg>
+ typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child_assoc(
+ Arg& arg
+ , ::boost::mpl::true_
+ )
+ {
+ ::std::pair<iterator,bool> p = _children.emplace(arg);
+
+ if (p.second)
+ {
+ _initialize(p.first);
+ }
+
+ return p.first;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ template <typename Arg>
+ typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child_assoc(
+ Arg& arg
+ , ::boost::mpl::false_
+ )
+ {
+ iterator to_child = _children.emplace(arg);
+ _initialize(to_child);
+ return to_child;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child_def()
+ {
+ return _add_child_def(::boost::is_associative_selector<Selector>());
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child_def(
+ ::boost::mpl::true_
+ )
+ {
+ return _add_child_def_assoc(
+ ::boost::is_unordered_selector<Selector>()
+ );
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child_def(
+ ::boost::mpl::false_
+ )
+ {
+ iterator to_child = _children.emplace(_children.end());
+ _initialize(to_child);
+ return to_child;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child_def_assoc(
+ ::boost::mpl::true_
+ )
+ {
+ ::std::pair<iterator,bool> p = _children.emplace(
+ ::boost::move(typename traits::data_type())
+ );
+
+ if (p.second)
+ {
+ _initialize(p.first);
+ }
+
+ return p.first;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child_def_assoc(
+ ::boost::mpl::false_
+ )
+ {
+ iterator to_child = _children.emplace();
+ _initialize(to_child);
+ return to_child;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline void
+ nary_node_base<Derived,T,Selector>::_initialize(iterator& to_child)
+ {
+ to_child->_parent = this->get_derived();
+ to_child->set_position_derived(
+ to_child
+ , ::boost::has_stable_iterators_selector<Selector>()
+ );
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ void
+ nary_node_base<Derived,T,Selector>::_clone(
+ nary_node_base const& copy
+ )
+ {
+ pointer p = this->get_derived();
+
+ for (
+ ::boost::tree_node::depth_first_descendant_iterator<
+ Derived const
+ > copy_itr(*copy.get_derived());
+ copy_itr;
+ ++copy_itr
+ )
+ {
+ switch (::boost::tree_node::traversal_state(copy_itr))
+ {
+ case ::boost::tree_node::pre_order_traversal:
+ {
+ p = &*p->_add_child(copy_itr->get_data());
+ break;
+ }
+
+ case ::boost::tree_node::post_order_traversal:
+ {
+ p = p->_parent;
+ break;
+ }
+ }
+ }
+
+ this->deep_update_derived();
+ }
+}} // namespace boost::tree_node
+
+//[reference__nary_node_base__operator_equals
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ bool
+ operator==(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ bool
+ operator==(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ )
+ {
+ return (
+ (
+ 0 == ::boost::tree_node::lexicographical_compare_3way(
+ ::boost::tree_node::breadth_first_iterator<Derived1 const>(
+ *lhs.get_derived()
+ )
+ , ::boost::tree_node::breadth_first_iterator<Derived2 const>(
+ *rhs.get_derived()
+ )
+ )
+ )
+ && ::boost::tree_node::_detail::skew_equal(
+ *lhs.get_derived()
+ , *rhs.get_derived()
+ )
+ );
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__nary_node_base__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ bool
+ operator!=(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ inline bool
+ operator!=(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__nary_node_base__operator_less_than
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ bool
+ operator<(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ bool
+ operator<(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ )
+ {
+ int value = ::boost::tree_node::lexicographical_compare_3way(
+ ::boost::tree_node::breadth_first_iterator<Derived1 const>(
+ *lhs.get_derived()
+ )
+ , ::boost::tree_node::breadth_first_iterator<Derived2 const>(
+ *rhs.get_derived()
+ )
+ );
+
+ if (value < 0)
+ {
+ return true;
+ }
+
+ if (0 < value)
+ {
+ return false;
+ }
+
+ return ::boost::tree_node::_detail::skew_less(
+ *lhs.get_derived()
+ , *rhs.get_derived()
+ );
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__nary_node_base__operator_greater_than
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ bool
+ operator>(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ inline bool
+ operator>(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ )
+ {
+ return rhs < lhs;
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__nary_node_base__operator_less_equal
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ bool
+ operator<=(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ inline bool
+ operator<=(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ )
+ {
+ return !(rhs < lhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__nary_node_base__operator_greater_equal
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ bool
+ operator>=(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ );
+
+ //<-
+ template <
+ typename Derived1
+ , typename T1
+ , typename Selector1
+ , typename Derived2
+ , typename T2
+ , typename Selector2
+ >
+ inline bool
+ operator>=(
+ nary_node_base<Derived1,T1,Selector1> const& lhs
+ , nary_node_base<Derived2,T2,Selector2> const& rhs
+ )
+ {
+ return !(lhs < rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+namespace boost { namespace tree_node {
+
+ template <typename T, typename Selector = ::boost::boost_dequeS>
+ class nary_node
+ : public
+ //[reference__nary_node__bases
+ nary_node_base<nary_node<T,Selector>,T,Selector>
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(nary_node);
+
+ //[reference__nary_node__super_t
+ typedef nary_node_base<nary_node,T,Selector> super_t;
+ //]
+
+ public:
+ //[reference__nary_node__traits
+ typedef typename super_t::traits traits;
+ //]
+
+ //[reference__nary_node__pointer
+ typedef typename super_t::pointer pointer;
+ //]
+
+ //[reference__nary_node__const_pointer
+ typedef typename super_t::const_pointer const_pointer;
+ //]
+
+ //[reference__nary_node__iterator
+ typedef typename super_t::iterator iterator;
+ //]
+
+ //[reference__nary_node__const_iterator
+ typedef typename super_t::const_iterator const_iterator;
+ //]
+
+ //[reference__nary_node__default_ctor
+ nary_node();
+ //]
+
+ //[reference__nary_node__data_ctor
+ explicit nary_node(typename traits::data_type const& data);
+ //]
+
+ nary_node(BOOST_RV_REF(nary_node) source);
+
+ nary_node& operator=(BOOST_COPY_ASSIGN_REF(nary_node) copy);
+
+ nary_node& operator=(BOOST_RV_REF(nary_node) source);
+ };
+
+ template <typename T, typename Selector>
+ nary_node<T,Selector>::nary_node() : super_t()
+ {
+ }
+
+ template <typename T, typename Selector>
+ nary_node<T,Selector>::nary_node(typename traits::data_type const& data)
+ : super_t(data)
+ {
+ }
+
+ template <typename T, typename Selector>
+ nary_node<T,Selector>::nary_node(BOOST_RV_REF(nary_node) source)
+ : super_t(::boost::move(static_cast<super_t&>(source)))
+ {
+ }
+
+ template <typename T, typename Selector>
+ inline nary_node<T,Selector>&
+ nary_node<T,Selector>::operator=(
+ BOOST_COPY_ASSIGN_REF(nary_node) copy
+ )
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ return *this;
+ }
+
+ template <typename T, typename Selector>
+ inline nary_node<T,Selector>&
+ nary_node<T,Selector>::operator=(BOOST_RV_REF(nary_node) source)
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ return *this;
+ }
+}} // namespace boost::tree_node
+//]
+
+//[reference__nary_node_gen
+namespace boost { namespace tree_node {
+
+ template <typename Selector = ::boost::boost_dequeS>
+ struct nary_node_gen
+ {
+ template <typename Derived, typename T>
+ struct apply
+ {
+ typedef nary_node_base<Derived,T,Selector> type;
+ };
+ };
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_NARY_NODE_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/post_order_desc_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/post_order_desc_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,289 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_POST_ORDER_DESC_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_POST_ORDER_DESC_ITERATOR_HPP_INCLUDED
+
+#include <deque>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+#include <boost/detail/metafunction/container_iterator.hpp>
+
+//[reference__post_order_descendant_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class post_order_descendant_iterator
+ : public ::boost::iterator_adaptor<
+ post_order_descendant_iterator<Node>
+ //, typename Node::iterator or typename Node::const_iterator
+ //<-
+ , typename ::boost::detail::container_iterator<Node>::type
+ //->
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ {
+ //<-
+ typedef typename ::boost::detail::container_iterator<Node>::type
+ child_iterator;
+ typedef ::boost::iterator_adaptor<
+ post_order_descendant_iterator<Node>
+ , child_iterator
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ std::deque<child_iterator> _stack;
+ traversal_state _state;
+ //->
+
+ public:
+ post_order_descendant_iterator();
+
+ explicit post_order_descendant_iterator(Node& node);
+
+ template <typename N>
+ post_order_descendant_iterator(
+ post_order_descendant_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ template <typename Node1, typename Node2>
+ friend bool
+ operator==(
+ post_order_descendant_iterator<Node1> const& lhs
+ , post_order_descendant_iterator<Node2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename Node>
+ post_order_descendant_iterator<Node>::post_order_descendant_iterator()
+ : super_t(), _stack(), _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ post_order_descendant_iterator<Node>::post_order_descendant_iterator(
+ Node& node
+ ) : super_t(), _stack(), _state(post_order_traversal)
+ {
+ child_iterator itr = node.begin();
+ child_iterator itr_end = node.end();
+
+ if (itr != itr_end)
+ {
+ ::std::deque<child_iterator> pre_order_stack;
+
+ for (;;)
+ {
+ while (itr != itr_end)
+ {
+ pre_order_stack.push_back(itr);
+ ++itr;
+ }
+
+ _stack.push_back(pre_order_stack.back());
+ pre_order_stack.pop_back();
+
+ if (pre_order_stack.empty())
+ {
+ Node& n = dereference_iterator(
+ this->base_reference() = _stack.back()
+ );
+
+ itr = n.begin();
+ itr_end = n.end();
+
+ if (itr == itr_end)
+ {
+ _stack.pop_back();
+ break;
+ }
+ }
+ else
+ {
+ Node& n = dereference_iterator(_stack.back());
+
+ itr = n.begin();
+ itr_end = n.end();
+ }
+ }
+ }
+
+ if (_stack.empty())
+ {
+ _state = no_traversal;
+ }
+ }
+
+ template <typename Node>
+ template <typename N>
+ post_order_descendant_iterator<Node>::post_order_descendant_iterator(
+ post_order_descendant_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _stack(other._stack.begin(), other._stack.end())
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline post_order_descendant_iterator<Node>::operator
+ traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ inline void post_order_descendant_iterator<Node>::increment()
+ {
+ if (_stack.empty())
+ {
+ _state = no_traversal;
+ }
+ else
+ {
+ this->base_reference() = _stack.back();
+ _stack.pop_back();
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__post_order_descendant_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator==(
+ post_order_descendant_iterator<Node1> const& lhs
+ , post_order_descendant_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator==(
+ post_order_descendant_iterator<Node1> const& lhs
+ , post_order_descendant_iterator<Node2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (lhs.base() == rhs.base()) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__post_order_descendant_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator!=(
+ post_order_descendant_iterator<Node1> const& lhs
+ , post_order_descendant_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator!=(
+ post_order_descendant_iterator<Node1> const& lhs
+ , post_order_descendant_iterator<Node2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_post_order_descendant_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ post_order_descendant_iterator<Node>
+ make_post_order_descendant_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline post_order_descendant_iterator<Node>
+ make_post_order_descendant_iterator(Node& node)
+ {
+ return post_order_descendant_iterator<Node>(node);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__post_order_iterate_descendants
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename UnaryFunction>
+ void post_order_iterate_descendants(Node& node, UnaryFunction function);
+
+ //<-
+ template <typename Node, typename UnaryFunction>
+ void post_order_iterate_descendants(Node& node, UnaryFunction function)
+ {
+ for (post_order_descendant_iterator<Node> itr(node); itr; ++itr)
+ {
+ function(*itr);
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_POST_ORDER_DESC_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/post_order_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/post_order_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,280 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_POST_ORDER_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_POST_ORDER_ITERATOR_HPP_INCLUDED
+
+#include <deque>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+#include <boost/detail/metafunction/container_iterator.hpp>
+
+//[reference__post_order_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class post_order_iterator
+ : public ::boost::iterator_adaptor<
+ post_order_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ {
+ //<-
+ typedef ::boost::iterator_adaptor<
+ post_order_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ std::deque<Node*> _stack;
+ traversal_state _state;
+ //->
+
+ public:
+ post_order_iterator();
+
+ explicit post_order_iterator(Node& node);
+
+ template <typename N>
+ post_order_iterator(
+ post_order_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ template <typename Node1, typename Node2>
+ friend bool
+ operator==(
+ post_order_iterator<Node1> const& lhs
+ , post_order_iterator<Node2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename Node>
+ post_order_iterator<Node>::post_order_iterator()
+ : super_t(), _stack(), _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ post_order_iterator<Node>::post_order_iterator(Node& node)
+ : super_t(&node), _stack(), _state(post_order_traversal)
+ {
+ typedef typename ::boost::detail::container_iterator<Node>::type
+ child_iterator;
+
+ _stack.push_back(&node);
+
+ child_iterator itr = node.begin();
+ child_iterator itr_end = node.end();
+
+ if (itr != itr_end)
+ {
+ ::std::deque<child_iterator> pre_order_stack;
+
+ for (;;)
+ {
+ while (itr != itr_end)
+ {
+ pre_order_stack.push_back(itr);
+ ++itr;
+ }
+
+ _stack.push_back(
+ &dereference_iterator(pre_order_stack.back())
+ );
+ pre_order_stack.pop_back();
+
+ if (pre_order_stack.empty())
+ {
+ Node* node_ptr = this->base_reference() = _stack.back();
+
+ itr = node_ptr->begin();
+ itr_end = node_ptr->end();
+
+ if (itr == itr_end)
+ {
+ _stack.pop_back();
+ break;
+ }
+ }
+ else
+ {
+ Node* node_ptr = _stack.back();
+
+ itr = node_ptr->begin();
+ itr_end = node_ptr->end();
+ }
+ }
+ }
+ }
+
+ template <typename Node>
+ template <typename N>
+ post_order_iterator<Node>::post_order_iterator(
+ post_order_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _stack(other._stack.begin(), other._stack.end())
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline post_order_iterator<Node>::operator traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ inline void post_order_iterator<Node>::increment()
+ {
+ if (_stack.empty())
+ {
+ _state = no_traversal;
+ }
+ else
+ {
+ this->base_reference() = _stack.back();
+ _stack.pop_back();
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__post_order_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator==(
+ post_order_iterator<Node1> const& lhs
+ , post_order_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator==(
+ post_order_iterator<Node1> const& lhs
+ , post_order_iterator<Node2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (lhs.base() == rhs.base()) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__post_order_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator!=(
+ post_order_iterator<Node1> const& lhs
+ , post_order_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator!=(
+ post_order_iterator<Node1> const& lhs
+ , post_order_iterator<Node2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_post_order_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ post_order_iterator<Node> make_post_order_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline post_order_iterator<Node> make_post_order_iterator(Node& node)
+ {
+ return post_order_iterator<Node>(node);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__post_order_iterate
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename UnaryFunction>
+ void post_order_iterate(Node& node, UnaryFunction function);
+
+ //<-
+ template <typename Node, typename UnaryFunction>
+ void post_order_iterate(Node& node, UnaryFunction function)
+ {
+ for (post_order_iterator<Node> itr(node); itr; ++itr)
+ {
+ function(*itr);
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_POST_ORDER_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/pre_order_desc_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/pre_order_desc_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,299 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_PRE_ORDER_DESC_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_PRE_ORDER_DESC_ITERATOR_HPP_INCLUDED
+
+#include <deque>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+#include <boost/detail/metafunction/container_iterator.hpp>
+
+//[reference__pre_order_descendant_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class pre_order_descendant_iterator
+ : public ::boost::iterator_adaptor<
+ pre_order_descendant_iterator<Node>
+ //, typename Node::iterator or typename Node::const_iterator
+ //<-
+ , typename ::boost::detail::container_iterator<Node>::type
+ //->
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ {
+ //<-
+ typedef typename ::boost::detail::container_iterator<Node>::type
+ child_iterator;
+ typedef ::boost::iterator_adaptor<
+ pre_order_descendant_iterator<Node>
+ , child_iterator
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ ::std::deque<Node*> _node_stack;
+ ::std::deque<child_iterator> _itr_stack;
+ Node* _current_node;
+ traversal_state _state;
+ //->
+
+ public:
+ pre_order_descendant_iterator();
+
+ explicit pre_order_descendant_iterator(Node& node);
+
+ template <typename N>
+ pre_order_descendant_iterator(
+ pre_order_descendant_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ template <typename Node1, typename Node2>
+ friend bool
+ operator==(
+ pre_order_descendant_iterator<Node1> const& lhs
+ , pre_order_descendant_iterator<Node2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename Node>
+ pre_order_descendant_iterator<Node>::pre_order_descendant_iterator()
+ : super_t()
+ , _node_stack()
+ , _itr_stack()
+ , _current_node()
+ , _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ pre_order_descendant_iterator<Node>::pre_order_descendant_iterator(
+ Node& node
+ ) : super_t()
+ , _node_stack()
+ , _itr_stack()
+ , _current_node(&node)
+ , _state(pre_order_traversal)
+ {
+ _itr_stack.push_back(node.begin());
+ increment();
+ }
+
+ template <typename Node>
+ template <typename N>
+ pre_order_descendant_iterator<Node>::pre_order_descendant_iterator(
+ pre_order_descendant_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _node_stack(other._node_stack.begin(), other._node_stack.end())
+ , _itr_stack(other._itr_stack.begin(), other._itr_stack.end())
+ , _current_node(other._current_node)
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline pre_order_descendant_iterator<Node>::operator
+ traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ void pre_order_descendant_iterator<Node>::increment()
+ {
+ if (_itr_stack.back() == _current_node->end())
+ {
+ bool is_post_order = true;
+
+ while (is_post_order)
+ {
+ _itr_stack.pop_back();
+
+ if (_node_stack.empty())
+ {
+ _state = no_traversal;
+ _itr_stack.clear();
+ is_post_order = false;
+ }
+ else
+ {
+ _current_node = _node_stack.back();
+ _node_stack.pop_back();
+
+ if (++this->base_reference() == _current_node->end())
+ {
+ child_iterator itr = _itr_stack.back();
+
+ _itr_stack.pop_back();
+
+ if (!_itr_stack.empty())
+ {
+ this->base_reference() = _itr_stack.back();
+ }
+
+ _itr_stack.push_back(itr);
+ }
+ else
+ {
+ _itr_stack.pop_back();
+ _node_stack.push_back(_current_node);
+ _itr_stack.push_back(this->base());
+ _current_node = &dereference_iterator(this->base());
+ _itr_stack.push_back(_current_node->begin());
+ is_post_order = false;
+ }
+ }
+ }
+ }
+ else
+ {
+ _node_stack.push_back(_current_node);
+ _current_node = &dereference_iterator(
+ this->base_reference() = _itr_stack.back()
+ );
+ _itr_stack.push_back(_current_node->begin());
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__pre_order_descendant_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator==(
+ pre_order_descendant_iterator<Node1> const& lhs
+ , pre_order_descendant_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator==(
+ pre_order_descendant_iterator<Node1> const& lhs
+ , pre_order_descendant_iterator<Node2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (*lhs == *rhs) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__pre_order_descendant_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator!=(
+ pre_order_descendant_iterator<Node1> const& lhs
+ , pre_order_descendant_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator!=(
+ pre_order_descendant_iterator<Node1> const& lhs
+ , pre_order_descendant_iterator<Node2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_pre_order_descendant_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ pre_order_descendant_iterator<Node>
+ make_pre_order_descendant_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline pre_order_descendant_iterator<Node>
+ make_pre_order_descendant_iterator(Node& node)
+ {
+ return pre_order_descendant_iterator<Node>(node);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__pre_order_iterate_descendants
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename UnaryFunction>
+ void pre_order_iterate_descendants(Node& node, UnaryFunction function);
+
+ //<-
+ template <typename Node, typename UnaryFunction>
+ void pre_order_iterate_descendants(Node& node, UnaryFunction function)
+ {
+ for (pre_order_descendant_iterator<Node> itr(node); itr; ++itr)
+ {
+ function(*itr);
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_PRE_ORDER_DESC_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/pre_order_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/pre_order_iterator.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,293 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_PRE_ORDER_ITERATOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_PRE_ORDER_ITERATOR_HPP_INCLUDED
+
+#include <deque>
+#include <boost/config.hpp>
+#ifndef BOOST_NO_SFINAE
+#include <boost/tr1/type_traits.hpp>
+#include <boost/utility/enable_if.hpp>
+#endif
+#include <boost/iterator/iterator_categories.hpp>
+#include <boost/iterator/iterator_adaptor.hpp>
+#include <boost/tree_node/traversal_state.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+#include <boost/detail/metafunction/container_iterator.hpp>
+
+//[reference__pre_order_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ class pre_order_iterator
+ : public ::boost::iterator_adaptor<
+ pre_order_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ {
+ //<-
+ typedef typename ::boost::detail::container_iterator<Node>::type
+ child_iterator;
+ typedef ::boost::iterator_adaptor<
+ pre_order_iterator<Node>
+ , Node*
+ , ::boost::use_default
+ , ::boost::forward_traversal_tag
+ >
+ super_t;
+
+#ifndef BOOST_NO_SFINAE
+ struct enabler
+ {
+ };
+#endif
+
+ public: // Should be private, but conversion ctor won't work.
+ ::std::deque<Node*> _node_stack;
+ ::std::deque<child_iterator> _itr_stack;
+ child_iterator _current_itr;
+ traversal_state _state;
+ //->
+
+ public:
+ pre_order_iterator();
+
+ explicit pre_order_iterator(Node& node);
+
+ template <typename N>
+ pre_order_iterator(
+ pre_order_iterator<N> const& other
+//<-
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type = enabler()
+#endif
+//->
+ );
+
+ operator traversal_state() const;
+
+ //<-
+#if !BOOST_WORKAROUND(__GNUC__, == 2)
+ private:
+ friend class ::boost::iterator_core_access;
+#endif
+
+ void increment();
+
+ template <typename Node1, typename Node2>
+ friend bool
+ operator==(
+ pre_order_iterator<Node1> const& lhs
+ , pre_order_iterator<Node2> const& rhs
+ );
+ //->
+ };
+
+ //<-
+ template <typename Node>
+ pre_order_iterator<Node>::pre_order_iterator()
+ : super_t()
+ , _node_stack()
+ , _itr_stack()
+ , _current_itr()
+ , _state(no_traversal)
+ {
+ }
+
+ template <typename Node>
+ pre_order_iterator<Node>::pre_order_iterator(Node& node)
+ : super_t(&node)
+ , _node_stack()
+ , _itr_stack()
+ , _current_itr()
+ , _state(pre_order_traversal)
+ {
+ _itr_stack.push_back(node.begin());
+ }
+
+ template <typename Node>
+ template <typename N>
+ pre_order_iterator<Node>::pre_order_iterator(
+ pre_order_iterator<N> const& other
+#ifndef BOOST_NO_SFINAE
+ , typename ::boost::enable_if<
+ ::std::tr1::is_convertible<N,Node>
+ , enabler
+ >::type
+#endif
+ ) : super_t(other.base())
+ , _node_stack(other._node_stack.begin(), other._node_stack.end())
+ , _itr_stack(other._itr_stack.begin(), other._itr_stack.end())
+ , _current_itr(other._current_itr)
+ , _state(other._state)
+ {
+ }
+
+ template <typename Node>
+ inline pre_order_iterator<Node>::operator traversal_state() const
+ {
+ return _state;
+ }
+
+ template <typename Node>
+ void pre_order_iterator<Node>::increment()
+ {
+ if (_itr_stack.back() == this->base()->end())
+ {
+ bool is_post_order = true;
+
+ while (is_post_order)
+ {
+ _itr_stack.pop_back();
+
+ if (_node_stack.empty())
+ {
+ _state = no_traversal;
+ _itr_stack.clear();
+ is_post_order = false;
+ }
+ else
+ {
+ this->base_reference() = _node_stack.back();
+ _node_stack.pop_back();
+
+ if (++_current_itr == this->base()->end())
+ {
+ child_iterator itr = _itr_stack.back();
+
+ _itr_stack.pop_back();
+
+ if (!_itr_stack.empty())
+ {
+ _current_itr = _itr_stack.back();
+ }
+
+ _itr_stack.push_back(itr);
+ }
+ else
+ {
+ _itr_stack.pop_back();
+ _node_stack.push_back(this->base());
+ _itr_stack.push_back(_current_itr);
+ this->base_reference() = &dereference_iterator(
+ _current_itr
+ );
+ _itr_stack.push_back(this->base()->begin());
+ is_post_order = false;
+ }
+ }
+ }
+ }
+ else
+ {
+ _node_stack.push_back(this->base());
+ this->base_reference() = &dereference_iterator(
+ _current_itr = _itr_stack.back()
+ );
+ _itr_stack.push_back(this->base()->begin());
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__pre_order_iterator__operator_equals
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator==(
+ pre_order_iterator<Node1> const& lhs
+ , pre_order_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator==(
+ pre_order_iterator<Node1> const& lhs
+ , pre_order_iterator<Node2> const& rhs
+ )
+ {
+ if (lhs._state == rhs._state)
+ {
+ return lhs._state ? (*lhs == *rhs) : !rhs._state;
+ }
+ else
+ {
+ return false;
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__pre_order_iterator__operator_not_equal
+namespace boost { namespace tree_node {
+
+ template <typename Node1, typename Node2>
+ bool
+ operator!=(
+ pre_order_iterator<Node1> const& lhs
+ , pre_order_iterator<Node2> const& rhs
+ );
+
+ //<-
+ template <typename Node1, typename Node2>
+ inline bool
+ operator!=(
+ pre_order_iterator<Node1> const& lhs
+ , pre_order_iterator<Node2> const& rhs
+ )
+ {
+ return !(lhs == rhs);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__make_pre_order_iterator
+namespace boost { namespace tree_node {
+
+ template <typename Node>
+ pre_order_iterator<Node> make_pre_order_iterator(Node& node);
+
+ //<-
+ template <typename Node>
+ inline pre_order_iterator<Node> make_pre_order_iterator(Node& node)
+ {
+ return pre_order_iterator<Node>(node);
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+//[reference__pre_order_iterate
+namespace boost { namespace tree_node {
+
+ template <typename Node, typename UnaryFunction>
+ void pre_order_iterate(Node& node, UnaryFunction function);
+
+ //<-
+ template <typename Node, typename UnaryFunction>
+ void pre_order_iterate(Node& node, UnaryFunction function)
+ {
+ for (pre_order_iterator<Node> itr(node); itr; ++itr)
+ {
+ function(*itr);
+ }
+ }
+ //->
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_PRE_ORDER_ITERATOR_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/traversal_state.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/traversal_state.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,24 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_TRAVERSAL_STATE_HPP_INCLUDED
+#define BOOST_TREE_NODE_TRAVERSAL_STATE_HPP_INCLUDED
+
+//[reference__traversal_state
+namespace boost { namespace tree_node {
+
+ enum traversal_state
+ {
+ no_traversal
+ , pre_order_traversal
+ , post_order_traversal
+ , breadth_first_traversal
+ , in_order_traversal
+ };
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_TRAVERSAL_STATE_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/typeof.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/typeof.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,56 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_TYPEOF_HPP_INCLUDED
+#define BOOST_TREE_NODE_TYPEOF_HPP_INCLUDED
+
+#include <boost/typeof/typeof.hpp>
+#include <boost/tree_node.hpp>
+
+#include BOOST_TYPEOF_INCREMENT_REGISTRATION_GROUP()
+BOOST_TYPEOF_REGISTER_TYPE(boost::tree_node::traversal_state)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::breadth_first_iterator, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(
+ boost::tree_node::breadth_first_descendant_iterator
+ , 1
+)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::pre_order_iterator, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(
+ boost::tree_node::pre_order_descendant_iterator
+ , 1
+)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::post_order_iterator, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(
+ boost::tree_node::post_order_descendant_iterator
+ , 1
+)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::in_order_iterator, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::depth_first_iterator, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(
+ boost::tree_node::depth_first_descendant_iterator
+ , 1
+)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::tree_node_base, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::binary_node_base, 2)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::binary_node, 1)
+BOOST_TYPEOF_REGISTER_TYPE(boost::tree_node::binary_node_gen)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::nary_node_base, 3)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::nary_node, 2)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::nary_node_gen, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::associative_node_base, 4)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::associative_node, 3)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::associative_node_gen, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_depth_base, 5)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_depth, 4)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_depth_gen, 2)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_position_base, 4)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_position, 3)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_position_gen, 1)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_red_black_flag_base, 4)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_red_black_flag, 3)
+BOOST_TYPEOF_REGISTER_TEMPLATE(boost::tree_node::with_red_black_flag_gen, 1)
+
+#endif // BOOST_TREE_NODE_TYPEOF_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/with_depth.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/with_depth.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,469 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_WITH_DEPTH_HPP_INCLUDED
+#define BOOST_TREE_NODE_WITH_DEPTH_HPP_INCLUDED
+
+#include <boost/cstdint.hpp>
+#include <boost/tr1/type_traits.hpp>
+#include <boost/mpl/apply_wrap.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/move/move.hpp>
+#include <boost/utility/value_init.hpp>
+#include <boost/tree_node/post_order_iterator.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ class with_depth_base
+ : public
+ //[reference__with_depth_base__bases
+ ::boost::mpl::eval_if<
+ ::std::tr1::is_void<T2>
+ , ::boost::mpl::apply_wrap2<BaseGenerator,Derived,T1>
+ , ::boost::mpl::apply_wrap3<BaseGenerator,Derived,T1,T2>
+ >::type
+ //]
+ {
+ friend struct tree_node_base<Derived>;
+
+ BOOST_COPYABLE_AND_MOVABLE(with_depth_base);
+
+ typedef typename ::boost::mpl::eval_if<
+ ::std::tr1::is_void<T2>
+ , ::boost::mpl::apply_wrap2<BaseGenerator,Derived,T1>
+ , ::boost::mpl::apply_wrap3<BaseGenerator,Derived,T1,T2>
+ >::type
+ super_t;
+
+ public:
+ typedef typename super_t::traits
+ traits;
+ typedef typename super_t::pointer
+ pointer;
+ typedef typename super_t::const_pointer
+ const_pointer;
+ typedef typename super_t::iterator
+ iterator;
+ typedef typename super_t::const_iterator
+ const_iterator;
+
+ private:
+ Depth _depth;
+
+ public:
+ //[reference__with_depth_base__default_ctor
+ with_depth_base();
+ //]
+
+ //[reference__with_depth_base__data_ctor
+ explicit with_depth_base(typename traits::data_type const& data);
+ //]
+
+ with_depth_base(BOOST_RV_REF(with_depth_base) source);
+
+ with_depth_base&
+ operator=(BOOST_COPY_ASSIGN_REF(with_depth_base) copy);
+
+ with_depth_base& operator=(BOOST_RV_REF(with_depth_base) source);
+
+ protected:
+ ~with_depth_base();
+
+ public:
+ //[reference__with_depth_base__get_depth
+ Depth const& get_depth() const;
+ //]
+
+ protected:
+ void shallow_update_impl();
+
+ void deep_update_impl();
+
+ private:
+ void _update_less_depth();
+
+ void _update_greater_depth();
+ };
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ with_depth_base<Derived,BaseGenerator,T1,T2,Depth>::with_depth_base()
+ : super_t(), _depth(::boost::initialized_value)
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ with_depth_base<Derived,BaseGenerator,T1,T2,Depth>::with_depth_base(
+ typename traits::data_type const& data
+ ) : super_t(data), _depth(::boost::initialized_value)
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ with_depth_base<Derived,BaseGenerator,T1,T2,Depth>::with_depth_base(
+ BOOST_RV_REF(with_depth_base) source
+ ) : super_t(::boost::move(static_cast<super_t&>(source)))
+ , _depth(source._depth)
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ inline with_depth_base<Derived,BaseGenerator,T1,T2,Depth>&
+ with_depth_base<Derived,BaseGenerator,T1,T2,Depth>::operator=(
+ BOOST_COPY_ASSIGN_REF(with_depth_base) copy
+ )
+ {
+ if (this != &copy)
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ _depth = copy._depth;
+ }
+
+ return *this;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ inline with_depth_base<Derived,BaseGenerator,T1,T2,Depth>&
+ with_depth_base<Derived,BaseGenerator,T1,T2,Depth>::operator=(
+ BOOST_RV_REF(with_depth_base) source
+ )
+ {
+ if (this != &source)
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ _depth = source._depth;
+ }
+
+ return *this;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ with_depth_base<Derived,BaseGenerator,T1,T2,Depth>::~with_depth_base()
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ inline Depth const&
+ with_depth_base<Derived,BaseGenerator,T1,T2,Depth>::get_depth() const
+ {
+ return _depth;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ void
+ with_depth_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ , Depth
+ >::shallow_update_impl()
+ {
+ super_t::shallow_update_impl();
+
+ Depth new_depth = ::boost::initialized_value, depth_plus_1;
+ const_iterator c_end(this->end());
+
+ for (const_iterator c_itr(this->begin()); c_itr != c_end; ++c_itr)
+ {
+ depth_plus_1 = dereference_iterator(c_itr).get_depth();
+
+ if (new_depth < ++depth_plus_1)
+ {
+ new_depth = depth_plus_1;
+ }
+ }
+
+ if (new_depth < _depth)
+ {
+ _depth = new_depth;
+ _update_less_depth();
+ }
+ else if (_depth < new_depth)
+ {
+ _depth = new_depth;
+ _update_greater_depth();
+ }
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ void with_depth_base<Derived,BaseGenerator,T1,T2,Depth>::deep_update_impl()
+ {
+ super_t::deep_update_impl();
+
+ Depth const old_depth = _depth;
+ Depth new_depth, depth_plus_1;
+ const_iterator c_itr, c_end;
+
+ for (
+ post_order_iterator<Derived> itr(*this->get_derived());
+ itr;
+ ++itr
+ )
+ {
+ new_depth = ::boost::initialized_value;
+ c_end = itr->end();
+
+ for (c_itr = itr->begin(); c_itr != c_end; ++c_itr)
+ {
+ depth_plus_1 = dereference_iterator(c_itr).get_depth();
+
+ if (new_depth < ++depth_plus_1)
+ {
+ new_depth = depth_plus_1;
+ }
+ }
+
+ itr->_depth = new_depth;
+ }
+
+ if (_depth < old_depth)
+ {
+ _update_less_depth();
+ }
+ else if (old_depth < _depth)
+ {
+ _update_greater_depth();
+ }
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ void
+ with_depth_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ , Depth
+ >::_update_less_depth()
+ {
+ pointer p = this->get_derived();
+ Depth new_depth, depth_plus_1;
+ const_iterator c_itr, c_end;
+
+ while (p = p->get_parent_ptr())
+ {
+ new_depth = ::boost::initialized_value;
+ c_end = p->end();
+
+ for (c_itr = p->begin(); c_itr != c_end; ++c_itr)
+ {
+ depth_plus_1 = dereference_iterator(c_itr).get_depth();
+
+ if (new_depth < ++depth_plus_1)
+ {
+ new_depth = depth_plus_1;
+ }
+ }
+
+ if (p->get_depth() == new_depth)
+ {
+ return;
+ }
+ else
+ {
+ // This is no longer the deepest branch.
+ p->_depth = new_depth;
+ }
+ }
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ , typename Depth
+ >
+ void
+ with_depth_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ , Depth
+ >::_update_greater_depth()
+ {
+ Depth this_depth = _depth;
+ pointer p = this->get_derived();
+
+ while ((p = p->get_parent_ptr()) && (p->_depth < ++this_depth))
+ {
+ // This is the new deepest branch.
+ p->_depth = this_depth;
+ }
+ }
+}} // namespace boost::tree_node
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename BaseGenerator
+ , typename T1
+ , typename T2 = void
+ , typename Depth = ::std::size_t
+ >
+ class with_depth
+ : public
+ //[reference__with_depth__bases
+ with_depth_base<
+ with_depth<BaseGenerator,T1,T2,Depth>
+ , BaseGenerator
+ , T1
+ , T2
+ , Depth
+ >
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(with_depth);
+
+ typedef with_depth_base<with_depth,BaseGenerator,T1,T2,Depth> super_t;
+
+ public:
+ typedef typename super_t::traits traits;
+ typedef typename super_t::pointer pointer;
+ typedef typename super_t::const_pointer const_pointer;
+ typedef typename super_t::iterator iterator;
+ typedef typename super_t::const_iterator const_iterator;
+
+ //[reference__with_depth__default_ctor
+ with_depth();
+ //]
+
+ //[reference__with_depth__data_ctor
+ explicit with_depth(typename traits::data_type const& data);
+ //]
+
+ with_depth(BOOST_RV_REF(with_depth) source);
+
+ with_depth& operator=(BOOST_COPY_ASSIGN_REF(with_depth) copy);
+
+ with_depth& operator=(BOOST_RV_REF(with_depth) source);
+ };
+
+ template <typename BaseGenerator, typename T1, typename T2, typename Depth>
+ with_depth<BaseGenerator,T1,T2,Depth>::with_depth() : super_t()
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2, typename Depth>
+ with_depth<BaseGenerator,T1,T2,Depth>::with_depth(
+ typename traits::data_type const& data
+ ) : super_t(data)
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2, typename Depth>
+ with_depth<BaseGenerator,T1,T2,Depth>::with_depth(
+ BOOST_RV_REF(with_depth) source
+ ) : super_t(::boost::move(static_cast<super_t&>(source)))
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2, typename Depth>
+ inline with_depth<BaseGenerator,T1,T2,Depth>&
+ with_depth<BaseGenerator,T1,T2,Depth>::operator=(
+ BOOST_COPY_ASSIGN_REF(with_depth) copy
+ )
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ return *this;
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2, typename Depth>
+ inline with_depth<BaseGenerator,T1,T2,Depth>&
+ with_depth<BaseGenerator,T1,T2,Depth>::operator=(
+ BOOST_RV_REF(with_depth) source
+ )
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ return *this;
+ }
+}} // namespace boost::tree_node
+
+//[reference__with_depth_gen
+namespace boost { namespace tree_node {
+
+ template <typename BaseGenerator, typename Depth = ::std::size_t>
+ struct with_depth_gen
+ {
+ template <typename Derived, typename T1, typename T2 = void>
+ struct apply
+ {
+ typedef with_depth_base<Derived,BaseGenerator,T1,T2,Depth> type;
+ };
+ };
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_WITH_DEPTH_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/with_position.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/with_position.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,351 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_WITH_POSITION_HPP_INCLUDED
+#define BOOST_TREE_NODE_WITH_POSITION_HPP_INCLUDED
+
+#include <boost/tr1/type_traits.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/mpl/apply_wrap.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/move/move.hpp>
+#include <boost/tree_node/algorithm/dereference_iterator.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ class with_position_base
+ : public
+ //[reference__with_position_base__bases
+ ::boost::mpl::eval_if<
+ ::std::tr1::is_void<T2>
+ , ::boost::mpl::apply_wrap2<BaseGenerator,Derived,T1>
+ , ::boost::mpl::apply_wrap3<BaseGenerator,Derived,T1,T2>
+ >::type
+ //]
+ {
+ friend struct tree_node_base<Derived>;
+
+ BOOST_COPYABLE_AND_MOVABLE(with_position_base);
+
+ typedef typename ::boost::mpl::eval_if<
+ ::std::tr1::is_void<T2>
+ , ::boost::mpl::apply_wrap2<BaseGenerator,Derived,T1>
+ , ::boost::mpl::apply_wrap3<BaseGenerator,Derived,T1,T2>
+ >::type
+ super_t;
+
+ public:
+ typedef typename super_t::traits
+ traits;
+ typedef typename super_t::pointer
+ pointer;
+ typedef typename super_t::const_pointer
+ const_pointer;
+ typedef typename super_t::iterator
+ iterator;
+ typedef typename super_t::const_iterator
+ const_iterator;
+
+ private:
+ iterator _position;
+
+ public:
+ //[reference__with_position_base__default_ctor
+ with_position_base();
+ //]
+
+ //[reference__with_position_base__data_ctor
+ explicit with_position_base(typename traits::data_type const& data);
+ //]
+
+ with_position_base(BOOST_RV_REF(with_position_base) source);
+
+ with_position_base&
+ operator=(BOOST_COPY_ASSIGN_REF(with_position_base) copy);
+
+ with_position_base&
+ operator=(BOOST_RV_REF(with_position_base) source);
+
+ protected:
+ ~with_position_base();
+
+ public:
+ //[reference__with_position_base__get_position__const
+ const_iterator get_position() const;
+ //]
+
+ //[reference__with_position_base__get_position
+ iterator get_position();
+ //]
+
+ protected:
+ void set_position_impl(iterator position, ::boost::mpl::true_);
+
+ void set_position_impl(iterator position, ::boost::mpl::false_);
+ };
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ with_position_base<Derived,BaseGenerator,T1,T2>::with_position_base()
+ : super_t()
+ , _position()
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ with_position_base<Derived,BaseGenerator,T1,T2>::with_position_base(
+ typename traits::data_type const& data
+ ) : super_t(data), _position()
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ with_position_base<Derived,BaseGenerator,T1,T2>::with_position_base(
+ BOOST_RV_REF(with_position_base) source
+ )
+ : super_t(::boost::move(static_cast<super_t&>(source)))
+ , _position(source._position)
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline with_position_base<Derived,BaseGenerator,T1,T2>&
+ with_position_base<Derived,BaseGenerator,T1,T2>::operator=(
+ BOOST_COPY_ASSIGN_REF(with_position_base) copy
+ )
+ {
+ if (this != &copy)
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ _position = copy._position;
+ }
+
+ return *this;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline with_position_base<Derived,BaseGenerator,T1,T2>&
+ with_position_base<Derived,BaseGenerator,T1,T2>::operator=(
+ BOOST_RV_REF(with_position_base) source
+ )
+ {
+ if (this != &source)
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ _position = source._position;
+ }
+
+ return *this;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ with_position_base<Derived,BaseGenerator,T1,T2>::~with_position_base()
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline typename with_position_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ >::const_iterator
+ with_position_base<Derived,BaseGenerator,T1,T2>::get_position() const
+ {
+ return _position;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline typename with_position_base<Derived,BaseGenerator,T1,T2>::iterator
+ with_position_base<Derived,BaseGenerator,T1,T2>::get_position()
+ {
+ return _position;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline void
+ with_position_base<Derived,BaseGenerator,T1,T2>::set_position_impl(
+ iterator position
+ , ::boost::mpl::true_ t
+ )
+ {
+ super_t::set_position_impl(position, t);
+ _position = position;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ void
+ with_position_base<Derived,BaseGenerator,T1,T2>::set_position_impl(
+ iterator position
+ , ::boost::mpl::false_ f
+ )
+ {
+ super_t::set_position_impl(position, f);
+
+ iterator c_end = this->get_parent_ptr()->end();
+
+ for (
+ position = this->get_parent_ptr()->begin();
+ position != c_end;
+ ++position
+ )
+ {
+ dereference_iterator(position)._position = position;
+ }
+ }
+}} // namespace boost::tree_node
+
+namespace boost { namespace tree_node {
+
+ template <typename BaseGenerator, typename T1, typename T2 = void>
+ class with_position
+ : public
+ //[reference__with_position__bases
+ with_position_base<
+ with_position<BaseGenerator,T1,T2>
+ , BaseGenerator
+ , T1
+ , T2
+ >
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(with_position);
+
+ typedef with_position_base<with_position,BaseGenerator,T1,T2> super_t;
+
+ public:
+ typedef typename super_t::traits traits;
+ typedef typename super_t::pointer pointer;
+ typedef typename super_t::const_pointer const_pointer;
+ typedef typename super_t::iterator iterator;
+ typedef typename super_t::const_iterator const_iterator;
+
+ //[reference__with_position__default_ctor
+ with_position();
+ //]
+
+ //[reference__with_position__data_ctor
+ explicit with_position(typename traits::data_type const& data);
+ //]
+
+ with_position(BOOST_RV_REF(with_position) source);
+
+ with_position& operator=(BOOST_COPY_ASSIGN_REF(with_position) copy);
+
+ with_position& operator=(BOOST_RV_REF(with_position) source);
+ };
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ with_position<BaseGenerator,T1,T2>::with_position() : super_t()
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ with_position<BaseGenerator,T1,T2>::with_position(
+ typename traits::data_type const& data
+ ) : super_t(data)
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ with_position<BaseGenerator,T1,T2>::with_position(
+ BOOST_RV_REF(with_position) source
+ ) : super_t(::boost::move(static_cast<super_t&>(source)))
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ inline with_position<BaseGenerator,T1,T2>&
+ with_position<BaseGenerator,T1,T2>::operator=(
+ BOOST_COPY_ASSIGN_REF(with_position) copy
+ )
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ return *this;
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ inline with_position<BaseGenerator,T1,T2>&
+ with_position<BaseGenerator,T1,T2>::operator=(
+ BOOST_RV_REF(with_position) source
+ )
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ return *this;
+ }
+}} // namespace boost::tree_node
+
+//[reference__with_position_gen
+namespace boost { namespace tree_node {
+
+ template <typename BaseGenerator>
+ struct with_position_gen
+ {
+ template <typename Derived, typename T1, typename T2 = void>
+ struct apply
+ {
+ typedef with_position_base<Derived,BaseGenerator,T1,T2> type;
+ };
+ };
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_WITH_POSITION_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/with_red_black_flag.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/with_red_black_flag.hpp 2012-01-31 14:22:38 EST (Tue, 31 Jan 2012)
@@ -0,0 +1,349 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// 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)
+
+#ifndef BOOST_TREE_NODE_WITH_RED_BLACK_FLAG_HPP_INCLUDED
+#define BOOST_TREE_NODE_WITH_RED_BLACK_FLAG_HPP_INCLUDED
+
+#include <boost/tr1/type_traits.hpp>
+#include <boost/mpl/apply_wrap.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/move/move.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ class with_red_black_flag_base
+ : public
+ //[reference__with_red_black_flag_base__bases
+ ::boost::mpl::eval_if<
+ ::std::tr1::is_void<T2>
+ , ::boost::mpl::apply_wrap2<BaseGenerator,Derived,T1>
+ , ::boost::mpl::apply_wrap3<BaseGenerator,Derived,T1,T2>
+ >::type
+ //]
+ {
+ BOOST_COPYABLE_AND_MOVABLE(with_red_black_flag_base);
+
+ typedef typename ::boost::mpl::eval_if<
+ ::std::tr1::is_void<T2>
+ , ::boost::mpl::apply_wrap2<BaseGenerator,Derived,T1>
+ , ::boost::mpl::apply_wrap3<BaseGenerator,Derived,T1,T2>
+ >::type
+ super_t;
+
+ public:
+ typedef typename super_t::traits
+ traits;
+ typedef typename super_t::pointer
+ pointer;
+ typedef typename super_t::const_pointer
+ const_pointer;
+ typedef typename super_t::iterator
+ iterator;
+ typedef typename super_t::const_iterator
+ const_iterator;
+
+ private:
+ bool _is_red;
+
+ public:
+ //[reference__with_red_black_flag_base__default_ctor
+ with_red_black_flag_base();
+ //]
+
+ //[reference__with_red_black_flag_base__data_ctor
+ explicit with_red_black_flag_base(
+ typename traits::data_type const& data
+ );
+ //]
+
+ with_red_black_flag_base(
+ BOOST_RV_REF(with_red_black_flag_base) source
+ );
+
+ with_red_black_flag_base&
+ operator=(BOOST_COPY_ASSIGN_REF(with_red_black_flag_base) copy);
+
+ with_red_black_flag_base&
+ operator=(BOOST_RV_REF(with_red_black_flag_base) source);
+
+ protected:
+ ~with_red_black_flag_base();
+
+ public:
+ //[reference__with_red_black_flag_base__is_red
+ bool is_red() const;
+ //]
+
+ //[reference__with_red_black_flag_base__is_black
+ bool is_black() const;
+ //]
+
+ //[reference__with_red_black_flag_base__set_red_flag
+ void set_red_flag(bool flag);
+ //]
+ };
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ with_red_black_flag_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ >::with_red_black_flag_base() : super_t(), _is_red(false)
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ with_red_black_flag_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ >::with_red_black_flag_base(typename traits::data_type const& data)
+ : super_t(data), _is_red(false)
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ with_red_black_flag_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ >::with_red_black_flag_base(BOOST_RV_REF(with_red_black_flag_base) source)
+ : super_t(::boost::move(static_cast<super_t&>(source)))
+ , _is_red(source._is_red)
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline with_red_black_flag_base<Derived,BaseGenerator,T1,T2>&
+ with_red_black_flag_base<Derived,BaseGenerator,T1,T2>::operator=(
+ BOOST_COPY_ASSIGN_REF(with_red_black_flag_base) copy
+ )
+ {
+ if (this != &copy)
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ _is_red = copy._is_red;
+ }
+
+ return *this;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline with_red_black_flag_base<Derived,BaseGenerator,T1,T2>&
+ with_red_black_flag_base<Derived,BaseGenerator,T1,T2>::operator=(
+ BOOST_RV_REF(with_red_black_flag_base) source
+ )
+ {
+ if (this != &source)
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ _is_red = source._is_red;
+ }
+
+ return *this;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ with_red_black_flag_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ >::~with_red_black_flag_base()
+ {
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline bool
+ with_red_black_flag_base<Derived,BaseGenerator,T1,T2>::is_red() const
+ {
+ return _is_red;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline bool
+ with_red_black_flag_base<
+ Derived
+ , BaseGenerator
+ , T1
+ , T2
+ >::is_black() const
+ {
+ return !_is_red;
+ }
+
+ template <
+ typename Derived
+ , typename BaseGenerator
+ , typename T1
+ , typename T2
+ >
+ inline void
+ with_red_black_flag_base<Derived,BaseGenerator,T1,T2>::set_red_flag(
+ bool flag
+ )
+ {
+ _is_red = flag;
+ }
+}} // namespace boost::tree_node
+
+namespace boost { namespace tree_node {
+
+ template <typename BaseGenerator, typename T1, typename T2 = void>
+ class with_red_black_flag
+ : public
+ //[reference__with_red_black_flag__bases
+ with_red_black_flag_base<
+ with_red_black_flag<BaseGenerator,T1,T2>
+ , BaseGenerator
+ , T1
+ , T2
+ >
+ //]
+ {
+ typedef with_red_black_flag_base<
+ with_red_black_flag
+ , BaseGenerator
+ , T1
+ , T2
+ >
+ super_t;
+
+ public:
+ typedef typename super_t::traits
+ traits;
+ typedef typename super_t::pointer
+ pointer;
+ typedef typename super_t::const_pointer
+ const_pointer;
+ typedef typename super_t::iterator
+ iterator;
+ typedef typename super_t::const_iterator
+ const_iterator;
+
+ //[reference__with_red_black_flag__default_ctor
+ with_red_black_flag();
+ //]
+
+ //[reference__with_red_black_flag__data_ctor
+ explicit with_red_black_flag(typename traits::data_type const& data);
+ //]
+
+ with_red_black_flag(BOOST_RV_REF(with_red_black_flag) source);
+
+ with_red_black_flag&
+ operator=(BOOST_COPY_ASSIGN_REF(with_red_black_flag) copy);
+
+ with_red_black_flag&
+ operator=(BOOST_RV_REF(with_red_black_flag) source);
+ };
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ with_red_black_flag<BaseGenerator,T1,T2>::with_red_black_flag() : super_t()
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ with_red_black_flag<BaseGenerator,T1,T2>::with_red_black_flag(
+ typename traits::data_type const& data
+ ) : super_t(data)
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ with_red_black_flag<BaseGenerator,T1,T2>::with_red_black_flag(
+ BOOST_RV_REF(with_red_black_flag) source
+ ) : super_t(::boost::move(static_cast<super_t&>(source)))
+ {
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ inline with_red_black_flag<BaseGenerator,T1,T2>&
+ with_red_black_flag<BaseGenerator,T1,T2>::operator=(
+ BOOST_COPY_ASSIGN_REF(with_red_black_flag) copy
+ )
+ {
+ super_t::operator=(static_cast<super_t const&>(copy));
+ return *this;
+ }
+
+ template <typename BaseGenerator, typename T1, typename T2>
+ inline with_red_black_flag<BaseGenerator,T1,T2>&
+ with_red_black_flag<BaseGenerator,T1,T2>::operator=(
+ BOOST_RV_REF(with_red_black_flag) source
+ )
+ {
+ super_t::operator=(::boost::move(static_cast<super_t&>(source)));
+ return *this;
+ }
+}} // namespace boost::tree_node
+
+//[reference__with_red_black_flag_gen
+namespace boost { namespace tree_node {
+
+ template <typename BaseGenerator>
+ struct with_red_black_flag_gen
+ {
+ template <typename Derived, typename T1, typename T2 = void>
+ struct apply
+ {
+ typedef with_red_black_flag_base<Derived,BaseGenerator,T1,T2>
+ type;
+ };
+ };
+}} // namespace boost::tree_node
+//]
+
+#endif // BOOST_TREE_NODE_WITH_RED_BLACK_FLAG_HPP_INCLUDED
+

Next message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r76813 - sandbox/gtl/boost/polygon"
Previous message: john_at_[hidden]: "[Boost-commit] svn:boost r76811 - in sandbox/math: boost/math/special_functions libs/math/test"

Date view	Thread view	Subject view	Author view