Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r83348 - in sandbox/tree_node: boost/tree_node boost/tree_node/container libs/tree_node/test
From: sponage_at_[hidden]
Date: 2013-03-07 12:16:28

Author: expaler
Date: 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
New Revision: 83348
URL: http://svn.boost.org/trac/boost/changeset/83348

Log:
Boost.TreeNode: fixed syntax errors; broke test/containers.cpp into separate tests.
Added:
   sandbox/tree_node/boost/tree_node/container/binode.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/container/binode_associative.hpp (contents, props changed)
   sandbox/tree_node/boost/tree_node/preprocessor.hpp (contents, props changed)
   sandbox/tree_node/libs/tree_node/test/avl_tree.hpp (contents, props changed)
   sandbox/tree_node/libs/tree_node/test/binode_container.cpp (contents, props changed)
   sandbox/tree_node/libs/tree_node/test/binode_map.cpp (contents, props changed)
   sandbox/tree_node/libs/tree_node/test/binode_set.cpp (contents, props changed)
   sandbox/tree_node/libs/tree_node/test/container_functions.hpp (contents, props changed)
   sandbox/tree_node/libs/tree_node/test/red_black_tree.hpp (contents, props changed)
   sandbox/tree_node/libs/tree_node/test/sequence.hpp (contents, props changed)
   sandbox/tree_node/libs/tree_node/test/type_definitions.hpp (contents, props changed)
Removed:
   sandbox/tree_node/libs/tree_node/test/containers.cpp

Added: sandbox/tree_node/boost/tree_node/container/binode.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/container/binode.hpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,2038 @@
+// Copyright (C) 2013 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_CONTAINER_BINODE_HPP_INCLUDED
+#define BOOST_TREE_NODE_CONTAINER_BINODE_HPP_INCLUDED
+
+#include <boost/config.hpp>
+
+#if !defined BOOST_NO_CXX11_NULLPTR
+#include <cstddef>
+#endif
+
+#include <utility>
+#include <boost/tr1/type_traits.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/mpl/apply_wrap.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/utility/value_init.hpp>
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#include <boost/move/move.hpp>
+#include <boost/container/allocator_traits.hpp>
+#endif
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/preprocessor/repetition/repeat.hpp>
+#endif
+
+#include <boost/tree_node/preprocessor.hpp>
+#include <boost/tree_node/key/data.hpp>
+#include <boost/tree_node/key/count.hpp>
+#include <boost/tree_node/iterator/in_order.hpp>
+#include <boost/tree_node/intrinsic/has_key.hpp>
+#include <boost/tree_node/intrinsic/value_at_key.hpp>
+#include <boost/tree_node/algorithm/binary_descendant_at_index.hpp>
+#include <boost/tree_node/container/binode_fwd.hpp>
+#include <boost/assert.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename NodeGenerator
+ , typename T
+ , typename Balancer
+ >
+ class binode_container
+ {
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ BOOST_COPYABLE_AND_MOVABLE(binode_container)
+#endif
+
+ public:
+ //[reference__binode_container__value_type
+ typedef T value_type;
+ //]
+
+ //[reference__binode_container__reference
+ typedef value_type& reference;
+ //]
+
+ //[reference__binode_container__const_reference
+ typedef value_type const& const_reference;
+ //]
+
+ //[reference__binode_container__pointer
+ typedef value_type* pointer;
+ //]
+
+ //[reference__binode_container__const_pointer
+ typedef value_type const* const_pointer;
+ //]
+
+ //[reference__binode_container__node
+ typedef typename ::boost::mpl::apply_wrap1<
+ NodeGenerator
+ , value_type
+ >::type
+ node;
+ //]
+
+ //[reference__binode_container__allocator_type
+ typedef typename node::traits::allocator allocator_type;
+ //]
+
+ private:
+ //[reference__binode_container__transform_function
+ struct transform_function
+ {
+ const_reference operator()(node const& n) const;
+ reference operator()(node& n) const;
+ };
+ //]
+
+ public:
+ //[reference__binode_container__iterator
+ typedef ::boost::transform_iterator<
+ transform_function
+ , in_order_iterator<node>
+ >
+ iterator;
+ //]
+
+ //[reference__binode_container__const_iterator
+ typedef ::boost::transform_iterator<
+ transform_function
+ , in_order_iterator<node const>
+ >
+ const_iterator;
+ //]
+
+ //[reference__binode_container__reverse_iterator
+ typedef ::boost::transform_iterator<
+ transform_function
+ , in_order_iterator<node,::boost::mpl::true_>
+ >
+ reverse_iterator;
+ //]
+
+ //[reference__binode_container__const_reverse_iterator
+ typedef ::boost::transform_iterator<
+ transform_function
+ , in_order_iterator<node const,::boost::mpl::true_>
+ >
+ const_reverse_iterator;
+ //]
+
+ //[reference__binode_container__size_type
+ typedef typename ::boost::mpl::eval_if<
+ result_of::has_key<node,count_key>
+ , result_of::value_at_key<node,count_key>
+ , typename node::size_type
+ >::type
+ size_type;
+ //]
+
+ private:
+ allocator_type _allocator;
+ typename node::pointer _root_ptr;
+
+ public:
+ //[reference__binode_container__default_ctor
+ binode_container();
+ //]
+
+ //[reference__binode_container__ctor_w_alloc
+ explicit binode_container(allocator_type const& allocator);
+ //]
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ //[reference__binode_container__copy_ctor
+ binode_container(binode_container const& copy);
+ //]
+#else
+ binode_container(
+ BOOST_COPY_ASSIGN_REF(binode_container) copy
+ );
+#endif
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ //[reference__binode_container__copy_ctor_w_alloc
+ binode_container(
+ binode_container const& copy
+ , allocator_type const& allocator
+ );
+ //]
+#else
+ binode_container(
+ BOOST_COPY_ASSIGN_REF(binode_container) copy
+ , allocator_type const& allocator
+ );
+#endif
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ //[reference__binode_container__copy_assign
+ binode_container& operator=(binode_container const& copy);
+ //]
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ binode_container(
+ BOOST_RV_REF(binode_container) source
+ );
+
+ binode_container(
+ BOOST_RV_REF(binode_container) source
+ , allocator_type const& allocator
+ );
+
+ binode_container& operator=(BOOST_RV_REF(binode_container) source);
+
+ binode_container&
+ operator=(BOOST_COPY_ASSIGN_REF(binode_container) copy);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+ //[reference__binode_container__dtor
+ ~binode_container();
+ //]
+
+ //[reference__binode_container__data__const
+ typename node::const_pointer data() const;
+ //]
+
+ //[reference__binode_container__data
+ typename node::pointer data();
+ //]
+
+ //[reference__binode_container__cbegin
+ const_iterator cbegin() const;
+ const_iterator begin() const;
+ //]
+
+ //[reference__binode_container__begin
+ iterator begin();
+ //]
+
+ //[reference__binode_container__cend
+ const_iterator cend() const;
+ const_iterator end() const;
+ //]
+
+ //[reference__binode_container__end
+ iterator end();
+ //]
+
+ //[reference__binode_container__crbegin
+ const_reverse_iterator crbegin() const;
+ const_reverse_iterator rbegin() const;
+ //]
+
+ //[reference__binode_container__rbegin
+ reverse_iterator rbegin();
+ //]
+
+ //[reference__binode_container__crend
+ const_reverse_iterator crend() const;
+ const_reverse_iterator rend() const;
+ //]
+
+ //[reference__binode_container__rend
+ reverse_iterator rend();
+ //]
+
+ //[reference__binode_container__cback
+ const_reference back() const;
+ //]
+
+ //[reference__binode_container__back
+ reference back();
+ //]
+
+ //[reference__binode_container__push_back
+ void push_back(const_reference t);
+ //]
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ //[reference__binode_container__emplace_back
+ template <typename ...Args>
+ void emplace_back(Args&& ...args);
+ //]
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ void \
+ emplace_back( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ //[reference__binode_container__pop_back
+ void pop_back();
+ //]
+
+ //[reference__binode_container__cfront
+ const_reference front() const;
+ //]
+
+ //[reference__binode_container__front
+ reference front();
+ //]
+
+ //[reference__binode_container__push_front
+ void push_front(const_reference t);
+ //]
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ //[reference__binode_container__emplace_front
+ template <typename ...Args>
+ void emplace_front(Args&& ...args);
+ //]
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ void \
+ emplace_front( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ //[reference__binode_container__pop_front
+ void pop_front();
+ //]
+
+ //[reference__binode_container__insert
+ iterator insert(const_iterator itr, const_reference t);
+ //]
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ //[reference__binode_container__emplace
+ template <typename ...Args>
+ iterator emplace(const_iterator itr, Args&& ...args);
+ //]
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ iterator \
+ emplace( \
+ const_iterator itr \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ //[reference__binode_container__erase
+ iterator erase(const_iterator p);
+ //]
+
+ //[reference__binode_container__erase_range
+ void erase(const_iterator itr, const_iterator itr_end);
+ //]
+
+ //[reference__binode_container__empty
+ bool empty() const;
+ //]
+
+ //[reference__binode_container__clear
+ void clear();
+ //]
+
+ //[reference__binode_container__size
+ size_type size() const;
+ //]
+
+ //[reference__binode_container__index_operator__const
+ const_reference operator[](size_type index) const;
+ //]
+
+ //[reference__binode_container__index_operator
+ reference operator[](size_type index);
+ //]
+
+ private:
+ static typename node::pointer
+ _construct_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , value_type const& value
+ );
+
+ static typename node::pointer
+ _construct_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , value_type const& value
+ );
+
+ static typename node::pointer
+ _construct_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , typename node::pointer p
+ );
+
+ static typename node::pointer
+ _construct_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , typename node::pointer p
+ );
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename ...Args>
+ static typename node::pointer
+ _construct_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , Args&& ...args
+ );
+
+ template <typename ...Args>
+ static typename node::pointer
+ _construct_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , Args&& ...args
+ );
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ static typename node::pointer \
+ _construct_from( \
+ ::std::tr1::true_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ static typename node::pointer \
+ _construct_from( \
+ ::std::tr1::false_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ size_type _size(::boost::mpl::true_) const;
+
+ size_type _size(::boost::mpl::false_) const;
+
+ typename node::const_pointer _back() const;
+
+ typename node::pointer _back();
+ };
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::const_reference
+ binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::transform_function::operator()(node const& n) const
+ {
+ return get(n, data_key());
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::reference
+ binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::transform_function::operator()(node& n) const
+ {
+ return get(n, data_key());
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ binode_container<NodeGenerator,T,Balancer>::binode_container()
+ : _allocator()
+ , _root_ptr(
+#if defined BOOST_NO_CXX11_NULLPTR
+ 0
+#else
+ nullptr
+#endif
+ )
+ {
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ binode_container<NodeGenerator,T,Balancer>::binode_container(
+ allocator_type const& allocator
+ ) : _allocator(allocator)
+ , _root_ptr(
+#if defined BOOST_NO_CXX11_NULLPTR
+ 0
+#else
+ nullptr
+#endif
+ )
+ {
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer
+ binode_container<NodeGenerator,T,Balancer>::_construct_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , typename node::pointer p
+ )
+ {
+ if (p)
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(result, *p);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::construct(allocator, result, *p);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+ else
+ {
+ return p;
+ }
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer
+ binode_container<NodeGenerator,T,Balancer>::_construct_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , typename node::pointer p
+ )
+ {
+ if (p)
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(result, *p, allocator);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::construct(allocator, result, *p, allocator);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+ else
+ {
+ return p;
+ }
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ binode_container<NodeGenerator,T,Balancer>::binode_container(
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ binode_container const& copy
+#else
+ BOOST_COPY_ASSIGN_REF(binode_container) copy
+#endif
+ ) : _allocator(copy._allocator)
+ , _root_ptr(
+ this->_construct_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , copy._root_ptr
+ )
+ )
+ {
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ binode_container<NodeGenerator,T,Balancer>::binode_container(
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ binode_container const& copy
+#else
+ BOOST_COPY_ASSIGN_REF(binode_container) copy
+#endif
+ , allocator_type const& allocator
+ ) : _allocator(copy._allocator)
+ , _root_ptr(
+ this->_construct_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , copy._root_ptr
+ )
+ )
+ {
+ }
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <typename NodeGenerator, typename T, typename Balancer>
+ binode_container<NodeGenerator,T,Balancer>::binode_container(
+ BOOST_RV_REF(binode_container) source
+ ) : _allocator(::boost::move(source._allocator))
+ , _root_ptr(source._root_ptr)
+ {
+#if defined BOOST_NO_CXX11_NULLPTR
+ source._root_ptr = 0;
+#else
+ source._root_ptr = nullptr;
+#endif
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ binode_container<NodeGenerator,T,Balancer>::binode_container(
+ BOOST_RV_REF(binode_container) source
+ , allocator_type const& allocator
+ ) : _allocator(allocator), _root_ptr(source._root_ptr)
+ {
+#if defined BOOST_NO_CXX11_NULLPTR
+ source._root_ptr = 0;
+#else
+ source._root_ptr = nullptr;
+#endif
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline binode_container<NodeGenerator,T,Balancer>&
+ binode_container<NodeGenerator,T,Balancer>::operator=(
+ BOOST_RV_REF(binode_container) source
+ )
+ {
+ if (this != &static_cast<binode_container&>(source))
+ {
+ this->_allocator = ::boost::move(source._allocator);
+ this->clear();
+ this->_root_ptr = source._root_ptr;
+#if defined BOOST_NO_CXX11_NULLPTR
+ source._root_ptr = 0;
+#else
+ source._root_ptr = nullptr;
+#endif
+ }
+
+ return *this;
+ }
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline binode_container<NodeGenerator,T,Balancer>&
+ binode_container<NodeGenerator,T,Balancer>::operator=(
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ binode_container const& copy
+#else
+ BOOST_COPY_ASSIGN_REF(binode_container) copy
+#endif
+ )
+ {
+ if (this != &copy)
+ {
+ if (copy._root_ptr)
+ {
+ if (this->_root_ptr)
+ {
+ *this->_root_ptr = *copy._root_ptr;
+ }
+ else
+ {
+ this->_root_ptr = this->_construct_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , copy._root_ptr
+ );
+ }
+ }
+ else
+ {
+ this->clear();
+ }
+ }
+
+ return *this;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ binode_container<NodeGenerator,T,Balancer>::~binode_container()
+ {
+ this->clear();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::node::const_pointer
+ binode_container<NodeGenerator,T,Balancer>::data() const
+ {
+ return this->_root_ptr;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::node::pointer
+ binode_container<NodeGenerator,T,Balancer>::data()
+ {
+ return this->_root_ptr;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::const_iterator
+ binode_container<NodeGenerator,T,Balancer>::cbegin() const
+ {
+ return this->_root_ptr ? const_iterator(
+ make_in_order_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->cend();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::const_iterator
+ binode_container<NodeGenerator,T,Balancer>::begin() const
+ {
+ return this->_root_ptr ? const_iterator(
+ make_in_order_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->end();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::iterator
+ binode_container<NodeGenerator,T,Balancer>::begin()
+ {
+ return this->_root_ptr ? iterator(
+ make_in_order_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->end();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::const_iterator
+ binode_container<NodeGenerator,T,Balancer>::cend() const
+ {
+ return const_iterator(
+ make_in_order_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::const_iterator
+ binode_container<NodeGenerator,T,Balancer>::end() const
+ {
+ return const_iterator(
+ make_in_order_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::iterator
+ binode_container<NodeGenerator,T,Balancer>::end()
+ {
+ return iterator(
+ make_in_order_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::const_reverse_iterator
+ binode_container<NodeGenerator,T,Balancer>::crbegin() const
+ {
+ return this->_root_ptr ? const_reverse_iterator(
+ make_in_order_reverse_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->crend();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::const_reverse_iterator
+ binode_container<NodeGenerator,T,Balancer>::rbegin() const
+ {
+ return this->_root_ptr ? const_reverse_iterator(
+ make_in_order_reverse_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->rend();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::reverse_iterator
+ binode_container<NodeGenerator,T,Balancer>::rbegin()
+ {
+ return this->_root_ptr ? reverse_iterator(
+ make_in_order_reverse_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->rend();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::const_reverse_iterator
+ binode_container<NodeGenerator,T,Balancer>::crend() const
+ {
+ return const_reverse_iterator(
+ make_in_order_reverse_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::const_reverse_iterator
+ binode_container<NodeGenerator,T,Balancer>::rend() const
+ {
+ return const_reverse_iterator(
+ make_in_order_reverse_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<
+ NodeGenerator
+ , T
+ , Balancer
+ >::reverse_iterator
+ binode_container<NodeGenerator,T,Balancer>::rend()
+ {
+ return reverse_iterator(
+ make_in_order_reverse_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::const_reference
+ binode_container<NodeGenerator,T,Balancer>::front() const
+ {
+ return *this->cbegin();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::reference
+ binode_container<NodeGenerator,T,Balancer>::front()
+ {
+ return *this->begin();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::const_reference
+ binode_container<NodeGenerator,T,Balancer>::back() const
+ {
+ return *this->crbegin();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::reference
+ binode_container<NodeGenerator,T,Balancer>::back()
+ {
+ return *this->rbegin();
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ void binode_container<NodeGenerator,T,Balancer>::pop_front()
+ {
+ this->erase(this->cbegin());
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::node::const_pointer
+ binode_container<NodeGenerator,T,Balancer>::_back() const
+ {
+ typename node::const_pointer result = this->_root_ptr;
+
+ if (result)
+ {
+ while (result->get_right_child_ptr())
+ {
+ result = result->get_right_child_ptr();
+ }
+ }
+
+ return result;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer
+ binode_container<NodeGenerator,T,Balancer>::_back()
+ {
+ typename node::pointer result = this->_root_ptr;
+
+ if (result)
+ {
+ while (result->get_right_child_ptr())
+ {
+ result = result->get_right_child_ptr();
+ }
+ }
+
+ return result;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ void binode_container<NodeGenerator,T,Balancer>::pop_back()
+ {
+ this->erase(
+ iterator(
+ make_in_order_iterator_position(*this->_back())
+ , transform_function()
+ )
+ );
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer
+ binode_container<NodeGenerator,T,Balancer>::_construct_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , value_type const& value
+ )
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(result, value);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::construct(allocator, result, value);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer
+ binode_container<NodeGenerator,T,Balancer>::_construct_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , value_type const& value
+ )
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(
+ result
+ , ::boost::container::allocator_arg
+ , allocator
+ , value
+ );
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<allocator_type>::construct(
+ allocator
+ , result
+ , ::boost::container::allocator_arg
+ , allocator
+ , value
+ );
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ void
+ binode_container<NodeGenerator,T,Balancer>::push_front(
+ const_reference t
+ )
+ {
+ if (this->_root_ptr)
+ {
+ typename node::pointer p = this->_root_ptr;
+
+ while (p->get_left_child_ptr())
+ {
+ p = p->get_left_child_ptr();
+ }
+
+ p = Balancer::post_insert(p = &*p->emplace_left(t));
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+ else // if (!this->_root_ptr)
+ {
+ this->_root_ptr = this->_construct_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , t
+ );
+ }
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ void
+ binode_container<NodeGenerator,T,Balancer>::push_back(
+ const_reference t
+ )
+ {
+ if (this->_root_ptr)
+ {
+ typename node::pointer p = this->_root_ptr;
+
+ while (p->get_right_child_ptr())
+ {
+ p = p->get_right_child_ptr();
+ }
+
+ p = Balancer::post_insert(p = &*p->emplace_right(t));
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+ else // if (!this->_root_ptr)
+ {
+ this->_root_ptr = this->_construct_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , t
+ );
+ }
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::iterator
+ binode_container<NodeGenerator,T,Balancer>::insert(
+ const_iterator itr
+ , const_reference t
+ )
+ {
+ if (itr.base())
+ {
+ typename node::pointer anc_ptr = const_cast<
+ typename node::pointer
+ >(&*itr.base());
+ typename node::pointer node_ptr = anc_ptr->get_left_child_ptr();
+
+ if (node_ptr)
+ {
+ while (node_ptr->get_right_child_ptr())
+ {
+ node_ptr = node_ptr->get_right_child_ptr();
+ }
+
+ node_ptr = &*node_ptr->emplace_right(t);
+ }
+ else
+ {
+ node_ptr = &*anc_ptr->emplace_left(t);
+ }
+
+ anc_ptr = Balancer::post_insert(node_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+
+ return iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ );
+ }
+ else // if (!itr)
+ {
+ this->push_back(t);
+ return this->end();
+ }
+ }
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename NodeGenerator, typename T, typename Balancer>
+ template <typename ...Args>
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer
+ binode_container<NodeGenerator,T,Balancer>::_construct_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , Args&& ...args
+ )
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(result, ::boost::forward<Args>(args)...);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::construct(allocator, result, ::boost::forward<Args>(args)...);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ template <typename ...Args>
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer
+ binode_container<NodeGenerator,T,Balancer>::_construct_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , Args&& ...args
+ )
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(
+ result
+ , ::boost::container::allocator_arg
+ , allocator
+ , ::boost::forward<Args>(args)...
+ );
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<allocator_type>::construct(
+ allocator
+ , result
+ , ::boost::container::allocator_arg
+ , allocator
+ , ::boost::forward<Args>(args)...
+ );
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ template <typename ...Args>
+ void
+ binode_container<NodeGenerator,T,Balancer>::emplace_front(
+ Args&& ...args
+ )
+ {
+ if (this->_root_ptr)
+ {
+ typename node::pointer p = this->_root;
+
+ while (p->get_left_child_ptr())
+ {
+ p = p->get_left_child_ptr();
+ }
+
+ p = Balancer::post_insert(
+ p = &*p->emplace_left(::boost::forward<Args>(args)...)
+ );
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+ else // if (!this->_root_ptr)
+ {
+ this->_root_ptr = this->_construct_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , ::boost::forward<Args>(args)...
+ );
+ }
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ template <typename ...Args>
+ void
+ binode_container<NodeGenerator,T,Balancer>::emplace_back(
+ Args&& ...args
+ )
+ {
+ if (this->_root_ptr)
+ {
+ typename node::pointer p = this->_root;
+
+ while (p->get_right_child_ptr())
+ {
+ p = p->get_right_child_ptr();
+ }
+
+ p = Balancer::post_insert(
+ p = &*p->emplace_right(::boost::forward<Args>(args)...)
+ );
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+ else // if (!this->_root_ptr)
+ {
+ this->_root_ptr = this->_construct_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , ::boost::forward<Args>(args)...
+ );
+ }
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ template <typename ...Args>
+ typename binode_container<NodeGenerator,T,Balancer>::iterator
+ binode_container<NodeGenerator,T,Balancer>::emplace(
+ const_iterator itr
+ , Args&& ...args
+ )
+ {
+ if (itr.base())
+ {
+ typename node::pointer anc_ptr = const_cast<
+ typename node::pointer
+ >(&*itr.base());
+ typename node::pointer node_ptr = anc_ptr->get_left_child_ptr();
+
+ if (node_ptr)
+ {
+ while (node_ptr->get_right_child_ptr())
+ {
+ node_ptr = node_ptr->get_right_child_ptr();
+ }
+
+ node_ptr = &*node_ptr->emplace_right(
+ ::boost::forward<Args>(args)...
+ );
+ }
+ else
+ {
+ node_ptr = &*anc_ptr->emplace_left(
+ ::boost::forward<Args>(args)...
+ );
+ }
+
+ anc_ptr = Balancer::post_insert(node_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+
+ return iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ );
+ }
+ else // if (!itr)
+ {
+ this->emplace_back(::boost::forward<Args>(args)...);
+ return this->end();
+ }
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ template <typename NodeGenerator, typename T, typename Balancer> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer \
+ binode_container<NodeGenerator,T,Balancer>::_construct_from( \
+ ::std::tr1::true_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename node::pointer result(allocator.allocate(1)); \
+ allocator.construct( \
+ result \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ template <typename NodeGenerator, typename T, typename Balancer> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer \
+ binode_container<NodeGenerator,T,Balancer>::_construct_from( \
+ ::std::tr1::false_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename node::pointer result(allocator.allocate(1)); \
+ allocator.construct( \
+ result \
+ , ::boost::container::allocator_arg \
+ , allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ template <typename NodeGenerator, typename T, typename Balancer> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer \
+ binode_container<NodeGenerator,T,Balancer>::_construct_from( \
+ ::std::tr1::true_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename node::pointer result( \
+ ::boost::container::allocator_traits< \
+ allocator_type \
+ >::allocate(allocator, 1) \
+ ); \
+ ::boost::container::allocator_traits<allocator_type>::construct( \
+ allocator \
+ , result \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ template <typename NodeGenerator, typename T, typename Balancer> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_container<NodeGenerator,T,Balancer>::node::pointer \
+ binode_container<NodeGenerator,T,Balancer>::_construct_from( \
+ ::std::tr1::false_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename node::pointer result( \
+ ::boost::container::allocator_traits< \
+ allocator_type \
+ >::allocate(allocator, 1) \
+ ); \
+ ::boost::container::allocator_traits<allocator_type>::construct( \
+ allocator \
+ , result \
+ , ::boost::container::allocator_arg \
+ , allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ template <typename NodeGenerator, typename T, typename Balancer> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ void \
+ binode_container<NodeGenerator,T,Balancer>::emplace_front( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ if (this->_root_ptr) \
+ { \
+ typename node::pointer p = this->_root; \
+ while (p->get_left_child_ptr()) \
+ { \
+ p = p->get_left_child_ptr(); \
+ } \
+ p = Balancer::post_insert( \
+ p = &*p->emplace_left( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ); \
+ if (!p->get_parent_ptr()) \
+ { \
+ this->_root_ptr = p; \
+ } \
+ } \
+ else \
+ { \
+ this->_root_ptr = this->_construct_from( \
+ ::std::tr1::is_const< \
+ typename ::std::tr1::remove_reference< \
+ typename node::traits::allocator_reference \
+ >::type \
+ >() \
+ , this->_allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ template <typename NodeGenerator, typename T, typename Balancer> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ void \
+ binode_container<NodeGenerator,T,Balancer>::emplace_back( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ if (this->_root_ptr) \
+ { \
+ typename node::pointer p = this->_root; \
+ while (p->get_right_child_ptr()) \
+ { \
+ p = p->get_right_child_ptr(); \
+ } \
+ p = Balancer::post_insert( \
+ p = &*p->emplace_right( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ); \
+ if (!p->get_parent_ptr()) \
+ { \
+ this->_root_ptr = p; \
+ } \
+ } \
+ else \
+ { \
+ this->_root_ptr = this->_construct_from( \
+ ::std::tr1::is_const< \
+ typename ::std::tr1::remove_reference< \
+ typename node::traits::allocator_reference \
+ >::type \
+ >() \
+ , this->_allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_MACRO(z, n, _) \
+ template <typename NodeGenerator, typename T, typename Balancer> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_container<NodeGenerator,T,Balancer>::iterator \
+ binode_container<NodeGenerator,T,Balancer>::emplace( \
+ const_iterator itr \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ if (itr.base()) \
+ { \
+ typename node::pointer anc_ptr = const_cast< \
+ typename node::pointer \
+ >(&*itr.base()); \
+ typename node::pointer node_ptr = ( \
+ anc_ptr->get_left_child_ptr() \
+ ); \
+ if (node_ptr) \
+ { \
+ while (node_ptr->get_right_child_ptr()) \
+ { \
+ node_ptr = node_ptr->get_right_child_ptr(); \
+ } \
+ node_ptr = &*node_ptr->emplace_right( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+ else \
+ { \
+ node_ptr = &*anc_ptr->emplace_left( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+ anc_ptr = Balancer::post_insert(node_ptr); \
+ if (!anc_ptr->get_parent_ptr()) \
+ { \
+ this->_root_ptr = anc_ptr; \
+ } \
+ return iterator( \
+ make_in_order_iterator_position(*node_ptr) \
+ , transform_function() \
+ ); \
+ } \
+ else \
+ { \
+ this->emplace_back( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return this->end(); \
+ } \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::iterator
+ binode_container<NodeGenerator,T,Balancer>::erase(
+ const_iterator itr
+ )
+ {
+ if (itr.base()->empty() && (this->_root_ptr == &*itr.base()))
+ {
+ this->clear();
+ return this->end();
+ }
+
+ typename node::pointer anc_ptr = const_cast<typename node::pointer>(
+ &*itr.base()
+ );
+ iterator result(
+ make_in_order_iterator_position(*anc_ptr)
+ , transform_function()
+ );
+ bool must_erase_begin = (result == this->begin());
+
+ if (!must_erase_begin)
+ {
+ --result;
+ }
+
+ for (typename node::pointer desc_ptr;;)
+ {
+ if (
+ (desc_ptr = anc_ptr->get_left_child_ptr()) && (
+ !anc_ptr->get_right_child_ptr()
+ )
+ )
+ {
+ while (desc_ptr->get_right_child_ptr())
+ {
+ desc_ptr = desc_ptr->get_right_child_ptr();
+ }
+
+ if (desc_ptr->get_parent_ptr() == anc_ptr)
+ {
+ if (!anc_ptr->get_right_child_ptr())
+ {
+ put(*anc_ptr, data_key(), get(*desc_ptr, data_key()));
+
+ bool must_rebalance = Balancer::pre_erase(*desc_ptr);
+
+ anc_ptr->erase_left();
+
+ if (must_rebalance)
+ {
+ anc_ptr = Balancer::post_erase_left(anc_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+ }
+
+ break;
+ }
+ }
+ else // if (desc_ptr == anc_ptr->get_right_child_ptr())
+ {
+ put(*anc_ptr, data_key(), get(*desc_ptr, data_key()));
+
+ if (desc_ptr->get_left_child_ptr())
+ {
+ anc_ptr = desc_ptr;
+ }
+ else // if (desc_ptr->empty())
+ {
+ anc_ptr = desc_ptr->get_parent_ptr();
+
+ if (anc_ptr->get_left_child_ptr())
+ {
+ put(*desc_ptr, data_key(), get(*anc_ptr, data_key()));
+ }
+ else // desc_ptr is only child of anc_ptr
+ {
+ bool must_rebalance = Balancer::pre_erase(*desc_ptr);
+
+ anc_ptr->erase_right();
+
+ if (must_rebalance)
+ {
+ anc_ptr = Balancer::post_erase_right(anc_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+ }
+
+ break;
+ }
+ }
+
+ continue;
+ }
+ }
+
+ if ((desc_ptr = anc_ptr->get_right_child_ptr()))
+ {
+ while (desc_ptr->get_left_child_ptr())
+ {
+ desc_ptr = desc_ptr->get_left_child_ptr();
+ }
+
+ put(*anc_ptr, data_key(), get(*desc_ptr, data_key()));
+
+ if (desc_ptr->get_right_child_ptr())
+ {
+ if (desc_ptr->get_right_child_ptr()->empty())
+ {
+ bool must_rebalance = Balancer::pre_erase(*desc_ptr);
+
+ anc_ptr->erase_right();
+
+ if (must_rebalance)
+ {
+ anc_ptr = Balancer::post_erase_right(anc_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+ }
+ }
+ else
+ {
+ anc_ptr = desc_ptr;
+ }
+ }
+ else if (desc_ptr->get_parent_ptr() == anc_ptr)
+ {
+ bool must_rebalance = Balancer::pre_erase(*desc_ptr);
+
+ anc_ptr->erase_right();
+
+ if (must_rebalance)
+ {
+ anc_ptr = Balancer::post_erase_right(anc_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+ }
+
+ break;
+ }
+ else
+ {
+ BOOST_ASSERT(desc_ptr->empty());
+ anc_ptr = desc_ptr->get_parent_ptr();
+ BOOST_ASSERT(anc_ptr->get_left_child_ptr() == desc_ptr);
+
+ if (anc_ptr->get_right_child_ptr())
+ {
+ put(*desc_ptr, data_key(), get(*anc_ptr, data_key()));
+ }
+ else // desc_ptr is only child of anc_ptr
+ {
+ bool must_rebalance = Balancer::pre_erase(*desc_ptr);
+
+ anc_ptr->erase_left();
+
+ if (must_rebalance)
+ {
+ anc_ptr = Balancer::post_erase_left(anc_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+ }
+
+ break;
+ }
+ }
+ }
+ else // if (anc_ptr->empty())
+ {
+ desc_ptr = anc_ptr;
+ anc_ptr = anc_ptr->get_parent_ptr();
+
+ bool must_rebalance = Balancer::pre_erase(*desc_ptr);
+
+ if (anc_ptr->get_left_child_ptr() == desc_ptr)
+ {
+ anc_ptr->erase_left();
+
+ if (must_rebalance)
+ {
+ anc_ptr = Balancer::post_erase_left(anc_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+ }
+ }
+ else // if (anc_ptr->get_right_child_ptr() == desc_ptr)
+ {
+ anc_ptr->erase_right();
+
+ if (must_rebalance)
+ {
+ anc_ptr = Balancer::post_erase_right(anc_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+ }
+ }
+
+ break;
+ }
+ }
+
+ return must_erase_begin ? this->begin() : ++result;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ void
+ binode_container<NodeGenerator,T,Balancer>::erase(
+ const_iterator itr
+ , const_iterator itr_end
+ )
+ {
+ while (itr != itr_end)
+ {
+ itr = this->erase(itr);
+ }
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline bool binode_container<NodeGenerator,T,Balancer>::empty() const
+ {
+ return !this->_root_ptr;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ void binode_container<NodeGenerator,T,Balancer>::clear()
+ {
+ if (this->_root_ptr)
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ this->_allocator.destroy(this->_root_ptr);
+ this->_allocator.deallocate(this->_root_ptr, 1);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::destroy(this->_allocator, this->_root_ptr);
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::deallocate(this->_allocator, this->_root_ptr, 1);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+#if defined BOOST_NO_CXX11_NULLPTR
+ this->_root_ptr = 0;
+#else
+ this->_root_ptr = nullptr;
+#endif
+ }
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::size_type
+ binode_container<NodeGenerator,T,Balancer>::_size(
+ ::boost::mpl::true_
+ ) const
+ {
+ return this->_root_ptr ? get(*this->_root_ptr, count_key()) : 0;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::size_type
+ binode_container<NodeGenerator,T,Balancer>::_size(
+ ::boost::mpl::false_
+ ) const
+ {
+ size_type result = ::boost::initialized_value;
+
+ for (const_iterator itr = this->cbegin(); itr; ++itr)
+ {
+ ++result;
+ }
+
+ return result;
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ inline typename binode_container<NodeGenerator,T,Balancer>::size_type
+ binode_container<NodeGenerator,T,Balancer>::size() const
+ {
+ return this->_size(result_of::has_key<node,count_key>());
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::const_reference
+ binode_container<NodeGenerator,T,Balancer>::operator[](
+ size_type index
+ ) const
+ {
+ BOOST_ASSERT_MSG(
+ this->_root_ptr && (index < this->size())
+ , "index out of bounds"
+ );
+
+ typename node::const_pointer node_ptr = this->_root_ptr;
+
+ return transform_function()(
+ *binary_descendant_at_index(node_ptr, index)
+ );
+ }
+
+ template <typename NodeGenerator, typename T, typename Balancer>
+ typename binode_container<NodeGenerator,T,Balancer>::reference
+ binode_container<NodeGenerator,T,Balancer>::operator[](size_type index)
+ {
+ BOOST_ASSERT_MSG(
+ this->_root_ptr && (index < this->size())
+ , "index out of bounds"
+ );
+
+ return transform_function()(
+ *binary_descendant_at_index(this->_root_ptr, index)
+ );
+ }
+}} // namespace boost::tree_node
+
+#endif // BOOST_TREE_NODE_CONTAINER_BINODE_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/container/binode_associative.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/container/binode_associative.hpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,4679 @@
+// Copyright (C) 2013 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_CONTAINER_BINODE_ASSOCIATIVE_HPP_INCLUDED
+#define BOOST_TREE_NODE_CONTAINER_BINODE_ASSOCIATIVE_HPP_INCLUDED
+
+#include <boost/config.hpp>
+
+#if !defined BOOST_NO_CXX11_NULLPTR
+#include <cstddef>
+#endif
+
+#include <utility>
+#include <boost/tr1/type_traits.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/mpl/apply_wrap.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/utility/value_init.hpp>
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#include <boost/move/move.hpp>
+#include <boost/container/allocator_traits.hpp>
+#endif
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/preprocessor/repetition/repeat.hpp>
+#endif
+
+#include <boost/tree_node/preprocessor.hpp>
+#include <boost/tree_node/key/data.hpp>
+#include <boost/tree_node/key/count.hpp>
+#include <boost/tree_node/iterator/in_order.hpp>
+#include <boost/tree_node/intrinsic/has_key.hpp>
+#include <boost/tree_node/intrinsic/value_at_key.hpp>
+#include <boost/tree_node/algorithm/binary_descendant.hpp>
+#include <boost/tree_node/algorithm/binary_lower_bound.hpp>
+#include <boost/tree_node/algorithm/binary_upper_bound.hpp>
+#include <boost/tree_node/algorithm/binary_descendant_at_index.hpp>
+#include <boost/tree_node/container/binode_associative_fwd.hpp>
+#include <boost/assert.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ class binode_associative_container
+ {
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ BOOST_COPYABLE_AND_MOVABLE(binode_associative_container)
+#endif
+
+ public:
+ //[reference__binode_associative_container__key_type
+ typedef T1 key_type;
+ //]
+
+ //[reference__binode_associative_container__value_type
+ typedef typename ::boost::mpl::if_<
+ ::std::tr1::is_void<T2>
+ , T1
+ , ::std::pair<T1 const,T2>
+ >::type
+ value_type;
+ //]
+
+ //[reference__binode_associative_container__reference
+ typedef value_type& reference;
+ //]
+
+ //[reference__binode_associative_container__const_reference
+ typedef value_type const& const_reference;
+ //]
+
+ //[reference__binode_associative_container__pointer
+ typedef value_type* pointer;
+ //]
+
+ //[reference__binode_associative_container__const_pointer
+ typedef value_type const* const_pointer;
+ //]
+
+ //[reference__binode_associative_container__node
+ typedef typename ::boost::mpl::apply_wrap1<
+ NodeGenerator
+ , typename ::boost::mpl::if_<
+ ::std::tr1::is_void<T2>
+ , T1
+ , ::std::pair<T1,T2>
+ >::type
+ >::type
+ node;
+ //]
+
+ //[reference__binode_associative_container__allocator_type
+ typedef typename node::traits::allocator allocator_type;
+ //]
+
+ private:
+ //[reference__binode_associative_container__transition_function
+ struct simple_transform_function
+ {
+ typedef const_reference const_result;
+ typedef const_reference mutable_result;
+ const_reference operator()(node const& n) const;
+ };
+
+ struct pair_associative_transform_function
+ {
+ typedef ::std::pair<T1 const&,T2 const&> const_result;
+ typedef ::std::pair<T1 const&,T2&> mutable_result;
+ const_result operator()(node const& n) const;
+ mutable_result operator()(node& n) const;
+ };
+
+ typedef typename ::boost::mpl::if_<
+ ::std::tr1::is_void<T2>
+ , simple_transform_function
+ , pair_associative_transform_function
+ >::type
+ transform_function;
+ //]
+
+ public:
+ //[reference__binode_associative_container__iterator
+ typedef ::boost::transform_iterator<
+ transform_function
+ , in_order_iterator<
+ typename ::boost::mpl::if_<
+ ::std::tr1::is_void<T2>
+ , node const
+ , node
+ >::type
+ >
+ >
+ iterator;
+ //]
+
+ //[reference__binode_associative_container__const_iterator
+ typedef ::boost::transform_iterator<
+ transform_function
+ , in_order_iterator<node const>
+ >
+ const_iterator;
+ //]
+
+ //[reference__binode_associative_container__reverse_iterator
+ typedef ::boost::transform_iterator<
+ transform_function
+ , in_order_iterator<
+ typename ::boost::mpl::if_<
+ ::std::tr1::is_void<T2>
+ , node const
+ , node
+ >::type
+ , ::boost::mpl::true_
+ >
+ >
+ reverse_iterator;
+ //]
+
+ //[reference__binode_associative_container__const_reverse_iterator
+ typedef ::boost::transform_iterator<
+ transform_function
+ , in_order_iterator<node const,::boost::mpl::true_>
+ >
+ const_reverse_iterator;
+ //]
+
+ //[reference__binode_associative_container__size_type
+ typedef typename ::boost::mpl::eval_if<
+ result_of::has_key<node,count_key>
+ , result_of::value_at_key<node,count_key>
+ , typename node::size_type
+ >::type
+ size_type;
+ //]
+
+ //[reference__binode_associative_container__key_compare
+ typedef typename ::boost::mpl::apply_wrap1<
+ CompareSelector
+ , key_type
+ >::type
+ key_compare;
+ //]
+
+ //[reference__binode_associative_container__value_compare
+ class value_compare
+ {
+ //<-
+ key_compare const& _compare;
+ //->
+
+ public:
+ typedef bool result_type;
+
+ explicit value_compare(key_compare const& compare);
+ result_type operator()(const_reference, const_reference) const;
+ result_type operator()(node const& n, key_type const& key) const;
+ result_type operator()(key_type const& key, node const& n) const;
+
+ //<-
+ private:
+ result_type
+ _evaluate(
+ const_reference arg1
+ , const_reference arg2
+ , ::std::tr1::true_type
+ ) const;
+ result_type
+ _evaluate(
+ const_reference arg1
+ , const_reference arg2
+ , ::std::tr1::false_type
+ ) const;
+ result_type
+ _evaluate(
+ node const& n
+ , key_type const& key
+ , ::std::tr1::true_type
+ ) const;
+ result_type
+ _evaluate(
+ node const& n
+ , key_type const& key
+ , ::std::tr1::false_type
+ ) const;
+ result_type
+ _evaluate(
+ key_type const& key
+ , node const& n
+ , ::std::tr1::true_type
+ ) const;
+ result_type
+ _evaluate(
+ key_type const& key
+ , node const& n
+ , ::std::tr1::false_type
+ ) const;
+ //->
+ };
+ //]
+
+ private:
+ class insert_compare
+ {
+ key_compare const& _compare;
+
+ public:
+ typedef bool result_type;
+
+ explicit insert_compare(key_compare const& compare);
+ result_type operator()(node const&, const_reference) const;
+ result_type operator()(const_reference, node const&) const;
+
+ private:
+ result_type
+ _evaluate(
+ node const& n
+ , const_reference value
+ , ::std::tr1::true_type
+ ) const;
+ result_type
+ _evaluate(
+ node const& n
+ , const_reference value
+ , ::std::tr1::false_type
+ ) const;
+ result_type
+ _evaluate(
+ const_reference value
+ , node const& n
+ , ::std::tr1::true_type
+ ) const;
+ result_type
+ _evaluate(
+ const_reference value
+ , node const& n
+ , ::std::tr1::false_type
+ ) const;
+ };
+
+ allocator_type _allocator;
+ typename node::pointer _root_ptr;
+ key_compare _key_compare;
+ value_compare _value_compare;
+
+ public:
+ //[reference__binode_associative_container__default_ctor
+ binode_associative_container();
+ //]
+
+ //[reference__binode_associative_container__ctor_w_alloc
+ explicit binode_associative_container(allocator_type const& allocator);
+ //]
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ //[reference__binode_associative_container__copy_ctor
+ binode_associative_container(
+ binode_associative_container const& copy
+ );
+ //]
+#else
+ binode_associative_container(
+ BOOST_COPY_ASSIGN_REF(binode_associative_container) copy
+ );
+#endif
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ //[reference__binode_associative_container__copy_ctor_w_alloc
+ binode_associative_container(
+ binode_associative_container const& copy
+ , allocator_type const& allocator
+ );
+ //]
+#else
+ binode_associative_container(
+ BOOST_COPY_ASSIGN_REF(binode_associative_container) copy
+ , allocator_type const& allocator
+ );
+#endif
+
+#if 0
+ //[reference__binode_associative_container__move_ctor
+ binode_associative_container(binode_associative_container&& source);
+ //]
+
+ //[reference__binode_associative_container__move_ctor_w_alloc
+ binode_associative_container(
+ binode_associative_container&& source
+ , allocator_type const& allocator
+ );
+ //]
+
+ //[reference__binode_associative_container__move_assign
+ binode_associative_container&
+ operator=(binode_associative_container&& source);
+ //]
+#endif
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ binode_associative_container(
+ BOOST_RV_REF(binode_associative_container) source
+ );
+
+ binode_associative_container(
+ BOOST_RV_REF(binode_associative_container) source
+ , allocator_type const& allocator
+ );
+
+ binode_associative_container&
+ operator=(BOOST_RV_REF(binode_associative_container) source);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ //[reference__binode_associative_container__copy_assign
+ binode_associative_container&
+ operator=(binode_associative_container const& copy);
+ //]
+#else
+ binode_associative_container&
+ operator=(
+ BOOST_COPY_ASSIGN_REF(binode_associative_container) copy
+ );
+#endif
+
+ //[reference__binode_associative_container__dtor
+ ~binode_associative_container();
+ //]
+
+ //[reference__binode_associative_container__data
+ typename node::const_pointer data() const;
+ //]
+
+ //[reference__binode_associative_container__cbegin
+ const_iterator cbegin() const;
+ const_iterator begin() const;
+ //]
+
+ //[reference__binode_associative_container__begin
+ iterator begin();
+ //]
+
+ //[reference__binode_associative_container__cend
+ const_iterator cend() const;
+ const_iterator end() const;
+ //]
+
+ //[reference__binode_associative_container__end
+ iterator end();
+ //]
+
+ //[reference__binode_associative_container__crbegin
+ const_reverse_iterator crbegin() const;
+ const_reverse_iterator rbegin() const;
+ //]
+
+ //[reference__binode_associative_container__rbegin
+ reverse_iterator rbegin();
+ //]
+
+ //[reference__binode_associative_container__crend
+ const_reverse_iterator crend() const;
+ const_reverse_iterator rend() const;
+ //]
+
+ //[reference__binode_associative_container__rend
+ reverse_iterator rend();
+ //]
+
+ //[reference__binode_associative_container__cfind
+ const_iterator find(key_type const& key) const;
+ //]
+
+ //[reference__binode_associative_container__find
+ iterator find(key_type const& key);
+ //]
+
+ //[reference__binode_associative_container__lower_bound__const
+ const_iterator lower_bound(key_type const& key) const;
+ //]
+
+ //[reference__binode_associative_container__lower_bound
+ iterator lower_bound(key_type const& key);
+ //]
+
+ //[reference__binode_associative_container__upper_bound__const
+ const_iterator upper_bound(key_type const& key) const;
+ //]
+
+ //[reference__binode_associative_container__upper_bound
+ iterator upper_bound(key_type const& key);
+ //]
+
+ //[reference__binode_associative_container__equal_range__const
+ ::std::pair<const_iterator,const_iterator>
+ equal_range(key_type const& key) const;
+ //]
+
+ //[reference__binode_associative_container__equal_range
+ ::std::pair<iterator,iterator> equal_range(key_type const& key);
+ //]
+
+ //[reference__binode_associative_container__insert
+ typename ::boost::mpl::if_<
+ IsMultipleAssociative
+ , iterator
+ , ::std::pair<iterator,bool>
+ >::type
+ insert(value_type const& value);
+ //]
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ //[reference__binode_associative_container__emplace
+ template <typename ...Args>
+ typename ::boost::mpl::if_<
+ IsMultipleAssociative
+ , iterator
+ , ::std::pair<iterator,bool>
+ >::type
+ emplace(Args&& ...args);
+ //]
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename ::boost::mpl::if_< \
+ IsMultipleAssociative \
+ , iterator \
+ , ::std::pair<iterator,bool> \
+ >::type \
+ emplace( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ //[reference__binode_associative_container__erase
+ size_type erase(key_type const& key);
+ //]
+
+ //[reference__binode_associative_container__empty
+ bool empty() const;
+ //]
+
+ //[reference__binode_associative_container__clear
+ void clear();
+ //]
+
+ //[reference__binode_associative_container__size
+ size_type size() const;
+ //]
+
+ //[reference__binode_associative_container__index_operator__const
+ typename transform_function::const_result
+ operator[](size_type const& index) const;
+ //]
+
+ //[reference__binode_associative_container__index_operator
+ typename transform_function::mutable_result
+ operator[](size_type const& index);
+ //]
+
+ private:
+ static typename node::pointer
+ _construct_node_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , value_type const& value
+ );
+
+ static typename node::pointer
+ _construct_node_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , value_type const& value
+ );
+
+ static typename node::pointer
+ _construct_node_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , typename node::pointer p
+ );
+
+ static typename node::pointer
+ _construct_node_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , typename node::pointer p
+ );
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename ...Args>
+ static typename node::pointer
+ _construct_node_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , Args&& ...args
+ );
+
+ template <typename ...Args>
+ static typename node::pointer
+ _construct_node_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , Args&& ...args
+ );
+
+ template <typename ...Args>
+ static value_type
+ _construct_value_from(
+ ::std::tr1::true_type
+ , Args&& ...args
+ );
+
+ template <typename ...Args>
+ static value_type
+ _construct_value_from(
+ ::std::tr1::false_type
+ , key_type const& key
+ , Args&& ...args
+ );
+
+ template <typename ...Args>
+ iterator _emplace(::boost::mpl::true_, Args&& ...args);
+
+ template <typename ...Args>
+ ::std::pair<iterator,bool>
+ _emplace(::boost::mpl::false_, Args&& ...args);
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ static typename node::pointer \
+ _construct_node_from( \
+ ::std::tr1::true_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ static typename node::pointer \
+ _construct_node_from( \
+ ::std::tr1::false_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ static value_type \
+ _construct_value_from( \
+ ::std::tr1::true_type \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ static value_type \
+ _construct_value_from( \
+ ::std::tr1::false_type \
+ , key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_PP_DEC(BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ iterator \
+ _emplace( \
+ ::boost::mpl::true_ \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ ::std::pair<iterator,bool> \
+ _emplace( \
+ ::boost::mpl::false_ \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ iterator _insert(value_type const& value, ::boost::mpl::true_);
+
+ ::std::pair<iterator,bool>
+ _insert(value_type const& value, ::boost::mpl::false_);
+
+ void _erase_one(typename node::pointer p);
+
+ size_type _erase(key_type const& key, ::boost::mpl::true_);
+
+ size_type _erase(key_type const& key, ::boost::mpl::false_);
+
+ size_type _size(::boost::mpl::true_) const;
+
+ size_type _size(::boost::mpl::false_) const;
+ };
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_reference
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::simple_transform_function::operator()(node const& n) const
+ {
+ return get(n, data_key());
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::pair_associative_transform_function::const_result
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::pair_associative_transform_function::operator()(node const& n) const
+ {
+ ::std::pair<T1,T2> const& p = get(n, data_key());
+ ::std::pair<T1 const&,T2 const&> result(p.first, p.second);
+ return result;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::pair_associative_transform_function::mutable_result
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::pair_associative_transform_function::operator()(node& n) const
+ {
+ ::std::pair<T1,T2>& p = get(n, data_key());
+ ::std::pair<T1 const&,T2&> result(p.first, p.second);
+ return result;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::value_compare(key_compare const& c) : _compare(c)
+ {
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::_evaluate(
+ const_reference arg1
+ , const_reference arg2
+ , ::std::tr1::true_type
+ ) const
+ {
+ return this->_compare(arg1, arg2);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::_evaluate(
+ const_reference arg1
+ , const_reference arg2
+ , ::std::tr1::false_type
+ ) const
+ {
+ return this->_compare(arg1.first, arg2.first);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::operator()(
+ const_reference arg1
+ , const_reference arg2
+ ) const
+ {
+ return this->_evaluate(arg1, arg2, ::std::tr1::is_void<T2>());
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::_evaluate(
+ node const& n
+ , key_type const& key
+ , ::std::tr1::true_type
+ ) const
+ {
+ return this->_compare(get(n, data_key()), key);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::_evaluate(
+ node const& n
+ , key_type const& key
+ , ::std::tr1::false_type
+ ) const
+ {
+ return this->_compare(get(n, data_key()).first, key);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::operator()(node const& n, key_type const& key) const
+ {
+ return this->_evaluate(n, key, ::std::tr1::is_void<T2>());
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::_evaluate(
+ key_type const& key
+ , node const& n
+ , ::std::tr1::true_type
+ ) const
+ {
+ return this->_compare(key, get(n, data_key()));
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::_evaluate(
+ key_type const& key
+ , node const& n
+ , ::std::tr1::false_type
+ ) const
+ {
+ return this->_compare(key, get(n, data_key()).first);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_compare::operator()(key_type const& key, node const& n) const
+ {
+ return this->_evaluate(key, n, ::std::tr1::is_void<T2>());
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::insert_compare(key_compare const& c) : _compare(c)
+ {
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::_evaluate(
+ const_reference value
+ , node const& n
+ , ::std::tr1::true_type
+ ) const
+ {
+ return this->_compare(value, get(n, data_key()));
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::_evaluate(
+ const_reference value
+ , node const& n
+ , ::std::tr1::false_type
+ ) const
+ {
+ return this->_compare(value.first, get(n, data_key()).first);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::operator()(
+ const_reference value
+ , node const& n
+ ) const
+ {
+ return this->_evaluate(value, n, ::std::tr1::is_void<T2>());
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::_evaluate(
+ node const& n
+ , const_reference value
+ , ::std::tr1::true_type
+ ) const
+ {
+ return this->_compare(get(n, data_key()), value);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::_evaluate(
+ node const& n
+ , const_reference value
+ , ::std::tr1::false_type
+ ) const
+ {
+ return this->_compare(get(n, data_key()).first, value.first);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::result_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert_compare::operator()(
+ node const& n
+ , const_reference value
+ ) const
+ {
+ return this->_evaluate(n, value, ::std::tr1::is_void<T2>());
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::binode_associative_container()
+ : _allocator()
+ , _root_ptr(
+#if defined BOOST_NO_CXX11_NULLPTR
+ 0
+#else
+ nullptr
+#endif
+ )
+ , _key_compare()
+ , _value_compare(this->_key_compare)
+ {
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::binode_associative_container(allocator_type const& allocator)
+ : _allocator(allocator)
+ , _root_ptr(
+#if defined BOOST_NO_CXX11_NULLPTR
+ 0
+#else
+ nullptr
+#endif
+ )
+ , _key_compare()
+ , _value_compare(this->_key_compare)
+ {
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::node::pointer
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_construct_node_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , typename node::pointer p
+ )
+ {
+ if (p)
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(result, *p);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::construct(allocator, result, *p);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+ else
+ {
+ return p;
+ }
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::node::pointer
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_construct_node_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , typename node::pointer p
+ )
+ {
+ if (p)
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(result, *p, allocator);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::construct(allocator, result, *p, allocator);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+ else
+ {
+ return p;
+ }
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::binode_associative_container(
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ binode_associative_container const& copy
+#else
+ BOOST_COPY_ASSIGN_REF(binode_associative_container) copy
+#endif
+ ) : _allocator(copy._allocator)
+ , _root_ptr(
+ this->_construct_node_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , copy._root_ptr
+ )
+ )
+ , _key_compare(copy._key_compare)
+ , _value_compare(this->_key_compare)
+ {
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::binode_associative_container(
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ binode_associative_container const& copy
+#else
+ BOOST_COPY_ASSIGN_REF(binode_associative_container) copy
+#endif
+ , allocator_type const& allocator
+ ) : _allocator(allocator)
+ , _root_ptr(
+ this->_construct_node_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , copy._root_ptr
+ )
+ )
+ , _key_compare(copy._key_compare)
+ , _value_compare(this->_key_compare)
+ {
+ }
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::binode_associative_container(
+ BOOST_RV_REF(binode_associative_container) source
+ ) : _allocator(::boost::move(source._allocator))
+ , _root_ptr(source._root_ptr)
+ , _key_compare(::boost::move(source._key_compare))
+ , _value_compare(this->_key_compare)
+ {
+#if defined BOOST_NO_CXX11_NULLPTR
+ source._root_ptr = 0;
+#else
+ source._root_ptr = nullptr;
+#endif
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::binode_associative_container(
+ BOOST_RV_REF(binode_associative_container) source
+ , allocator_type const& allocator
+ ) : _allocator(allocator)
+ , _root_ptr(source._root_ptr)
+ , _key_compare(::boost::move(source._key_compare))
+ , _value_compare(this->_key_compare)
+ {
+#if defined BOOST_NO_CXX11_NULLPTR
+ source._root_ptr = 0;
+#else
+ source._root_ptr = nullptr;
+#endif
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >&
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::operator=(BOOST_RV_REF(binode_associative_container) source)
+ {
+ if (this != &static_cast<binode_associative_container&>(source))
+ {
+ this->_allocator = ::boost::move(source._allocator);
+ this->clear();
+ this->_root_ptr = source._root_ptr;
+#if defined BOOST_NO_CXX11_NULLPTR
+ source._root_ptr = 0;
+#else
+ source._root_ptr = nullptr;
+#endif
+ this->_key_compare = ::boost::move(source._key_compare);
+ }
+
+ return *this;
+ }
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >&
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::operator=(
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ binode_associative_container const& copy
+#else
+ BOOST_COPY_ASSIGN_REF(binode_associative_container) copy
+#endif
+ )
+ {
+ if (this != &static_cast<binode_associative_container const&>(copy))
+ {
+ if (copy._root_ptr)
+ {
+ if (this->_root_ptr)
+ {
+ *this->_root_ptr = *copy._root_ptr;
+ }
+ else
+ {
+ this->_root_ptr = this->_construct_node_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , copy._root_ptr
+ );
+ }
+ }
+ else
+ {
+ this->clear();
+ }
+
+ this->_key_compare = copy._key_compare;
+ }
+
+ return *this;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::~binode_associative_container()
+ {
+ this->clear();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::node::const_pointer
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::data() const
+ {
+ return this->_root_ptr;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::cbegin() const
+ {
+ return this->_root_ptr ? const_iterator(
+ make_in_order_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->cend();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::begin() const
+ {
+ return this->_root_ptr ? const_iterator(
+ make_in_order_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->end();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::begin()
+ {
+ return this->_root_ptr ? iterator(
+ make_in_order_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->end();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::cend() const
+ {
+ return const_iterator(
+ make_in_order_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::end() const
+ {
+ return const_iterator(
+ make_in_order_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::end()
+ {
+ return iterator(
+ make_in_order_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_reverse_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::crbegin() const
+ {
+ return this->_root_ptr ? const_reverse_iterator(
+ make_in_order_reverse_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->crend();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_reverse_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::rbegin() const
+ {
+ return this->_root_ptr ? const_reverse_iterator(
+ make_in_order_reverse_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->rend();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::reverse_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::rbegin()
+ {
+ return this->_root_ptr ? reverse_iterator(
+ make_in_order_reverse_iterator(*this->_root_ptr)
+ , transform_function()
+ ) : this->rend();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_reverse_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::crend() const
+ {
+ return const_reverse_iterator(
+ make_in_order_reverse_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_reverse_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::rend() const
+ {
+ return const_reverse_iterator(
+ make_in_order_reverse_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::reverse_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::rend()
+ {
+ return reverse_iterator(
+ make_in_order_reverse_iterator_end(this->_root_ptr)
+ , transform_function()
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::find(key_type const& key) const
+ {
+ typename node::const_pointer node_ptr = this->_root_ptr;
+
+ node_ptr = binary_descendant(node_ptr, key, this->_value_compare);
+ return node_ptr ? const_iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ ) : this->cend();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::find(key_type const& key)
+ {
+ typename node::pointer node_ptr = binary_descendant(
+ this->_root_ptr
+ , key
+ , this->_value_compare
+ );
+
+ return node_ptr ? iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ ) : this->end();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::lower_bound(key_type const& key) const
+ {
+ typename node::const_pointer node_ptr = this->_root_ptr;
+
+ node_ptr = binary_lower_bound(node_ptr, key, this->_value_compare);
+ return node_ptr ? const_iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ ) : this->cend();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::lower_bound(key_type const& key)
+ {
+ typename node::pointer node_ptr = binary_lower_bound(
+ this->_root_ptr
+ , key
+ , this->_value_compare
+ );
+
+ return node_ptr ? iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ ) : this->end();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::upper_bound(key_type const& key) const
+ {
+ typename node::const_pointer node_ptr = this->_root_ptr;
+
+ node_ptr = binary_upper_bound(node_ptr, key, this->_value_compare);
+ return node_ptr ? const_iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ ) : this->cend();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::upper_bound(key_type const& key)
+ {
+ typename node::pointer node_ptr = binary_upper_bound(
+ this->_root_ptr
+ , key
+ , this->_value_compare
+ );
+
+ return node_ptr ? iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ ) : this->end();
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline ::std::pair<
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ , typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::const_iterator
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::equal_range(key_type const& key) const
+ {
+ return ::std::make_pair(
+ this->lower_bound(key)
+ , this->upper_bound(key)
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline ::std::pair<
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ , typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::equal_range(key_type const& key)
+ {
+ return ::std::make_pair(
+ this->lower_bound(key)
+ , this->upper_bound(key)
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::node::pointer
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_construct_node_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , value_type const& value
+ )
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(result, value);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::construct(allocator, result, value);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::node::pointer
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_construct_node_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , value_type const& value
+ )
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(
+ result
+ , ::boost::container::allocator_arg
+ , allocator
+ , value
+ );
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<allocator_type>::construct(
+ allocator
+ , result
+ , ::boost::container::allocator_arg
+ , allocator
+ , value
+ );
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_insert(value_type const& value, ::boost::mpl::true_)
+ {
+ if (!this->_root_ptr)
+ {
+ return iterator(
+ make_in_order_iterator(
+ *(
+ this->_root_ptr = this->_construct_node_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , value
+ )
+ )
+ )
+ , transform_function()
+ );
+ }
+
+ typename node::pointer node_ptr = binary_upper_bound(
+ this->_root_ptr
+ , value
+ , insert_compare(this->_key_compare)
+ );
+
+ if (node_ptr)
+ {
+ if (node_ptr->get_left_child_ptr())
+ {
+ for (
+ node_ptr = node_ptr->get_left_child_ptr();
+ node_ptr->get_right_child_ptr();
+ node_ptr = node_ptr->get_right_child_ptr()
+ )
+ {
+ }
+
+ node_ptr = &*node_ptr->emplace_right(value);
+ }
+ else
+ {
+ node_ptr = &*node_ptr->emplace_left(value);
+ }
+ }
+ else // if (!node_ptr)
+ {
+ for (
+ node_ptr = this->_root_ptr;
+ node_ptr->get_right_child_ptr();
+ node_ptr = node_ptr->get_right_child_ptr()
+ )
+ {
+ }
+
+ node_ptr = &*node_ptr->emplace_right(value);
+ }
+
+ node_ptr = Balancer::post_insert(node_ptr);
+
+ if (!node_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = node_ptr;
+ }
+
+ return iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ ::std::pair<
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ , bool
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_insert(value_type const& value, ::boost::mpl::false_)
+ {
+ if (!this->_root_ptr)
+ {
+ return ::std::make_pair(
+ iterator(
+ make_in_order_iterator(
+ *(
+ this->_root_ptr = this->_construct_node_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , value
+ )
+ )
+ )
+ , transform_function()
+ )
+ , true
+ );
+ }
+
+ insert_compare compare(this->_key_compare);
+ typename node::pointer p = this->_root_ptr;
+
+ for (;;)
+ {
+ if (compare(value, *p))
+ {
+ if (p->get_left_child_ptr())
+ {
+ p = p->get_left_child_ptr();
+ }
+ else
+ {
+ typename node::pointer n = Balancer::post_insert(
+ p = &*p->emplace_left(value)
+ );
+
+ if (!n->get_parent_ptr())
+ {
+ this->_root_ptr = n;
+ }
+
+ return ::std::make_pair(
+ iterator(
+ make_in_order_iterator_position(*p)
+ , transform_function()
+ )
+ , true
+ );
+ }
+ }
+ else if (compare(*p, value))
+ {
+ if (p->get_right_child_ptr())
+ {
+ p = p->get_right_child_ptr();
+ }
+ else
+ {
+ typename node::pointer n = Balancer::post_insert(
+ p = &*p->emplace_right(value)
+ );
+
+ if (!n->get_parent_ptr())
+ {
+ this->_root_ptr = n;
+ }
+
+ return ::std::make_pair(
+ iterator(
+ make_in_order_iterator_position(*p)
+ , transform_function()
+ )
+ , true
+ );
+ }
+ }
+ else
+ {
+ break;
+ }
+ }
+
+ return ::std::make_pair(
+ iterator(
+ make_in_order_iterator_position(*p)
+ , transform_function()
+ )
+ , false
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename ::boost::mpl::if_<
+ IsMultipleAssociative
+ , typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ , ::std::pair<
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ , bool
+ >
+ >::type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::insert(value_type const& value)
+ {
+ return this->_insert(value, IsMultipleAssociative());
+ }
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ template <typename ...Args>
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::node::pointer
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_construct_node_from(
+ ::std::tr1::true_type
+ , allocator_type& allocator
+ , Args&& ...args
+ )
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(result, ::boost::forward<Args>(args)...);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::construct(allocator, result, ::boost::forward<Args>(args)...);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ template <typename ...Args>
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::node::pointer
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_construct_node_from(
+ ::std::tr1::false_type
+ , allocator_type& allocator
+ , Args&& ...args
+ )
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(allocator.allocate(1));
+ allocator.construct(
+ result
+ , ::boost::container::allocator_arg
+ , allocator
+ , ::boost::forward<Args>(args)...
+ );
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ typename node::pointer result(
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::allocate(allocator, 1)
+ );
+ ::boost::container::allocator_traits<allocator_type>::construct(
+ allocator
+ , result
+ , ::boost::container::allocator_arg
+ , allocator
+ , ::boost::forward<Args>(args)...
+ );
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ return result;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ template <typename ...Args>
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_construct_value_from(
+ ::std::tr1::true_type
+ , Args&& ...args
+ )
+ {
+ return value_type(::boost::forward<Args>(args)...);
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ template <typename ...Args>
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::value_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_construct_value_from(
+ ::std::tr1::false_type
+ , key_type const& key
+ , Args&& ...args
+ )
+ {
+ return value_type(key, T2(::boost::forward<Args>(args)...));
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ template <typename ...Args>
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_emplace(::boost::mpl::true_, Args&& ...args)
+ {
+ if (!this->_root_ptr)
+ {
+ return iterator(
+ make_in_order_iterator(
+ *(
+ this->_root_ptr = this->_construct_node_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , ::boost::forward<Args>(args)...
+ )
+ )
+ )
+ , transform_function()
+ );
+ }
+
+ typename node::pointer node_ptr = binary_upper_bound(
+ this->_root_ptr
+ , this->_construct_value_from(
+ ::std::tr1::is_void<T2>()
+ , ::boost::forward<Args>(args)...
+ )
+ , insert_compare(this->_key_compare)
+ );
+
+ if (node_ptr)
+ {
+ if (node_ptr->get_left_child_ptr())
+ {
+ for (
+ node_ptr = node_ptr->get_left_child_ptr();
+ node_ptr->get_right_child_ptr();
+ node_ptr = node_ptr->get_right_child_ptr()
+ )
+ {
+ }
+
+ node_ptr = &*node_ptr->emplace_right(
+ ::boost::forward<Args>(args)...
+ );
+ }
+ else
+ {
+ node_ptr = &*node_ptr->emplace_left(
+ ::boost::forward<Args>(args)...
+ );
+ }
+ }
+ else // if (!node_ptr)
+ {
+ for (
+ node_ptr = this->_root_ptr;
+ node_ptr->get_right_child_ptr();
+ node_ptr = node_ptr->get_right_child_ptr()
+ )
+ {
+ }
+
+ node_ptr = &*node_ptr->emplace_right(
+ ::boost::forward<Args>(args)...
+ );
+ }
+
+ typename node::pointer anc_ptr = Balancer::post_insert(node_ptr);
+
+ if (!anc_ptr->get_parent_ptr())
+ {
+ this->_root_ptr = anc_ptr;
+ }
+
+ return iterator(
+ make_in_order_iterator_position(*node_ptr)
+ , transform_function()
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ template <typename ...Args>
+ ::std::pair<
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ , bool
+ >
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_emplace(::boost::mpl::false_, Args&& ...args)
+ {
+ if (!this->_root_ptr)
+ {
+ return ::std::make_pair(
+ iterator(
+ make_in_order_iterator(
+ *(
+ this->_root_ptr = this->_construct_node_from(
+ ::std::tr1::is_const<
+ typename ::std::tr1::remove_reference<
+ typename node::traits::allocator_reference
+ >::type
+ >()
+ , this->_allocator
+ , ::boost::forward<Args>(args)...
+ )
+ )
+ )
+ , transform_function()
+ )
+ , true
+ );
+ }
+
+ value_type value(
+ this->_construct_value_from(
+ ::std::tr1::is_void<T2>()
+ , ::boost::forward<Args>(args)...
+ )
+ );
+ insert_compare compare(this->_key_compare);
+ typename node::pointer p = this->_root_ptr;
+
+ for (;;)
+ {
+ if (compare(value, *p))
+ {
+ if (p->get_left_child_ptr())
+ {
+ p = p->get_left_child_ptr();
+ }
+ else
+ {
+ typename node::pointer n = Balancer::post_insert(
+ p = &*p->emplace_left(::boost::forward<Args>(args)...)
+ );
+
+ if (!n->get_parent_ptr())
+ {
+ this->_root_ptr = n;
+ }
+
+ return ::std::make_pair(
+ iterator(
+ make_in_order_iterator_position(*p)
+ , transform_function()
+ )
+ , true
+ );
+ }
+ }
+ else if (compare(*p, value))
+ {
+ if (p->get_right_child_ptr())
+ {
+ p = p->get_right_child_ptr();
+ }
+ else
+ {
+ typename node::pointer n = Balancer::post_insert(
+ p = &*p->emplace_right(::boost::forward<Args>(args)...)
+ );
+
+ if (!n->get_parent_ptr())
+ {
+ this->_root_ptr = n;
+ }
+
+ return ::std::make_pair(
+ iterator(
+ make_in_order_iterator_position(*p)
+ , transform_function()
+ )
+ , true
+ );
+ }
+ }
+ else
+ {
+ break;
+ }
+ }
+
+ return ::std::make_pair(
+ iterator(
+ make_in_order_iterator_position(*p)
+ , transform_function()
+ )
+ , false
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ template <typename ...Args>
+ inline typename ::boost::mpl::if_<
+ IsMultipleAssociative
+ , typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ , ::std::pair<
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::iterator
+ , bool
+ >
+ >::type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::emplace(Args&& ...args)
+ {
+ return this->_emplace(
+ IsMultipleAssociative()
+ , ::boost::forward<Args>(args)...
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::node::pointer \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::_construct_node_from( \
+ ::std::tr1::true_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename node::pointer result(allocator.allocate(1)); \
+ allocator.construct( \
+ result \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::node::pointer \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::_construct_node_from( \
+ ::std::tr1::false_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename node::pointer result(allocator.allocate(1)); \
+ allocator.construct( \
+ result \
+ , ::boost::container::allocator_arg \
+ , allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::node::pointer \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::_construct_node_from( \
+ ::std::tr1::true_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename node::pointer result( \
+ ::boost::container::allocator_traits< \
+ allocator_type \
+ >::allocate(allocator, 1) \
+ ); \
+ ::boost::container::allocator_traits<allocator_type>::construct( \
+ allocator \
+ , result \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::node::pointer \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::_construct_node_from( \
+ ::std::tr1::false_type \
+ , allocator_type& allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename node::pointer result( \
+ ::boost::container::allocator_traits< \
+ allocator_type \
+ >::allocate(allocator, 1) \
+ ); \
+ ::boost::container::allocator_traits<allocator_type>::construct( \
+ allocator \
+ , result \
+ , ::boost::container::allocator_arg \
+ , allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ inline typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::value_type \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::_construct_value_from( \
+ ::std::tr1::true_type \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ return value_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ inline typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::value_type \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::_construct_value_from( \
+ ::std::tr1::false_type \
+ , key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ return value_type( \
+ key \
+ , T2( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_PP_DEC(BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::iterator \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::_emplace( \
+ ::boost::mpl::true_ \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ if (!this->_root_ptr) \
+ { \
+ return iterator( \
+ make_in_order_iterator( \
+ *( \
+ this->_root_ptr = this->_construct_node_from( \
+ ::std::tr1::is_const< \
+ typename ::std::tr1::remove_reference< \
+ typename node::traits::allocator_reference \
+ >::type \
+ >() \
+ , this->_allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ) \
+ ) \
+ , transform_function() \
+ ); \
+ } \
+ typename node::pointer node_ptr = binary_upper_bound( \
+ this->_root_ptr \
+ , this->_construct_value_from( \
+ ::std::tr1::is_void<T2>() \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ , insert_compare(this->_key_compare) \
+ ); \
+ if (node_ptr) \
+ { \
+ if (node_ptr->get_left_child_ptr()) \
+ { \
+ for ( \
+ node_ptr = node_ptr->get_left_child_ptr(); \
+ node_ptr->get_right_child_ptr(); \
+ node_ptr = node_ptr->get_right_child_ptr() \
+ ) \
+ { \
+ } \
+ node_ptr = &*node_ptr->emplace_right( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+ else \
+ { \
+ node_ptr = &*node_ptr->emplace_left( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+ } \
+ else \
+ { \
+ for ( \
+ node_ptr = this->_root_ptr; \
+ node_ptr->get_right_child_ptr(); \
+ node_ptr = node_ptr->get_right_child_ptr() \
+ ) \
+ { \
+ } \
+ node_ptr = &*node_ptr->emplace_right( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+ node_ptr = Balancer::post_insert(node_ptr); \
+ if (!node_ptr->get_parent_ptr()) \
+ { \
+ this->_root_ptr = node_ptr; \
+ } \
+ return iterator( \
+ make_in_order_iterator_position(*node_ptr) \
+ , transform_function() \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ ::std::pair< \
+ typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::iterator \
+ , bool \
+ > \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::_emplace( \
+ ::boost::mpl::false_ \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ if (!this->_root_ptr) \
+ { \
+ return ::std::make_pair( \
+ iterator( \
+ make_in_order_iterator( \
+ *( \
+ this->_root_ptr = this->_construct_node_from( \
+ ::std::tr1::is_const< \
+ typename ::std::tr1::remove_reference< \
+ typename node::traits::allocator_reference \
+ >::type \
+ >() \
+ , this->_allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ) \
+ ) \
+ , transform_function() \
+ ) \
+ , true \
+ ); \
+ } \
+ value_type value( \
+ this->_construct_value_from( \
+ ::std::tr1::is_void<T2>() \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ); \
+ insert_compare compare(this->_key_compare); \
+ typename node::pointer p = this->_root_ptr; \
+ for (;;) \
+ { \
+ if (compare(value, *p)) \
+ { \
+ if (p->get_left_child_ptr()) \
+ { \
+ p = p->get_left_child_ptr(); \
+ } \
+ else \
+ { \
+ typename node::pointer n = Balancer::post_insert( \
+ p = &*p->emplace_left( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ); \
+ if (!n->get_parent_ptr()) \
+ { \
+ this->_root_ptr = n; \
+ } \
+ return ::std::make_pair( \
+ iterator( \
+ make_in_order_iterator_position(*p) \
+ , transform_function() \
+ ) \
+ , true \
+ ); \
+ } \
+ } \
+ else if (compare(*p, value)) \
+ { \
+ if (p->get_right_child_ptr()) \
+ { \
+ p = p->get_right_child_ptr(); \
+ } \
+ else \
+ { \
+ typename node::pointer n = Balancer::post_insert( \
+ p = &*p->emplace_right( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ); \
+ if (!n->get_parent_ptr()) \
+ { \
+ this->_root_ptr = n; \
+ } \
+ return ::std::make_pair( \
+ iterator( \
+ make_in_order_iterator_position(*p) \
+ , transform_function() \
+ ) \
+ , true \
+ ); \
+ } \
+ } \
+ else \
+ { \
+ break; \
+ } \
+ } \
+ return ::std::make_pair( \
+ iterator( \
+ make_in_order_iterator_position(*p) \
+ , transform_function() \
+ ) \
+ , false \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+
+#define BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO(z, n, _) \
+ template < \
+ typename NodeGenerator \
+ , typename T1 \
+ , typename T2 \
+ , typename IsMultipleAssociative \
+ , typename CompareSelector \
+ , typename Balancer \
+ > \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ inline typename ::boost::mpl::if_< \
+ IsMultipleAssociative \
+ , typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::iterator \
+ , ::std::pair< \
+ typename binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::iterator \
+ , bool \
+ > \
+ >::type \
+ binode_associative_container< \
+ NodeGenerator \
+ , T1 \
+ , T2 \
+ , IsMultipleAssociative \
+ , CompareSelector \
+ , Balancer \
+ >::emplace( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ return this->_emplace( \
+ IsMultipleAssociative() \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_CONTAINER_BINARY_ASSOCIATIVE_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ void
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_erase_one(typename node::pointer p)
+ {
+ for (typename node::pointer s;;)
+ {
+ if (
+ (s = p->get_left_child_ptr()) && (
+ !p->get_right_child_ptr() || Balancer::choose_predecessor(
+ *typename node::const_pointer(p)
+ )
+ )
+ )
+ {
+ while (s->get_right_child_ptr())
+ {
+ s = s->get_right_child_ptr();
+ }
+
+ if (s->get_parent_ptr() == p)
+ {
+ if (!p->get_right_child_ptr())
+ {
+ put(*p, data_key(), get(*s, data_key()));
+
+ bool must_rebalance = Balancer::pre_erase(*s);
+
+ p->erase_left();
+
+ if (must_rebalance)
+ {
+ p = Balancer::post_erase_left(p);
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+
+ break;
+ }
+ }
+ else // if (s == s->get_parent_ptr()->get_right_child_ptr())
+ {
+ put(*p, data_key(), get(*s, data_key()));
+
+ if (s->get_left_child_ptr())
+ {
+ p = s;
+ }
+ else // if (s->empty())
+ {
+ p = s->get_parent_ptr();
+
+ if (p->get_left_child_ptr())
+ {
+ put(*s, data_key(), get(*p, data_key()));
+ }
+ else // s is only child of p
+ {
+ bool must_rebalance = Balancer::pre_erase(*s);
+
+ p->erase_right();
+
+ if (must_rebalance)
+ {
+ p = Balancer::post_erase_right(p);
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+
+ break;
+ }
+ }
+
+ continue;
+ }
+ }
+
+ if ((s = p->get_right_child_ptr()))
+ {
+ while (s->get_left_child_ptr())
+ {
+ s = s->get_left_child_ptr();
+ }
+
+ put(*p, data_key(), get(*s, data_key()));
+
+ if (s->get_right_child_ptr())
+ {
+ p = s;
+ }
+ else if (s->get_parent_ptr() == p)
+ {
+ bool must_rebalance = Balancer::pre_erase(*s);
+
+ p->erase_right();
+
+ if (must_rebalance)
+ {
+ p = Balancer::post_erase_right(p);
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+
+ break;
+ }
+ else
+ {
+ BOOST_ASSERT(s->empty());
+ p = s->get_parent_ptr();
+ BOOST_ASSERT(p->get_left_child_ptr() == s);
+
+ if (p->get_right_child_ptr())
+ {
+ put(*s, data_key(), get(*p, data_key()));
+ }
+ else // s is only child of p
+ {
+ bool must_rebalance = Balancer::pre_erase(*s);
+
+ p->erase_left();
+
+ if (must_rebalance)
+ {
+ p = Balancer::post_erase_left(p);
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+
+ break;
+ }
+ }
+ }
+ else // if (p->empty())
+ {
+ s = p;
+ p = p->get_parent_ptr();
+
+ bool must_rebalance = Balancer::pre_erase(*s);
+
+ if (p->get_left_child_ptr() == s)
+ {
+ p->erase_left();
+
+ if (must_rebalance)
+ {
+ p = Balancer::post_erase_left(p);
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+ }
+ else // if (p->get_right_child_ptr() == s)
+ {
+ p->erase_right();
+
+ if (must_rebalance)
+ {
+ p = Balancer::post_erase_right(p);
+
+ if (!p->get_parent_ptr())
+ {
+ this->_root_ptr = p;
+ }
+ }
+ }
+
+ break;
+ }
+ }
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::size_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_erase(key_type const& key, ::boost::mpl::true_)
+ {
+ size_type result = ::boost::initialized_value;
+
+ for (
+ typename node::pointer p;
+ (
+ p = binary_descendant(
+ this->_root_ptr
+ , key
+ , this->_value_compare
+ )
+ );
+ ++result
+ )
+ {
+ this->_erase_one(p);
+ }
+
+ return result;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::size_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_erase(key_type const& key, ::boost::mpl::false_)
+ {
+ this->_erase_one(
+ binary_descendant(
+ this->_root_ptr
+ , key
+ , this->_value_compare
+ )
+ );
+ return 1;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::size_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::erase(key_type const& key)
+ {
+ if (this->_root_ptr)
+ {
+ if (this->_root_ptr->empty())
+ {
+ this->clear();
+ return 1;
+ }
+ else
+ {
+ return this->_erase(key, IsMultipleAssociative());
+ }
+ }
+ else
+ {
+ return 0;
+ }
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline bool
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::empty() const
+ {
+ return !this->_root_ptr;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ void
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::clear()
+ {
+ if (this->_root_ptr)
+ {
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ this->_allocator.destroy(this->_root_ptr);
+ this->_allocator.deallocate(this->_root_ptr, 1);
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::destroy(this->_allocator, this->_root_ptr);
+ ::boost::container::allocator_traits<
+ allocator_type
+ >::deallocate(this->_allocator, this->_root_ptr, 1);
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+#if defined BOOST_NO_CXX11_NULLPTR
+ this->_root_ptr = 0;
+#else
+ this->_root_ptr = nullptr;
+#endif
+ }
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::size_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_size(::boost::mpl::true_) const
+ {
+ return this->_root_ptr ? get(*this->_root_ptr, count_key()) : 0;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::size_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::_size(::boost::mpl::false_) const
+ {
+ size_type result = ::boost::initialized_value;
+
+ for (const_iterator itr = this->cbegin(); itr; ++itr)
+ {
+ ++result;
+ }
+
+ return result;
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::size_type
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::size() const
+ {
+ return this->_size(result_of::has_key<node,count_key>());
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::transform_function::const_result
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::operator[](size_type const& index) const
+ {
+ BOOST_ASSERT_MSG(
+ this->_root_ptr && (index < this->size())
+ , "index out of bounds"
+ );
+
+ typename node::const_pointer node_ptr = this->_root_ptr;
+
+ return transform_function()(
+ *binary_descendant_at_index(node_ptr, index)
+ );
+ }
+
+ template <
+ typename NodeGenerator
+ , typename T1
+ , typename T2
+ , typename IsMultipleAssociative
+ , typename CompareSelector
+ , typename Balancer
+ >
+ inline typename binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::transform_function::mutable_result
+ binode_associative_container<
+ NodeGenerator
+ , T1
+ , T2
+ , IsMultipleAssociative
+ , CompareSelector
+ , Balancer
+ >::operator[](size_type const& index)
+ {
+ BOOST_ASSERT_MSG(
+ this->_root_ptr && (index < this->size())
+ , "index out of bounds"
+ );
+
+ return transform_function()(
+ *binary_descendant_at_index(this->_root_ptr, index)
+ );
+ }
+}} // namespace boost::tree_node
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename NodeGenerator
+ , typename T
+ , typename CompareSelector
+ , typename Balancer
+ >
+ class binode_set
+ : public
+ //[reference__binode_set__bases
+ binode_associative_container<
+ NodeGenerator
+ , T
+ , void
+ , ::boost::mpl::false_
+ , CompareSelector
+ , Balancer
+ >
+ //]
+ {
+ typedef binode_associative_container<
+ NodeGenerator
+ , T
+ , void
+ , ::boost::mpl::false_
+ , CompareSelector
+ , Balancer
+ >
+ super_t;
+
+ public:
+ BOOST_TREE_NODE_ASSOCIATIVE_CONTAINER_DERIVED_BODY(binode_set, super_t)
+ };
+}} // namespace boost::tree_node
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename NodeGenerator
+ , typename T
+ , typename CompareSelector
+ , typename Balancer
+ >
+ class binode_multiset
+ : public
+ //[reference__binode_multiset__bases
+ binode_associative_container<
+ NodeGenerator
+ , T
+ , void
+ , ::boost::mpl::true_
+ , CompareSelector
+ , Balancer
+ >
+ //]
+ {
+ typedef binode_associative_container<
+ NodeGenerator
+ , T
+ , void
+ , ::boost::mpl::true_
+ , CompareSelector
+ , Balancer
+ >
+ super_t;
+
+ public:
+ BOOST_TREE_NODE_ASSOCIATIVE_CONTAINER_DERIVED_BODY(
+ binode_multiset
+ , super_t
+ )
+ };
+}} // namespace boost::tree_node
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename NodeGenerator
+ , typename Key
+ , typename Mapped
+ , typename CompareSelector
+ , typename Balancer
+ >
+ class binode_map
+ : public
+ //[reference__binode_map__bases
+ binode_associative_container<
+ NodeGenerator
+ , Key
+ , Mapped
+ , ::boost::mpl::false_
+ , CompareSelector
+ , Balancer
+ >
+ //]
+ {
+ typedef binode_associative_container<
+ NodeGenerator
+ , Key
+ , Mapped
+ , ::boost::mpl::false_
+ , CompareSelector
+ , Balancer
+ >
+ super_t;
+
+ public:
+ //[reference__binode_map__mapped_type
+ typedef Mapped mapped_type;
+ //]
+
+ BOOST_TREE_NODE_ASSOCIATIVE_CONTAINER_DERIVED_BODY(binode_map, super_t)
+ };
+}} // namespace boost::tree_node
+
+namespace boost { namespace tree_node {
+
+ template <
+ typename NodeGenerator
+ , typename Key
+ , typename Mapped
+ , typename CompareSelector
+ , typename Balancer
+ >
+ class binode_multimap
+ : public
+ //[reference__binode_multimap__bases
+ binode_associative_container<
+ NodeGenerator
+ , Key
+ , Mapped
+ , ::boost::mpl::true_
+ , CompareSelector
+ , Balancer
+ >
+ //]
+ {
+ typedef binode_associative_container<
+ NodeGenerator
+ , Key
+ , Mapped
+ , ::boost::mpl::true_
+ , CompareSelector
+ , Balancer
+ >
+ super_t;
+
+ public:
+ //[reference__binode_multimap__mapped_type
+ typedef Mapped mapped_type;
+ //]
+
+ BOOST_TREE_NODE_ASSOCIATIVE_CONTAINER_DERIVED_BODY(
+ binode_multimap
+ , super_t
+ )
+ };
+}} // namespace boost::tree_node
+
+#endif // BOOST_TREE_NODE_CONTAINER_BINODE_ASSOCIATIVE_HPP_INCLUDED
+

Added: sandbox/tree_node/boost/tree_node/preprocessor.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/preprocessor.hpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,445 @@
+// Copyright (C) 2012-2013 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_PREPROCESSOR_HPP_INCLUDED
+#define BOOST_TREE_NODE_PREPROCESSOR_HPP_INCLUDED
+
+#include <boost/config.hpp>
+
+#if !defined BOOST_NO_SFINAE \
+ && !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION \
+ && !defined BOOST_TREE_NODE_CAN_USE_FUSION
+#define BOOST_TREE_NODE_CAN_USE_FUSION
+#endif
+
+#if defined BOOST_TREE_NODE_CAN_USE_FUSION \
+ && defined BOOST_TYPEOF_NATIVE \
+ && !defined BOOST_TREE_NODE_CAN_USE_FUSION_WITH_TYPEOF
+#define BOOST_TREE_NODE_CAN_USE_FUSION_WITH_TYPEOF
+#endif
+
+#include <boost/container/scoped_allocator_fwd.hpp>
+#include <boost/container/detail/workaround.hpp>
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/preprocessor/cat.hpp>
+#include <boost/preprocessor/repetition/enum.hpp>
+#include <boost/preprocessor/repetition/enum_params.hpp>
+#include <boost/preprocessor/repetition/enum_trailing.hpp>
+#include <boost/preprocessor/control/expr_if.hpp>
+#include <boost/preprocessor/control/expr_iif.hpp>
+#include <boost/preprocessor/comparison/equal.hpp>
+#include <boost/preprocessor/arithmetic/dec.hpp>
+#include <boost/preprocessor/tuple/elem.hpp>
+#include <boost/container/detail/preprocessor.hpp>
+
+//[reference__macro__emplacement_ctor_header
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_HEADER(z, n, Type) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ BOOST_PP_EXPR_IIF(BOOST_PP_EQUAL(n, 1), explicit) \
+ Type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+//]
+
+//[reference__macro__emplacement_ctor_fwd_decl
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_FWD_DECL(z, n, Type) \
+ BOOST_TREE_NODE_EMPLACEMENT_CTOR_HEADER(z, n, Type); \
+//]
+
+//[reference__macro__emplacement_ctor_base_fwd
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_BASE_FWD(z, n, Base) \
+ : Base( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+//]
+
+//[reference__macro__emplacement_ctor_inline_header
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_INLINE_HEADER(z, n, Tuple) \
+ BOOST_TREE_NODE_EMPLACEMENT_CTOR_HEADER( \
+ z \
+ , n \
+ , BOOST_PP_TUPLE_ELEM(2, 0, Tuple) \
+ ) \
+ BOOST_TREE_NODE_EMPLACEMENT_CTOR_BASE_FWD( \
+ z \
+ , n \
+ , BOOST_PP_TUPLE_ELEM(2, 1, Tuple) \
+ ) \
+//]
+
+//[reference__macro__emplacement_ctor_inline_def
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_INLINE_DEF(z, n, Tuple) \
+ BOOST_TREE_NODE_EMPLACEMENT_CTOR_INLINE_HEADER(z, n, Tuple) \
+ { \
+ Base::on_post_emplacement_construct(); \
+ } \
+//]
+
+//[reference__macro__emplacement_ctor_w_alloc_header
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_HEADER(z, n, Type) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ BOOST_PP_EXPR_IIF(BOOST_PP_EQUAL(n, 1), explicit) \
+ Type( \
+ ::boost::container::allocator_arg_t \
+ , typename traits::allocator_reference allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+//]
+
+//[reference__macro__emplacement_ctor_w_alloc_fwd_decl
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_FWD_DECL(z, n, Type) \
+ BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_HEADER(z, n, Type); \
+//]
+
+//[reference__macro__emplacement_ctor_w_alloc_base_fwd
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_BASE_FWD(z, n, Base) \
+ : Base( \
+ ::boost::container::allocator_arg \
+ , allocator \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+//]
+
+//[reference__macro__emplacement_ctor_w_alloc_inline_header
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_INLINE_HEADER(z, n, Tuple) \
+ BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_HEADER( \
+ z \
+ , n \
+ , BOOST_PP_TUPLE_ELEM(2, 0, Tuple) \
+ ) \
+ BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_BASE_FWD( \
+ z \
+ , n \
+ , BOOST_PP_TUPLE_ELEM(2, 1, Tuple) \
+ ) \
+//]
+
+//[reference__macro__emplacement_ctor_w_alloc_inline_def
+#define BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_INLINE_DEF(z, n, Tuple) \
+ BOOST_TREE_NODE_EMPLACEMENT_CTOR_W_ALLOC_INLINE_HEADER(z, n, Tuple) \
+ { \
+ Base::on_post_emplacement_construct(); \
+ } \
+//]
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+//[reference__macro__copy_constructible
+#define BOOST_TREE_NODE_COPY_CONSTRUCTIBLE(Derived, Base) \
+ inline Derived(Derived const& copy) : Base(copy) \
+ { \
+ Base::on_post_copy_or_move(); \
+ } \
+ inline Derived( \
+ Derived const& copy \
+ , typename traits::allocator_reference a \
+ ) : Base(copy, a) \
+ { \
+ Base::on_post_copy_or_move(); \
+ } \
+ inline Derived(Derived& copy) \
+ : Base(const_cast<Derived const&>(copy)) \
+ { \
+ Base::on_post_copy_or_move(); \
+ } \
+ inline Derived( \
+ Derived& copy \
+ , typename traits::allocator_reference a \
+ ) : Base(const_cast<Derived const&>(copy), a) \
+ { \
+ Base::on_post_copy_or_move(); \
+ } \
+//]
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#define BOOST_TREE_NODE_COPYABLE_AND_MOVABLE(Derived, Base) \
+ BOOST_TREE_NODE_COPY_CONSTRUCTIBLE(Derived, Base) \
+ inline Derived& operator=(Derived const& copy) \
+ { \
+ if (this != &copy) \
+ { \
+ Base::copy_assign(copy); \
+ Base::on_post_copy_or_move(); \
+ } \
+ return *this; \
+ } \
+ inline Derived& operator=(Derived& copy) \
+ { \
+ if (this != &copy) \
+ { \
+ Base::copy_assign(const_cast<Derived const&>(copy)); \
+ Base::on_post_copy_or_move(); \
+ } \
+ return *this; \
+ } \
+//!
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#if defined BOOST_NO_RVALUE_REFERENCES
+#include <boost/move/move.hpp>
+#define BOOST_TREE_NODE_COPYABLE_AND_MOVABLE(Derived, Base) \
+ BOOST_TREE_NODE_COPY_CONSTRUCTIBLE(Derived, Base) \
+ inline Derived(::boost::rv<Derived>& source) : Base(source) \
+ { \
+ Base::on_post_copy_or_move(); \
+ } \
+ inline Derived( \
+ ::boost::rv<Derived>& source \
+ , typename traits::allocator_reference a \
+ ) : Base(source, a) \
+ { \
+ Base::on_post_copy_or_move(); \
+ } \
+ inline operator ::boost::rv<Derived> const&() const \
+ { \
+ return *static_cast< ::boost::rv<Derived> const*>(this); \
+ } \
+ inline operator ::boost::rv<Derived>&() \
+ { \
+ return *static_cast< ::boost::rv<Derived>*>(this); \
+ } \
+ inline Derived& operator=(::boost::rv<Derived> const& ca_ref) \
+ { \
+ Derived const& copy = static_cast<Derived const&>(ca_ref); \
+ if (this != &copy) \
+ { \
+ Base::copy_assign(copy); \
+ Base::on_post_copy_or_move(); \
+ } \
+ return *this; \
+ } \
+ inline Derived& operator=(::boost::rv<Derived>& rv_ref) \
+ { \
+ if (this != &static_cast<Derived&>(rv_ref)) \
+ { \
+ Base::move_assign(rv_ref); \
+ Base::on_post_copy_or_move(); \
+ } \
+ return *this; \
+ } \
+ inline Derived& operator=(Derived& copy) \
+ { \
+ if (this != &copy) \
+ { \
+ Base::copy_assign(const_cast<Derived const&>(copy)); \
+ Base::on_post_copy_or_move(); \
+ } \
+ return *this; \
+ } \
+//!
+#else // !defined BOOST_NO_RVALUE_REFERENCES
+//[reference__macro__copyable_and_movable
+#define BOOST_TREE_NODE_COPYABLE_AND_MOVABLE(Derived, Base) \
+ BOOST_TREE_NODE_COPY_CONSTRUCTIBLE(Derived, Base) \
+ inline Derived(Derived&& source) \
+ : Base(static_cast<Derived&&>(source)) \
+ { \
+ Base::on_post_copy_or_move(); \
+ } \
+ inline Derived( \
+ Derived&& source \
+ , typename traits::allocator_reference a \
+ ) : Base(static_cast<Derived&&>(source), a) \
+ { \
+ Base::on_post_copy_or_move(); \
+ } \
+ inline Derived& operator=(Derived const& copy) \
+ { \
+ if (this != &copy) \
+ { \
+ Base::copy_assign(copy); \
+ Base::on_post_copy_or_move(); \
+ } \
+ return *this; \
+ } \
+ inline Derived& operator=(Derived&& source) \
+ { \
+ if (this != &static_cast<Derived&>(source)) \
+ { \
+ Base::move_assign(static_cast<Derived&&>(source)); \
+ Base::on_post_copy_or_move(); \
+ } \
+ return *this; \
+ } \
+//]
+#endif // BOOST_NO_RVALUE_REFERENCES
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+//[reference__macro__container_derived_impl
+#define BOOST_TREE_NODE_CONTAINER_DERIVED_IMPL(Derived, Base) \
+ typedef typename Base::reference reference; \
+ typedef typename Base::const_reference const_reference; \
+ typedef typename Base::pointer pointer; \
+ typedef typename Base::const_pointer const_pointer; \
+ typedef typename Base::iterator iterator; \
+ typedef typename Base::const_iterator const_iterator; \
+ typedef typename Base::size_type size_type; \
+ typedef typename Base::allocator_type allocator_type; \
+ inline Derived() : Base() \
+ { \
+ } \
+ inline explicit Derived(allocator_type const& a) : Base(a) \
+ { \
+ } \
+ inline Derived(Derived const& copy) \
+ : Base(static_cast<Base const&>(copy)) \
+ { \
+ } \
+ inline Derived(Derived const& copy, allocator_type const& a) \
+ : Base(static_cast<Base const&>(copy), a) \
+ { \
+ } \
+ inline Derived(Derived& copy) \
+ : Base( \
+ static_cast<Base const&>(const_cast<Derived const&>(copy)) \
+ ) \
+ { \
+ } \
+ inline Derived(Derived& copy, allocator_type const& a) \
+ : Base( \
+ static_cast<Base const&>(const_cast<Derived const&>(copy)) \
+ , a \
+ ) \
+ { \
+ } \
+//]
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#define BOOST_TREE_NODE_CONTAINER_DERIVED_BODY(Derived, Base) \
+ BOOST_TREE_NODE_CONTAINER_DERIVED_IMPL(Derived, Base) \
+ inline Derived& operator=(Derived const& copy) \
+ { \
+ if (this != &copy) \
+ { \
+ Base::operator=(const_cast<Base const&>(copy)); \
+ } \
+ return *this; \
+ } \
+ inline Derived& operator=(Derived& copy) \
+ { \
+ if (this != &copy) \
+ { \
+ Base::operator=(const_cast<Base const&>(copy)); \
+ } \
+ return *this; \
+ } \
+//!
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#if defined BOOST_NO_RVALUE_REFERENCES
+#include <boost/move/move.hpp>
+#define BOOST_TREE_NODE_CONTAINER_DERIVED_BODY(Derived, Base) \
+ BOOST_TREE_NODE_CONTAINER_DERIVED_IMPL(Derived, Base) \
+ inline Derived(::boost::rv<Derived>& source) \
+ : Base(::boost::move(static_cast<Base&>(source))) \
+ { \
+ } \
+ inline Derived( \
+ ::boost::rv<Derived>& source \
+ , allocator_type const& a \
+ ) : Base(::boost::move(static_cast<Base&>(source)), a) \
+ { \
+ } \
+ inline operator ::boost::rv<Derived> const&() const \
+ { \
+ return *static_cast< ::boost::rv<Derived> const*>(this); \
+ } \
+ inline operator ::boost::rv<Derived>&() \
+ { \
+ return *static_cast< ::boost::rv<Derived>*>(this); \
+ } \
+ inline Derived& operator=(::boost::rv<Derived> const& ca_ref) \
+ { \
+ Base const& copy = static_cast<Base const&>( \
+ static_cast<Derived const&>(ca_ref) \
+ ); \
+ if (this != &copy) \
+ { \
+ Base::operator=(copy); \
+ } \
+ return *this; \
+ } \
+ inline Derived& operator=(::boost::rv<Derived>& rv_ref) \
+ { \
+ if (this != &static_cast<Derived&>(rv_ref)) \
+ { \
+ Base::operator=(::boost::move(static_cast<Base&>(rv_ref))); \
+ } \
+ return *this; \
+ } \
+ inline Derived& operator=(Derived& copy) \
+ { \
+ if (this != &copy) \
+ { \
+ Base::operator=( \
+ static_cast<Base const&>( \
+ const_cast<Derived const&>(copy) \
+ ) \
+ ); \
+ } \
+ return *this; \
+ } \
+//!
+#else // !defined BOOST_NO_RVALUE_REFERENCES
+//[reference__macro__container_derived_body
+#define BOOST_TREE_NODE_CONTAINER_DERIVED_BODY(Derived, Base) \
+ BOOST_TREE_NODE_CONTAINER_DERIVED_IMPL(Derived, Base) \
+ inline Derived(Derived&& source) \
+ : Base(static_cast<Base&&>(source)) \
+ { \
+ } \
+ inline Derived(Derived&& source, allocator_type const& a) \
+ : Base(static_cast<Base&&>(source), a) \
+ { \
+ } \
+ inline Derived& operator=(Derived const& copy) \
+ { \
+ if (this != &copy) \
+ { \
+ Base::operator=(static_cast<Base const&>(copy)); \
+ } \
+ return *this; \
+ } \
+ inline Derived& operator=(Derived&& source) \
+ { \
+ if (this != &static_cast<Derived&>(source)) \
+ { \
+ Base::operator=(static_cast<Derived&&>(source)); \
+ } \
+ return *this; \
+ } \
+//]
+#endif // BOOST_NO_RVALUE_REFERENCES
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+//[reference__macro__associative_container_derived_body
+#define BOOST_TREE_NODE_ASSOCIATIVE_CONTAINER_DERIVED_BODY(Derived, Base) \
+ typedef typename Base::key_type key_type; \
+ typedef typename Base::value_type value_type; \
+ typedef typename Base::key_compare key_compare; \
+ typedef typename Base::value_compare value_compare; \
+ BOOST_TREE_NODE_CONTAINER_DERIVED_BODY(Derived, Base) \
+//]
+
+#endif // BOOST_TREE_NODE_PREPROCESSOR_HPP_INCLUDED
+

Added: sandbox/tree_node/libs/tree_node/test/avl_tree.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/test/avl_tree.hpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,36 @@
+// Copyright (C) 2013 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 LIBS_TREE_NODE_TEST_AVL_TREE_HPP_INCLUDED
+#define LIBS_TREE_NODE_TEST_AVL_TREE_HPP_INCLUDED
+
+template <typename Tree, typename Values>
+void test_avl_tree()
+{
+ Tree avl_tree;
+ Values values;
+
+ BOOST_CHECK(avl_tree.empty());
+ BOOST_CHECK(0 == avl_tree.size());
+
+ test_insert(avl_tree, values, 13);
+ test_insert(avl_tree, values, 8);
+ test_insert(avl_tree, values, 1);
+ test_insert(avl_tree, values, 6);
+ test_insert(avl_tree, values, 11);
+ test_insert(avl_tree, values, 17);
+ test_insert(avl_tree, values, 15);
+ test_insert(avl_tree, values, 22);
+ test_insert(avl_tree, values, 25);
+ test_insert(avl_tree, values, 27);
+ test_insert(avl_tree, values, 20);
+ test_insert(avl_tree, values, 21);
+ test_erase(avl_tree, values, 1);
+ test_erase(avl_tree, values, 11);
+ test_erase(avl_tree, values, 15);
+}
+
+#endif // LIBS_TREE_NODE_TEST_AVL_TREE_HPP_INCLUDED
+

Added: sandbox/tree_node/libs/tree_node/test/binode_container.cpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/test/binode_container.cpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,334 @@
+// Copyright (C) 2013 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)
+
+#include <boost/config.hpp>
+
+#if defined BOOST_MSVC
+ #pragma warning (push)
+ #pragma warning (disable : 4996) // fn called w/params that may be unsafe
+#endif
+
+#include <boost/tree_node/balancer/red_black.hpp>
+#include <boost/tree_node/balancer/adelson_velskii_landis.hpp>
+#include <boost/tree_node/container/binode.hpp>
+#include <boost/test/minimal.hpp>
+#include "type_definitions.hpp"
+#include "container_functions.hpp"
+
+typedef boost::tree_node::binode_container<RedBlackNodeGen,boost::int32_t>
+ RedBlackTreeSequence;
+
+void
+ test_push_front(
+ RedBlackTreeSequence& red_black_tree
+ , ValueSequence& values
+ , RedBlackTreeSequence::value_type t
+ )
+{
+ red_black_tree.push_front(t);
+ std::cout << std::endl << "After red_black_tree.push_front(" << t << "):";
+ test_red_black_node(*red_black_tree.data());
+ values.push_front(t);
+ test_tree_container(red_black_tree, values);
+}
+
+void
+ test_push_back(
+ RedBlackTreeSequence& red_black_tree
+ , ValueSequence& values
+ , RedBlackTreeSequence::value_type t
+ )
+{
+ red_black_tree.push_back(t);
+ std::cout << std::endl << "After red_black_tree.push_back(" << t << "):";
+ test_red_black_node(*red_black_tree.data());
+ values.push_back(t);
+ test_tree_container(red_black_tree, values);
+}
+
+void
+ test_pop_front(
+ RedBlackTreeSequence& red_black_tree
+ , ValueSequence& values
+ )
+{
+ red_black_tree.pop_front();
+ std::cout << std::endl << "After red_black_tree.pop_front():";
+ test_red_black_node(*red_black_tree.data());
+ values.pop_front();
+ test_tree_container(red_black_tree, values);
+}
+
+void
+ test_pop_back(
+ RedBlackTreeSequence& red_black_tree
+ , ValueSequence& values
+ )
+{
+ red_black_tree.pop_back();
+ std::cout << std::endl << "After red_black_tree.pop_back():";
+ test_red_black_node(*red_black_tree.data());
+ values.pop_back();
+ test_tree_container(red_black_tree, values);
+}
+
+void
+ test_insert(
+ RedBlackTreeSequence& red_black_tree
+ , ValueSequence& values
+ , RedBlackTreeSequence::size_type index
+ , RedBlackTreeSequence::value_type t
+ )
+{
+ red_black_tree.insert(red_black_tree.begin() + index, t);
+ std::cout << std::endl << "After red_black_tree.insert[" << index << "](";
+ std::cout << t << "):";
+ test_red_black_node(*red_black_tree.data());
+ values.insert(values.begin() + index, t);
+ test_tree_container(red_black_tree, values);
+}
+
+void
+ test_erase(
+ RedBlackTreeSequence& red_black_tree
+ , ValueSequence& values
+ , RedBlackTreeSequence::size_type index
+ )
+{
+ RedBlackTreeSequence::iterator tree_itr = red_black_tree.erase(
+ red_black_tree.begin() + index
+ );
+
+ if (index == red_black_tree.size())
+ {
+ BOOST_CHECK(tree_itr == red_black_tree.end());
+ }
+ else
+ {
+ BOOST_CHECK(test_tree_values(*tree_itr, red_black_tree[index]));
+ }
+
+ std::cout << std::endl << "After red_black_tree.erase[" << index << "]:";
+ test_red_black_node(*red_black_tree.data());
+ values.erase(values.begin() + index);
+ test_tree_container(red_black_tree, values);
+}
+
+typedef boost::tree_node::binode_container<
+ AVLNodeGen
+ , boost::int32_t
+ , boost::tree_node::adelson_velskii_landis_balancer
+ >
+ AVLTreeSequence;
+
+void
+ test_push_front(
+ AVLTreeSequence& avl_tree
+ , ValueSequence& values
+ , AVLTreeSequence::value_type t
+ )
+{
+ avl_tree.push_front(t);
+ std::cout << std::endl << "After avl_tree.push_front(" << t << "):";
+ test_avl_node(*avl_tree.data());
+ values.push_front(t);
+ test_tree_container(avl_tree, values);
+}
+
+void
+ test_push_back(
+ AVLTreeSequence& avl_tree
+ , ValueSequence& values
+ , AVLTreeSequence::value_type t
+ )
+{
+ avl_tree.push_back(t);
+ std::cout << std::endl << "After avl_tree.push_back(" << t << "):";
+ test_avl_node(*avl_tree.data());
+ values.push_back(t);
+ test_tree_container(avl_tree, values);
+}
+
+void test_pop_front(AVLTreeSequence& avl_tree, ValueSequence& values)
+{
+ avl_tree.pop_front();
+ std::cout << std::endl << "After avl_tree.pop_front():";
+ test_avl_node(*avl_tree.data());
+ values.pop_front();
+ test_tree_container(avl_tree, values);
+}
+
+void test_pop_back(AVLTreeSequence& avl_tree, ValueSequence& values)
+{
+ avl_tree.pop_back();
+ std::cout << std::endl << "After avl_tree.pop_back():";
+ test_avl_node(*avl_tree.data());
+ values.pop_back();
+ test_tree_container(avl_tree, values);
+}
+
+void
+ test_insert(
+ AVLTreeSequence& avl_tree
+ , ValueSequence& values
+ , AVLTreeSequence::size_type index
+ , AVLTreeSequence::value_type t
+ )
+{
+ avl_tree.insert(avl_tree.begin() + index, t);
+ std::cout << std::endl << "After avl_tree.insert[" << index << "](";
+ std::cout << t << "):";
+ test_avl_node(*avl_tree.data());
+ values.insert(values.begin() + index, t);
+ test_tree_container(avl_tree, values);
+}
+
+void
+ test_erase(
+ AVLTreeSequence& avl_tree
+ , ValueSequence& values
+ , AVLTreeSequence::size_type index
+ )
+{
+ AVLTreeSequence::iterator tree_itr = avl_tree.erase(
+ avl_tree.begin() + index
+ );
+
+ if (index == avl_tree.size())
+ {
+ BOOST_CHECK(tree_itr == avl_tree.end());
+ }
+ else
+ {
+ BOOST_CHECK(test_tree_values(*tree_itr, avl_tree[index]));
+ }
+
+ std::cout << std::endl << "After avl_tree.erase[" << index << "]:";
+ test_avl_node(*avl_tree.data());
+ values.erase(values.begin() + index);
+ test_tree_container(avl_tree, values);
+}
+
+#include "sequence.hpp"
+
+void test_red_black_sequence()
+{
+ RedBlackTreeSequence red_black_tree;
+ ValueSequence values;
+
+ test_sequence(red_black_tree, values);
+
+ RedBlackTreeSequence red_black_copy;
+ ValueSequence value_copies;
+
+ for (
+ RedBlackTreeSequence::size_type index = 0;
+ index + 1 < red_black_tree.size();
+ ++index
+ )
+ {
+ red_black_copy = red_black_tree;
+ value_copies = values;
+
+ if (!index)
+ {
+ test_tree_container(red_black_copy, value_copies);
+ }
+
+ test_erase(red_black_copy, value_copies, index);
+
+ switch (index)
+ {
+ case 2:
+ {
+ test_erase(red_black_copy, value_copies, 1);
+ break;
+ }
+
+ case 4:
+ {
+ test_erase(red_black_copy, value_copies, 4);
+ break;
+ }
+
+ default:
+ {
+ break;
+ }
+ }
+ }
+}
+
+void test_avl_sequence()
+{
+ AVLTreeSequence avl_tree;
+ ValueSequence values;
+
+ test_sequence(avl_tree, values);
+
+ AVLTreeSequence avl_copy;
+ ValueSequence value_copies;
+
+ for (
+ AVLTreeSequence::size_type index = 0;
+ index + 1 < avl_tree.size();
+ ++index
+ )
+ {
+ avl_copy = avl_tree;
+ value_copies = values;
+
+ if (!index)
+ {
+ test_tree_container(avl_copy, value_copies);
+ }
+
+ test_erase(avl_copy, value_copies, index);
+
+ switch (index)
+ {
+ case 0:
+ {
+ test_erase(avl_copy, value_copies, 0);
+ break;
+ }
+
+ case 1:
+ {
+ test_erase(avl_copy, value_copies, 1);
+ break;
+ }
+
+ case 3:
+ {
+ test_erase(avl_copy, value_copies, 5);
+ break;
+ }
+
+ case 4:
+ {
+ test_erase(avl_copy, value_copies, 4);
+ break;
+ }
+
+ default:
+ {
+ break;
+ }
+ }
+ }
+}
+
+int test_main(int argc, char** argv)
+{
+ test_red_black_sequence();
+ test_avl_sequence();
+ return 0;
+}
+
+#if defined BOOST_MSVC
+ #pragma warning (pop)
+#endif
+

Added: sandbox/tree_node/libs/tree_node/test/binode_map.cpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/test/binode_map.cpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,155 @@
+// Copyright (C) 2013 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)
+
+#include <boost/config.hpp>
+
+#if defined BOOST_MSVC
+ #pragma warning (push)
+ #pragma warning (disable : 4996) // fn called w/params that may be unsafe
+#endif
+
+#include <boost/tree_node/balancer/red_black.hpp>
+#include <boost/tree_node/balancer/adelson_velskii_landis.hpp>
+#include <boost/tree_node/container/binode_associative.hpp>
+#include <boost/test/minimal.hpp>
+#include "type_definitions.hpp"
+#include "container_functions.hpp"
+
+void test_value_insert(ValueMap& values, ValueMap::key_type const& key)
+{
+ values.insert(ValueMap::value_type(key, key));
+}
+
+typedef boost::tree_node::binode_map<
+ RedBlackNodeGen
+ , boost::int32_t
+ , boost::int32_t
+ >
+ RedBlackTreeMap;
+
+void
+ test_insert(
+ RedBlackTreeMap& red_black_tree
+ , ValueMap& values
+ , RedBlackTreeMap::key_type const& key
+ )
+{
+ std::pair<RedBlackTreeMap::iterator,bool> p = red_black_tree.emplace(
+ key
+ , key
+ );
+
+ if (values.insert(ValueMap::value_type(key, key)).second)
+ {
+ BOOST_CHECK(p.second);
+ std::cout << std::endl << "After emplacing " << key << ':';
+ test_red_black_node(*red_black_tree.data());
+ BOOST_CHECK(p.first->first == key);
+ BOOST_CHECK(p.first->second == key);
+ BOOST_CHECK(p.first == red_black_tree.find(key));
+ BOOST_CHECK(!red_black_tree.empty());
+ test_tree_container(red_black_tree, values);
+ }
+ else
+ {
+ BOOST_CHECK(!p.second);
+ }
+}
+
+void
+ test_erase(
+ RedBlackTreeMap& red_black_tree
+ , ValueMap& values
+ , RedBlackTreeMap::key_type const& key
+ )
+{
+ BOOST_CHECK(red_black_tree.erase(key) == values.erase(key));
+ std::cout << std::endl << "After erasing " << key;
+
+ if (red_black_tree.empty())
+ {
+ std::cout << ", red_black_tree is empty." << std::endl;
+ }
+ {
+ std::cout << ':';
+ test_red_black_node(*red_black_tree.data());
+ }
+
+ test_tree_container(red_black_tree, values);
+}
+
+#include "red_black_tree.hpp"
+
+typedef boost::tree_node::binode_map<
+ AVLNodeGen
+ , boost::int32_t
+ , boost::int32_t
+ , boost::default_ordering_selector
+ , boost::tree_node::adelson_velskii_landis_balancer
+ >
+ AVLTreeMap;
+
+void
+ test_insert(
+ AVLTreeMap& avl_tree
+ , ValueMap& values
+ , AVLTreeMap::key_type const& key
+ )
+{
+ std::pair<AVLTreeMap::iterator,bool> p = avl_tree.emplace(key, key);
+
+ if (values.insert(ValueMap::value_type(key, key)).second)
+ {
+ BOOST_CHECK(p.second);
+ std::cout << std::endl << "After emplacing " << key << ':';
+ test_avl_node(*avl_tree.data());
+ BOOST_CHECK(p.first->first == key);
+ BOOST_CHECK(p.first->second == key);
+ BOOST_CHECK(p.first == avl_tree.find(key));
+ BOOST_CHECK(!avl_tree.empty());
+ test_tree_container(avl_tree, values);
+ }
+ else
+ {
+ BOOST_CHECK(!p.second);
+ }
+}
+
+void
+ test_erase(
+ AVLTreeMap& avl_tree
+ , ValueMap& values
+ , AVLTreeMap::key_type const& key
+ )
+{
+ BOOST_CHECK(avl_tree.erase(key) == values.erase(key));
+ std::cout << std::endl << "After erasing " << key;
+
+ if (avl_tree.empty())
+ {
+ std::cout << ", avl_tree is empty." << std::endl;
+ }
+ else
+ {
+ std::cout << ':';
+ test_avl_node(*avl_tree.data());
+ }
+
+ test_tree_container(avl_tree, values);
+}
+
+#include "avl_tree.hpp"
+
+int test_main(int argc, char** argv)
+{
+ test_red_black_tree<RedBlackTreeMap,ValueMap>();
+ test_avl_tree<AVLTreeMap,ValueMap>();
+ return 0;
+}
+
+#if defined BOOST_MSVC
+ #pragma warning (pop)
+#endif
+

Added: sandbox/tree_node/libs/tree_node/test/binode_set.cpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/test/binode_set.cpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,145 @@
+// Copyright (C) 2013 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)
+
+#include <boost/config.hpp>
+
+#if defined BOOST_MSVC
+ #pragma warning (push)
+ #pragma warning (disable : 4996) // fn called w/params that may be unsafe
+#endif
+
+#include <boost/tree_node/balancer/red_black.hpp>
+#include <boost/tree_node/balancer/adelson_velskii_landis.hpp>
+#include <boost/tree_node/container/binode_associative.hpp>
+#include <boost/test/minimal.hpp>
+#include "type_definitions.hpp"
+#include "container_functions.hpp"
+
+void test_value_insert(ValueSet& values, ValueSet::key_type const& key)
+{
+ values.insert(key);
+}
+
+typedef boost::tree_node::binode_set<RedBlackNodeGen,boost::int32_t>
+ RedBlackTreeSet;
+
+void
+ test_insert(
+ RedBlackTreeSet& red_black_tree
+ , ValueSet& values
+ , RedBlackTreeSet::key_type const& key
+ )
+{
+ std::pair<RedBlackTreeSet::iterator,bool> p = red_black_tree.insert(key);
+
+ if (values.insert(key).second)
+ {
+ BOOST_CHECK(p.second);
+ std::cout << std::endl << "After inserting " << key << ':';
+ test_red_black_node(*red_black_tree.data());
+ BOOST_CHECK(*p.first == key);
+ BOOST_CHECK(p.first == red_black_tree.find(key));
+ BOOST_CHECK(!red_black_tree.empty());
+ test_tree_container(red_black_tree, values);
+ }
+ else
+ {
+ BOOST_CHECK(!p.second);
+ }
+}
+
+void
+ test_erase(
+ RedBlackTreeSet& red_black_tree
+ , ValueSet& values
+ , RedBlackTreeSet::key_type const& key
+ )
+{
+ BOOST_CHECK(red_black_tree.erase(key) == values.erase(key));
+ std::cout << std::endl << "After erasing " << key;
+
+ if (red_black_tree.empty())
+ {
+ std::cout << ", red_black_tree is empty." << std::endl;
+ }
+ {
+ std::cout << ':';
+ test_red_black_node(*red_black_tree.data());
+ }
+
+ test_tree_container(red_black_tree, values);
+}
+
+#include "red_black_tree.hpp"
+
+typedef boost::tree_node::binode_set<
+ AVLNodeGen
+ , boost::int32_t
+ , boost::default_ordering_selector
+ , boost::tree_node::adelson_velskii_landis_balancer
+ >
+ AVLTreeSet;
+
+void
+ test_insert(
+ AVLTreeSet& avl_tree
+ , ValueSet& values
+ , AVLTreeSet::key_type const& key
+ )
+{
+ std::pair<AVLTreeSet::iterator,bool> p = avl_tree.insert(key);
+
+ if (values.insert(key).second)
+ {
+ BOOST_CHECK(p.second);
+ std::cout << std::endl << "After inserting " << key << ':';
+ test_avl_node(*avl_tree.data());
+ BOOST_CHECK(*p.first == key);
+ BOOST_CHECK(p.first == avl_tree.find(key));
+ BOOST_CHECK(!avl_tree.empty());
+ test_tree_container(avl_tree, values);
+ }
+ else
+ {
+ BOOST_CHECK(!p.second);
+ }
+}
+
+void
+ test_erase(
+ AVLTreeSet& avl_tree
+ , ValueSet& values
+ , AVLTreeSet::key_type const& key
+ )
+{
+ BOOST_CHECK(avl_tree.erase(key) == values.erase(key));
+ std::cout << std::endl << "After erasing " << key;
+
+ if (avl_tree.empty())
+ {
+ std::cout << ", avl_tree is empty." << std::endl;
+ }
+ else
+ {
+ std::cout << ':';
+ test_avl_node(*avl_tree.data());
+ }
+
+ test_tree_container(avl_tree, values);
+}
+
+#include "avl_tree.hpp"
+
+int test_main(int argc, char** argv)
+{
+ test_red_black_tree<RedBlackTreeSet,ValueSet>();
+ test_avl_tree<AVLTreeSet,ValueSet>();
+ return 0;
+}
+
+#if defined BOOST_MSVC
+ #pragma warning (pop)
+#endif
+

Added: sandbox/tree_node/libs/tree_node/test/container_functions.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/test/container_functions.hpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,367 @@
+// Copyright (C) 2013 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 LIBS_TREE_NODE_TEST_CONTAINER_FUNCTIONS_HPP_INCLUDED
+#define LIBS_TREE_NODE_TEST_CONTAINER_FUNCTIONS_HPP_INCLUDED
+
+#include <iostream>
+#include <utility>
+#include <boost/utility/value_init.hpp>
+#include <boost/range/adaptors.hpp>
+#include <boost/range/algorithm/equal.hpp>
+#include <boost/tree_node/key/data.hpp>
+#include <boost/tree_node/key/red_black_flag.hpp>
+#include <boost/tree_node/key/height.hpp>
+#include <boost/tree_node/iterator/breadth_first.hpp>
+#include <boost/tree_node/iterator/breadth_first_descendant.hpp>
+#include <boost/tree_node/iterator/depth_first.hpp>
+
+template <typename T1, typename T2>
+void test_output_data(std::pair<T1,T2> const& p)
+{
+ std::cout << '<' << p.first << ", " << p.second << '>';
+}
+
+template <typename T>
+void test_output_data(T const& t)
+{
+ std::cout << t;
+}
+
+template <typename Node>
+void test_red_black_node(Node const& root)
+{
+ typename Node::size_type black_depth = boost::initialized_value;
+ std::cout << std::endl;
+
+ for (
+ boost::tree_node::depth_first_iterator<Node const> itr(root);
+ itr;
+ ++itr
+ )
+ {
+ switch (boost::tree_node::traversal_state(itr))
+ {
+ case boost::tree_node::pre_order_traversal:
+ {
+ ++black_depth;
+
+ for (
+ typename Node::size_type depth = 0;
+ depth < black_depth;
+ ++depth
+ )
+ {
+ std::cout << " ";
+ }
+
+ if (Node const* p = itr->get_parent_ptr())
+ {
+ std::cout << (
+ (&*itr == p->get_left_child_ptr()) ? "left" : "right"
+ );
+ }
+
+ std::cout << '(' << (
+ get(*itr, boost::tree_node::red_flag_key())
+ ? "red,"
+ : "black,"
+ );
+ test_output_data(get(*itr, boost::tree_node::data_key()));
+ std::cout << std::endl;
+ break;
+ }
+
+ case boost::tree_node::post_order_traversal:
+ {
+ for (
+ typename Node::size_type depth = 0;
+ depth < black_depth;
+ ++depth
+ )
+ {
+ std::cout << " ";
+ }
+
+ --black_depth;
+ std::cout << (
+ get(*itr, boost::tree_node::red_flag_key())
+ ? "red,"
+ : "black,"
+ );
+ test_output_data(get(*itr, boost::tree_node::data_key()));
+ std::cout << ')' << std::endl;
+ break;
+ }
+
+ default:
+ {
+ BOOST_CHECK(false);
+ }
+ }
+ }
+
+ BOOST_CHECK(get(root, boost::tree_node::black_flag_key()));
+
+ if (root.empty())
+ {
+ return;
+ }
+
+ for (
+ boost::tree_node::breadth_first_descendant_iterator<Node const> itr(
+ root
+ );
+ itr;
+ ++itr
+ )
+ {
+ if (get(*itr, boost::tree_node::red_flag_key()))
+ {
+ BOOST_CHECK(
+ !itr->get_left_child_ptr() || get(
+ *itr->get_left_child_ptr()
+ , boost::tree_node::black_flag_key()
+ )
+ );
+ BOOST_CHECK(
+ !itr->get_right_child_ptr() || get(
+ *itr->get_right_child_ptr()
+ , boost::tree_node::black_flag_key()
+ )
+ );
+ }
+
+ if (!itr->get_left_child_ptr() || !itr->get_right_child_ptr())
+ {
+ typename Node::size_type depth = boost::initialized_value;
+
+ for (Node const* p = &*itr; p; p = p->get_parent_ptr())
+ {
+ if (get(*p, boost::tree_node::black_flag_key()))
+ {
+ ++depth;
+ }
+ }
+
+ if (black_depth)
+ {
+ BOOST_CHECK(black_depth == depth);
+ }
+ else
+ {
+ black_depth = depth;
+ }
+ }
+ }
+}
+
+template <typename Node>
+void test_avl_node(Node const& root)
+{
+ typename Node::size_type max_depth = boost::initialized_value;
+ std::cout << std::endl;
+
+ for (
+ boost::tree_node::depth_first_iterator<Node const> itr(root);
+ itr;
+ ++itr
+ )
+ {
+ switch (boost::tree_node::traversal_state(itr))
+ {
+ case boost::tree_node::pre_order_traversal:
+ {
+ ++max_depth;
+
+ for (
+ typename Node::size_type depth = 0;
+ depth < max_depth;
+ ++depth
+ )
+ {
+ std::cout << " ";
+ }
+
+ if (Node const* p = itr->get_parent_ptr())
+ {
+ std::cout << (
+ (&*itr == p->get_left_child_ptr()) ? "left" : "right"
+ );
+ }
+
+ std::cout << '(' << get(
+ *itr
+ , boost::tree_node::height_key()
+ ) << ", ";
+ test_output_data(get(*itr, boost::tree_node::data_key()));
+ std::cout << std::endl;
+ break;
+ }
+
+ case boost::tree_node::post_order_traversal:
+ {
+ for (
+ typename Node::size_type depth = 0;
+ depth < max_depth;
+ ++depth
+ )
+ {
+ std::cout << " ";
+ }
+
+ --max_depth;
+ std::cout << get(
+ *itr
+ , boost::tree_node::height_key()
+ ) << ", ";
+ test_output_data(get(*itr, boost::tree_node::data_key()));
+ std::cout << ')' << std::endl;
+ break;
+ }
+
+ default:
+ {
+ BOOST_CHECK(false);
+ }
+ }
+ }
+
+ for (
+ boost::tree_node::breadth_first_iterator<Node const> itr(root);
+ itr;
+ ++itr
+ )
+ {
+ if (itr->get_left_child_ptr())
+ {
+ if (itr->get_right_child_ptr())
+ {
+ BOOST_CHECK(
+ (
+ get(
+ *itr->get_left_child_ptr()
+ , boost::tree_node::height_key()
+ ) == get(
+ *itr->get_right_child_ptr()
+ , boost::tree_node::height_key()
+ )
+ ) || (
+ 1 + get(
+ *itr->get_left_child_ptr()
+ , boost::tree_node::height_key()
+ ) == get(
+ *itr->get_right_child_ptr()
+ , boost::tree_node::height_key()
+ )
+ ) || (
+ get(
+ *itr->get_left_child_ptr()
+ , boost::tree_node::height_key()
+ ) == 1 + get(
+ *itr->get_right_child_ptr()
+ , boost::tree_node::height_key()
+ )
+ )
+ );
+ }
+ else
+ {
+ BOOST_CHECK(
+ !get(
+ *itr->get_left_child_ptr()
+ , boost::tree_node::height_key()
+ )
+ );
+ }
+ }
+ else if (itr->get_right_child_ptr())
+ {
+ BOOST_CHECK(
+ !get(
+ *itr->get_right_child_ptr()
+ , boost::tree_node::height_key()
+ )
+ );
+ }
+ }
+}
+
+template <typename K1, typename V1, typename K2, typename V2>
+bool test_tree_values(std::pair<K1,V1> const& p1, std::pair<K2,V2> const& p2)
+{
+ return (p1.first == p2.first) && (p1.second == p2.second);
+}
+
+template <typename T1, typename T2>
+bool test_tree_values(T1 const& t1, T2 const& t2)
+{
+ return t1 == t2;
+}
+
+struct test_equal_trees_predicate
+{
+ template <typename T1, typename T2>
+ bool operator()(T1 const& t1, T2 const& t2) const
+ {
+ return test_tree_values(t1, t2);
+ }
+};
+
+template <typename Tree, typename Values>
+void test_tree_container(Tree const& tree, Values const& values)
+{
+ BOOST_CHECK(tree.empty() == values.empty());
+ BOOST_CHECK(tree.size() == values.size());
+ BOOST_CHECK(
+ boost::range::equal(tree, values, test_equal_trees_predicate())
+ );
+
+ typename Tree::const_reverse_iterator t_rend = tree.crend();
+ typename Values::const_reverse_iterator v_ritr = values.rbegin();
+ typename Values::const_reverse_iterator v_rend = values.rend();
+
+ for (
+ typename Tree::const_reverse_iterator t_ritr = tree.crbegin();
+ t_ritr != t_rend;
+ ++t_ritr
+ )
+ {
+ if (v_ritr == v_rend)
+ {
+ BOOST_CHECK(false);
+ break;
+ }
+
+ BOOST_CHECK(test_tree_values(*t_ritr, *v_ritr));
+ ++v_ritr;
+ }
+
+ BOOST_CHECK(v_ritr == v_rend);
+
+ typename Tree::size_type index = 0;
+ typename Tree::const_iterator t_end = tree.cend();
+
+ for (
+ typename Tree::const_iterator t_itr = tree.cbegin();
+ t_itr != t_end;
+ ++t_itr
+ )
+ {
+ BOOST_CHECK(test_tree_values(tree[index], *t_itr));
+ ++index;
+ }
+}
+
+template <typename Tree, typename Values>
+void test_clear(Tree& tree, Values& values)
+{
+ tree.clear();
+ values.clear();
+ test_tree_container(tree, values);
+}
+
+#endif // LIBS_TREE_NODE_TEST_CONTAINER_FUNCTIONS_HPP_INCLUDED
+

Deleted: sandbox/tree_node/libs/tree_node/test/containers.cpp
==============================================================================
--- sandbox/tree_node/libs/tree_node/test/containers.cpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
+++ (empty file)
@@ -1,1291 +0,0 @@
-// Copyright (C) 2013 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)
-
-#include <boost/config.hpp>
-
-#if defined BOOST_MSVC
- #pragma warning (push)
- #pragma warning (disable : 4996) // fn called w/params that may be unsafe
-#endif
-
-#include <set>
-#include <boost/cstdint.hpp>
-#include <boost/tuple/tuple.hpp>
-#include <boost/range/adaptors.hpp>
-#include <boost/range/algorithm/equal.hpp>
-#include <boost/container_gen/selectors.hpp>
-#include <boost/container_gen/container_gen.hpp>
-#include <boost/container_gen/emplace_function_gen.hpp>
-#include <boost/typeof/boost/tree_node/with_count.hpp>
-#include <boost/typeof/boost/tree_node/with_height.hpp>
-#include <boost/typeof/boost/tree_node/with_position.hpp>
-#include <boost/typeof/boost/tree_node/with_red_black_flag.hpp>
-#include <boost/typeof/boost/tree_node/binary_node.hpp>
-#include <boost/tree_node/iterator/breadth_first.hpp>
-#include <boost/tree_node/iterator/breadth_first_descendant.hpp>
-#include <boost/tree_node/iterator/depth_first.hpp>
-#include <boost/tree_node/balancer/adelson_velskii_landis.hpp>
-#include <boost/tree_node/container/binode.hpp>
-#include <boost/tree_node/container/binode_associative.hpp>
-#include <boost/test/minimal.hpp>
-
-template <typename T1, typename T2>
-void test_output_data(::std::pair<T1,T2> const& p)
-{
- std::cout << '<' << p.first << ", " << p.second << '>';
-}
-
-template <typename T>
-void test_output_data(T const& t)
-{
- std::cout << t;
-}
-
-template <typename Node>
-void test_red_black_node(Node const& root)
-{
- typename Node::size_type black_depth = boost::initialized_value;
- std::cout << std::endl;
-
- for (
- boost::tree_node::depth_first_iterator<Node const> itr(root);
- itr;
- ++itr
- )
- {
- switch (boost::tree_node::traversal_state(itr))
- {
- case boost::tree_node::pre_order_traversal:
- {
- ++black_depth;
-
- for (
- typename Node::size_type depth = 0;
- depth < black_depth;
- ++depth
- )
- {
- std::cout << " ";
- }
-
- if (Node const* p = itr->get_parent_ptr())
- {
- std::cout << (
- (&*itr == p->get_left_child_ptr()) ? "left" : "right"
- );
- }
-
- std::cout << '(' << (
- get(*itr, boost::tree_node::red_flag_key())
- ? "red,"
- : "black,"
- );
- test_output_data(get(*itr, boost::tree_node::data_key()));
- std::cout << std::endl;
- break;
- }
-
- case boost::tree_node::post_order_traversal:
- {
- for (
- typename Node::size_type depth = 0;
- depth < black_depth;
- ++depth
- )
- {
- std::cout << " ";
- }
-
- --black_depth;
- std::cout << (
- get(*itr, boost::tree_node::red_flag_key())
- ? "red,"
- : "black,"
- );
- test_output_data(get(*itr, boost::tree_node::data_key()));
- std::cout << ')' << std::endl;
- break;
- }
-
- default:
- {
- BOOST_CHECK(false);
- }
- }
- }
-
- BOOST_CHECK(get(root, boost::tree_node::black_flag_key()));
-
- if (root.empty())
- {
- return;
- }
-
- for (
- boost::tree_node::breadth_first_descendant_iterator<Node const> itr(
- root
- );
- itr;
- ++itr
- )
- {
- if (get(*itr, boost::tree_node::red_flag_key()))
- {
- BOOST_CHECK(
- !itr->get_left_child_ptr() || get(
- *itr->get_left_child_ptr()
- , boost::tree_node::black_flag_key()
- )
- );
- BOOST_CHECK(
- !itr->get_right_child_ptr() || get(
- *itr->get_right_child_ptr()
- , boost::tree_node::black_flag_key()
- )
- );
- }
-
- if (!itr->get_left_child_ptr() || !itr->get_right_child_ptr())
- {
- typename Node::size_type depth = boost::initialized_value;
-
- for (Node const* p = &*itr; p; p = p->get_parent_ptr())
- {
- if (get(*p, boost::tree_node::black_flag_key()))
- {
- ++depth;
- }
- }
-
- if (black_depth)
- {
- BOOST_CHECK(black_depth == depth);
- }
- else
- {
- black_depth = depth;
- }
- }
- }
-}
-
-template <typename Node>
-void test_avl_node(Node const& root)
-{
- typename Node::size_type max_depth = boost::initialized_value;
- std::cout << std::endl;
-
- for (
- boost::tree_node::depth_first_iterator<Node const> itr(root);
- itr;
- ++itr
- )
- {
- switch (boost::tree_node::traversal_state(itr))
- {
- case boost::tree_node::pre_order_traversal:
- {
- ++max_depth;
-
- for (
- typename Node::size_type depth = 0;
- depth < max_depth;
- ++depth
- )
- {
- std::cout << " ";
- }
-
- if (Node const* p = itr->get_parent_ptr())
- {
- std::cout << (
- (&*itr == p->get_left_child_ptr()) ? "left" : "right"
- );
- }
-
- std::cout << '(' << get(
- *itr
- , boost::tree_node::height_key()
- ) << ", ";
- test_output_data(get(*itr, boost::tree_node::data_key()));
- std::cout << std::endl;
- break;
- }
-
- case boost::tree_node::post_order_traversal:
- {
- for (
- typename Node::size_type depth = 0;
- depth < max_depth;
- ++depth
- )
- {
- std::cout << " ";
- }
-
- --max_depth;
- std::cout << get(
- *itr
- , boost::tree_node::height_key()
- ) << ", ";
- test_output_data(get(*itr, boost::tree_node::data_key()));
- std::cout << ')' << std::endl;
- break;
- }
-
- default:
- {
- BOOST_CHECK(false);
- }
- }
- }
-
- for (
- boost::tree_node::breadth_first_iterator<Node const> itr(root);
- itr;
- ++itr
- )
- {
- if (itr->get_left_child_ptr())
- {
- if (itr->get_right_child_ptr())
- {
- BOOST_CHECK(
- (
- get(
- *itr->get_left_child_ptr()
- , boost::tree_node::height_key()
- ) == get(
- *itr->get_right_child_ptr()
- , boost::tree_node::height_key()
- )
- ) || (
- 1 + get(
- *itr->get_left_child_ptr()
- , boost::tree_node::height_key()
- ) == get(
- *itr->get_right_child_ptr()
- , boost::tree_node::height_key()
- )
- ) || (
- get(
- *itr->get_left_child_ptr()
- , boost::tree_node::height_key()
- ) == 1 + get(
- *itr->get_right_child_ptr()
- , boost::tree_node::height_key()
- )
- )
- );
- }
- else
- {
- BOOST_CHECK(
- !get(
- *itr->get_left_child_ptr()
- , boost::tree_node::height_key()
- )
- );
- }
- }
- else if (itr->get_right_child_ptr())
- {
- BOOST_CHECK(
- !get(
- *itr->get_right_child_ptr()
- , boost::tree_node::height_key()
- )
- );
- }
- }
-}
-
-template <typename K1, typename V1, typename K2, typename V2>
-bool test_tree_values(std::pair<K1,V1> const& p1, std::pair<K2,V2> const& p2)
-{
- return (p1.first == p2.first) && (p1.second == p2.second);
-}
-
-template <typename T1, typename T2>
-bool test_tree_values(T1 const& t1, T2 const& t2)
-{
- return t1 == t2;
-}
-
-struct test_equal_trees_predicate
-{
- template <typename T1, typename T2>
- bool operator()(T1 const& t1, T2 const& t2) const
- {
- return test_tree_values(t1, t2);
- }
-};
-
-template <typename Tree, typename Values>
-void test_tree_container(Tree const& tree, Values const& values)
-{
- BOOST_CHECK(tree.empty() == values.empty());
- BOOST_CHECK(tree.size() == values.size());
- BOOST_CHECK(
- boost::range::equal(tree, values, test_equal_trees_predicate())
- );
-
- typename Tree::const_reverse_iterator t_rend = tree.crend();
- typename Values::const_reverse_iterator v_ritr = values.rbegin();
- typename Values::const_reverse_iterator v_rend = values.rend();
-
- for (
- typename Tree::const_reverse_iterator t_ritr = tree.crbegin();
- t_ritr != t_rend;
- ++t_ritr
- )
- {
- if (v_ritr == v_rend)
- {
- BOOST_CHECK(false);
- break;
- }
-
- BOOST_CHECK(test_tree_values(*t_ritr, *v_ritr));
- ++v_ritr;
- }
-
- BOOST_CHECK(v_ritr == v_rend);
-
- typename Tree::size_type index = 0;
- typename Tree::const_iterator t_end = tree.cend();
-
- for (
- typename Tree::const_iterator t_itr = tree.cbegin();
- t_itr != t_end;
- ++t_itr
- )
- {
- BOOST_CHECK(test_tree_values(tree[index], *t_itr));
- ++index;
- }
-}
-
-template <typename Tree, typename Values>
-void test_clear(Tree& tree, Values& values)
-{
- tree.clear();
- values.clear();
- test_tree_container(tree, values);
-}
-
-typedef std::deque<boost::int32_t>
- ValueSequence;
-typedef boost::tree_node::with_red_black_flag_gen<
- boost::tree_node::with_count_base_gen<
- boost::tree_node::binary_node_base_gen<>
- >
- >
- RedBlackNodeGen;
-typedef boost::tree_node::binode_container<RedBlackNodeGen,boost::int32_t>
- RedBlackTreeSequence;
-
-void
- test_push_front(
- RedBlackTreeSequence& red_black_tree
- , ValueSequence& values
- , RedBlackTreeSequence::value_type t
- )
-{
- red_black_tree.push_front(t);
- std::cout << std::endl << "After red_black_tree.push_front(" << t << "):";
- test_red_black_node(*red_black_tree.data());
- values.push_front(t);
- test_tree_container(red_black_tree, values);
-}
-
-void
- test_push_back(
- RedBlackTreeSequence& red_black_tree
- , ValueSequence& values
- , RedBlackTreeSequence::value_type t
- )
-{
- red_black_tree.push_back(t);
- std::cout << std::endl << "After red_black_tree.push_back(" << t << "):";
- test_red_black_node(*red_black_tree.data());
- values.push_back(t);
- test_tree_container(red_black_tree, values);
-}
-
-void
- test_pop_front(
- RedBlackTreeSequence& red_black_tree
- , ValueSequence& values
- )
-{
- red_black_tree.pop_front();
- std::cout << std::endl << "After red_black_tree.pop_front():";
- test_red_black_node(*red_black_tree.data());
- values.pop_front();
- test_tree_container(red_black_tree, values);
-}
-
-void
- test_pop_back(
- RedBlackTreeSequence& red_black_tree
- , ValueSequence& values
- )
-{
- red_black_tree.pop_back();
- std::cout << std::endl << "After red_black_tree.pop_back():";
- test_red_black_node(*red_black_tree.data());
- values.pop_back();
- test_tree_container(red_black_tree, values);
-}
-
-void
- test_insert(
- RedBlackTreeSequence& red_black_tree
- , ValueSequence& values
- , RedBlackTreeSequence::size_type index
- , RedBlackTreeSequence::value_type t
- )
-{
- red_black_tree.insert(red_black_tree.begin() + index, t);
- std::cout << std::endl << "After red_black_tree.insert[" << index << "](";
- std::cout << t << "):";
- test_red_black_node(*red_black_tree.data());
- values.insert(values.begin() + index, t);
- test_tree_container(red_black_tree, values);
-}
-
-void
- test_erase(
- RedBlackTreeSequence& red_black_tree
- , ValueSequence& values
- , RedBlackTreeSequence::size_type index
- )
-{
- RedBlackTreeSequence::iterator tree_itr = red_black_tree.erase(
- red_black_tree.begin() + index
- );
-
- if (index == red_black_tree.size())
- {
- BOOST_CHECK(tree_itr == red_black_tree.end());
- }
- else
- {
- BOOST_CHECK(test_tree_values(*tree_itr, red_black_tree[index]));
- }
-
- std::cout << std::endl << "After red_black_tree.erase[" << index << "]:";
- test_red_black_node(*red_black_tree.data());
- values.erase(values.begin() + index);
- test_tree_container(red_black_tree, values);
-}
-
-typedef boost::tree_node::with_height_gen<
- boost::tree_node::with_count_base_gen<
- boost::tree_node::binary_node_base_gen<>
- >
- >
- AVLNodeGen;
-typedef boost::tree_node::binode_container<
- AVLNodeGen
- , boost::int32_t
- , boost::tree_node::adelson_velskii_landis_balancer
- >
- AVLTreeSequence;
-
-void
- test_push_front(
- AVLTreeSequence& avl_tree
- , ValueSequence& values
- , AVLTreeSequence::value_type t
- )
-{
- avl_tree.push_front(t);
- std::cout << std::endl << "After avl_tree.push_front(" << t << "):";
- test_avl_node(*avl_tree.data());
- values.push_front(t);
- test_tree_container(avl_tree, values);
-}
-
-void
- test_push_back(
- AVLTreeSequence& avl_tree
- , ValueSequence& values
- , AVLTreeSequence::value_type t
- )
-{
- avl_tree.push_back(t);
- std::cout << std::endl << "After avl_tree.push_back(" << t << "):";
- test_avl_node(*avl_tree.data());
- values.push_back(t);
- test_tree_container(avl_tree, values);
-}
-
-void test_pop_front(AVLTreeSequence& avl_tree, ValueSequence& values)
-{
- avl_tree.pop_front();
- std::cout << std::endl << "After avl_tree.pop_front():";
- test_avl_node(*avl_tree.data());
- values.pop_front();
- test_tree_container(avl_tree, values);
-}
-
-void test_pop_back(AVLTreeSequence& avl_tree, ValueSequence& values)
-{
- avl_tree.pop_back();
- std::cout << std::endl << "After avl_tree.pop_back():";
- test_avl_node(*avl_tree.data());
- values.pop_back();
- test_tree_container(avl_tree, values);
-}
-
-void
- test_insert(
- AVLTreeSequence& avl_tree
- , ValueSequence& values
- , AVLTreeSequence::size_type index
- , AVLTreeSequence::value_type t
- )
-{
- avl_tree.insert(avl_tree.begin() + index, t);
- std::cout << std::endl << "After avl_tree.insert[" << index << "](";
- std::cout << t << "):";
- test_avl_node(*avl_tree.data());
- values.insert(values.begin() + index, t);
- test_tree_container(avl_tree, values);
-}
-
-void
- test_erase(
- AVLTreeSequence& avl_tree
- , ValueSequence& values
- , AVLTreeSequence::size_type index
- )
-{
- AVLTreeSequence::iterator tree_itr = avl_tree.erase(
- avl_tree.begin() + index
- );
-
- if (index == avl_tree.size())
- {
- BOOST_CHECK(tree_itr == avl_tree.end());
- }
- else
- {
- BOOST_CHECK(test_tree_values(*tree_itr, avl_tree[index]));
- }
-
- std::cout << std::endl << "After avl_tree.erase[" << index << "]:";
- test_avl_node(*avl_tree.data());
- values.erase(values.begin() + index);
- test_tree_container(avl_tree, values);
-}
-
-template <typename TreeSequence>
-void test_sequence(TreeSequence& tree_sequence, ValueSequence& values)
-{
- BOOST_CHECK(tree_sequence.empty());
- BOOST_CHECK(0 == tree_sequence.size());
-
- for (boost::int32_t i = -5; -15 < i; --i)
- {
- test_push_back(tree_sequence, values, i);
- }
-
- for (boost::int32_t i = 5; i < 15; ++i)
- {
- test_push_front(tree_sequence, values, i);
- }
-
- test_pop_back(tree_sequence, values);
- test_pop_front(tree_sequence, values);
- typename TreeSequence::size_type index = 0;
-
- for (boost::int32_t i = -4; i < 5; ++i)
- {
- test_insert(tree_sequence, values, index += 2, i);
- }
-}
-
-void test_red_black_sequence()
-{
- RedBlackTreeSequence red_black_tree;
- ValueSequence values;
-
- test_sequence(red_black_tree, values);
-
- RedBlackTreeSequence red_black_copy;
- ValueSequence value_copies;
-
- for (
- RedBlackTreeSequence::size_type index = 0;
- index + 1 < red_black_tree.size();
- ++index
- )
- {
- red_black_copy = red_black_tree;
- value_copies = values;
-
- if (!index)
- {
- test_tree_container(red_black_copy, value_copies);
- }
-
- test_erase(red_black_copy, value_copies, index);
-
- switch (index)
- {
- case 2:
- {
- test_erase(red_black_copy, value_copies, 1);
- break;
- }
-
- case 4:
- {
- test_erase(red_black_copy, value_copies, 4);
- break;
- }
-
- default:
- {
- break;
- }
- }
- }
-}
-
-void test_avl_sequence()
-{
- AVLTreeSequence avl_tree;
- ValueSequence values;
-
- test_sequence(avl_tree, values);
-
- AVLTreeSequence avl_copy;
- ValueSequence value_copies;
-
- for (
- AVLTreeSequence::size_type index = 0;
- index + 1 < avl_tree.size();
- ++index
- )
- {
- avl_copy = avl_tree;
- value_copies = values;
-
- if (!index)
- {
- test_tree_container(avl_copy, value_copies);
- }
-
- test_erase(avl_copy, value_copies, index);
-
- switch (index)
- {
- case 0:
- {
- test_erase(avl_copy, value_copies, 0);
- break;
- }
-
- case 1:
- {
- test_erase(avl_copy, value_copies, 1);
- break;
- }
-
- case 3:
- {
- test_erase(avl_copy, value_copies, 5);
- break;
- }
-
- case 4:
- {
- test_erase(avl_copy, value_copies, 4);
- break;
- }
-
- default:
- {
- break;
- }
- }
- }
-}
-
-typedef std::set<boost::int32_t>
- ValueSet;
-typedef std::map<boost::int32_t,boost::int32_t>
- ValueMap;
-
-void test_value_insert(ValueSet& values, ValueSet::key_type const& key)
-{
- values.insert(key);
-}
-
-void test_value_insert(ValueMap& values, ValueMap::key_type const& key)
-{
- values.insert(ValueMap::value_type(key, key));
-}
-
-typedef boost::tree_node::binode_set<RedBlackNodeGen,boost::int32_t>
- RedBlackTreeSet;
-
-void
- test_insert(
- RedBlackTreeSet& red_black_tree
- , ValueSet& values
- , RedBlackTreeSet::key_type const& key
- )
-{
- std::pair<RedBlackTreeSet::iterator,bool> p = red_black_tree.insert(key);
-
- if (values.insert(key).second)
- {
- BOOST_CHECK(p.second);
- std::cout << std::endl << "After inserting " << key << ':';
- test_red_black_node(*red_black_tree.data());
- BOOST_CHECK(*p.first == key);
- BOOST_CHECK(p.first == red_black_tree.find(key));
- BOOST_CHECK(!red_black_tree.empty());
- test_tree_container(red_black_tree, values);
- }
- else
- {
- BOOST_CHECK(!p.second);
- }
-}
-
-void
- test_erase(
- RedBlackTreeSet& red_black_tree
- , ValueSet& values
- , RedBlackTreeSet::key_type const& key
- )
-{
- BOOST_CHECK(red_black_tree.erase(key) == values.erase(key));
- std::cout << std::endl << "After erasing " << key;
-
- if (red_black_tree.empty())
- {
- std::cout << ", red_black_tree is empty." << std::endl;
- }
- {
- std::cout << ':';
- test_red_black_node(*red_black_tree.data());
- }
-
- test_tree_container(red_black_tree, values);
-}
-
-typedef boost::tree_node::binode_map<
- RedBlackNodeGen
- , boost::int32_t
- , boost::int32_t
- >
- RedBlackTreeMap;
-
-void
- test_insert(
- RedBlackTreeMap& red_black_tree
- , ValueMap& values
- , RedBlackTreeMap::key_type const& key
- )
-{
- std::pair<RedBlackTreeMap::iterator,bool> p = red_black_tree.emplace(
- key
- , key
- );
-
- if (values.insert(ValueMap::value_type(key, key)).second)
- {
- BOOST_CHECK(p.second);
- std::cout << std::endl << "After emplacing " << key << ':';
- test_red_black_node(*red_black_tree.data());
- BOOST_CHECK(p.first->first == key);
- BOOST_CHECK(p.first->second == key);
- BOOST_CHECK(p.first == red_black_tree.find(key));
- BOOST_CHECK(!red_black_tree.empty());
- test_tree_container(red_black_tree, values);
- }
- else
- {
- BOOST_CHECK(!p.second);
- }
-}
-
-void
- test_erase(
- RedBlackTreeMap& red_black_tree
- , ValueMap& values
- , RedBlackTreeMap::key_type const& key
- )
-{
- BOOST_CHECK(red_black_tree.erase(key) == values.erase(key));
- std::cout << std::endl << "After erasing " << key;
-
- if (red_black_tree.empty())
- {
- std::cout << ", red_black_tree is empty." << std::endl;
- }
- {
- std::cout << ':';
- test_red_black_node(*red_black_tree.data());
- }
-
- test_tree_container(red_black_tree, values);
-}
-
-template <typename Tree, typename Values>
-void test_red_black_tree()
-{
- Tree red_black_tree;
- Values values;
-
- BOOST_CHECK(red_black_tree.empty());
- BOOST_CHECK(0 == red_black_tree.size());
- test_insert(red_black_tree, values, 1);
- test_insert(red_black_tree, values, 2);
- test_insert(red_black_tree, values, 4);
- test_insert(red_black_tree, values, 3);
- test_erase(red_black_tree, values, 1);
- test_clear(red_black_tree, values);
- test_insert(red_black_tree, values, -1);
- test_insert(red_black_tree, values, -2);
- test_insert(red_black_tree, values, -4);
- test_insert(red_black_tree, values, -3);
- test_erase(red_black_tree, values, -1);
- test_clear(red_black_tree, values);
-
- for (int i = 5; i < 10; ++i)
- {
- test_insert(red_black_tree, values, i);
- }
-
- for (int i = 15; 9 < i; --i)
- {
- test_insert(red_black_tree, values, i);
- }
-
- test_erase(red_black_tree, values, 5);
- test_clear(red_black_tree, values);
-
- for (int i = 5; i < 10; ++i)
- {
- test_insert(red_black_tree, values, -i);
- }
-
- for (int i = 15; 9 < i; --i)
- {
- test_insert(red_black_tree, values, -i);
- }
-
- test_erase(red_black_tree, values, -5);
- test_clear(red_black_tree, values);
- test_insert(red_black_tree, values, 13);
- test_insert(red_black_tree, values, 8);
- test_insert(red_black_tree, values, 1);
- test_insert(red_black_tree, values, 6);
- test_insert(red_black_tree, values, 11);
- test_insert(red_black_tree, values, 17);
- test_insert(red_black_tree, values, 15);
- test_insert(red_black_tree, values, 22);
- test_insert(red_black_tree, values, 25);
- test_insert(red_black_tree, values, 28);
-
- Tree red_black_copy(red_black_tree);
-
- test_tree_container(red_black_copy, values);
- test_insert(red_black_copy, values, 26);
- test_insert(red_black_copy, values, 27);
- test_erase(red_black_copy, values, 15);
- test_value_insert(values, 15);
- values.erase(27);
- values.erase(26);
- test_insert(red_black_tree, values, 20);
- test_insert(red_black_tree, values, 21);
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 11);
- red_black_copy = red_black_tree;
- test_value_insert(values, 11);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 15);
- test_clear(red_black_tree, values);
- test_insert(red_black_tree, values, -13);
- test_insert(red_black_tree, values, -8);
- test_insert(red_black_tree, values, -1);
- test_insert(red_black_tree, values, -6);
- test_insert(red_black_tree, values, -11);
- test_insert(red_black_tree, values, -17);
- test_insert(red_black_tree, values, -15);
- test_insert(red_black_tree, values, -22);
- test_insert(red_black_tree, values, -25);
- test_insert(red_black_tree, values, -28);
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_insert(red_black_copy, values, -26);
- test_insert(red_black_copy, values, -27);
- test_erase(red_black_copy, values, -15);
- test_value_insert(values, -15);
- values.erase(-27);
- values.erase(-26);
- test_insert(red_black_tree, values, -20);
- test_insert(red_black_tree, values, -21);
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -11);
- red_black_copy = red_black_tree;
- test_value_insert(values, -11);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -15);
- test_clear(red_black_tree, values);
- test_insert(red_black_tree, values, 8);
- test_insert(red_black_tree, values, 4);
- test_insert(red_black_tree, values, 9);
- test_insert(red_black_tree, values, 2);
- test_insert(red_black_tree, values, 6);
- test_insert(red_black_tree, values, 1);
- test_insert(red_black_tree, values, 3);
- test_insert(red_black_tree, values, 5);
- test_insert(red_black_tree, values, 7);
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 9);
- test_erase(red_black_copy, values, 2);
- test_erase(red_black_copy, values, 3);
- test_erase(red_black_copy, values, 1);
- test_clear(red_black_tree, values);
- test_insert(red_black_tree, values, -8);
- test_insert(red_black_tree, values, -4);
- test_insert(red_black_tree, values, -9);
- test_insert(red_black_tree, values, -2);
- test_insert(red_black_tree, values, -6);
- test_insert(red_black_tree, values, -1);
- test_insert(red_black_tree, values, -3);
- test_insert(red_black_tree, values, -5);
- test_insert(red_black_tree, values, -7);
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -9);
- test_erase(red_black_copy, values, -2);
- test_erase(red_black_copy, values, -3);
- test_erase(red_black_copy, values, -1);
- test_clear(red_black_tree, values);
-
- for (int i = 1; i < 10; ++i)
- {
- test_insert(red_black_tree, values, i);
- }
-
- for (int i = 15; 9 < i; --i)
- {
- test_insert(red_black_tree, values, i);
- }
-
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 1);
- red_black_copy = red_black_tree;
- test_value_insert(values, 1);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 3);
- red_black_copy = red_black_tree;
- test_value_insert(values, 3);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 5);
- red_black_copy = red_black_tree;
- test_value_insert(values, 5);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 7);
- test_erase(red_black_copy, values, 6);
- test_erase(red_black_copy, values, 5);
- test_erase(red_black_copy, values, 8);
- test_erase(red_black_copy, values, 9);
- red_black_copy = red_black_tree;
- test_value_insert(values, 9);
- test_value_insert(values, 8);
- test_value_insert(values, 5);
- test_value_insert(values, 6);
- test_value_insert(values, 7);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 15);
- test_clear(red_black_tree, values);
-
- for (int i = 1; i < 10; ++i)
- {
- test_insert(red_black_tree, values, -i);
- }
-
- for (int i = 15; 9 < i; --i)
- {
- test_insert(red_black_tree, values, -i);
- }
-
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -1);
- red_black_copy = red_black_tree;
- test_value_insert(values, -1);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -3);
- red_black_copy = red_black_tree;
- test_value_insert(values, -3);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -5);
- red_black_copy = red_black_tree;
- test_value_insert(values, -5);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -7);
- test_erase(red_black_copy, values, -6);
- test_erase(red_black_copy, values, -5);
- test_erase(red_black_copy, values, -8);
- test_erase(red_black_copy, values, -9);
- red_black_copy = red_black_tree;
- test_value_insert(values, -9);
- test_value_insert(values, -8);
- test_value_insert(values, -5);
- test_value_insert(values, -6);
- test_value_insert(values, -7);
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -15);
- test_clear(red_black_tree, values);
-
- for (int i = 1; i < 16; ++i)
- {
- test_insert(red_black_tree, values, i);
- }
-
- test_erase(red_black_tree, values, 5);
- test_clear(red_black_tree, values);
-
- for (int i = 1; i < 16; ++i)
- {
- test_insert(red_black_tree, values, -i);
- }
-
- test_erase(red_black_tree, values, -5);
- test_clear(red_black_tree, values);
- test_insert(red_black_tree, values, 0);
- test_insert(red_black_tree, values, -8);
- test_insert(red_black_tree, values, 8);
- test_insert(red_black_tree, values, -16);
- test_insert(red_black_tree, values, -4);
- test_insert(red_black_tree, values, 4);
- test_insert(red_black_tree, values, 16);
- test_insert(red_black_tree, values, -18);
- test_insert(red_black_tree, values, -12);
- test_insert(red_black_tree, values, -6);
- test_insert(red_black_tree, values, -2);
- test_insert(red_black_tree, values, 2);
- test_insert(red_black_tree, values, 6);
- test_insert(red_black_tree, values, 12);
- test_insert(red_black_tree, values, 18);
- test_insert(red_black_tree, values, -19);
- test_insert(red_black_tree, values, -17);
- test_insert(red_black_tree, values, -14);
- test_insert(red_black_tree, values, -10);
- test_insert(red_black_tree, values, -7);
- test_insert(red_black_tree, values, -5);
- test_insert(red_black_tree, values, -3);
- test_insert(red_black_tree, values, -1);
- test_insert(red_black_tree, values, 1);
- test_insert(red_black_tree, values, 3);
- test_insert(red_black_tree, values, 5);
- test_insert(red_black_tree, values, 7);
- test_insert(red_black_tree, values, 10);
- test_insert(red_black_tree, values, 14);
- test_insert(red_black_tree, values, 17);
- test_insert(red_black_tree, values, 19);
- test_insert(red_black_tree, values, -15);
- test_insert(red_black_tree, values, -13);
- test_insert(red_black_tree, values, -11);
- test_insert(red_black_tree, values, -9);
- test_insert(red_black_tree, values, 9);
- test_insert(red_black_tree, values, 11);
- test_insert(red_black_tree, values, 13);
- test_insert(red_black_tree, values, 15);
- test_erase(red_black_tree, values, -19);
- test_erase(red_black_tree, values, -17);
- test_erase(red_black_tree, values, -7);
- test_erase(red_black_tree, values, -5);
- test_erase(red_black_tree, values, -3);
- test_erase(red_black_tree, values, -1);
- test_erase(red_black_tree, values, 1);
- test_erase(red_black_tree, values, 3);
- test_erase(red_black_tree, values, 5);
- test_erase(red_black_tree, values, 7);
- test_erase(red_black_tree, values, 17);
- test_erase(red_black_tree, values, 19);
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, 0);
- test_erase(red_black_copy, values, 2);
- test_value_insert(values, 2);
- test_value_insert(values, 0);
- red_black_copy = red_black_tree;
- test_tree_container(red_black_copy, values);
- test_erase(red_black_copy, values, -2);
- test_erase(red_black_copy, values, 0);
-}
-
-typedef boost::tree_node::binode_set<
- AVLNodeGen
- , boost::int32_t
- , boost::default_ordering_selector
- , boost::tree_node::adelson_velskii_landis_balancer
- >
- AVLTreeSet;
-
-void
- test_insert(
- AVLTreeSet& avl_tree
- , ValueSet& values
- , AVLTreeSet::key_type const& key
- )
-{
- std::pair<AVLTreeSet::iterator,bool> p = avl_tree.insert(key);
-
- if (values.insert(key).second)
- {
- BOOST_CHECK(p.second);
- std::cout << std::endl << "After inserting " << key << ':';
- test_avl_node(*avl_tree.data());
- BOOST_CHECK(*p.first == key);
- BOOST_CHECK(p.first == avl_tree.find(key));
- BOOST_CHECK(!avl_tree.empty());
- test_tree_container(avl_tree, values);
- }
- else
- {
- BOOST_CHECK(!p.second);
- }
-}
-
-void
- test_erase(
- AVLTreeSet& avl_tree
- , ValueSet& values
- , AVLTreeSet::key_type const& key
- )
-{
- BOOST_CHECK(avl_tree.erase(key) == values.erase(key));
- std::cout << std::endl << "After erasing " << key;
-
- if (avl_tree.empty())
- {
- std::cout << ", avl_tree is empty." << std::endl;
- }
- else
- {
- std::cout << ':';
- test_avl_node(*avl_tree.data());
- }
-
- test_tree_container(avl_tree, values);
-}
-
-typedef boost::tree_node::binode_map<
- AVLNodeGen
- , boost::int32_t
- , boost::int32_t
- , boost::default_ordering_selector
- , boost::tree_node::adelson_velskii_landis_balancer
- >
- AVLTreeMap;
-
-void
- test_insert(
- AVLTreeMap& avl_tree
- , ValueMap& values
- , AVLTreeMap::key_type const& key
- )
-{
- std::pair<AVLTreeMap::iterator,bool> p = avl_tree.emplace(key, key);
-
- if (values.insert(ValueMap::value_type(key, key)).second)
- {
- BOOST_CHECK(p.second);
- std::cout << std::endl << "After emplacing " << key << ':';
- test_avl_node(*avl_tree.data());
- BOOST_CHECK(p.first->first == key);
- BOOST_CHECK(p.first->second == key);
- BOOST_CHECK(p.first == avl_tree.find(key));
- BOOST_CHECK(!avl_tree.empty());
- test_tree_container(avl_tree, values);
- }
- else
- {
- BOOST_CHECK(!p.second);
- }
-}
-
-void
- test_erase(
- AVLTreeMap& avl_tree
- , ValueMap& values
- , AVLTreeMap::key_type const& key
- )
-{
- BOOST_CHECK(avl_tree.erase(key) == values.erase(key));
- std::cout << std::endl << "After erasing " << key;
-
- if (avl_tree.empty())
- {
- std::cout << ", avl_tree is empty." << std::endl;
- }
- else
- {
- std::cout << ':';
- test_avl_node(*avl_tree.data());
- }
-
- test_tree_container(avl_tree, values);
-}
-
-template <typename Tree, typename Values>
-void test_avl_tree()
-{
- Tree avl_tree;
- Values values;
-
- BOOST_CHECK(avl_tree.empty());
- BOOST_CHECK(0 == avl_tree.size());
-
- test_insert(avl_tree, values, 13);
- test_insert(avl_tree, values, 8);
- test_insert(avl_tree, values, 1);
- test_insert(avl_tree, values, 6);
- test_insert(avl_tree, values, 11);
- test_insert(avl_tree, values, 17);
- test_insert(avl_tree, values, 15);
- test_insert(avl_tree, values, 22);
- test_insert(avl_tree, values, 25);
- test_insert(avl_tree, values, 27);
- test_insert(avl_tree, values, 20);
- test_insert(avl_tree, values, 21);
- test_erase(avl_tree, values, 1);
- test_erase(avl_tree, values, 11);
- test_erase(avl_tree, values, 15);
-}
-
-int test_main(int argc, char** argv)
-{
- test_red_black_sequence();
- test_avl_sequence();
- test_red_black_tree<RedBlackTreeSet,ValueSet>();
- test_red_black_tree<RedBlackTreeMap,ValueMap>();
- test_avl_tree<AVLTreeSet,ValueSet>();
- test_avl_tree<AVLTreeMap,ValueMap>();
- return 0;
-}
-
-#if defined BOOST_MSVC
- #pragma warning (pop)
-#endif
-

Added: sandbox/tree_node/libs/tree_node/test/red_black_tree.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/test/red_black_tree.hpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,305 @@
+// Copyright (C) 2013 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 LIBS_TREE_NODE_TEST_RED_BLACK_TREE_HPP_INCLUDED
+#define LIBS_TREE_NODE_TEST_RED_BLACK_TREE_HPP_INCLUDED
+
+#include "container_functions.hpp"
+
+template <typename Tree, typename Values>
+void test_red_black_tree()
+{
+ Tree red_black_tree;
+ Values values;
+
+ BOOST_CHECK(red_black_tree.empty());
+ BOOST_CHECK(0 == red_black_tree.size());
+ test_insert(red_black_tree, values, 1);
+ test_insert(red_black_tree, values, 2);
+ test_insert(red_black_tree, values, 4);
+ test_insert(red_black_tree, values, 3);
+ test_erase(red_black_tree, values, 1);
+ test_clear(red_black_tree, values);
+ test_insert(red_black_tree, values, -1);
+ test_insert(red_black_tree, values, -2);
+ test_insert(red_black_tree, values, -4);
+ test_insert(red_black_tree, values, -3);
+ test_erase(red_black_tree, values, -1);
+ test_clear(red_black_tree, values);
+
+ for (int i = 5; i < 10; ++i)
+ {
+ test_insert(red_black_tree, values, i);
+ }
+
+ for (int i = 15; 9 < i; --i)
+ {
+ test_insert(red_black_tree, values, i);
+ }
+
+ test_erase(red_black_tree, values, 5);
+ test_clear(red_black_tree, values);
+
+ for (int i = 5; i < 10; ++i)
+ {
+ test_insert(red_black_tree, values, -i);
+ }
+
+ for (int i = 15; 9 < i; --i)
+ {
+ test_insert(red_black_tree, values, -i);
+ }
+
+ test_erase(red_black_tree, values, -5);
+ test_clear(red_black_tree, values);
+ test_insert(red_black_tree, values, 13);
+ test_insert(red_black_tree, values, 8);
+ test_insert(red_black_tree, values, 1);
+ test_insert(red_black_tree, values, 6);
+ test_insert(red_black_tree, values, 11);
+ test_insert(red_black_tree, values, 17);
+ test_insert(red_black_tree, values, 15);
+ test_insert(red_black_tree, values, 22);
+ test_insert(red_black_tree, values, 25);
+ test_insert(red_black_tree, values, 28);
+
+ Tree red_black_copy(red_black_tree);
+
+ test_tree_container(red_black_copy, values);
+ test_insert(red_black_copy, values, 26);
+ test_insert(red_black_copy, values, 27);
+ test_erase(red_black_copy, values, 15);
+ test_value_insert(values, 15);
+ values.erase(27);
+ values.erase(26);
+ test_insert(red_black_tree, values, 20);
+ test_insert(red_black_tree, values, 21);
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 11);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, 11);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 15);
+ test_clear(red_black_tree, values);
+ test_insert(red_black_tree, values, -13);
+ test_insert(red_black_tree, values, -8);
+ test_insert(red_black_tree, values, -1);
+ test_insert(red_black_tree, values, -6);
+ test_insert(red_black_tree, values, -11);
+ test_insert(red_black_tree, values, -17);
+ test_insert(red_black_tree, values, -15);
+ test_insert(red_black_tree, values, -22);
+ test_insert(red_black_tree, values, -25);
+ test_insert(red_black_tree, values, -28);
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_insert(red_black_copy, values, -26);
+ test_insert(red_black_copy, values, -27);
+ test_erase(red_black_copy, values, -15);
+ test_value_insert(values, -15);
+ values.erase(-27);
+ values.erase(-26);
+ test_insert(red_black_tree, values, -20);
+ test_insert(red_black_tree, values, -21);
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -11);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, -11);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -15);
+ test_clear(red_black_tree, values);
+ test_insert(red_black_tree, values, 8);
+ test_insert(red_black_tree, values, 4);
+ test_insert(red_black_tree, values, 9);
+ test_insert(red_black_tree, values, 2);
+ test_insert(red_black_tree, values, 6);
+ test_insert(red_black_tree, values, 1);
+ test_insert(red_black_tree, values, 3);
+ test_insert(red_black_tree, values, 5);
+ test_insert(red_black_tree, values, 7);
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 9);
+ test_erase(red_black_copy, values, 2);
+ test_erase(red_black_copy, values, 3);
+ test_erase(red_black_copy, values, 1);
+ test_clear(red_black_tree, values);
+ test_insert(red_black_tree, values, -8);
+ test_insert(red_black_tree, values, -4);
+ test_insert(red_black_tree, values, -9);
+ test_insert(red_black_tree, values, -2);
+ test_insert(red_black_tree, values, -6);
+ test_insert(red_black_tree, values, -1);
+ test_insert(red_black_tree, values, -3);
+ test_insert(red_black_tree, values, -5);
+ test_insert(red_black_tree, values, -7);
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -9);
+ test_erase(red_black_copy, values, -2);
+ test_erase(red_black_copy, values, -3);
+ test_erase(red_black_copy, values, -1);
+ test_clear(red_black_tree, values);
+
+ for (int i = 1; i < 10; ++i)
+ {
+ test_insert(red_black_tree, values, i);
+ }
+
+ for (int i = 15; 9 < i; --i)
+ {
+ test_insert(red_black_tree, values, i);
+ }
+
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 1);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, 1);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 3);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, 3);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 5);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, 5);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 7);
+ test_erase(red_black_copy, values, 6);
+ test_erase(red_black_copy, values, 5);
+ test_erase(red_black_copy, values, 8);
+ test_erase(red_black_copy, values, 9);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, 9);
+ test_value_insert(values, 8);
+ test_value_insert(values, 5);
+ test_value_insert(values, 6);
+ test_value_insert(values, 7);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 15);
+ test_clear(red_black_tree, values);
+
+ for (int i = 1; i < 10; ++i)
+ {
+ test_insert(red_black_tree, values, -i);
+ }
+
+ for (int i = 15; 9 < i; --i)
+ {
+ test_insert(red_black_tree, values, -i);
+ }
+
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -1);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, -1);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -3);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, -3);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -5);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, -5);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -7);
+ test_erase(red_black_copy, values, -6);
+ test_erase(red_black_copy, values, -5);
+ test_erase(red_black_copy, values, -8);
+ test_erase(red_black_copy, values, -9);
+ red_black_copy = red_black_tree;
+ test_value_insert(values, -9);
+ test_value_insert(values, -8);
+ test_value_insert(values, -5);
+ test_value_insert(values, -6);
+ test_value_insert(values, -7);
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -15);
+ test_clear(red_black_tree, values);
+
+ for (int i = 1; i < 16; ++i)
+ {
+ test_insert(red_black_tree, values, i);
+ }
+
+ test_erase(red_black_tree, values, 5);
+ test_clear(red_black_tree, values);
+
+ for (int i = 1; i < 16; ++i)
+ {
+ test_insert(red_black_tree, values, -i);
+ }
+
+ test_erase(red_black_tree, values, -5);
+ test_clear(red_black_tree, values);
+ test_insert(red_black_tree, values, 0);
+ test_insert(red_black_tree, values, -8);
+ test_insert(red_black_tree, values, 8);
+ test_insert(red_black_tree, values, -16);
+ test_insert(red_black_tree, values, -4);
+ test_insert(red_black_tree, values, 4);
+ test_insert(red_black_tree, values, 16);
+ test_insert(red_black_tree, values, -18);
+ test_insert(red_black_tree, values, -12);
+ test_insert(red_black_tree, values, -6);
+ test_insert(red_black_tree, values, -2);
+ test_insert(red_black_tree, values, 2);
+ test_insert(red_black_tree, values, 6);
+ test_insert(red_black_tree, values, 12);
+ test_insert(red_black_tree, values, 18);
+ test_insert(red_black_tree, values, -19);
+ test_insert(red_black_tree, values, -17);
+ test_insert(red_black_tree, values, -14);
+ test_insert(red_black_tree, values, -10);
+ test_insert(red_black_tree, values, -7);
+ test_insert(red_black_tree, values, -5);
+ test_insert(red_black_tree, values, -3);
+ test_insert(red_black_tree, values, -1);
+ test_insert(red_black_tree, values, 1);
+ test_insert(red_black_tree, values, 3);
+ test_insert(red_black_tree, values, 5);
+ test_insert(red_black_tree, values, 7);
+ test_insert(red_black_tree, values, 10);
+ test_insert(red_black_tree, values, 14);
+ test_insert(red_black_tree, values, 17);
+ test_insert(red_black_tree, values, 19);
+ test_insert(red_black_tree, values, -15);
+ test_insert(red_black_tree, values, -13);
+ test_insert(red_black_tree, values, -11);
+ test_insert(red_black_tree, values, -9);
+ test_insert(red_black_tree, values, 9);
+ test_insert(red_black_tree, values, 11);
+ test_insert(red_black_tree, values, 13);
+ test_insert(red_black_tree, values, 15);
+ test_erase(red_black_tree, values, -19);
+ test_erase(red_black_tree, values, -17);
+ test_erase(red_black_tree, values, -7);
+ test_erase(red_black_tree, values, -5);
+ test_erase(red_black_tree, values, -3);
+ test_erase(red_black_tree, values, -1);
+ test_erase(red_black_tree, values, 1);
+ test_erase(red_black_tree, values, 3);
+ test_erase(red_black_tree, values, 5);
+ test_erase(red_black_tree, values, 7);
+ test_erase(red_black_tree, values, 17);
+ test_erase(red_black_tree, values, 19);
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, 0);
+ test_erase(red_black_copy, values, 2);
+ test_value_insert(values, 2);
+ test_value_insert(values, 0);
+ red_black_copy = red_black_tree;
+ test_tree_container(red_black_copy, values);
+ test_erase(red_black_copy, values, -2);
+ test_erase(red_black_copy, values, 0);
+}
+
+#endif // LIBS_TREE_NODE_TEST_RED_BLACK_TREE_HPP_INCLUDED
+

Added: sandbox/tree_node/libs/tree_node/test/sequence.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/test/sequence.hpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,38 @@
+// Copyright (C) 2013 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 LIBS_TREE_NODE_TEST_SEQUENCE_HPP_INCLUDED
+#define LIBS_TREE_NODE_TEST_SEQUENCE_HPP_INCLUDED
+
+#include <boost/cstdint.hpp>
+
+template <typename TreeSequence>
+void test_sequence(TreeSequence& tree_sequence, ValueSequence& values)
+{
+ BOOST_CHECK(tree_sequence.empty());
+ BOOST_CHECK(0 == tree_sequence.size());
+
+ for (boost::int32_t i = -5; -15 < i; --i)
+ {
+ test_push_back(tree_sequence, values, i);
+ }
+
+ for (boost::int32_t i = 5; i < 15; ++i)
+ {
+ test_push_front(tree_sequence, values, i);
+ }
+
+ test_pop_back(tree_sequence, values);
+ test_pop_front(tree_sequence, values);
+ typename TreeSequence::size_type index = 0;
+
+ for (boost::int32_t i = -4; i < 5; ++i)
+ {
+ test_insert(tree_sequence, values, index += 2, i);
+ }
+}
+
+#endif // LIBS_TREE_NODE_TEST_SEQUENCE_HPP_INCLUDED
+

Added: sandbox/tree_node/libs/tree_node/test/type_definitions.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/test/type_definitions.hpp 2013-03-07 12:16:26 EST (Thu, 07 Mar 2013)
@@ -0,0 +1,43 @@
+// Copyright (C) 2013 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 LIBS_TREE_NODE_TEST_TYPE_DEFINITIONS_HPP_INCLUDED
+#define LIBS_TREE_NODE_TEST_TYPE_DEFINITIONS_HPP_INCLUDED
+
+#include <deque>
+#include <set>
+#include <map>
+#include <boost/cstdint.hpp>
+#include <boost/typeof/boost/tree_node/with_count.hpp>
+#include <boost/typeof/boost/tree_node/with_height.hpp>
+#include <boost/typeof/boost/tree_node/with_red_black_flag.hpp>
+#include <boost/typeof/boost/tree_node/binary_node.hpp>
+
+//[test__container_types
+typedef std::deque<boost::int32_t>
+ ValueSequence;
+typedef std::set<boost::int32_t>
+ ValueSet;
+typedef std::map<boost::int32_t,boost::int32_t>
+ ValueMap;
+//]
+
+//[test__node_types
+typedef boost::tree_node::with_red_black_flag_gen<
+ boost::tree_node::with_count_base_gen<
+ boost::tree_node::binary_node_base_gen<>
+ >
+ >
+ RedBlackNodeGen;
+typedef boost::tree_node::with_height_gen<
+ boost::tree_node::with_count_base_gen<
+ boost::tree_node::binary_node_base_gen<>
+ >
+ >
+ AVLNodeGen;
+//]
+
+#endif // LIBS_TREE_NODE_TEST_TYPE_DEFINITIONS_HPP_INCLUDED
+

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk