Subject: [Boost-commit] svn:boost r81240 - in sandbox: container_gen/boost/container_gen container_gen/boost/graph container_gen/boost/graph/detail container_gen/libs/container_gen/doc/html container_gen/libs/container_gen/example container_gen/libs/container_gen/test tree_node/boost/tree_node tree_node/libs/tree_node/example
From: sponage_at_[hidden]
Date: 2012-11-08 00:18:16
Author: expaler
Date: 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
New Revision: 81240
URL: http://svn.boost.org/trac/boost/changeset/81240
Log:
Updated Boost.ContainerGen and Boost.TreeNode to work with Boost 1.52; temporarily removed Boost.ContainerGen documentation.
Added:
sandbox/container_gen/boost/container_gen/emplace_assoc_function_gen.hpp (contents, props changed)
sandbox/container_gen/boost/container_gen/emplace_function_gen.hpp (contents, props changed)
sandbox/container_gen/boost/graph/adjacency_list.hpp (contents, props changed)
sandbox/container_gen/boost/graph/detail/adjacency_list.hpp (contents, props changed)
sandbox/container_gen/libs/container_gen/example/output_char_tallies.cpp (contents, props changed)
sandbox/container_gen/libs/container_gen/test/emplace_function_gen.cpp (contents, props changed)
sandbox/tree_node/boost/tree_node/nary_node.hpp (contents, props changed)
sandbox/tree_node/libs/tree_node/example/nary_node.cpp (contents, props changed)
Removed:
sandbox/container_gen/libs/container_gen/doc/html/
Added: sandbox/container_gen/boost/container_gen/emplace_assoc_function_gen.hpp
==============================================================================
--- (empty file)
+++ sandbox/container_gen/boost/container_gen/emplace_assoc_function_gen.hpp 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
@@ -0,0 +1,832 @@
+//=======================================================================
+// Copyright (C) 2012 Cromwell D. Enage
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#ifndef BOOST_CONTAINER_GEN_EMPLACE_ASSOC_FUNCTION_GEN_HPP_INCLUDED
+#define BOOST_CONTAINER_GEN_EMPLACE_ASSOC_FUNCTION_GEN_HPP_INCLUDED
+
+#include <utility>
+#include <boost/config.hpp>
+#include <boost/tr1/type_traits.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/aux_/lambda_support.hpp>
+#include <boost/container/detail/workaround.hpp>
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/preprocessor/cat.hpp>
+#include <boost/preprocessor/arithmetic/inc.hpp>
+#include <boost/preprocessor/arithmetic/dec.hpp>
+#include <boost/preprocessor/repetition/enum.hpp>
+#include <boost/preprocessor/repetition/enum_params.hpp>
+#include <boost/preprocessor/repetition/enum_trailing.hpp>
+#include <boost/preprocessor/repetition/enum_trailing_params.hpp>
+#include <boost/preprocessor/repetition/repeat.hpp>
+#include <boost/preprocessor/control/expr_if.hpp>
+#include <boost/container/detail/preprocessor.hpp>
+#endif
+
+namespace boost { namespace detail {
+
+ template <typename F, typename C>
+ class emplace_assoc_function_proxy
+ {
+ F const _function;
+ C& _container;
+
+ public:
+ explicit emplace_assoc_function_proxy(C& c);
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename ...Args>
+ inline emplace_assoc_function_proxy&
+ operator()(typename C::key_type const& key, Args&& ...args)
+ {
+ this->_function(
+ this->_container
+ , key
+ , ::boost::forward<Args>(args)...
+ );
+ return *this;
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ inline emplace_assoc_function_proxy& \
+ operator()( \
+ typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) \
+ { \
+ this->_function( \
+ this->_container \
+ , key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ); \
+ return *this; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename F, typename C>
+ emplace_assoc_function_proxy<F,C>::emplace_assoc_function_proxy(C& c)
+ : _function(), _container(c)
+ {
+ }
+
+ struct uac_emplace_associative_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<uac_emplace_associative_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(
+ C& _container
+ , typename C::key_type const& key
+ , Args&& ...args
+ ) const
+ {
+ return _container.emplace(
+ key
+ , ::boost::move(
+ typename C::mapped_type(::boost::forward<Args>(args)...)
+ )
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return _container.emplace( \
+ key \
+ , ::boost::move( \
+ typename C::mapped_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_PP_DEC(BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<uac_emplace_associative_function,C>
+ uac_emplace_associative_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<
+ uac_emplace_associative_function
+ , C
+ >(_container);
+ }
+
+ struct uac_emplace_emu_associative_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<uac_emplace_emu_associative_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(
+ C& _container
+ , typename C::key_type const& key
+ , Args&& ...args
+ ) const
+ {
+ return _container.insert(
+ typename C::value_type(
+ key
+ , typename C::mapped_type(::boost::forward<Args>(args)...)
+ )
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return _container.insert( \
+ typename C::value_type( \
+ key \
+ , typename C::mapped_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<uac_emplace_emu_associative_function,C>
+ uac_emplace_emu_associative_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<
+ uac_emplace_emu_associative_function
+ , C
+ >(_container);
+ }
+
+ struct mac_emplace_associative_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<mac_emplace_associative_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(
+ C& _container
+ , typename C::key_type const& key
+ , Args&& ...args
+ ) const
+ {
+ return ::std::make_pair(
+ _container.emplace(
+ key
+ , ::boost::move(
+ typename C::mapped_type(
+ ::boost::forward<Args>(args)...
+ )
+ )
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return ::std::make_pair( \
+ _container.emplace( \
+ key \
+ , ::boost::move( \
+ typename C::mapped_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_PP_DEC(BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS)
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<mac_emplace_associative_function,C>
+ mac_emplace_associative_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<
+ mac_emplace_associative_function
+ , C
+ >(_container);
+ }
+
+ struct mac_emplace_emu_associative_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<mac_emplace_emu_associative_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(
+ C& _container
+ , typename C::key_type const& key
+ , Args&& ...args
+ ) const
+ {
+ return ::std::make_pair(
+ _container.insert(
+ typename C::value_type(
+ key
+ , typename C::mapped_type(
+ ::boost::forward<Args>(args)...
+ )
+ )
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return ::std::make_pair( \
+ _container.insert( \
+ typename C::value_type( \
+ key \
+ , typename C::mapped_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<mac_emplace_emu_associative_function,C>
+ mac_emplace_emu_associative_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<
+ mac_emplace_emu_associative_function
+ , C
+ >(_container);
+ }
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+
+ struct huac_emplace_associative_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<huac_emplace_associative_function,C>
+ operator[](C& _container) const;
+
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return _container.emplace( \
+ ::boost::unordered::piecewise_construct \
+ , ::boost::make_tuple(key) \
+ , ::boost::make_tuple( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<huac_emplace_associative_function,C>
+ huac_emplace_associative_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<
+ huac_emplace_associative_function
+ , C
+ >(_container);
+ }
+
+ struct hmac_emplace_associative_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<hmac_emplace_associative_function,C>
+ operator[](C& _container) const;
+
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return ::std::make_pair( \
+ _container.emplace( \
+ ::boost::unordered::piecewise_construct \
+ , ::boost::make_tuple(key) \
+ , ::boost::make_tuple( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<hmac_emplace_associative_function,C>
+ hmac_emplace_associative_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<
+ hmac_emplace_associative_function
+ , C
+ >(_container);
+ }
+
+#if defined BOOST_HAS_TR1_UNORDERED_MAP
+
+// Handle different native TR1 emplacement implementations.
+#if defined BOOST_MSVC
+
+ struct tr1_huac_emplace_associative_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<tr1_huac_emplace_associative_function,C>
+ operator[](C& _container) const;
+
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return _container.emplace( \
+ ::boost::move( \
+ typename C::value_type( \
+ key \
+ , typename C::mapped_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<tr1_huac_emplace_associative_function,C>
+ tr1_huac_emplace_associative_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<
+ tr1_huac_emplace_associative_function
+ , C
+ >(_container);
+ }
+
+ typedef tr1_huac_emplace_associative_function
+ tr1_hmac_emplace_associative_function;
+#else // TR1 == Boost wrt unordered_[multi]map::emplace
+#define BOOST_CONTAINER_GEN_EMPLACE_ASSOC_FUNCTION_GEN_USE_NO_NATIVE_TR1
+#endif
+
+#else // !defined BOOST_HAS_TR1_UNORDERED_MAP
+#define BOOST_CONTAINER_GEN_EMPLACE_ASSOC_FUNCTION_GEN_USE_NO_NATIVE_TR1
+#endif // BOOST_HAS_TR1_UNORDERED_MAP
+
+#if defined BOOST_CONTAINER_GEN_EMPLACE_ASSOC_FUNCTION_GEN_USE_NO_NATIVE_TR1
+ typedef huac_emplace_associative_function
+ tr1_huac_emplace_associative_function;
+ typedef hmac_emplace_associative_function
+ tr1_hmac_emplace_associative_function;
+#undef BOOST_CONTAINER_GEN_EMPLACE_ASSOC_FUNCTION_GEN_USE_NO_NATIVE_TR1
+#endif // BOOST_CONTAINER_GEN_EMPLACE_ASSOC_FUNCTION_GEN_USE_NO_NATIVE_TR1
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ struct ua_ptr_emplace_assoc_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<ua_ptr_emplace_assoc_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(
+ C& _container
+ , typename C::key_type const& key
+ , Args&& ...args
+ ) const
+ {
+ typedef typename ::std::tr1::remove_pointer<
+ typename C::mapped_type
+ >::type
+ _data_type;
+
+ typename C::key_type k(key);
+ return _container.insert(
+ k
+ , new _data_type(::boost::forward<Args>(args)...)
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ typedef typename ::std::tr1::remove_pointer< \
+ typename C::mapped_type \
+ >::type \
+ _data_type; \
+ typename C::key_type k(key); \
+ return _container.insert( \
+ k \
+ , new _data_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<ua_ptr_emplace_assoc_function,C>
+ ua_ptr_emplace_assoc_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<ua_ptr_emplace_assoc_function,C>(
+ _container
+ );
+ }
+
+ struct ma_ptr_emplace_assoc_function
+ {
+ template <typename C>
+ emplace_assoc_function_proxy<ma_ptr_emplace_assoc_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(
+ C& _container
+ , typename C::key_type const& key
+ , Args&& ...args
+ ) const
+ {
+ typedef typename ::std::tr1::remove_pointer<
+ typename C::mapped_type
+ >::type
+ _data_type;
+
+ typename C::key_type k(key);
+ return ::std::make_pair(
+ _container.insert(
+ k
+ , new _data_type(::boost::forward<Args>(args)...)
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ , typename C::key_type const& key \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ typedef typename ::std::tr1::remove_pointer< \
+ typename C::mapped_type \
+ >::type \
+ _data_type; \
+ typename C::key_type k(key); \
+ return ::std::make_pair( \
+ _container.insert( \
+ k \
+ , new _data_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPL_ASSOC_FUNC_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_assoc_function_proxy<ma_ptr_emplace_assoc_function,C>
+ ma_ptr_emplace_assoc_function::operator[](C& _container) const
+ {
+ return emplace_assoc_function_proxy<ma_ptr_emplace_assoc_function,C>(
+ _container
+ );
+ }
+}} // namespace boost::detail
+
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/container_gen/has_emplace_mfunc_selector.hpp>
+#include <boost/container_gen/is_associative_selector.hpp>
+#include <boost/container_gen/is_unique_assoc_selector.hpp>
+#include <boost/container_gen/is_multiple_assoc_selector.hpp>
+#include <boost/container_gen/is_ptr_selector.hpp>
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/container_gen/is_hashed_assoc_selector.hpp>
+#include <boost/container_gen/is_tr1_selector.hpp>
+#endif
+
+//[reference__emplace_associative_function_gen
+namespace boost {
+
+ template <typename Selector>
+ struct emplace_associative_function_gen
+ //<-
+ : ::boost::mpl::eval_if<
+ is_ptr_selector<Selector>
+ , ::boost::mpl::if_<
+ is_multiple_associative_selector<Selector>
+ , detail::ma_ptr_emplace_assoc_function
+ , detail::ua_ptr_emplace_assoc_function
+ >
+ , ::boost::mpl::eval_if<
+ has_emplace_member_function_selector<Selector>
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+ , ::boost::mpl::eval_if<
+ is_hashed_associative_selector<Selector>
+ , ::boost::mpl::eval_if<
+ is_tr1_selector<Selector>
+ , ::boost::mpl::if_<
+ is_unique_associative_selector<Selector>
+ , detail::tr1_huac_emplace_associative_function
+ , detail::tr1_hmac_emplace_associative_function
+ >
+ , ::boost::mpl::if_<
+ is_unique_associative_selector<Selector>
+ , detail::huac_emplace_associative_function
+ , detail::hmac_emplace_associative_function
+ >
+ >
+#endif
+ , ::boost::mpl::if_<
+ is_multiple_associative_selector<Selector>
+ , detail::mac_emplace_associative_function
+ , detail::uac_emplace_associative_function
+ >
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+ >
+#endif
+ , ::boost::mpl::if_<
+ is_multiple_associative_selector<Selector>
+ , detail::mac_emplace_emu_associative_function
+ , detail::uac_emplace_emu_associative_function
+ >
+ >
+ >
+ //->
+ {
+ // typedef ... type;
+ //<-
+ BOOST_MPL_AUX_LAMBDA_SUPPORT(
+ 1
+ , emplace_associative_function_gen
+ , (Selector)
+ )
+ //->
+ };
+} // namespace boost
+//]
+
+#endif // BOOST_CONTAINER_GEN_EMPLACE_ASSOC_FUNCTION_GEN_HPP_INCLUDED
+
Added: sandbox/container_gen/boost/container_gen/emplace_function_gen.hpp
==============================================================================
--- (empty file)
+++ sandbox/container_gen/boost/container_gen/emplace_function_gen.hpp 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
@@ -0,0 +1,850 @@
+//=======================================================================
+// Copyright (C) 2012 Cromwell D. Enage
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+
+#ifndef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_HPP_INCLUDED
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_HPP_INCLUDED
+
+#include <utility>
+#include <boost/config.hpp>
+#include <boost/tr1/type_traits.hpp>
+#include <boost/mpl/identity.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/mpl/aux_/lambda_support.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/repetition/enum_trailing_params.hpp>
+#include <boost/preprocessor/repetition/repeat.hpp>
+#include <boost/preprocessor/control/expr_if.hpp>
+#include <boost/container/detail/preprocessor.hpp>
+
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_SEQUENCE_MACRO(z, n, itr) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) const \
+ { \
+ return ::std::make_pair( \
+ _container.emplace( \
+ itr \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_SEQ_EMU_MACRO(z, n, itr) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) const \
+ { \
+ return ::std::make_pair( \
+ _container.insert( \
+ itr \
+ , typename C::value_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+namespace boost { namespace detail {
+
+ template <typename F, typename C>
+ class emplace_function_proxy
+ {
+ F const _function;
+ C& _container;
+
+ public:
+ explicit emplace_function_proxy(C& c);
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename ...Args>
+ inline emplace_function_proxy& operator()(Args&& ...args)
+ {
+ this->_function(this->_container, ::boost::forward<Args>(args)...);
+ return *this;
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO(z, n, poop) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ inline emplace_function_proxy& \
+ operator()( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) \
+ { \
+ this->_function( \
+ this->_container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ); \
+ return *this; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename F, typename C>
+ emplace_function_proxy<F,C>::emplace_function_proxy(C& c)
+ : _function(), _container(c)
+ {
+ }
+
+ struct fis_emplace_function
+ {
+ template <typename C>
+ emplace_function_proxy<fis_emplace_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ return ::std::make_pair(
+ _container.emplace(
+ _container.begin()
+ , ::boost::forward<Args>(args)...
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_SEQUENCE_MACRO
+ , _container.begin()
+ )
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<fis_emplace_function,C>
+ fis_emplace_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<fis_emplace_function,C>(_container);
+ }
+
+ struct bis_emplace_function
+ {
+ template <typename C>
+ emplace_function_proxy<bis_emplace_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ return ::std::make_pair(
+ _container.emplace(
+ _container.end()
+ , ::boost::forward<Args>(args)...
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_SEQUENCE_MACRO
+ , _container.end()
+ )
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<bis_emplace_function,C>
+ bis_emplace_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<bis_emplace_function,C>(_container);
+ }
+
+ struct fis_emplace_emu_function
+ {
+ template <typename C>
+ emplace_function_proxy<fis_emplace_emu_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ return ::std::make_pair(
+ _container.insert(
+ _container.begin()
+ , typename C::value_type(
+ ::boost::forward<Args>(args)...
+ )
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_SEQ_EMU_MACRO
+ , _container.begin()
+ )
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<fis_emplace_emu_function,C>
+ fis_emplace_emu_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<fis_emplace_emu_function,C>(_container);
+ }
+
+ struct bis_emplace_emu_function
+ {
+ template <typename C>
+ emplace_function_proxy<bis_emplace_emu_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ return ::std::make_pair(
+ _container.insert(
+ _container.end()
+ , typename C::value_type(
+ ::boost::forward<Args>(args)...
+ )
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_SEQ_EMU_MACRO
+ , _container.end()
+ )
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<bis_emplace_emu_function,C>
+ bis_emplace_emu_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<bis_emplace_emu_function,C>(_container);
+ }
+
+ struct uac_emplace_function
+ {
+ template <typename C>
+ emplace_function_proxy<uac_emplace_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ return _container.emplace(::boost::forward<Args>(args)...);
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return _container.emplace( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<uac_emplace_function,C>
+ uac_emplace_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<uac_emplace_function,C>(_container);
+ }
+
+ struct uac_emplace_emu_function
+ {
+ template <typename C>
+ emplace_function_proxy<uac_emplace_emu_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ return _container.insert(
+ typename C::value_type(::boost::forward<Args>(args)...)
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return _container.insert( \
+ typename C::value_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<uac_emplace_emu_function,C>
+ uac_emplace_emu_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<uac_emplace_emu_function,C>(_container);
+ }
+
+ struct mac_emplace_function
+ {
+ template <typename C>
+ emplace_function_proxy<mac_emplace_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ return ::std::make_pair(
+ _container.emplace(::boost::forward<Args>(args)...)
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return ::std::make_pair( \
+ _container.emplace( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<mac_emplace_function,C>
+ mac_emplace_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<mac_emplace_function,C>(_container);
+ }
+
+ struct mac_emplace_emu_function
+ {
+ template <typename C>
+ emplace_function_proxy<mac_emplace_emu_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ return ::std::make_pair(
+ _container.insert(
+ typename C::value_type(::boost::forward<Args>(args)...)
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return ::std::make_pair( \
+ _container.insert( \
+ typename C::value_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<mac_emplace_emu_function,C>
+ mac_emplace_emu_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<mac_emplace_emu_function,C>(_container);
+ }
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#if defined BOOST_HAS_TR1_UNORDERED_SET
+
+// Handle different native TR1 emplacement implementations.
+#if defined BOOST_MSVC
+
+ struct tr1_huac_emplace_function
+ {
+ template <typename C>
+ emplace_function_proxy<tr1_huac_emplace_function,C>
+ operator[](C& _container) const;
+
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ return _container.emplace( \
+ ::boost::move( \
+ typename C::value_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ };
+
+ template <typename C>
+ emplace_function_proxy<tr1_huac_emplace_function,C>
+ tr1_huac_emplace_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<tr1_huac_emplace_function,C>(_container);
+ }
+
+ typedef tr1_huac_emplace_function tr1_hmac_emplace_function;
+#else // TR1 == Boost wrt unordered_[multi]set::emplace
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_USE_NO_NATIVE_TR1
+#endif
+
+#else // !defined BOOST_HAS_TR1_UNORDERED_SET
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_USE_NO_NATIVE_TR1
+#endif // BOOST_HAS_TR1_UNORDERED_SET
+
+#if defined BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_USE_NO_NATIVE_TR1
+ typedef uac_emplace_function tr1_huac_emplace_function;
+ typedef mac_emplace_function tr1_hmac_emplace_function;
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_USE_NO_NATIVE_TR1
+#endif // BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_USE_NO_NATIVE_TR1
+#endif // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+
+ struct ptr_sequence_emplace_function
+ {
+ template <typename C>
+ emplace_function_proxy<ptr_sequence_emplace_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ typedef typename ::std::tr1::remove_pointer<
+ typename C::value_type
+ >::type
+ _data_type;
+
+ return ::std::make_pair(
+ _container.insert(
+ _container.end()
+ , new _data_type(::boost::forward<Args>(args)...)
+ )
+ , true
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ typedef typename ::std::tr1::remove_pointer< \
+ typename C::value_type \
+ >::type \
+ _data_type; \
+ return ::std::make_pair( \
+ _container.insert( \
+ _container.end() \
+ , new _data_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ) \
+ , true \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<ptr_sequence_emplace_function,C>
+ ptr_sequence_emplace_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<ptr_sequence_emplace_function,C>(
+ _container
+ );
+ }
+
+ struct ua_ptr_container_emplace_function
+ {
+ template <typename C>
+ emplace_function_proxy<ua_ptr_container_emplace_function,C>
+ operator[](C& _container) const;
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename C, typename ...Args>
+ inline ::std::pair<typename C::iterator,bool>
+ operator()(C& _container, Args&& ...args) const
+ {
+ typedef typename ::std::tr1::remove_pointer<
+ typename C::value_type
+ >::type
+ _data_type;
+
+ return _container.insert(
+ new _data_type(::boost::forward<Args>(args)...)
+ );
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO(z, n, poop) \
+ template < \
+ typename C \
+ BOOST_PP_ENUM_TRAILING_PARAMS_Z(z, n, typename P) \
+ > \
+ inline ::std::pair<typename C::iterator,bool> \
+ operator()( \
+ C& _container \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , poop \
+ ) \
+ ) const \
+ { \
+ typedef typename ::std::tr1::remove_pointer< \
+ typename C::value_type \
+ >::type \
+ _data_type; \
+ return _container.insert( \
+ new _data_type( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , poop \
+ ) \
+ ) \
+ ); \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+ , _
+ )
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_CALL_OP_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+ };
+
+ template <typename C>
+ emplace_function_proxy<ua_ptr_container_emplace_function,C>
+ ua_ptr_container_emplace_function::operator[](C& _container) const
+ {
+ return emplace_function_proxy<ua_ptr_container_emplace_function,C>(
+ _container
+ );
+ }
+}} // namespace boost::detail
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_SEQ_EMU_MACRO
+#undef BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_SEQUENCE_MACRO
+#endif
+
+#include <boost/mpl/identity.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/eval_if.hpp>
+#include <boost/container_gen/has_emplace_mfunc_selector.hpp>
+#include <boost/container_gen/is_associative_selector.hpp>
+#include <boost/container_gen/is_unique_assoc_selector.hpp>
+#include <boost/container_gen/is_multiple_assoc_selector.hpp>
+#include <boost/container_gen/is_ptr_selector.hpp>
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/container_gen/is_tr1_selector.hpp>
+#endif
+
+//[reference__emplace_function_gen
+namespace boost {
+
+ template <typename Selector>
+ struct emplace_function_gen
+ //<-
+ : ::boost::mpl::eval_if<
+ is_ptr_selector<Selector>
+ , ::boost::mpl::if_<
+ is_unique_associative_selector<Selector>
+ , detail::ua_ptr_container_emplace_function
+ , detail::ptr_sequence_emplace_function
+ >
+ , ::boost::mpl::eval_if<
+ has_emplace_member_function_selector<Selector>
+ , ::boost::mpl::eval_if<
+ is_associative_selector<Selector>
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+ , ::boost::mpl::eval_if<
+ is_tr1_selector<Selector>
+ , ::boost::mpl::if_<
+ is_multiple_associative_selector<Selector>
+ , detail::tr1_hmac_emplace_function
+ , detail::tr1_huac_emplace_function
+ >
+#endif
+ , ::boost::mpl::if_<
+ is_multiple_associative_selector<Selector>
+ , detail::mac_emplace_function
+ , detail::uac_emplace_function
+ >
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+ >
+#endif
+ , ::boost::mpl::identity<detail::bis_emplace_function>
+ >
+ , ::boost::mpl::eval_if<
+ is_associative_selector<Selector>
+ , ::boost::mpl::if_<
+ is_unique_associative_selector<Selector>
+ , detail::uac_emplace_emu_function
+ , detail::mac_emplace_emu_function
+ >
+ , ::boost::mpl::identity<detail::bis_emplace_emu_function>
+ >
+ >
+ >
+ //->
+ {
+ // typedef ... type;
+ //<-
+ BOOST_MPL_AUX_LAMBDA_SUPPORT(1, emplace_function_gen, (Selector))
+ //->
+ };
+} // namespace boost
+//]
+
+#include <boost/container_gen/selectors.hpp>
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+namespace boost {
+
+ template <typename AllocatorSelector>
+ struct emplace_function_gen<slist_selector<AllocatorSelector> >
+ {
+ typedef detail::fis_emplace_function type;
+ };
+} // namespace boost
+
+#elif !defined BOOST_NO_SLIST
+
+namespace boost {
+
+ template <>
+ struct emplace_function_gen<slist_selector_base>
+ {
+ typedef detail::fis_emplace_emu_function type;
+ };
+} // namespace boost
+
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION, BOOST_NO_SLIST
+
+#endif // BOOST_CONTAINER_GEN_EMPLACE_FUNCTION_GEN_HPP_INCLUDED
+
Added: sandbox/container_gen/boost/graph/adjacency_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/container_gen/boost/graph/adjacency_list.hpp 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
@@ -0,0 +1,312 @@
+//=======================================================================
+// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
+// Copyright 2010 Thomas Claveirole
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
+//
+// 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_GRAPH_ADJACENCY_LIST_HPP
+#define BOOST_GRAPH_ADJACENCY_LIST_HPP
+
+
+#include <boost/config.hpp>
+#include <boost/scoped_ptr.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/graph_mutability_traits.hpp>
+#include <boost/graph/graph_selectors.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/graph/detail/edge.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/detail/workaround.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/named_graph.hpp>
+#include <boost/container_gen/is_random_access_selector.hpp>
+#include <boost/container_gen/is_associative_selector.hpp>
+#include <boost/container_gen/is_unique_assoc_selector.hpp>
+#include <boost/container_gen/selectors.hpp>
+#include <boost/container_gen/container_gen.hpp>
+
+namespace boost {
+
+ template <typename StorageSelector>
+ struct parallel_edge_traits
+ {
+ typedef typename mpl::if_<is_unique_associative_selector<StorageSelector>,
+ disallow_parallel_edge_tag,allow_parallel_edge_tag
+ >::type type;
+ };
+
+ //===========================================================================
+ // The adjacency_list_traits class, which provides a way to access
+ // some of the associated types of an adjacency_list type without
+ // having to first create the adjacency_list type. This is useful
+ // when trying to create interior vertex or edge properties who's
+ // value type is a vertex or edge descriptor.
+
+ template <class OutEdgeListS = vecS,
+ class VertexListS = vecS,
+ class DirectedS = directedS,
+ class EdgeListS = listS>
+ struct adjacency_list_traits
+ {
+ typedef typename mpl::and_<
+ is_random_access_selector<VertexListS>
+ , mpl::not_<is_associative_selector<VertexListS> >
+ >::type is_rand_access;
+ typedef typename DirectedS::is_bidir_t is_bidir;
+ typedef typename DirectedS::is_directed_t is_directed;
+
+ typedef typename mpl::if_<is_bidir,
+ bidirectional_tag,
+ typename mpl::if_<is_directed,
+ directed_tag, undirected_tag
+ >::type
+ >::type directed_category;
+
+ typedef typename parallel_edge_traits<OutEdgeListS>::type
+ edge_parallel_category;
+
+ typedef std::size_t vertices_size_type;
+ typedef void* vertex_ptr;
+ typedef typename mpl::if_<is_rand_access,
+ vertices_size_type, vertex_ptr>::type vertex_descriptor;
+ typedef detail::edge_desc_impl<directed_category, vertex_descriptor>
+ edge_descriptor;
+
+ private:
+ // Logic to figure out the edges_size_type
+ struct dummy {};
+ typedef typename container_gen<EdgeListS, dummy>::type EdgeContainer;
+ typedef typename DirectedS::is_bidir_t BidirectionalT;
+ typedef typename DirectedS::is_directed_t DirectedT;
+ typedef typename mpl::and_<DirectedT,
+ typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
+ public:
+ typedef typename mpl::if_<on_edge_storage,
+ std::size_t, typename EdgeContainer::size_type
+ >::type edges_size_type;
+
+ };
+
+} // namespace boost
+
+#include <boost/graph/detail/adjacency_list.hpp>
+
+namespace boost {
+
+ //===========================================================================
+ // The adjacency_list class.
+ //
+
+ template <class OutEdgeListS = vecS, // a Sequence or an AssociativeContainer
+ class VertexListS = vecS, // a Sequence or a RandomAccessContainer
+ class DirectedS = directedS,
+ class VertexProperty = no_property,
+ class EdgeProperty = no_property,
+ class GraphProperty = no_property,
+ class EdgeListS = listS>
+ class adjacency_list
+ : public detail::adj_list_gen<
+ adjacency_list<OutEdgeListS,VertexListS,DirectedS,
+ VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
+ VertexListS, OutEdgeListS, DirectedS,
+ VertexProperty, EdgeProperty,
+ GraphProperty, EdgeListS>::type,
+ // Support for named vertices
+ public graph::maybe_named_graph<
+ adjacency_list<OutEdgeListS,VertexListS,DirectedS,
+ VertexProperty,EdgeProperty,GraphProperty,EdgeListS>,
+ typename adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS,
+ EdgeListS>::vertex_descriptor,
+ VertexProperty>
+ {
+ public:
+ typedef GraphProperty graph_property_type;
+ typedef typename lookup_one_property<GraphProperty, graph_bundle_t>::type graph_bundled;
+
+ typedef VertexProperty vertex_property_type;
+ typedef typename lookup_one_property<VertexProperty, vertex_bundle_t>::type vertex_bundled;
+
+ typedef EdgeProperty edge_property_type;
+ typedef typename lookup_one_property<EdgeProperty, edge_bundle_t>::type edge_bundled;
+
+ private:
+ typedef adjacency_list self;
+ typedef typename detail::adj_list_gen<
+ self, VertexListS, OutEdgeListS, DirectedS,
+ vertex_property_type, edge_property_type, GraphProperty, EdgeListS
+ >::type Base;
+
+ public:
+ typedef typename Base::stored_vertex stored_vertex;
+ typedef typename Base::vertices_size_type vertices_size_type;
+ typedef typename Base::edges_size_type edges_size_type;
+ typedef typename Base::degree_size_type degree_size_type;
+ typedef typename Base::vertex_descriptor vertex_descriptor;
+ typedef typename Base::edge_descriptor edge_descriptor;
+ typedef OutEdgeListS out_edge_list_selector;
+ typedef VertexListS vertex_list_selector;
+ typedef DirectedS directed_selector;
+ typedef EdgeListS edge_list_selector;
+
+
+ adjacency_list(const GraphProperty& p = GraphProperty())
+ : m_property(new graph_property_type(p))
+ { }
+
+ adjacency_list(const adjacency_list& x)
+ : Base(x), m_property(new graph_property_type(*x.m_property))
+ { }
+
+ adjacency_list& operator=(const adjacency_list& x) {
+ // TBD: probably should give the strong guarantee
+ if (&x != this) {
+ Base::operator=(x);
+
+ // Copy/swap the ptr since we can't just assign it...
+ property_ptr p(new graph_property_type(*x.m_property));
+ m_property.swap(p);
+ }
+ return *this;
+ }
+
+ // Required by Mutable Graph
+ adjacency_list(vertices_size_type num_vertices,
+ const GraphProperty& p = GraphProperty())
+ : Base(num_vertices), m_property(new graph_property_type(p))
+ { }
+
+#if !defined(BOOST_MSVC) || BOOST_MSVC >= 1300
+ // Required by Iterator Constructible Graph
+ template <class EdgeIterator>
+ adjacency_list(EdgeIterator first, EdgeIterator last,
+ vertices_size_type n,
+ edges_size_type = 0,
+ const GraphProperty& p = GraphProperty())
+ : Base(n, first, last), m_property(new graph_property_type(p))
+ { }
+
+ template <class EdgeIterator, class EdgePropertyIterator>
+ adjacency_list(EdgeIterator first, EdgeIterator last,
+ EdgePropertyIterator ep_iter,
+ vertices_size_type n,
+ edges_size_type = 0,
+ const GraphProperty& p = GraphProperty())
+ : Base(n, first, last, ep_iter), m_property(new graph_property_type(p))
+ { }
+#endif
+
+ void swap(adjacency_list& x) {
+ // Is there a more efficient way to do this?
+ adjacency_list tmp(x);
+ x = *this;
+ *this = tmp;
+ }
+
+ void clear()
+ {
+ this->clearing_graph();
+ Base::clear();
+ }
+
+#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+ // Directly access a vertex or edge bundle
+ vertex_bundled& operator[](vertex_descriptor v)
+ { return get(vertex_bundle, *this)[v]; }
+
+ const vertex_bundled& operator[](vertex_descriptor v) const
+ { return get(vertex_bundle, *this)[v]; }
+
+ edge_bundled& operator[](edge_descriptor e)
+ { return get(edge_bundle, *this)[e]; }
+
+ const edge_bundled& operator[](edge_descriptor e) const
+ { return get(edge_bundle, *this)[e]; }
+
+ graph_bundled& operator[](graph_bundle_t)
+ { return get_property(*this); }
+
+ graph_bundled const& operator[](graph_bundle_t) const
+ { return get_property(*this); }
+#endif
+
+ // protected: (would be protected if friends were more portable)
+ typedef scoped_ptr<graph_property_type> property_ptr;
+ property_ptr m_property;
+ };
+
+#define ADJLIST_PARAMS \
+ typename OEL, typename VL, typename D, typename VP, typename EP, \
+ typename GP, typename EL
+#define ADJLIST adjacency_list<OEL,VL,D,VP,EP,GP,EL>
+
+ template<ADJLIST_PARAMS, typename Tag, typename Value>
+ inline void set_property(ADJLIST& g, Tag tag, Value const& value) {
+ get_property_value(*g.m_property, tag) = value;
+ }
+
+ template<ADJLIST_PARAMS, typename Tag>
+ inline typename graph_property<ADJLIST, Tag>::type&
+ get_property(ADJLIST& g, Tag tag) {
+ return get_property_value(*g.m_property, tag);
+ }
+
+ template<ADJLIST_PARAMS, typename Tag>
+ inline typename graph_property<ADJLIST, Tag>::type const&
+ get_property(ADJLIST const& g, Tag tag) {
+ return get_property_value(*g.m_property, tag);
+ }
+
+ // dwa 09/25/00 - needed to be more explicit so reverse_graph would work.
+ template <class Directed, class Vertex,
+ class OutEdgeListS,
+ class VertexListS,
+ class DirectedS,
+ class VertexProperty,
+ class EdgeProperty,
+ class GraphProperty, class EdgeListS>
+ inline Vertex
+ source(const detail::edge_base<Directed,Vertex>& e,
+ const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
+ VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
+ {
+ return e.m_source;
+ }
+
+ template <class Directed, class Vertex, class OutEdgeListS,
+ class VertexListS, class DirectedS, class VertexProperty,
+ class EdgeProperty, class GraphProperty, class EdgeListS>
+ inline Vertex
+ target(const detail::edge_base<Directed,Vertex>& e,
+ const adjacency_list<OutEdgeListS, VertexListS, DirectedS,
+ VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&)
+ {
+ return e.m_target;
+ }
+
+// Mutability Traits
+template <ADJLIST_PARAMS>
+struct graph_mutability_traits<ADJLIST> {
+ typedef mutable_property_graph_tag category;
+};
+
+// Can't remove vertices from adjacency lists with VL==vecS
+template <typename OEL, typename D, typename VP, typename EP, typename GP, typename EL>
+struct graph_mutability_traits< adjacency_list<OEL,vecS,D,VP,EP,GP,EL> > {
+ typedef add_only_property_graph_tag category;
+};
+#undef ADJLIST_PARAMS
+#undef ADJLIST
+
+
+} // namespace boost
+
+
+#endif // BOOST_GRAPH_ADJACENCY_LIST_HPP
Added: sandbox/container_gen/boost/graph/detail/adjacency_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/container_gen/boost/graph/detail/adjacency_list.hpp 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
@@ -0,0 +1,2794 @@
+// -*- c++ -*-
+//=======================================================================
+// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
+// Copyright 2010 Thomas Claveirole
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek, Thomas Claveirole
+//
+// 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_GRAPH_DETAIL_ADJACENCY_LIST_HPP
+#define BOOST_GRAPH_DETAIL_ADJACENCY_LIST_HPP
+
+#include <map> // for vertex_map in copy_impl
+#include <boost/config.hpp>
+#include <boost/detail/workaround.hpp>
+#include <boost/operators.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/range/irange.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <memory>
+#include <algorithm>
+#include <boost/limits.hpp>
+
+#include <boost/iterator/iterator_adaptor.hpp>
+
+#include <boost/container_gen/is_random_access_selector.hpp>
+#include <boost/container_gen/is_ptr_selector.hpp>
+
+#include <boost/mpl/if.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/mpl/and.hpp>
+#include <boost/graph/graph_concepts.hpp>
+#include <boost/pending/container_traits.hpp>
+#include <boost/graph/detail/adj_list_edge_iterator.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/pending/property.hpp>
+#include <boost/graph/adjacency_iterator.hpp>
+#include <boost/static_assert.hpp>
+#include <boost/assert.hpp>
+
+/*
+ Outline for this file:
+
+ out_edge_iterator and in_edge_iterator implementation
+ edge_iterator for undirected graph
+ stored edge types (these object live in the out-edge/in-edge lists)
+ directed edges helper class
+ directed graph helper class
+ undirected graph helper class
+ bidirectional graph helper class
+ bidirectional graph helper class (without edge properties)
+ bidirectional graph helper class (with edge properties)
+ adjacency_list helper class
+ adj_list_impl class
+ vec_adj_list_impl class
+ adj_list_gen class
+ vertex property map
+ edge property map
+
+
+ Note: it would be nice to merge some of the undirected and
+ bidirectional code... it is awful similar.
+ */
+
+
+namespace boost {
+
+ namespace detail {
+
+ template <typename DirectedS>
+ struct directed_category_traits {
+ typedef directed_tag directed_category;
+ };
+
+ template <>
+ struct directed_category_traits<directedS> {
+ typedef directed_tag directed_category;
+ };
+ template <>
+ struct directed_category_traits<undirectedS> {
+ typedef undirected_tag directed_category;
+ };
+ template <>
+ struct directed_category_traits<bidirectionalS> {
+ typedef bidirectional_tag directed_category;
+ };
+
+ template <class Vertex>
+ struct target_is {
+ target_is(const Vertex& v) : m_target(v) { }
+ template <class StoredEdge>
+ bool operator()(const StoredEdge& e) const {
+ return e.get_target() == m_target;
+ }
+ Vertex m_target;
+ };
+
+ // O(E/V)
+ template <class EdgeList, class vertex_descriptor>
+ void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
+ allow_parallel_edge_tag)
+ {
+ boost::graph_detail::erase_if(el, detail::target_is<vertex_descriptor>(v));
+ }
+ // O(log(E/V))
+ template <class EdgeList, class vertex_descriptor>
+ void erase_from_incidence_list(EdgeList& el, vertex_descriptor v,
+ disallow_parallel_edge_tag)
+ {
+ typedef typename EdgeList::value_type StoredEdge;
+ el.erase(StoredEdge(v));
+ }
+
+ //=========================================================================
+ // Out-Edge and In-Edge Iterator Implementation
+
+ template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
+ struct out_edge_iter
+ : iterator_adaptor<
+ out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
+ , BaseIter
+ , EdgeDescriptor
+ , use_default
+ , EdgeDescriptor
+ , Difference
+ >
+ {
+ typedef iterator_adaptor<
+ out_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
+ , BaseIter
+ , EdgeDescriptor
+ , use_default
+ , EdgeDescriptor
+ , Difference
+ > super_t;
+
+ inline out_edge_iter() { }
+ inline out_edge_iter(const BaseIter& i, const VertexDescriptor& src)
+ : super_t(i), m_src(src) { }
+
+ inline EdgeDescriptor
+ dereference() const
+ {
+ return EdgeDescriptor(m_src, (*this->base()).get_target(),
+ &(*this->base()).get_property());
+ }
+ VertexDescriptor m_src;
+ };
+
+ template <class BaseIter, class VertexDescriptor, class EdgeDescriptor, class Difference>
+ struct in_edge_iter
+ : iterator_adaptor<
+ in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
+ , BaseIter
+ , EdgeDescriptor
+ , use_default
+ , EdgeDescriptor
+ , Difference
+ >
+ {
+ typedef iterator_adaptor<
+ in_edge_iter<BaseIter, VertexDescriptor, EdgeDescriptor, Difference>
+ , BaseIter
+ , EdgeDescriptor
+ , use_default
+ , EdgeDescriptor
+ , Difference
+ > super_t;
+
+ inline in_edge_iter() { }
+ inline in_edge_iter(const BaseIter& i, const VertexDescriptor& src)
+ : super_t(i), m_src(src) { }
+
+ inline EdgeDescriptor
+ dereference() const
+ {
+ return EdgeDescriptor((*this->base()).get_target(), m_src,
+ &this->base()->get_property());
+ }
+ VertexDescriptor m_src;
+ };
+
+ //=========================================================================
+ // Undirected Edge Iterator Implementation
+
+ template <class EdgeIter, class EdgeDescriptor, class Difference>
+ struct undirected_edge_iter
+ : iterator_adaptor<
+ undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
+ , EdgeIter
+ , EdgeDescriptor
+ , use_default
+ , EdgeDescriptor
+ , Difference
+ >
+ {
+ typedef iterator_adaptor<
+ undirected_edge_iter<EdgeIter, EdgeDescriptor, Difference>
+ , EdgeIter
+ , EdgeDescriptor
+ , use_default
+ , EdgeDescriptor
+ , Difference
+ > super_t;
+
+ undirected_edge_iter() {}
+
+ explicit undirected_edge_iter(EdgeIter i)
+ : super_t(i) {}
+
+ inline EdgeDescriptor
+ dereference() const {
+ return EdgeDescriptor(
+ (*this->base()).m_source
+ , (*this->base()).m_target
+ , &this->base()->get_property());
+ }
+ };
+
+ //=========================================================================
+ // Edge Storage Types (stored in the out-edge/in-edge lists)
+
+ template <class Vertex>
+ class stored_edge
+ : public boost::equality_comparable1< stored_edge<Vertex>,
+ boost::less_than_comparable1< stored_edge<Vertex> > >
+ {
+ public:
+ typedef no_property property_type;
+ inline stored_edge() { }
+ inline stored_edge(Vertex target, const no_property& = no_property())
+ : m_target(target) { }
+ // Need to write this explicitly so stored_edge_property can
+ // invoke Base::operator= (at least, for SGI MIPSPro compiler)
+ inline stored_edge& operator=(const stored_edge& x) {
+ m_target = x.m_target;
+ return *this;
+ }
+ inline Vertex& get_target() const { return m_target; }
+ inline const no_property& get_property() const { return s_prop; }
+ inline bool operator==(const stored_edge& x) const
+ { return m_target == x.get_target(); }
+ inline bool operator<(const stored_edge& x) const
+ { return m_target < x.get_target(); }
+ //protected: need to add hash<> as a friend
+ static no_property s_prop;
+ // Sometimes target not used as key in the set, and in that case
+ // it is ok to change the target.
+ mutable Vertex m_target;
+ };
+ template <class Vertex>
+ no_property stored_edge<Vertex>::s_prop;
+
+ template <class Vertex, class Property>
+ class stored_edge_property : public stored_edge<Vertex> {
+ typedef stored_edge_property self;
+ typedef stored_edge<Vertex> Base;
+ public:
+ typedef Property property_type;
+ inline stored_edge_property() { }
+ inline stored_edge_property(Vertex target,
+ const Property& p = Property())
+ : stored_edge<Vertex>(target), m_property(new Property(p)) { }
+ stored_edge_property(const self& x)
+ : Base(x), m_property(const_cast<self&>(x).m_property) { }
+ self& operator=(const self& x) {
+ Base::operator=(x);
+ m_property = const_cast<self&>(x).m_property;
+ return *this;
+ }
+ inline Property& get_property() { return *m_property; }
+ inline const Property& get_property() const { return *m_property; }
+ protected:
+ // Holding the property by-value causes edge-descriptor
+ // invalidation for add_edge() with EdgeList=vecS. Instead we
+ // hold a pointer to the property. std::auto_ptr is not
+ // a perfect fit for the job, but it is darn close.
+ std::auto_ptr<Property> m_property;
+ };
+
+
+ template <class Vertex, class Iter, class Property>
+ class stored_edge_iter
+ : public stored_edge<Vertex>
+ {
+ public:
+ typedef Property property_type;
+ inline stored_edge_iter() { }
+ inline stored_edge_iter(Vertex v)
+ : stored_edge<Vertex>(v) { }
+ inline stored_edge_iter(Vertex v, Iter i, void* = 0)
+ : stored_edge<Vertex>(v), m_iter(i) { }
+ inline Property& get_property() { return m_iter->get_property(); }
+ inline const Property& get_property() const {
+ return m_iter->get_property();
+ }
+ inline Iter get_iter() const { return m_iter; }
+ protected:
+ Iter m_iter;
+ };
+
+ // For when the EdgeList is a std::vector.
+ // Want to make the iterator stable, so use an offset
+ // instead of an iterator into a std::vector
+ template <class Vertex, class EdgeVec, class Property>
+ class stored_ra_edge_iter
+ : public stored_edge<Vertex>
+ {
+ typedef typename EdgeVec::iterator Iter;
+ public:
+ typedef Property property_type;
+ inline stored_ra_edge_iter() { }
+ inline stored_ra_edge_iter(Vertex v, Iter i = Iter(),
+ EdgeVec* edge_vec = 0)
+ : stored_edge<Vertex>(v), m_i(i - edge_vec->begin()), m_vec(edge_vec){ }
+ inline Property& get_property() { return (*m_vec)[m_i].get_property(); }
+ inline const Property& get_property() const {
+ return (*m_vec)[m_i].get_property();
+ }
+ inline Iter get_iter() const { return m_vec->begin() + m_i; }
+ protected:
+ std::size_t m_i;
+ EdgeVec* m_vec;
+ };
+
+ } // namespace detail
+
+ template <class Tag, class Vertex, class Property>
+ const typename property_value<Property,Tag>::type&
+ get(Tag property_tag,
+ const detail::stored_edge_property<Vertex, Property>& e)
+ {
+ return get_property_value(e.get_property(), property_tag);
+ }
+
+ template <class Tag, class Vertex, class Iter, class Property>
+ const typename property_value<Property,Tag>::type&
+ get(Tag property_tag,
+ const detail::stored_edge_iter<Vertex, Iter, Property>& e)
+ {
+ return get_property_value(e.get_property(), property_tag);
+ }
+
+ template <class Tag, class Vertex, class EdgeVec, class Property>
+ const typename property_value<Property,Tag>::type&
+ get(Tag property_tag,
+ const detail::stored_ra_edge_iter<Vertex, EdgeVec, Property>& e)
+ {
+ return get_property_value(e.get_property(), property_tag);
+ }
+
+ //=========================================================================
+ // Directed Edges Helper Class
+
+ namespace detail {
+
+ // O(E/V)
+ template <class edge_descriptor, class EdgeList, class StoredProperty>
+ inline void
+ remove_directed_edge_dispatch(edge_descriptor, EdgeList& el,
+ StoredProperty& p)
+ {
+ for (typename EdgeList::iterator i = el.begin();
+ i != el.end(); ++i)
+ if (&(*i).get_property() == &p) {
+ el.erase(i);
+ return;
+ }
+ }
+
+ template <class incidence_iterator, class EdgeList, class Predicate>
+ inline void
+ remove_directed_edge_if_dispatch(incidence_iterator first,
+ incidence_iterator last,
+ EdgeList& el, Predicate pred,
+ boost::allow_parallel_edge_tag)
+ {
+ // remove_if
+ while (first != last && !pred(*first))
+ ++first;
+ incidence_iterator i = first;
+ if (first != last)
+ for (++i; i != last; ++i)
+ if (!pred(*i)) {
+ *first.base() = *i.base();
+ ++first;
+ }
+ el.erase(first.base(), el.end());
+ }
+ template <class incidence_iterator, class EdgeList, class Predicate>
+ inline void
+ remove_directed_edge_if_dispatch(incidence_iterator first,
+ incidence_iterator last,
+ EdgeList& el,
+ Predicate pred,
+ boost::disallow_parallel_edge_tag)
+ {
+ for (incidence_iterator next = first;
+ first != last; first = next) {
+ ++next;
+ if (pred(*first))
+ el.erase( first.base() );
+ }
+ }
+
+ template <class PropT, class Graph, class incidence_iterator,
+ class EdgeList, class Predicate>
+ inline void
+ undirected_remove_out_edge_if_dispatch(Graph& g,
+ incidence_iterator first,
+ incidence_iterator last,
+ EdgeList& el, Predicate pred,
+ boost::allow_parallel_edge_tag)
+ {
+ typedef typename Graph::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_same<EdgeListS, vecS>::value));
+
+ // remove_if
+ while (first != last && !pred(*first))
+ ++first;
+ incidence_iterator i = first;
+ bool self_loop_removed = false;
+ if (first != last)
+ for (; i != last; ++i) {
+ if (self_loop_removed) {
+ /* With self loops, the descriptor will show up
+ * twice. The first time it will be removed, and now it
+ * will be skipped.
+ */
+ self_loop_removed = false;
+ }
+ else if (!pred(*i)) {
+ *first.base() = *i.base();
+ ++first;
+ } else {
+ if (source(*i, g) == target(*i, g)) self_loop_removed = true;
+ else {
+ // Remove the edge from the target
+ detail::remove_directed_edge_dispatch
+ (*i,
+ g.out_edge_list(target(*i, g)),
+ *(PropT*)(*i).get_property());
+ }
+
+ // Erase the edge property
+ g.m_edges.erase( (*i.base()).get_iter() );
+ }
+ }
+ el.erase(first.base(), el.end());
+ }
+ template <class PropT, class Graph, class incidence_iterator,
+ class EdgeList, class Predicate>
+ inline void
+ undirected_remove_out_edge_if_dispatch(Graph& g,
+ incidence_iterator first,
+ incidence_iterator last,
+ EdgeList& el,
+ Predicate pred,
+ boost::disallow_parallel_edge_tag)
+ {
+ typedef typename Graph::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ for (incidence_iterator next = first;
+ first != last; first = next) {
+ ++next;
+ if (pred(*first)) {
+ if (source(*first, g) != target(*first, g)) {
+ // Remove the edge from the target
+ detail::remove_directed_edge_dispatch
+ (*first,
+ g.out_edge_list(target(*first, g)),
+ *(PropT*)(*first).get_property());
+ }
+
+ // Erase the edge property
+ g.m_edges.erase( (*first.base()).get_iter() );
+
+ // Erase the edge in the source
+ el.erase( first.base() );
+ }
+ }
+ }
+
+ // O(E/V)
+ template <class edge_descriptor, class EdgeList, class StoredProperty>
+ inline void
+ remove_directed_edge_dispatch(edge_descriptor e, EdgeList& el,
+ no_property&)
+ {
+ for (typename EdgeList::iterator i = el.begin();
+ i != el.end(); ++i)
+ if ((*i).get_target() == e.m_target) {
+ el.erase(i);
+ return;
+ }
+ }
+
+ } // namespace detail
+
+ template <class Config>
+ struct directed_edges_helper {
+
+ // Placement of these overloaded remove_edge() functions
+ // inside the class avoids a VC++ bug.
+
+ // O(E/V)
+ inline void
+ remove_edge(typename Config::edge_descriptor e)
+ {
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(*this);
+ typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
+ typedef typename Config::OutEdgeList::value_type::property_type PType;
+ detail::remove_directed_edge_dispatch(e, el,
+ *(PType*)e.get_property());
+ }
+
+ // O(1)
+ inline void
+ remove_edge(typename Config::out_edge_iterator iter)
+ {
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(*this);
+ typename Config::edge_descriptor e = *iter;
+ typename Config::OutEdgeList& el = g.out_edge_list(source(e, g));
+ el.erase(iter.base());
+ }
+
+ };
+
+ // O(1)
+ template <class Config>
+ inline std::pair<typename Config::edge_iterator,
+ typename Config::edge_iterator>
+ edges(const directed_edges_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_iterator edge_iterator;
+ const graph_type& cg = static_cast<const graph_type&>(g_);
+ graph_type& g = const_cast<graph_type&>(cg);
+ return std::make_pair( edge_iterator(g.vertex_set().begin(),
+ g.vertex_set().begin(),
+ g.vertex_set().end(), g),
+ edge_iterator(g.vertex_set().begin(),
+ g.vertex_set().end(),
+ g.vertex_set().end(), g) );
+ }
+
+ //=========================================================================
+ // Directed Graph Helper Class
+
+ struct adj_list_dir_traversal_tag :
+ public virtual vertex_list_graph_tag,
+ public virtual incidence_graph_tag,
+ public virtual adjacency_graph_tag,
+ public virtual edge_list_graph_tag { };
+
+ template <class Config>
+ struct directed_graph_helper
+ : public directed_edges_helper<Config> {
+ typedef typename Config::edge_descriptor edge_descriptor;
+ typedef adj_list_dir_traversal_tag traversal_category;
+ };
+
+ // O(E/V)
+ template <class Config>
+ inline void
+ remove_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ directed_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_parallel_category Cat;
+ graph_type& g = static_cast<graph_type&>(g_);
+ detail::erase_from_incidence_list(g.out_edge_list(u), v, Cat());
+ }
+
+ template <class Config, class Predicate>
+ inline void
+ remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
+ directed_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::out_edge_iterator first, last;
+ boost::tie(first, last) = out_edges(u, g);
+ typedef typename Config::edge_parallel_category edge_parallel_category;
+ detail::remove_directed_edge_if_dispatch
+ (first, last, g.out_edge_list(u), pred, edge_parallel_category());
+ }
+
+ template <class Config, class Predicate>
+ inline void
+ remove_edge_if(Predicate pred, directed_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+
+ typename Config::vertex_iterator vi, vi_end;
+ for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
+ remove_out_edge_if(*vi, pred, g);
+ }
+
+ template <class EdgeOrIter, class Config>
+ inline void
+ remove_edge(EdgeOrIter e_or_iter, directed_graph_helper<Config>& g_)
+ {
+ g_.remove_edge(e_or_iter);
+ }
+
+ // O(V + E) for allow_parallel_edges
+ // O(V * log(E/V)) for disallow_parallel_edges
+ template <class Config>
+ inline void
+ clear_vertex(typename Config::vertex_descriptor u,
+ directed_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_parallel_category Cat;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::vertex_iterator vi, viend;
+ for (boost::tie(vi, viend) = vertices(g); vi != viend; ++vi)
+ detail::erase_from_incidence_list(g.out_edge_list(*vi), u, Cat());
+ g.out_edge_list(u).clear();
+ // clear() should be a req of Sequence and AssociativeContainer,
+ // or maybe just Container
+ }
+
+ template <class Config>
+ inline void
+ clear_out_edges(typename Config::vertex_descriptor u,
+ directed_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_parallel_category Cat;
+ graph_type& g = static_cast<graph_type&>(g_);
+ g.out_edge_list(u).clear();
+ // clear() should be a req of Sequence and AssociativeContainer,
+ // or maybe just Container
+ }
+
+ // O(V), could do better...
+ template <class Config>
+ inline typename Config::edges_size_type
+ num_edges(const directed_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ const graph_type& g = static_cast<const graph_type&>(g_);
+ typename Config::edges_size_type num_e = 0;
+ typename Config::vertex_iterator vi, vi_end;
+ for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
+ num_e += out_degree(*vi, g);
+ return num_e;
+ }
+ // O(1) for allow_parallel_edge_tag
+ // O(log(E/V)) for disallow_parallel_edge_tag
+ template <class Config>
+ inline std::pair<typename directed_graph_helper<Config>::edge_descriptor, bool>
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ const typename Config::edge_property_type& p,
+ directed_graph_helper<Config>& g_)
+ {
+ typedef typename Config::edge_descriptor edge_descriptor;
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::StoredEdge StoredEdge;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::OutEdgeList::iterator i;
+ bool inserted;
+ boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
+ StoredEdge(v, p));
+ return std::make_pair(edge_descriptor(u, v, &(*i).get_property()),
+ inserted);
+ }
+ // Did not use default argument here because that
+ // causes Visual C++ to get confused.
+ template <class Config>
+ inline std::pair<typename Config::edge_descriptor, bool>
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ directed_graph_helper<Config>& g_)
+ {
+ typename Config::edge_property_type p;
+ return add_edge(u, v, p, g_);
+ }
+ //=========================================================================
+ // Undirected Graph Helper Class
+
+ template <class Config>
+ struct undirected_graph_helper;
+
+ struct undir_adj_list_traversal_tag :
+ public virtual vertex_list_graph_tag,
+ public virtual incidence_graph_tag,
+ public virtual adjacency_graph_tag,
+ public virtual edge_list_graph_tag,
+ public virtual bidirectional_graph_tag { };
+
+ namespace detail {
+
+ // using class with specialization for dispatch is a VC++ workaround.
+ template <class StoredProperty>
+ struct remove_undirected_edge_dispatch {
+
+ // O(E/V)
+ template <class edge_descriptor, class Config>
+ static void
+ apply(edge_descriptor e,
+ undirected_graph_helper<Config>& g_,
+ StoredProperty& p)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+
+ typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
+ typename Config::OutEdgeList::iterator out_i = out_el.begin();
+ typename Config::EdgeIter edge_iter_to_erase;
+ for (; out_i != out_el.end(); ++out_i)
+ if (&(*out_i).get_property() == &p) {
+ edge_iter_to_erase = (*out_i).get_iter();
+ out_el.erase(out_i);
+ break;
+ }
+ typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
+ typename Config::OutEdgeList::iterator in_i = in_el.begin();
+ for (; in_i != in_el.end(); ++in_i)
+ if (&(*in_i).get_property() == &p) {
+ in_el.erase(in_i);
+ break;
+ }
+ g.m_edges.erase(edge_iter_to_erase);
+ }
+ };
+
+ template <>
+ struct remove_undirected_edge_dispatch<no_property> {
+ // O(E/V)
+ template <class edge_descriptor, class Config>
+ static void
+ apply(edge_descriptor e,
+ undirected_graph_helper<Config>& g_,
+ no_property&)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+ no_property* p = (no_property*)e.get_property();
+ typename Config::OutEdgeList& out_el = g.out_edge_list(source(e, g));
+ typename Config::OutEdgeList::iterator out_i = out_el.begin();
+ typename Config::EdgeIter edge_iter_to_erase;
+ for (; out_i != out_el.end(); ++out_i)
+ if (&(*out_i).get_property() == p) {
+ edge_iter_to_erase = (*out_i).get_iter();
+ out_el.erase(out_i);
+ break;
+ }
+ typename Config::OutEdgeList& in_el = g.out_edge_list(target(e, g));
+ typename Config::OutEdgeList::iterator in_i = in_el.begin();
+ for (; in_i != in_el.end(); ++in_i)
+ if (&(*in_i).get_property() == p) {
+ in_el.erase(in_i);
+ break;
+ }
+ g.m_edges.erase(edge_iter_to_erase);
+ }
+ };
+
+ // O(E/V)
+ template <class Graph, class EdgeList, class Vertex>
+ inline void
+ remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
+ boost::allow_parallel_edge_tag cat)
+ {
+ typedef typename Graph::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename EdgeList::value_type StoredEdge;
+ typename EdgeList::iterator i = el.begin(), end = el.end();
+ for (; i != end; ++i) {
+ if ((*i).get_target() == v) {
+ // NOTE: Wihtout this skip, this loop will double-delete properties
+ // of loop edges. This solution is based on the observation that
+ // the incidence edges of a vertex with a loop are adjacent in the
+ // out edge list. This *may* actually hold for multisets also.
+ bool skip = (boost::next(i) != end && i->get_iter() == boost::next(i)->get_iter());
+ g.m_edges.erase((*i).get_iter());
+ if (skip) ++i;
+ }
+ }
+ detail::erase_from_incidence_list(el, v, cat);
+ }
+ // O(log(E/V))
+ template <class Graph, class EdgeList, class Vertex>
+ inline void
+ remove_edge_and_property(Graph& g, EdgeList& el, Vertex v,
+ boost::disallow_parallel_edge_tag)
+ {
+ typedef typename Graph::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename EdgeList::value_type StoredEdge;
+ typename EdgeList::iterator i = el.find(StoredEdge(v)), end = el.end();
+ BOOST_ASSERT ((i != end));
+ if (i != end) {
+ g.m_edges.erase((*i).get_iter());
+ el.erase(i);
+ }
+ }
+
+ } // namespace detail
+
+ template <class Vertex, class EdgeProperty>
+ struct list_edge // short name due to VC++ truncation and linker problems
+ : public boost::detail::edge_base<boost::undirected_tag, Vertex>
+ {
+ typedef EdgeProperty property_type;
+ typedef boost::detail::edge_base<boost::undirected_tag, Vertex> Base;
+ list_edge(Vertex u, Vertex v, const EdgeProperty& p = EdgeProperty())
+ : Base(u, v), m_property(p) { }
+ EdgeProperty& get_property() { return m_property; }
+ const EdgeProperty& get_property() const { return m_property; }
+ // the following methods should never be used, but are needed
+ // to make SGI MIPSpro C++ happy
+ list_edge() { }
+ bool operator==(const list_edge&) const { return false; }
+ bool operator<(const list_edge&) const { return false; }
+ EdgeProperty m_property;
+ };
+
+ template <class Config>
+ struct undirected_graph_helper {
+
+ typedef undir_adj_list_traversal_tag traversal_category;
+
+ // Placement of these overloaded remove_edge() functions
+ // inside the class avoids a VC++ bug.
+
+ // O(E/V)
+ inline void
+ remove_edge(typename Config::edge_descriptor e)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::OutEdgeList::value_type::property_type PType;
+ detail::remove_undirected_edge_dispatch<PType>::apply
+ (e, *this, *(PType*)e.get_property());
+ }
+ // O(E/V)
+ inline void
+ remove_edge(typename Config::out_edge_iterator iter)
+ {
+ this->remove_edge(*iter);
+ }
+ };
+
+ // Had to make these non-members to avoid accidental instantiation
+ // on SGI MIPSpro C++
+ template <class C>
+ inline typename C::InEdgeList&
+ in_edge_list(undirected_graph_helper<C>&,
+ typename C::vertex_descriptor v)
+ {
+ typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
+ return sv->m_out_edges;
+ }
+ template <class C>
+ inline const typename C::InEdgeList&
+ in_edge_list(const undirected_graph_helper<C>&,
+ typename C::vertex_descriptor v) {
+ typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
+ return sv->m_out_edges;
+ }
+
+ // O(E/V)
+ template <class EdgeOrIter, class Config>
+ inline void
+ remove_edge(EdgeOrIter e, undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ g_.remove_edge(e);
+ }
+
+ // O(E/V) or O(log(E/V))
+ template <class Config>
+ void
+ remove_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typedef typename Config::edge_parallel_category Cat;
+ detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
+ detail::erase_from_incidence_list(g.out_edge_list(v), u, Cat());
+ }
+
+ template <class Config, class Predicate>
+ void
+ remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
+ undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::OutEdgeList::value_type::property_type PropT;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::out_edge_iterator first, last;
+ boost::tie(first, last) = out_edges(u, g);
+ typedef typename Config::edge_parallel_category Cat;
+ detail::undirected_remove_out_edge_if_dispatch<PropT>
+ (g, first, last, g.out_edge_list(u), pred, Cat());
+ }
+ template <class Config, class Predicate>
+ void
+ remove_in_edge_if(typename Config::vertex_descriptor u, Predicate pred,
+ undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ remove_out_edge_if(u, pred, g_);
+ }
+
+ // O(E/V * E) or O(log(E/V) * E)
+ template <class Predicate, class Config>
+ void
+ remove_edge_if(Predicate pred, undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::edge_iterator ei, ei_end, next;
+ boost::tie(ei, ei_end) = edges(g);
+ for (next = ei; ei != ei_end; ei = next) {
+ ++next;
+ if (pred(*ei))
+ remove_edge(*ei, g);
+ }
+ }
+
+ // O(1)
+ template <class Config>
+ inline std::pair<typename Config::edge_iterator,
+ typename Config::edge_iterator>
+ edges(const undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_iterator edge_iterator;
+ const graph_type& cg = static_cast<const graph_type&>(g_);
+ graph_type& g = const_cast<graph_type&>(cg);
+ return std::make_pair( edge_iterator(g.m_edges.begin()),
+ edge_iterator(g.m_edges.end()) );
+ }
+ // O(1)
+ template <class Config>
+ inline typename Config::edges_size_type
+ num_edges(const undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ const graph_type& g = static_cast<const graph_type&>(g_);
+ return g.m_edges.size();
+ }
+ // O(E/V * E/V)
+ template <class Config>
+ inline void
+ clear_vertex(typename Config::vertex_descriptor u,
+ undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_parallel_category Cat;
+ graph_type& g = static_cast<graph_type&>(g_);
+ while (true) {
+ typename Config::out_edge_iterator ei, ei_end;
+ boost::tie(ei, ei_end) = out_edges(u, g);
+ if (ei == ei_end) break;
+ remove_edge(*ei, g);
+ }
+ }
+ // O(1) for allow_parallel_edge_tag
+ // O(log(E/V)) for disallow_parallel_edge_tag
+ template <class Config>
+ inline std::pair<typename Config::edge_descriptor, bool>
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ const typename Config::edge_property_type& p,
+ undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::StoredEdge StoredEdge;
+ typedef typename Config::edge_descriptor edge_descriptor;
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+
+ bool inserted;
+ typename Config::EdgeContainer::value_type e(u, v, p);
+ typename Config::EdgeContainer::iterator p_iter
+ = graph_detail::push(g.m_edges, e).first;
+
+ typename Config::OutEdgeList::iterator i;
+ boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
+ StoredEdge(v, p_iter, &g.m_edges));
+ if (inserted) {
+ boost::graph_detail::push(g.out_edge_list(v), StoredEdge(u, p_iter, &g.m_edges));
+ return std::make_pair(edge_descriptor(u, v, &p_iter->get_property()),
+ true);
+ } else {
+ g.m_edges.erase(p_iter);
+ return std::make_pair
+ (edge_descriptor(u, v, &i->get_iter()->get_property()), false);
+ }
+ }
+ template <class Config>
+ inline std::pair<typename Config::edge_descriptor, bool>
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ undirected_graph_helper<Config>& g_)
+ {
+ typename Config::edge_property_type p;
+ return add_edge(u, v, p, g_);
+ }
+
+ // O(1)
+ template <class Config>
+ inline typename Config::degree_size_type
+ degree(typename Config::vertex_descriptor u,
+ const undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type Graph;
+ const Graph& g = static_cast<const Graph&>(g_);
+ return out_degree(u, g);
+ }
+
+ template <class Config>
+ inline std::pair<typename Config::in_edge_iterator,
+ typename Config::in_edge_iterator>
+ in_edges(typename Config::vertex_descriptor u,
+ const undirected_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type Graph;
+ const Graph& cg = static_cast<const Graph&>(g_);
+ Graph& g = const_cast<Graph&>(cg);
+ typedef typename Config::in_edge_iterator in_edge_iterator;
+ return
+ std::make_pair(in_edge_iterator(g.out_edge_list(u).begin(), u),
+ in_edge_iterator(g.out_edge_list(u).end(), u));
+ }
+
+ template <class Config>
+ inline typename Config::degree_size_type
+ in_degree(typename Config::vertex_descriptor u,
+ const undirected_graph_helper<Config>& g_)
+ { return degree(u, g_); }
+
+ //=========================================================================
+ // Bidirectional Graph Helper Class
+
+ struct bidir_adj_list_traversal_tag :
+ public virtual vertex_list_graph_tag,
+ public virtual incidence_graph_tag,
+ public virtual adjacency_graph_tag,
+ public virtual edge_list_graph_tag,
+ public virtual bidirectional_graph_tag { };
+
+ template <class Config>
+ struct bidirectional_graph_helper
+ : public directed_edges_helper<Config> {
+ typedef bidir_adj_list_traversal_tag traversal_category;
+ };
+
+ // Had to make these non-members to avoid accidental instantiation
+ // on SGI MIPSpro C++
+ template <class C>
+ inline typename C::InEdgeList&
+ in_edge_list(bidirectional_graph_helper<C>&,
+ typename C::vertex_descriptor v)
+ {
+ typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
+ return sv->m_in_edges;
+ }
+ template <class C>
+ inline const typename C::InEdgeList&
+ in_edge_list(const bidirectional_graph_helper<C>&,
+ typename C::vertex_descriptor v) {
+ typename C::stored_vertex* sv = (typename C::stored_vertex*)v;
+ return sv->m_in_edges;
+ }
+
+ template <class Predicate, class Config>
+ inline void
+ remove_edge_if(Predicate pred, bidirectional_graph_helper<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::edge_iterator ei, ei_end, next;
+ boost::tie(ei, ei_end) = edges(g);
+ for (next = ei; ei != ei_end; ei = next) {
+ ++next;
+ if (pred(*ei))
+ remove_edge(*ei, g);
+ }
+ }
+
+ template <class Config>
+ inline std::pair<typename Config::in_edge_iterator,
+ typename Config::in_edge_iterator>
+ in_edges(typename Config::vertex_descriptor u,
+ const bidirectional_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ const graph_type& cg = static_cast<const graph_type&>(g_);
+ graph_type& g = const_cast<graph_type&>(cg);
+ typedef typename Config::in_edge_iterator in_edge_iterator;
+ return
+ std::make_pair(in_edge_iterator(in_edge_list(g, u).begin(), u),
+ in_edge_iterator(in_edge_list(g, u).end(), u));
+ }
+
+ // O(1)
+ template <class Config>
+ inline std::pair<typename Config::edge_iterator,
+ typename Config::edge_iterator>
+ edges(const bidirectional_graph_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_iterator edge_iterator;
+ const graph_type& cg = static_cast<const graph_type&>(g_);
+ graph_type& g = const_cast<graph_type&>(cg);
+ return std::make_pair( edge_iterator(g.m_edges.begin()),
+ edge_iterator(g.m_edges.end()) );
+ }
+
+ //=========================================================================
+ // Bidirectional Graph Helper Class (with edge properties)
+
+
+ template <class Config>
+ struct bidirectional_graph_helper_with_property
+ : public bidirectional_graph_helper<Config>
+ {
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::out_edge_iterator out_edge_iterator;
+
+ std::pair<out_edge_iterator, out_edge_iterator>
+ get_parallel_edge_sublist(typename Config::edge_descriptor e,
+ const graph_type& g,
+ void*)
+ { return out_edges(source(e, g), g); }
+
+ std::pair<out_edge_iterator, out_edge_iterator>
+ get_parallel_edge_sublist(typename Config::edge_descriptor e,
+ const graph_type& g,
+ setS*)
+ { return edge_range(source(e, g), target(e, g), g); }
+
+ std::pair<out_edge_iterator, out_edge_iterator>
+ get_parallel_edge_sublist(typename Config::edge_descriptor e,
+ const graph_type& g,
+ multisetS*)
+ { return edge_range(source(e, g), target(e, g), g); }
+
+ std::pair<out_edge_iterator, out_edge_iterator>
+ get_parallel_edge_sublist(typename Config::edge_descriptor e,
+ const graph_type& g,
+ hash_setS*)
+ { return edge_range(source(e, g), target(e, g), g); }
+
+ // Placement of these overloaded remove_edge() functions
+ // inside the class avoids a VC++ bug.
+
+ // O(E/V) or O(log(E/V))
+ void
+ remove_edge(typename Config::edge_descriptor e)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ graph_type& g = static_cast<graph_type&>(*this);
+
+ typedef typename Config::edgelist_selector OutEdgeListS;
+
+ std::pair<out_edge_iterator, out_edge_iterator> rng =
+ get_parallel_edge_sublist(e, g, (OutEdgeListS*)(0));
+ rng.first = std::find(rng.first, rng.second, e);
+ BOOST_ASSERT(rng.first != rng.second);
+ remove_edge(rng.first);
+ }
+
+ inline void
+ remove_edge(typename Config::out_edge_iterator iter)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(*this);
+ typename Config::edge_descriptor e = *iter;
+ typename Config::OutEdgeList& oel = g.out_edge_list(source(e, g));
+ typename Config::InEdgeList& iel = in_edge_list(g, target(e, g));
+ typedef typename Config::OutEdgeList::value_type::property_type PType;
+ PType& p = *(PType*)e.get_property();
+ detail::remove_directed_edge_dispatch(*iter, iel, p);
+ g.m_edges.erase(iter.base()->get_iter());
+ oel.erase(iter.base());
+ }
+ };
+
+ // O(E/V) for allow_parallel_edge_tag
+ // O(log(E/V)) for disallow_parallel_edge_tag
+ template <class Config>
+ inline void
+ remove_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typedef typename Config::edge_parallel_category Cat;
+ detail::remove_edge_and_property(g, g.out_edge_list(u), v, Cat());
+ detail::erase_from_incidence_list(in_edge_list(g, v), u, Cat());
+ }
+
+ // O(E/V) or O(log(E/V))
+ template <class EdgeOrIter, class Config>
+ inline void
+ remove_edge(EdgeOrIter e,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ g_.remove_edge(e);
+ }
+
+ template <class Config, class Predicate>
+ inline void
+ remove_out_edge_if(typename Config::vertex_descriptor u, Predicate pred,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::OutEdgeList::value_type::property_type PropT;
+ graph_type& g = static_cast<graph_type&>(g_);
+
+ typedef typename Config::EdgeIter EdgeIter;
+ typedef std::vector<EdgeIter> Garbage;
+ Garbage garbage;
+
+ // First remove the edges from the targets' in-edge lists and
+ // from the graph's edge set list.
+ typename Config::out_edge_iterator out_i, out_end;
+ for (boost::tie(out_i, out_end) = out_edges(u, g); out_i != out_end; ++out_i)
+ if (pred(*out_i)) {
+ detail::remove_directed_edge_dispatch
+ (*out_i, in_edge_list(g, target(*out_i, g)),
+ *(PropT*)(*out_i).get_property());
+ // Put in garbage to delete later. Will need the properties
+ // for the remove_if of the out-edges.
+ garbage.push_back((*out_i.base()).get_iter());
+ }
+
+ // Now remove the edges from this out-edge list.
+ typename Config::out_edge_iterator first, last;
+ boost::tie(first, last) = out_edges(u, g);
+ typedef typename Config::edge_parallel_category Cat;
+ detail::remove_directed_edge_if_dispatch
+ (first, last, g.out_edge_list(u), pred, Cat());
+
+ // Now delete the edge properties from the g.m_edges list
+ for (typename Garbage::iterator i = garbage.begin();
+ i != garbage.end(); ++i)
+ g.m_edges.erase(*i);
+ }
+ template <class Config, class Predicate>
+ inline void
+ remove_in_edge_if(typename Config::vertex_descriptor v, Predicate pred,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::OutEdgeList::value_type::property_type PropT;
+ graph_type& g = static_cast<graph_type&>(g_);
+
+ typedef typename Config::EdgeIter EdgeIter;
+ typedef std::vector<EdgeIter> Garbage;
+ Garbage garbage;
+
+ // First remove the edges from the sources' out-edge lists and
+ // from the graph's edge set list.
+ typename Config::in_edge_iterator in_i, in_end;
+ for (boost::tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
+ if (pred(*in_i)) {
+ typename Config::vertex_descriptor u = source(*in_i, g);
+ detail::remove_directed_edge_dispatch
+ (*in_i, g.out_edge_list(u), *(PropT*)(*in_i).get_property());
+ // Put in garbage to delete later. Will need the properties
+ // for the remove_if of the out-edges.
+ garbage.push_back((*in_i.base()).get_iter());
+ }
+ // Now remove the edges from this in-edge list.
+ typename Config::in_edge_iterator first, last;
+ boost::tie(first, last) = in_edges(v, g);
+ typedef typename Config::edge_parallel_category Cat;
+ detail::remove_directed_edge_if_dispatch
+ (first, last, in_edge_list(g, v), pred, Cat());
+
+ // Now delete the edge properties from the g.m_edges list
+ for (typename Garbage::iterator i = garbage.begin();
+ i != garbage.end(); ++i)
+ g.m_edges.erase(*i);
+ }
+
+ // O(1)
+ template <class Config>
+ inline typename Config::edges_size_type
+ num_edges(const bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ const graph_type& g = static_cast<const graph_type&>(g_);
+ return g.m_edges.size();
+ }
+ // O(E/V * E/V) for allow_parallel_edge_tag
+ // O(E/V * log(E/V)) for disallow_parallel_edge_tag
+ template <class Config>
+ inline void
+ clear_vertex(typename Config::vertex_descriptor u,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_parallel_category Cat;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::OutEdgeList& el = g.out_edge_list(u);
+ typename Config::OutEdgeList::iterator
+ ei = el.begin(), ei_end = el.end();
+ for (; ei != ei_end; ++ei) {
+ detail::erase_from_incidence_list
+ (in_edge_list(g, (*ei).get_target()), u, Cat());
+ g.m_edges.erase((*ei).get_iter());
+ }
+ typename Config::InEdgeList& in_el = in_edge_list(g, u);
+ typename Config::InEdgeList::iterator
+ in_ei = in_el.begin(), in_ei_end = in_el.end();
+ for (; in_ei != in_ei_end; ++in_ei) {
+ detail::erase_from_incidence_list
+ (g.out_edge_list((*in_ei).get_target()), u, Cat());
+ g.m_edges.erase((*in_ei).get_iter());
+ }
+ g.out_edge_list(u).clear();
+ in_edge_list(g, u).clear();
+ }
+
+ template <class Config>
+ inline void
+ clear_out_edges(typename Config::vertex_descriptor u,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_parallel_category Cat;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::OutEdgeList& el = g.out_edge_list(u);
+ typename Config::OutEdgeList::iterator
+ ei = el.begin(), ei_end = el.end();
+ for (; ei != ei_end; ++ei) {
+ detail::erase_from_incidence_list
+ (in_edge_list(g, (*ei).get_target()), u, Cat());
+ g.m_edges.erase((*ei).get_iter());
+ }
+ g.out_edge_list(u).clear();
+ }
+
+ template <class Config>
+ inline void
+ clear_in_edges(typename Config::vertex_descriptor u,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Config::graph_type graph_type;
+ typedef typename Config::edge_parallel_category Cat;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typename Config::InEdgeList& in_el = in_edge_list(g, u);
+ typename Config::InEdgeList::iterator
+ in_ei = in_el.begin(), in_ei_end = in_el.end();
+ for (; in_ei != in_ei_end; ++in_ei) {
+ detail::erase_from_incidence_list
+ (g.out_edge_list((*in_ei).get_target()), u, Cat());
+ g.m_edges.erase((*in_ei).get_iter());
+ }
+ in_edge_list(g, u).clear();
+ }
+
+ // O(1) for allow_parallel_edge_tag
+ // O(log(E/V)) for disallow_parallel_edge_tag
+ template <class Config>
+ inline std::pair<typename Config::edge_descriptor, bool>
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ const typename Config::edge_property_type& p,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ graph_type& g = static_cast<graph_type&>(g_);
+ typedef typename Config::edge_descriptor edge_descriptor;
+ typedef typename Config::StoredEdge StoredEdge;
+ bool inserted;
+ typename Config::EdgeContainer::value_type e(u, v, p);
+ typename Config::EdgeContainer::iterator p_iter
+ = graph_detail::push(g.m_edges, e).first;
+ typename Config::OutEdgeList::iterator i;
+ boost::tie(i, inserted) = boost::graph_detail::push(g.out_edge_list(u),
+ StoredEdge(v, p_iter, &g.m_edges));
+ if (inserted) {
+ boost::graph_detail::push(in_edge_list(g, v), StoredEdge(u, p_iter, &g.m_edges));
+ return std::make_pair(edge_descriptor(u, v, &p_iter->m_property),
+ true);
+ } else {
+ g.m_edges.erase(p_iter);
+ return std::make_pair(edge_descriptor(u, v,
+ &i->get_iter()->get_property()),
+ false);
+ }
+ }
+
+ template <class Config>
+ inline std::pair<typename Config::edge_descriptor, bool>
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typename Config::edge_property_type p;
+ return add_edge(u, v, p, g_);
+ }
+ // O(1)
+ template <class Config>
+ inline typename Config::degree_size_type
+ degree(typename Config::vertex_descriptor u,
+ const bidirectional_graph_helper_with_property<Config>& g_)
+ {
+ typedef typename Config::graph_type graph_type;
+ const graph_type& g = static_cast<const graph_type&>(g_);
+ return in_degree(u, g) + out_degree(u, g);
+ }
+
+ //=========================================================================
+ // Adjacency List Helper Class
+
+ template <class Config, class Base>
+ struct adj_list_helper : public Base
+ {
+ typedef typename Config::graph_type AdjList;
+ typedef typename Config::vertex_descriptor vertex_descriptor;
+ typedef typename Config::edge_descriptor edge_descriptor;
+ typedef typename Config::out_edge_iterator out_edge_iterator;
+ typedef typename Config::in_edge_iterator in_edge_iterator;
+ typedef typename Config::adjacency_iterator adjacency_iterator;
+ typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
+ typedef typename Config::vertex_iterator vertex_iterator;
+ typedef typename Config::edge_iterator edge_iterator;
+ typedef typename Config::directed_category directed_category;
+ typedef typename Config::edge_parallel_category edge_parallel_category;
+ typedef typename Config::vertices_size_type vertices_size_type;
+ typedef typename Config::edges_size_type edges_size_type;
+ typedef typename Config::degree_size_type degree_size_type;
+ typedef typename Config::StoredEdge StoredEdge;
+ typedef typename Config::vertex_property_type vertex_property_type;
+ typedef typename Config::edge_property_type edge_property_type;
+ typedef typename Config::graph_property_type graph_property_type;
+
+ typedef typename Config::global_edgelist_selector
+ global_edgelist_selector;
+
+ typedef typename lookup_one_property<vertex_property_type, vertex_bundle_t>::type vertex_bundled;
+ typedef typename lookup_one_property<edge_property_type, edge_bundle_t>::type edge_bundled;
+ typedef typename lookup_one_property<graph_property_type, graph_bundle_t>::type graph_bundled;
+ };
+
+ template <class Config, class Base>
+ inline std::pair<typename Config::adjacency_iterator,
+ typename Config::adjacency_iterator>
+ adjacent_vertices(typename Config::vertex_descriptor u,
+ const adj_list_helper<Config, Base>& g_)
+ {
+ typedef typename Config::graph_type AdjList;
+ const AdjList& cg = static_cast<const AdjList&>(g_);
+ AdjList& g = const_cast<AdjList&>(cg);
+ typedef typename Config::adjacency_iterator adjacency_iterator;
+ typename Config::out_edge_iterator first, last;
+ boost::tie(first, last) = out_edges(u, g);
+ return std::make_pair(adjacency_iterator(first, &g),
+ adjacency_iterator(last, &g));
+ }
+ template <class Config, class Base>
+ inline std::pair<typename Config::inv_adjacency_iterator,
+ typename Config::inv_adjacency_iterator>
+ inv_adjacent_vertices(typename Config::vertex_descriptor u,
+ const adj_list_helper<Config, Base>& g_)
+ {
+ typedef typename Config::graph_type AdjList;
+ const AdjList& cg = static_cast<const AdjList&>(g_);
+ AdjList& g = const_cast<AdjList&>(cg);
+ typedef typename Config::inv_adjacency_iterator inv_adjacency_iterator;
+ typename Config::in_edge_iterator first, last;
+ boost::tie(first, last) = in_edges(u, g);
+ return std::make_pair(inv_adjacency_iterator(first, &g),
+ inv_adjacency_iterator(last, &g));
+ }
+ template <class Config, class Base>
+ inline std::pair<typename Config::out_edge_iterator,
+ typename Config::out_edge_iterator>
+ out_edges(typename Config::vertex_descriptor u,
+ const adj_list_helper<Config, Base>& g_)
+ {
+ typedef typename Config::graph_type AdjList;
+ typedef typename Config::out_edge_iterator out_edge_iterator;
+ const AdjList& cg = static_cast<const AdjList&>(g_);
+ AdjList& g = const_cast<AdjList&>(cg);
+ return
+ std::make_pair(out_edge_iterator(g.out_edge_list(u).begin(), u),
+ out_edge_iterator(g.out_edge_list(u).end(), u));
+ }
+ template <class Config, class Base>
+ inline std::pair<typename Config::vertex_iterator,
+ typename Config::vertex_iterator>
+ vertices(const adj_list_helper<Config, Base>& g_)
+ {
+ typedef typename Config::graph_type AdjList;
+ const AdjList& cg = static_cast<const AdjList&>(g_);
+ AdjList& g = const_cast<AdjList&>(cg);
+ return std::make_pair( g.vertex_set().begin(), g.vertex_set().end() );
+ }
+ template <class Config, class Base>
+ inline typename Config::vertices_size_type
+ num_vertices(const adj_list_helper<Config, Base>& g_)
+ {
+ typedef typename Config::graph_type AdjList;
+ const AdjList& g = static_cast<const AdjList&>(g_);
+ return g.vertex_set().size();
+ }
+ template <class Config, class Base>
+ inline typename Config::degree_size_type
+ out_degree(typename Config::vertex_descriptor u,
+ const adj_list_helper<Config, Base>& g_)
+ {
+ typedef typename Config::graph_type AdjList;
+ const AdjList& g = static_cast<const AdjList&>(g_);
+ return g.out_edge_list(u).size();
+ }
+ template <class Config, class Base>
+ inline std::pair<typename Config::edge_descriptor, bool>
+ edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ const adj_list_helper<Config, Base>& g_)
+ {
+ typedef typename Config::graph_type Graph;
+ typedef typename Config::StoredEdge StoredEdge;
+ const Graph& cg = static_cast<const Graph&>(g_);
+ typedef typename Config::out_edge_iterator out_edge_iterator;
+ const typename Config::OutEdgeList& el = cg.out_edge_list(u);
+ typename Config::OutEdgeList::const_iterator it = graph_detail::
+ find(el, StoredEdge(v));
+ return std::make_pair(
+ typename Config::edge_descriptor
+ (u, v, (it == el.end() ? 0 : &(*it).get_property())),
+ (it != el.end()));
+ }
+
+ template <class Config, class Base>
+ inline std::pair<typename Config::out_edge_iterator,
+ typename Config::out_edge_iterator>
+ edge_range(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ const adj_list_helper<Config, Base>& g_)
+ {
+ typedef typename Config::graph_type Graph;
+ typedef typename Config::StoredEdge StoredEdge;
+ const Graph& cg = static_cast<const Graph&>(g_);
+ Graph& g = const_cast<Graph&>(cg);
+ typedef typename Config::out_edge_iterator out_edge_iterator;
+ typename Config::OutEdgeList& el = g.out_edge_list(u);
+ typename Config::OutEdgeList::iterator first, last;
+ typename Config::EdgeContainer fake_edge_container;
+ boost::tie(first, last) = graph_detail::
+ equal_range(el, StoredEdge(v, fake_edge_container.end(),
+ &fake_edge_container));
+ return std::make_pair(out_edge_iterator(first, u),
+ out_edge_iterator(last, u));
+ }
+
+ template <class Config>
+ inline typename Config::degree_size_type
+ in_degree(typename Config::vertex_descriptor u,
+ const directed_edges_helper<Config>& g_)
+ {
+ typedef typename Config::graph_type Graph;
+ const Graph& cg = static_cast<const Graph&>(g_);
+ Graph& g = const_cast<Graph&>(cg);
+ return in_edge_list(g, u).size();
+ }
+
+ namespace detail {
+ template <class Config, class Base, class Property>
+ inline
+ typename boost::property_map<typename Config::graph_type,
+ Property>::type
+ get_dispatch(adj_list_helper<Config,Base>&, Property p,
+ boost::edge_property_tag) {
+ typedef typename Config::graph_type Graph;
+ typedef typename boost::property_map<Graph, Property>::type PA;
+ return PA(p);
+ }
+ template <class Config, class Base, class Property>
+ inline
+ typename boost::property_map<typename Config::graph_type,
+ Property>::const_type
+ get_dispatch(const adj_list_helper<Config,Base>&, Property p,
+ boost::edge_property_tag) {
+ typedef typename Config::graph_type Graph;
+ typedef typename boost::property_map<Graph, Property>::const_type PA;
+ return PA(p);
+ }
+
+ template <class Config, class Base, class Property>
+ inline
+ typename boost::property_map<typename Config::graph_type,
+ Property>::type
+ get_dispatch(adj_list_helper<Config,Base>& g, Property p,
+ boost::vertex_property_tag) {
+ typedef typename Config::graph_type Graph;
+ typedef typename boost::property_map<Graph, Property>::type PA;
+ return PA(&static_cast<Graph&>(g), p);
+ }
+ template <class Config, class Base, class Property>
+ inline
+ typename boost::property_map<typename Config::graph_type,
+ Property>::const_type
+ get_dispatch(const adj_list_helper<Config, Base>& g, Property p,
+ boost::vertex_property_tag) {
+ typedef typename Config::graph_type Graph;
+ typedef typename boost::property_map<Graph, Property>::const_type PA;
+ const Graph& cg = static_cast<const Graph&>(g);
+ return PA(&cg, p);
+ }
+
+ } // namespace detail
+
+ // Implementation of the PropertyGraph interface
+ template <class Config, class Base, class Property>
+ inline
+ typename boost::property_map<typename Config::graph_type, Property>::type
+ get(Property p, adj_list_helper<Config, Base>& g) {
+ typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind;
+ return detail::get_dispatch(g, p, Kind());
+ }
+ template <class Config, class Base, class Property>
+ inline
+ typename boost::property_map<typename Config::graph_type,
+ Property>::const_type
+ get(Property p, const adj_list_helper<Config, Base>& g) {
+ typedef typename detail::property_kind_from_graph<adj_list_helper<Config, Base>, Property>::type Kind;
+ return detail::get_dispatch(g, p, Kind());
+ }
+
+ template <class Config, class Base, class Property, class Key>
+ inline
+ typename boost::property_traits<
+ typename boost::property_map<typename Config::graph_type,
+ Property>::type
+ >::reference
+ get(Property p, adj_list_helper<Config, Base>& g, const Key& key) {
+ return get(get(p, g), key);
+ }
+
+ template <class Config, class Base, class Property, class Key>
+ inline
+ typename boost::property_traits<
+ typename boost::property_map<typename Config::graph_type,
+ Property>::const_type
+ >::reference
+ get(Property p, const adj_list_helper<Config, Base>& g, const Key& key) {
+ return get(get(p, g), key);
+ }
+
+ template <class Config, class Base, class Property, class Key,class Value>
+ inline void
+ put(Property p, adj_list_helper<Config, Base>& g,
+ const Key& key, const Value& value)
+ {
+ typedef typename Config::graph_type Graph;
+ typedef typename boost::property_map<Graph, Property>::type Map;
+ Map pmap = get(p, static_cast<Graph&>(g));
+ put(pmap, key, value);
+ }
+
+
+ //=========================================================================
+ // Generalize Adjacency List Implementation
+
+ struct adj_list_tag { };
+
+ template <class Derived, class Config, class Base>
+ class adj_list_impl
+ : public adj_list_helper<Config, Base>
+ {
+ typedef typename Config::OutEdgeList OutEdgeList;
+ typedef typename Config::InEdgeList InEdgeList;
+ typedef typename Config::StoredVertexList StoredVertexList;
+ public:
+ typedef typename Config::stored_vertex stored_vertex;
+ typedef typename Config::EdgeContainer EdgeContainer;
+ typedef typename Config::vertex_descriptor vertex_descriptor;
+ typedef typename Config::edge_descriptor edge_descriptor;
+ typedef typename Config::vertex_iterator vertex_iterator;
+ typedef typename Config::edge_iterator edge_iterator;
+ typedef typename Config::edge_parallel_category edge_parallel_category;
+ typedef typename Config::vertices_size_type vertices_size_type;
+ typedef typename Config::edges_size_type edges_size_type;
+ typedef typename Config::degree_size_type degree_size_type;
+ typedef typename Config::edge_property_type edge_property_type;
+ typedef adj_list_tag graph_tag;
+
+ static vertex_descriptor null_vertex()
+ {
+ return 0;
+ }
+
+ inline adj_list_impl() { }
+
+ inline adj_list_impl(const adj_list_impl& x) {
+ copy_impl(x);
+ }
+ inline adj_list_impl& operator=(const adj_list_impl& x) {
+ this->clear();
+ copy_impl(x);
+ return *this;
+ }
+ inline void clear() {
+ for (typename StoredVertexList::iterator i = m_vertices.begin();
+ i != m_vertices.end(); ++i)
+ delete (stored_vertex*)*i;
+ m_vertices.clear();
+ m_edges.clear();
+ }
+ inline adj_list_impl(vertices_size_type num_vertices) {
+ for (vertices_size_type i = 0; i < num_vertices; ++i)
+ add_vertex(static_cast<Derived&>(*this));
+ }
+ template <class EdgeIterator>
+ inline adj_list_impl(vertices_size_type num_vertices,
+ EdgeIterator first, EdgeIterator last)
+ {
+ vertex_descriptor* v = new vertex_descriptor[num_vertices];
+ for (vertices_size_type i = 0; i < num_vertices; ++i)
+ v[i] = add_vertex(static_cast<Derived&>(*this));
+
+ while (first != last) {
+ add_edge(v[(*first).first], v[(*first).second], *this);
+ ++first;
+ }
+ delete [] v;
+ }
+ template <class EdgeIterator, class EdgePropertyIterator>
+ inline adj_list_impl(vertices_size_type num_vertices,
+ EdgeIterator first, EdgeIterator last,
+ EdgePropertyIterator ep_iter)
+ {
+ vertex_descriptor* v = new vertex_descriptor[num_vertices];
+ for (vertices_size_type i = 0; i < num_vertices; ++i)
+ v[i] = add_vertex(static_cast<Derived&>(*this));
+
+ while (first != last) {
+ add_edge(v[(*first).first], v[(*first).second], *ep_iter, *this);
+ ++first;
+ ++ep_iter;
+ }
+ delete [] v;
+ }
+ ~adj_list_impl() {
+ for (typename StoredVertexList::iterator i = m_vertices.begin();
+ i != m_vertices.end(); ++i)
+ delete (stored_vertex*)*i;
+ }
+ // protected:
+ inline OutEdgeList& out_edge_list(vertex_descriptor v) {
+ stored_vertex* sv = (stored_vertex*)v;
+ return sv->m_out_edges;
+ }
+ inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
+ stored_vertex* sv = (stored_vertex*)v;
+ return sv->m_out_edges;
+ }
+ inline StoredVertexList& vertex_set() { return m_vertices; }
+ inline const StoredVertexList& vertex_set() const { return m_vertices; }
+
+ inline void copy_impl(const adj_list_impl& x_)
+ {
+ const Derived& x = static_cast<const Derived&>(x_);
+
+ // Would be better to have a constant time way to get from
+ // vertices in x to the corresponding vertices in *this.
+ std::map<stored_vertex*,stored_vertex*> vertex_map;
+
+ // Copy the stored vertex objects by adding each vertex
+ // and copying its property object.
+ vertex_iterator vi, vi_end;
+ for (boost::tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) {
+ stored_vertex* v = (stored_vertex*)add_vertex(*this);
+ v->m_property = ((stored_vertex*)*vi)->m_property;
+ vertex_map[(stored_vertex*)*vi] = v;
+ }
+ // Copy the edges by adding each edge and copying its
+ // property object.
+ edge_iterator ei, ei_end;
+ for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
+ edge_descriptor e;
+ bool inserted;
+ vertex_descriptor s = source(*ei,x), t = target(*ei,x);
+ boost::tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s],
+ vertex_map[(stored_vertex*)t], *this);
+ *((edge_property_type*)e.m_eproperty)
+ = *((edge_property_type*)(*ei).m_eproperty);
+ }
+ }
+
+
+ typename Config::EdgeContainer m_edges;
+ StoredVertexList m_vertices;
+ };
+
+ // O(1)
+ template <class Derived, class Config, class Base>
+ inline typename Config::vertex_descriptor
+ add_vertex(adj_list_impl<Derived, Config, Base>& g_)
+ {
+ Derived& g = static_cast<Derived&>(g_);
+ typedef typename Config::stored_vertex stored_vertex;
+ stored_vertex* v = new stored_vertex;
+ typename Config::StoredVertexList::iterator pos;
+ bool inserted;
+ boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
+ v->m_position = pos;
+ g.added_vertex(v);
+ return v;
+ }
+ // O(1)
+ template <class Derived, class Config, class Base>
+ inline typename Config::vertex_descriptor
+ add_vertex(const typename Config::vertex_property_type& p,
+ adj_list_impl<Derived, Config, Base>& g_)
+ {
+ typedef typename Config::vertex_descriptor vertex_descriptor;
+ Derived& g = static_cast<Derived&>(g_);
+ if (optional<vertex_descriptor> v
+ = g.vertex_by_property(get_property_value(p, vertex_bundle)))
+ return *v;
+
+ typedef typename Config::stored_vertex stored_vertex;
+ stored_vertex* v = new stored_vertex(p);
+ typename Config::StoredVertexList::iterator pos;
+ bool inserted;
+ boost::tie(pos,inserted) = boost::graph_detail::push(g.m_vertices, v);
+ v->m_position = pos;
+ g.added_vertex(v);
+ return v;
+ }
+ // O(1)
+ template <class Derived, class Config, class Base>
+ inline void remove_vertex(typename Config::vertex_descriptor u,
+ adj_list_impl<Derived, Config, Base>& g_)
+ {
+ typedef typename Config::stored_vertex stored_vertex;
+ Derived& g = static_cast<Derived&>(g_);
+ g.removing_vertex(u);
+ stored_vertex* su = (stored_vertex*)u;
+ g.m_vertices.erase(su->m_position);
+ delete su;
+ }
+ // O(V)
+ template <class Derived, class Config, class Base>
+ inline typename Config::vertex_descriptor
+ vertex(typename Config::vertices_size_type n,
+ const adj_list_impl<Derived, Config, Base>& g_)
+ {
+ const Derived& g = static_cast<const Derived&>(g_);
+ typename Config::vertex_iterator i = vertices(g).first;
+ while (n--) ++i; // std::advance(i, n); (not VC++ portable)
+ return *i;
+ }
+
+ //=========================================================================
+ // Vector-Backbone Adjacency List Implementation
+
+ namespace detail {
+
+ template <class Graph, class vertex_descriptor>
+ inline void
+ remove_vertex_dispatch(Graph& g, vertex_descriptor u,
+ boost::directed_tag)
+ {
+ typedef typename Graph::edge_parallel_category edge_parallel_category;
+ g.m_vertices.erase(g.m_vertices.begin() + u);
+ vertex_descriptor V = num_vertices(g);
+ if (u != V) {
+ for (vertex_descriptor v = 0; v < V; ++v)
+ reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category());
+ }
+ }
+
+ template <class Graph, class vertex_descriptor>
+ inline void
+ remove_vertex_dispatch(Graph& g, vertex_descriptor u,
+ boost::undirected_tag)
+ {
+ typedef typename Graph::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Graph::edge_parallel_category edge_parallel_category;
+ g.m_vertices.erase(g.m_vertices.begin() + u);
+ vertex_descriptor V = num_vertices(g);
+ for (vertex_descriptor v = 0; v < V; ++v)
+ reindex_edge_list(g.out_edge_list(v), u,
+ edge_parallel_category());
+ typedef typename Graph::EdgeContainer Container;
+ typedef typename Container::iterator Iter;
+ Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
+ for (; ei != ei_end; ++ei) {
+ if (ei->m_source > u)
+ --ei->m_source;
+ if (ei->m_target > u)
+ --ei->m_target;
+ }
+ }
+ template <class Graph, class vertex_descriptor>
+ inline void
+ remove_vertex_dispatch(Graph& g, vertex_descriptor u,
+ boost::bidirectional_tag)
+ {
+ typedef typename Graph::global_edgelist_selector EdgeListS;
+ BOOST_STATIC_ASSERT((!is_random_access_selector<EdgeListS>::value));
+
+ typedef typename Graph::edge_parallel_category edge_parallel_category;
+ g.m_vertices.erase(g.m_vertices.begin() + u);
+ vertex_descriptor V = num_vertices(g);
+ vertex_descriptor v;
+ if (u != V) {
+ for (v = 0; v < V; ++v)
+ reindex_edge_list(g.out_edge_list(v), u,
+ edge_parallel_category());
+ for (v = 0; v < V; ++v)
+ reindex_edge_list(in_edge_list(g, v), u,
+ edge_parallel_category());
+
+ typedef typename Graph::EdgeContainer Container;
+ typedef typename Container::iterator Iter;
+ Iter ei = g.m_edges.begin(), ei_end = g.m_edges.end();
+ for (; ei != ei_end; ++ei) {
+ if (ei->m_source > u)
+ --ei->m_source;
+ if (ei->m_target > u)
+ --ei->m_target;
+ }
+ }
+ }
+
+ template <class EdgeList, class vertex_descriptor>
+ inline void
+ reindex_edge_list(EdgeList& el, vertex_descriptor u,
+ boost::allow_parallel_edge_tag)
+ {
+ typename EdgeList::iterator ei = el.begin(), e_end = el.end();
+ for (; ei != e_end; ++ei)
+ if ((*ei).get_target() > u)
+ --(*ei).get_target();
+ }
+ template <class EdgeList, class vertex_descriptor>
+ inline void
+ reindex_edge_list(EdgeList& el, vertex_descriptor u,
+ boost::disallow_parallel_edge_tag)
+ {
+ typename EdgeList::iterator ei = el.begin(), e_end = el.end();
+ while (ei != e_end) {
+ typename EdgeList::value_type ce = *ei;
+ ++ei;
+ if (ce.get_target() > u) {
+ el.erase(ce);
+ --ce.get_target();
+ el.insert(ce);
+ }
+ }
+ }
+ } // namespace detail
+
+ struct vec_adj_list_tag { };
+
+ template <class Graph, class Config, class Base>
+ class vec_adj_list_impl
+ : public adj_list_helper<Config, Base>
+ {
+ typedef typename Config::OutEdgeList OutEdgeList;
+ typedef typename Config::InEdgeList InEdgeList;
+ typedef typename Config::StoredVertexList StoredVertexList;
+ public:
+ typedef typename Config::vertex_descriptor vertex_descriptor;
+ typedef typename Config::edge_descriptor edge_descriptor;
+ typedef typename Config::out_edge_iterator out_edge_iterator;
+ typedef typename Config::edge_iterator edge_iterator;
+ typedef typename Config::directed_category directed_category;
+ typedef typename Config::vertices_size_type vertices_size_type;
+ typedef typename Config::edges_size_type edges_size_type;
+ typedef typename Config::degree_size_type degree_size_type;
+ typedef typename Config::StoredEdge StoredEdge;
+ typedef typename Config::stored_vertex stored_vertex;
+ typedef typename Config::EdgeContainer EdgeContainer;
+ typedef typename Config::edge_property_type edge_property_type;
+ typedef vec_adj_list_tag graph_tag;
+
+ static vertex_descriptor null_vertex()
+ {
+ return (std::numeric_limits<vertex_descriptor>::max)();
+ }
+
+ inline vec_adj_list_impl() { }
+
+ inline vec_adj_list_impl(const vec_adj_list_impl& x) {
+ copy_impl(x);
+ }
+ inline vec_adj_list_impl& operator=(const vec_adj_list_impl& x) {
+ this->clear();
+ copy_impl(x);
+ return *this;
+ }
+ inline void clear() {
+ m_vertices.clear();
+ m_edges.clear();
+ }
+
+ inline vec_adj_list_impl(vertices_size_type _num_vertices)
+ : m_vertices(_num_vertices) { }
+
+ template <class EdgeIterator>
+ inline vec_adj_list_impl(vertices_size_type num_vertices,
+ EdgeIterator first, EdgeIterator last)
+ : m_vertices(num_vertices)
+ {
+ while (first != last) {
+ add_edge((*first).first, (*first).second,
+ static_cast<Graph&>(*this));
+ ++first;
+ }
+ }
+ template <class EdgeIterator, class EdgePropertyIterator>
+ inline vec_adj_list_impl(vertices_size_type num_vertices,
+ EdgeIterator first, EdgeIterator last,
+ EdgePropertyIterator ep_iter)
+ : m_vertices(num_vertices)
+ {
+ while (first != last) {
+ add_edge((*first).first, (*first).second, *ep_iter,
+ static_cast<Graph&>(*this));
+ ++first;
+ ++ep_iter;
+ }
+ }
+
+ // protected:
+ inline boost::integer_range<vertex_descriptor> vertex_set() const {
+ return boost::integer_range<vertex_descriptor>(0, m_vertices.size());
+ }
+ inline OutEdgeList& out_edge_list(vertex_descriptor v) {
+ return m_vertices[v].m_out_edges;
+ }
+ inline const OutEdgeList& out_edge_list(vertex_descriptor v) const {
+ return m_vertices[v].m_out_edges;
+ }
+ inline void copy_impl(const vec_adj_list_impl& x_)
+ {
+ const Graph& x = static_cast<const Graph&>(x_);
+ // Copy the stored vertex objects by adding each vertex
+ // and copying its property object.
+ for (vertices_size_type i = 0; i < num_vertices(x); ++i) {
+ vertex_descriptor v = add_vertex(*this);
+ m_vertices[v].m_property = x.m_vertices[i].m_property;
+ }
+ // Copy the edges by adding each edge and copying its
+ // property object.
+ edge_iterator ei, ei_end;
+ for (boost::tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) {
+ edge_descriptor e;
+ bool inserted;
+ boost::tie(e, inserted) = add_edge(source(*ei,x), target(*ei,x) , *this);
+ *((edge_property_type*)e.m_eproperty)
+ = *((edge_property_type*)(*ei).m_eproperty);
+ }
+ }
+ typename Config::EdgeContainer m_edges;
+ StoredVertexList m_vertices;
+ };
+ // Had to make these non-members to avoid accidental instantiation
+ // on SGI MIPSpro C++
+ template <class G, class C, class B>
+ inline typename C::InEdgeList&
+ in_edge_list(vec_adj_list_impl<G,C,B>& g,
+ typename C::vertex_descriptor v) {
+ return g.m_vertices[v].m_in_edges;
+ }
+ template <class G, class C, class B>
+ inline const typename C::InEdgeList&
+ in_edge_list(const vec_adj_list_impl<G,C,B>& g,
+ typename C::vertex_descriptor v) {
+ return g.m_vertices[v].m_in_edges;
+ }
+
+ // O(1)
+ template <class Graph, class Config, class Base>
+ inline typename Config::vertex_descriptor
+ add_vertex(vec_adj_list_impl<Graph, Config, Base>& g_) {
+ Graph& g = static_cast<Graph&>(g_);
+ g.m_vertices.resize(g.m_vertices.size() + 1);
+ g.added_vertex(g.m_vertices.size() - 1);
+ return g.m_vertices.size() - 1;
+ }
+
+ template <class Graph, class Config, class Base>
+ inline typename Config::vertex_descriptor
+ add_vertex(const typename Config::vertex_property_type& p,
+ vec_adj_list_impl<Graph, Config, Base>& g_) {
+ typedef typename Config::vertex_descriptor vertex_descriptor;
+ Graph& g = static_cast<Graph&>(g_);
+ if (optional<vertex_descriptor> v
+ = g.vertex_by_property(get_property_value(p, vertex_bundle)))
+ return *v;
+ typedef typename Config::stored_vertex stored_vertex;
+ g.m_vertices.push_back(stored_vertex(p));
+ g.added_vertex(g.m_vertices.size() - 1);
+ return g.m_vertices.size() - 1;
+ }
+
+ // Here we override the directed_graph_helper add_edge() function
+ // so that the number of vertices is automatically changed if
+ // either u or v is greater than the number of vertices.
+ template <class Graph, class Config, class Base>
+ inline std::pair<typename Config::edge_descriptor, bool>
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ const typename Config::edge_property_type& p,
+ vec_adj_list_impl<Graph, Config, Base>& g_)
+ {
+ BOOST_USING_STD_MAX();
+ typename Config::vertex_descriptor x = max BOOST_PREVENT_MACRO_SUBSTITUTION(u, v);
+ if (x >= num_vertices(g_))
+ g_.m_vertices.resize(x + 1);
+ adj_list_helper<Config, Base>& g = g_;
+ return add_edge(u, v, p, g);
+ }
+ template <class Graph, class Config, class Base>
+ inline std::pair<typename Config::edge_descriptor, bool>
+ add_edge(typename Config::vertex_descriptor u,
+ typename Config::vertex_descriptor v,
+ vec_adj_list_impl<Graph, Config, Base>& g_)
+ {
+ typename Config::edge_property_type p;
+ return add_edge(u, v, p, g_);
+ }
+
+
+ // O(V + E)
+ template <class Graph, class Config, class Base>
+ inline void remove_vertex(typename Config::vertex_descriptor v,
+ vec_adj_list_impl<Graph, Config, Base>& g_)
+ {
+ typedef typename Config::directed_category Cat;
+ Graph& g = static_cast<Graph&>(g_);
+ g.removing_vertex(v);
+ detail::remove_vertex_dispatch(g, v, Cat());
+ }
+ // O(1)
+ template <class Graph, class Config, class Base>
+ inline typename Config::vertex_descriptor
+ vertex(typename Config::vertices_size_type n,
+ const vec_adj_list_impl<Graph, Config, Base>&)
+ {
+ return n;
+ }
+
+
+ namespace detail {
+
+ //=========================================================================
+ // Adjacency List Generator
+
+ template <class Graph, class VertexListS, class OutEdgeListS,
+ class DirectedS, class VertexProperty, class EdgeProperty,
+ class GraphProperty, class EdgeListS>
+ struct adj_list_gen
+ {
+ // Remove these assertions once PtrContainer support is implemented.
+ BOOST_STATIC_ASSERT((!is_ptr_selector<VertexListS>::value));
+ BOOST_STATIC_ASSERT((!is_ptr_selector<OutEdgeListS>::value));
+ BOOST_STATIC_ASSERT((!is_ptr_selector<EdgeListS>::value));
+
+ typedef typename is_random_access_selector<VertexListS>::type
+ is_rand_access;
+ typedef typename has_property<EdgeProperty>::type has_edge_property;
+ typedef typename DirectedS::is_directed_t DirectedT;
+ typedef typename DirectedS::is_bidir_t BidirectionalT;
+
+ struct config
+ {
+ typedef OutEdgeListS edgelist_selector;
+ typedef EdgeListS global_edgelist_selector;
+
+ typedef Graph graph_type;
+ typedef EdgeProperty edge_property_type;
+ typedef VertexProperty vertex_property_type;
+ typedef GraphProperty graph_property_type;
+ typedef std::size_t vertices_size_type;
+
+ typedef adjacency_list_traits<OutEdgeListS, VertexListS, DirectedS>
+ Traits;
+
+ typedef typename Traits::directed_category directed_category;
+ typedef typename Traits::edge_parallel_category edge_parallel_category;
+ typedef typename Traits::vertex_descriptor vertex_descriptor;
+ typedef typename Traits::edge_descriptor edge_descriptor;
+
+ typedef void* vertex_ptr;
+
+ // need to reorganize this to avoid instantiating stuff
+ // that doesn't get used -JGS
+
+ // VertexList and vertex_iterator
+ typedef typename container_gen<VertexListS,
+ vertex_ptr>::type SeqVertexList;
+ typedef boost::integer_range<vertex_descriptor> RandVertexList;
+ typedef typename mpl::if_<is_rand_access,
+ RandVertexList, SeqVertexList>::type VertexList;
+
+ typedef typename VertexList::iterator vertex_iterator;
+
+ // EdgeContainer and StoredEdge
+
+ typedef typename container_gen<EdgeListS,
+ list_edge<vertex_descriptor, EdgeProperty> >::type EdgeContainer;
+
+ typedef typename mpl::and_<DirectedT,
+ typename mpl::not_<BidirectionalT>::type >::type on_edge_storage;
+
+ typedef typename mpl::if_<on_edge_storage,
+ std::size_t, typename EdgeContainer::size_type
+ >::type edges_size_type;
+
+ typedef typename EdgeContainer::iterator EdgeIter;
+
+ typedef typename is_random_access_selector<EdgeListS>::type is_edge_ra;
+
+ typedef typename mpl::if_<on_edge_storage,
+ stored_edge_property<vertex_descriptor, EdgeProperty>,
+ typename mpl::if_<is_edge_ra,
+ stored_ra_edge_iter<vertex_descriptor, EdgeContainer, EdgeProperty>,
+ stored_edge_iter<vertex_descriptor, EdgeIter, EdgeProperty>
+ >::type
+ >::type StoredEdge;
+
+ // Adjacency Types
+
+ typedef typename container_gen<OutEdgeListS, StoredEdge>::type
+ OutEdgeList;
+ typedef typename OutEdgeList::size_type degree_size_type;
+ typedef typename OutEdgeList::iterator OutEdgeIter;
+
+ typedef boost::detail::iterator_traits<OutEdgeIter> OutEdgeIterTraits;
+ typedef typename OutEdgeIterTraits::iterator_category OutEdgeIterCat;
+ typedef typename OutEdgeIterTraits::difference_type OutEdgeIterDiff;
+
+ typedef out_edge_iter<
+ OutEdgeIter, vertex_descriptor, edge_descriptor, OutEdgeIterDiff
+ > out_edge_iterator;
+
+ typedef typename adjacency_iterator_generator<graph_type,
+ vertex_descriptor, out_edge_iterator>::type adjacency_iterator;
+
+ typedef OutEdgeList InEdgeList;
+ typedef OutEdgeIter InEdgeIter;
+ typedef OutEdgeIterCat InEdgeIterCat;
+ typedef OutEdgeIterDiff InEdgeIterDiff;
+
+ typedef in_edge_iter<
+ InEdgeIter, vertex_descriptor, edge_descriptor, InEdgeIterDiff
+ > in_edge_iterator;
+
+ typedef typename inv_adjacency_iterator_generator<graph_type,
+ vertex_descriptor, in_edge_iterator>::type inv_adjacency_iterator;
+
+ // Edge Iterator
+
+ typedef boost::detail::iterator_traits<EdgeIter> EdgeIterTraits;
+ typedef typename EdgeIterTraits::iterator_category EdgeIterCat;
+ typedef typename EdgeIterTraits::difference_type EdgeIterDiff;
+
+ typedef undirected_edge_iter<
+ EdgeIter
+ , edge_descriptor
+ , EdgeIterDiff
+ > UndirectedEdgeIter; // also used for bidirectional
+
+ typedef adj_list_edge_iterator<vertex_iterator, out_edge_iterator,
+ graph_type> DirectedEdgeIter;
+
+ typedef typename mpl::if_<on_edge_storage,
+ DirectedEdgeIter, UndirectedEdgeIter>::type edge_iterator;
+
+ // stored_vertex and StoredVertexList
+ typedef typename container_gen<VertexListS, vertex_ptr>::type
+ SeqStoredVertexList;
+ struct seq_stored_vertex {
+ seq_stored_vertex() { }
+ seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
+ OutEdgeList m_out_edges;
+ VertexProperty m_property;
+ typename SeqStoredVertexList::iterator m_position;
+ };
+ struct bidir_seq_stored_vertex {
+ bidir_seq_stored_vertex() { }
+ bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
+ OutEdgeList m_out_edges;
+ InEdgeList m_in_edges;
+ VertexProperty m_property;
+ typename SeqStoredVertexList::iterator m_position;
+ };
+ struct rand_stored_vertex {
+ rand_stored_vertex() { }
+ rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
+ OutEdgeList m_out_edges;
+ VertexProperty m_property;
+ };
+ struct bidir_rand_stored_vertex {
+ bidir_rand_stored_vertex() { }
+ bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
+ OutEdgeList m_out_edges;
+ InEdgeList m_in_edges;
+ VertexProperty m_property;
+ };
+ typedef typename mpl::if_<is_rand_access,
+ typename mpl::if_<BidirectionalT,
+ bidir_rand_stored_vertex, rand_stored_vertex>::type,
+ typename mpl::if_<BidirectionalT,
+ bidir_seq_stored_vertex, seq_stored_vertex>::type
+ >::type StoredVertex;
+ struct stored_vertex : public StoredVertex {
+ stored_vertex() { }
+ stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
+ };
+
+ typedef typename container_gen<VertexListS, stored_vertex>::type
+ RandStoredVertexList;
+ typedef typename mpl::if_< is_rand_access,
+ RandStoredVertexList, SeqStoredVertexList>::type StoredVertexList;
+ }; // end of config
+
+
+ typedef typename mpl::if_<BidirectionalT,
+ bidirectional_graph_helper_with_property<config>,
+ typename mpl::if_<DirectedT,
+ directed_graph_helper<config>,
+ undirected_graph_helper<config>
+ >::type
+ >::type DirectedHelper;
+
+ typedef typename mpl::if_<is_rand_access,
+ vec_adj_list_impl<Graph, config, DirectedHelper>,
+ adj_list_impl<Graph, config, DirectedHelper>
+ >::type type;
+
+ };
+
+ } // namespace detail
+
+ //=========================================================================
+ // Vertex Property Maps
+
+ template <class Graph, class ValueType, class Reference, class Tag>
+ struct adj_list_vertex_property_map
+ : public boost::put_get_helper<
+ Reference,
+ adj_list_vertex_property_map<Graph, ValueType, Reference, Tag>
+ >
+ {
+ typedef typename Graph::stored_vertex StoredVertex;
+ typedef ValueType value_type;
+ typedef Reference reference;
+ typedef typename Graph::vertex_descriptor key_type;
+ typedef boost::lvalue_property_map_tag category;
+ inline adj_list_vertex_property_map(const Graph* = 0, Tag tag = Tag()): m_tag(tag) { }
+ inline Reference operator[](key_type v) const {
+ StoredVertex* sv = (StoredVertex*)v;
+ return get_property_value(sv->m_property, m_tag);
+ }
+ inline Reference operator()(key_type v) const {
+ return this->operator[](v);
+ }
+ Tag m_tag;
+ };
+
+ template <class Graph, class Property, class PropRef>
+ struct adj_list_vertex_all_properties_map
+ : public boost::put_get_helper<PropRef,
+ adj_list_vertex_all_properties_map<Graph, Property, PropRef>
+ >
+ {
+ typedef typename Graph::stored_vertex StoredVertex;
+ typedef Property value_type;
+ typedef PropRef reference;
+ typedef typename Graph::vertex_descriptor key_type;
+ typedef boost::lvalue_property_map_tag category;
+ inline adj_list_vertex_all_properties_map(const Graph* = 0, vertex_all_t = vertex_all_t()) { }
+ inline PropRef operator[](key_type v) const {
+ StoredVertex* sv = (StoredVertex*)v;
+ return sv->m_property;
+ }
+ inline PropRef operator()(key_type v) const {
+ return this->operator[](v);
+ }
+ };
+
+ template <class Graph, class GraphPtr, class ValueType, class Reference,
+ class Tag>
+ struct vec_adj_list_vertex_property_map
+ : public boost::put_get_helper<
+ Reference,
+ vec_adj_list_vertex_property_map<Graph,GraphPtr,ValueType,Reference,
+ Tag>
+ >
+ {
+ typedef ValueType value_type;
+ typedef Reference reference;
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
+ typedef boost::lvalue_property_map_tag category;
+ vec_adj_list_vertex_property_map(GraphPtr g = 0, Tag tag = Tag()) : m_g(g), m_tag(tag) { }
+ inline Reference operator[](key_type v) const {
+ return get_property_value(m_g->m_vertices[v].m_property, m_tag);
+ }
+ inline Reference operator()(key_type v) const {
+ return this->operator[](v);
+ }
+ GraphPtr m_g;
+ Tag m_tag;
+ };
+
+ template <class Graph, class GraphPtr, class Property, class PropertyRef>
+ struct vec_adj_list_vertex_all_properties_map
+ : public boost::put_get_helper<PropertyRef,
+ vec_adj_list_vertex_all_properties_map<Graph,GraphPtr,Property,
+ PropertyRef>
+ >
+ {
+ typedef Property value_type;
+ typedef PropertyRef reference;
+ typedef typename boost::graph_traits<Graph>::vertex_descriptor key_type;
+ typedef boost::lvalue_property_map_tag category;
+ vec_adj_list_vertex_all_properties_map(GraphPtr g = 0, vertex_all_t = vertex_all_t()) : m_g(g) { }
+ inline PropertyRef operator[](key_type v) const {
+ return m_g->m_vertices[v].m_property;
+ }
+ inline PropertyRef operator()(key_type v) const {
+ return this->operator[](v);
+ }
+ GraphPtr m_g;
+ };
+
+ struct adj_list_any_vertex_pa {
+ template <class Tag, class Graph, class Property>
+ struct bind_ {
+ typedef typename property_value<Property, Tag>::type value_type;
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+
+ typedef adj_list_vertex_property_map
+ <Graph, value_type, reference, Tag> type;
+ typedef adj_list_vertex_property_map
+ <Graph, value_type, const_reference, Tag> const_type;
+ };
+ };
+ struct adj_list_all_vertex_pa {
+ template <class Tag, class Graph, class Property>
+ struct bind_ {
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef adj_list_vertex_all_properties_map<Graph,Property,
+ Property&> type;
+ typedef adj_list_vertex_all_properties_map<Graph,Property,
+ const Property&> const_type;
+ };
+ };
+
+ template <class Property, class Vertex>
+ struct vec_adj_list_vertex_id_map
+ : public boost::put_get_helper<
+ Vertex, vec_adj_list_vertex_id_map<Property, Vertex>
+ >
+ {
+ typedef Vertex value_type;
+ typedef Vertex key_type;
+ typedef Vertex reference;
+ typedef boost::readable_property_map_tag category;
+ inline vec_adj_list_vertex_id_map() { }
+ template <class Graph>
+ inline vec_adj_list_vertex_id_map(const Graph&, vertex_index_t) { }
+ inline value_type operator[](key_type v) const { return v; }
+ inline value_type operator()(key_type v) const { return v; }
+ };
+
+ struct vec_adj_list_any_vertex_pa {
+ template <class Tag, class Graph, class Property>
+ struct bind_ {
+ typedef typename property_value<Property, Tag>::type value_type;
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+
+ typedef vec_adj_list_vertex_property_map
+ <Graph, Graph*, value_type, reference, Tag> type;
+ typedef vec_adj_list_vertex_property_map
+ <Graph, const Graph*, value_type, const_reference, Tag> const_type;
+ };
+ };
+ struct vec_adj_list_id_vertex_pa {
+ template <class Tag, class Graph, class Property>
+ struct bind_ {
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef vec_adj_list_vertex_id_map<Property, Vertex> type;
+ typedef vec_adj_list_vertex_id_map<Property, Vertex> const_type;
+ };
+ };
+ struct vec_adj_list_all_vertex_pa {
+ template <class Tag, class Graph, class Property>
+ struct bind_ {
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef vec_adj_list_vertex_all_properties_map
+ <Graph, Graph*, Property, Property&> type;
+ typedef vec_adj_list_vertex_all_properties_map
+ <Graph, const Graph*, Property, const Property&> const_type;
+ };
+ };
+ namespace detail {
+ template <class Tag, class Graph, class Property>
+ struct adj_list_choose_vertex_pa
+ : boost::mpl::if_<
+ boost::is_same<Tag, vertex_all_t>,
+ adj_list_all_vertex_pa,
+ adj_list_any_vertex_pa>::type
+ ::template bind_<Tag, Graph, Property>
+ {};
+
+
+ template <class Tag>
+ struct vec_adj_list_choose_vertex_pa_helper {
+ typedef vec_adj_list_any_vertex_pa type;
+ };
+ template <>
+ struct vec_adj_list_choose_vertex_pa_helper<vertex_index_t> {
+ typedef vec_adj_list_id_vertex_pa type;
+ };
+ template <>
+ struct vec_adj_list_choose_vertex_pa_helper<vertex_all_t> {
+ typedef vec_adj_list_all_vertex_pa type;
+ };
+ template <class Tag, class Graph, class Property>
+ struct vec_adj_list_choose_vertex_pa
+ : vec_adj_list_choose_vertex_pa_helper<Tag>::type::template bind_<Tag,Graph,Property>
+ {};
+ } // namespace detail
+
+ //=========================================================================
+ // Edge Property Map
+
+ template <class Directed, class Value, class Ref, class Vertex,
+ class Property, class Tag>
+ struct adj_list_edge_property_map
+ : public put_get_helper<
+ Ref,
+ adj_list_edge_property_map<Directed, Value, Ref, Vertex, Property,
+ Tag>
+ >
+ {
+ Tag tag;
+ explicit adj_list_edge_property_map(Tag tag = Tag()): tag(tag) {}
+
+ typedef Value value_type;
+ typedef Ref reference;
+ typedef detail::edge_desc_impl<Directed, Vertex> key_type;
+ typedef boost::lvalue_property_map_tag category;
+ inline Ref operator[](key_type e) const {
+ Property& p = *(Property*)e.get_property();
+ return get_property_value(p, tag);
+ }
+ inline Ref operator()(key_type e) const {
+ return this->operator[](e);
+ }
+ };
+
+ template <class Directed, class Property, class PropRef, class PropPtr,
+ class Vertex>
+ struct adj_list_edge_all_properties_map
+ : public put_get_helper<PropRef,
+ adj_list_edge_all_properties_map<Directed, Property, PropRef,
+ PropPtr, Vertex>
+ >
+ {
+ explicit adj_list_edge_all_properties_map(edge_all_t = edge_all_t()) {}
+ typedef Property value_type;
+ typedef PropRef reference;
+ typedef detail::edge_desc_impl<Directed, Vertex> key_type;
+ typedef boost::lvalue_property_map_tag category;
+ inline PropRef operator[](key_type e) const {
+ return *(PropPtr)e.get_property();
+ }
+ inline PropRef operator()(key_type e) const {
+ return this->operator[](e);
+ }
+ };
+
+ // Edge Property Maps
+
+ namespace detail {
+ struct adj_list_any_edge_pmap {
+ template <class Graph, class Property, class Tag>
+ struct bind_ {
+ typedef typename property_value<Property,Tag>::type value_type;
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+
+ typedef adj_list_edge_property_map
+ <typename Graph::directed_category, value_type, reference,
+ typename Graph::vertex_descriptor,Property,Tag> type;
+ typedef adj_list_edge_property_map
+ <typename Graph::directed_category, value_type, const_reference,
+ typename Graph::vertex_descriptor,const Property, Tag> const_type;
+ };
+ };
+ struct adj_list_all_edge_pmap {
+ template <class Graph, class Property, class Tag>
+ struct bind_ {
+ typedef adj_list_edge_all_properties_map
+ <typename Graph::directed_category, Property, Property&, Property*,
+ typename Graph::vertex_descriptor> type;
+ typedef adj_list_edge_all_properties_map
+ <typename Graph::directed_category, Property, const Property&,
+ const Property*, typename Graph::vertex_descriptor> const_type;
+ };
+ };
+
+ template <class Tag>
+ struct adj_list_choose_edge_pmap_helper {
+ typedef adj_list_any_edge_pmap type;
+ };
+ template <>
+ struct adj_list_choose_edge_pmap_helper<edge_all_t> {
+ typedef adj_list_all_edge_pmap type;
+ };
+ template <class Tag, class Graph, class Property>
+ struct adj_list_choose_edge_pmap
+ : adj_list_choose_edge_pmap_helper<Tag>::type::template bind_<Graph, Property, Tag>
+ {};
+ struct adj_list_edge_property_selector {
+ template <class Graph, class Property, class Tag>
+ struct bind_: adj_list_choose_edge_pmap<Tag, Graph, Property> {};
+ };
+ } // namespace detail
+
+ template <>
+ struct edge_property_selector<adj_list_tag> {
+ typedef detail::adj_list_edge_property_selector type;
+ };
+ template <>
+ struct edge_property_selector<vec_adj_list_tag> {
+ typedef detail::adj_list_edge_property_selector type;
+ };
+
+ // Vertex Property Maps
+
+ struct adj_list_vertex_property_selector {
+ template <class Graph, class Property, class Tag>
+ struct bind_
+ : detail::adj_list_choose_vertex_pa<Tag,Graph,Property>
+ {};
+ };
+ template <>
+ struct vertex_property_selector<adj_list_tag> {
+ typedef adj_list_vertex_property_selector type;
+ };
+
+ struct vec_adj_list_vertex_property_selector {
+ template <class Graph, class Property, class Tag>
+ struct bind_: detail::vec_adj_list_choose_vertex_pa<Tag,Graph,Property> {};
+ };
+ template <>
+ struct vertex_property_selector<vec_adj_list_tag> {
+ typedef vec_adj_list_vertex_property_selector type;
+ };
+
+} // namespace boost
+
+#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION)
+namespace boost {
+
+ template <typename V>
+ struct hash< boost::detail::stored_edge<V> >
+ {
+ std::size_t
+ operator()(const boost::detail::stored_edge<V>& e) const
+ {
+ return hash<V>()(e.m_target);
+ }
+ };
+
+ template <typename V, typename P>
+ struct hash< boost::detail::stored_edge_property <V,P> >
+ {
+ std::size_t
+ operator()(const boost::detail::stored_edge_property<V,P>& e) const
+ {
+ return hash<V>()(e.m_target);
+ }
+ };
+
+ template <typename V, typename I, typename P>
+ struct hash< boost::detail::stored_edge_iter<V,I, P> >
+ {
+ std::size_t
+ operator()(const boost::detail::stored_edge_iter<V,I,P>& e) const
+ {
+ return hash<V>()(e.m_target);
+ }
+ };
+
+}
+#endif
+
+
+#endif // BOOST_GRAPH_DETAIL_DETAIL_ADJACENCY_LIST_CCT
+
+/*
+ Implementation Notes:
+
+ Many of the public interface functions in this file would have been
+ more conveniently implemented as inline friend functions.
+ However there are a few compiler bugs that make that approach
+ non-portable.
+
+ 1. g++ inline friend in namespace bug
+ 2. g++ using clause doesn't work with inline friends
+ 3. VC++ doesn't have Koenig lookup
+
+ For these reasons, the functions were all written as non-inline free
+ functions, and static cast was used to convert from the helper
+ class to the adjacency_list derived class.
+
+ Looking back, it might have been better to write out all functions
+ in terms of the adjacency_list, and then use a tag to dispatch
+ to the various helpers instead of using inheritance.
+
+ */
Added: sandbox/container_gen/libs/container_gen/example/output_char_tallies.cpp
==============================================================================
--- (empty file)
+++ sandbox/container_gen/libs/container_gen/example/output_char_tallies.cpp 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
@@ -0,0 +1,66 @@
+//=======================================================================
+// Copyright (C) 2011-2012 Cromwell D. Enage
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+#include <iostream>
+#include <string>
+#include <boost/config.hpp>
+#include <boost/container_gen/selectors.hpp>
+#include <boost/container_gen/container_gen.hpp>
+
+//[example__output_char_tallies__definition
+template <typename Selector>
+void output_char_tallies(std::string const& str, Selector)
+{
+ typedef typename boost::container_gen<Selector,char,std::size_t>::type
+ FrequencyTable;
+
+ FrequencyTable freq_table;
+
+ for (std::size_t i = 0; i < str.size(); ++i)
+ {
+ typename FrequencyTable::iterator ft_itr = freq_table.find(str[i]);
+
+ if (ft_itr == freq_table.end())
+ {
+ freq_table.insert(typename FrequencyTable::value_type(str[i], 1));
+ }
+ else
+ {
+ ++ft_itr->second;
+ }
+ }
+
+ for (
+ typename FrequencyTable::const_iterator ft_itr = freq_table.begin();
+ ft_itr != freq_table.end();
+ ++ft_itr
+ )
+ {
+ std::cout << ft_itr->first << ": " << ft_itr->second << std::endl;
+ }
+
+ std::cout << std::endl;
+}
+//]
+
+//[example__output_char_tallies__calls
+int main(int, char**)
+{
+//<-
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION || defined BOOST_HAS_HASH
+//->
+ output_char_tallies("abacadabra", boost::hash_mapS());
+//<-
+#else
+ output_char_tallies("abacadabra", boost::mapS());
+#endif
+//->
+ output_char_tallies("loolapalooza", boost::multimapS());
+ return 0;
+}
+//]
+
Added: sandbox/container_gen/libs/container_gen/test/emplace_function_gen.cpp
==============================================================================
--- (empty file)
+++ sandbox/container_gen/libs/container_gen/test/emplace_function_gen.cpp 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
@@ -0,0 +1,556 @@
+// Copyright (C) 2012 Cromwell D. Enage
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#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 <utility>
+#include <cstring>
+#include <boost/mpl/bool.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/container_gen/is_unique_assoc_selector.hpp>
+#include "type_definitions.hpp"
+#include <boost/test/minimal.hpp>
+
+template <typename Emplacer, typename C>
+void
+ test_emplacer(
+ Emplacer const& emplacer
+ , C& c
+ , bool should_be_successful
+ , char const* value
+ )
+{
+ typename C::size_type old_size = c.size();
+ std::pair<typename C::iterator,bool> p = emplacer(c, value);
+
+ BOOST_CHECK(p.second == should_be_successful);
+
+ if (p.second)
+ {
+ BOOST_CHECK(!strcmp((*p.first).c_str(), value));
+ BOOST_CHECK(c.size() == old_size + 1);
+ }
+ else
+ {
+ BOOST_CHECK(c.size() == old_size);
+ }
+}
+
+template <typename Selector>
+void test_emplace_function_gen()
+{
+ typename boost::container_gen<Selector,test_string>::type
+ test_container_1, test_container_2;
+ typename boost::emplace_function_gen<Selector>::type emplacer;
+ bool is_multi = !boost::is_unique_associative_selector<Selector>::value;
+
+ test_emplacer(emplacer, test_container_1, true, "able");
+ test_emplacer(emplacer, test_container_1, true, "fox");
+ test_emplacer(emplacer, test_container_1, true, "easy");
+ test_emplacer(emplacer, test_container_1, true, "baker");
+ test_emplacer(emplacer, test_container_1, true, "charlie");
+ test_emplacer(emplacer, test_container_1, true, "dog");
+ test_emplacer(emplacer, test_container_1, is_multi, "able");
+ test_emplacer(emplacer, test_container_1, is_multi, "fox");
+ test_emplacer(emplacer, test_container_1, is_multi, "easy");
+ test_emplacer(emplacer, test_container_1, is_multi, "baker");
+ test_emplacer(emplacer, test_container_1, is_multi, "charlie");
+ test_emplacer(emplacer, test_container_1, is_multi, "dog");
+
+ emplacer[test_container_2]
+ ("able")("fox")("easy")("baker")("charlie")("dog")
+ ("able")("fox")("easy")("baker")("charlie")("dog");
+
+ BOOST_CHECK(boost::range::equal(test_container_1, test_container_2));
+}
+
+template <typename T>
+void test_recursive_element(T const& t)
+{
+ BOOST_CHECK(
+ !strcmp(t.word.c_str(), "")
+ || !strcmp(t.word.c_str(), "sol")
+ );
+ BOOST_CHECK((t.number == 0) || (t.number == 42));
+ BOOST_CHECK((t.letter == '\0') || (t.letter == 'X'));
+
+ typedef typename T::next_level_t C;
+ typename C::const_iterator itr_end = t.next_level.end();
+
+ for (
+ typename C::const_iterator itr = t.next_level.begin();
+ itr != itr_end;
+ ++itr
+ )
+ {
+ BOOST_CHECK((*itr).previous_level == &t);
+ test_recursive_element(*itr);
+ }
+}
+
+template <typename Emplacer, typename T>
+void test_emplacer_recursive(Emplacer const& emplacer, T& t)
+{
+ typedef typename T::next_level_t C;
+ typename C::size_type old_size = t.next_level.size();
+ std::pair<typename C::iterator,bool> p = emplacer(t.next_level);
+
+ (*p.first).previous_level = &t;
+ BOOST_CHECK(p.second);
+ test_recursive_element(t);
+ BOOST_CHECK(!strcmp((*p.first).word.c_str(), ""));
+ BOOST_CHECK((*p.first).number == 0);
+ BOOST_CHECK((*p.first).letter == '\0');
+ BOOST_CHECK((*p.first).flag == false);
+ BOOST_CHECK(t.next_level.size() == old_size + 1);
+}
+
+template <typename Emplacer, typename T>
+void test_emplacer_recursive(Emplacer const& emplacer, T& t, char const* word)
+{
+ typedef typename T::next_level_t C;
+ typename C::size_type old_size = t.next_level.size();
+ std::pair<typename C::iterator,bool> p = emplacer(t.next_level, word);
+
+ (*p.first).previous_level = &t;
+ BOOST_CHECK(p.second);
+ test_recursive_element(t);
+ BOOST_CHECK(!strcmp((*p.first).word.c_str(), word));
+ BOOST_CHECK((*p.first).number == 0);
+ BOOST_CHECK((*p.first).letter == '\0');
+ BOOST_CHECK((*p.first).flag == false);
+ BOOST_CHECK(t.next_level.size() == old_size + 1);
+}
+
+template <typename Emplacer, typename T>
+void
+ test_emplacer_recursive(
+ Emplacer const& emplacer
+ , T& t
+ , char const* word
+ , long n
+ )
+{
+ typedef typename T::next_level_t C;
+ typename C::size_type old_size = t.next_level.size();
+ std::pair<typename C::iterator,bool> p = emplacer(t.next_level, word, n);
+
+ (*p.first).previous_level = &t;
+ BOOST_CHECK(p.second);
+ test_recursive_element(t);
+ BOOST_CHECK(!strcmp((*p.first).word.c_str(), word));
+ BOOST_CHECK((*p.first).number == n);
+ BOOST_CHECK((*p.first).letter == '\0');
+ BOOST_CHECK((*p.first).flag == false);
+ BOOST_CHECK(t.next_level.size() == old_size + 1);
+}
+
+template <typename Emplacer, typename T>
+void
+ test_emplacer_recursive(
+ Emplacer const& emplacer
+ , T& t
+ , char const* word
+ , long n
+ , char letter
+ )
+{
+ typedef typename T::next_level_t C;
+ typename C::size_type old_size = t.next_level.size();
+ std::pair<typename C::iterator,bool> p = emplacer(
+ t.next_level
+ , word
+ , n
+ , letter
+ );
+
+ (*p.first).previous_level = &t;
+ BOOST_CHECK(p.second);
+ test_recursive_element(t);
+ BOOST_CHECK(!strcmp((*p.first).word.c_str(), word));
+ BOOST_CHECK((*p.first).number == n);
+ BOOST_CHECK((*p.first).letter == letter);
+ BOOST_CHECK((*p.first).flag == false);
+ BOOST_CHECK(t.next_level.size() == old_size + 1);
+}
+
+template <typename Emplacer, typename T>
+void
+ test_emplacer_recursive(
+ Emplacer const& emplacer
+ , T& t
+ , char const* word
+ , long n
+ , char letter
+ , bool b
+ )
+{
+ typedef typename T::next_level_t C;
+ typename C::size_type old_size = t.next_level.size();
+ std::pair<typename C::iterator,bool> p = emplacer(
+ t.next_level
+ , word
+ , n
+ , letter
+ , b
+ );
+
+ (*p.first).previous_level = &t;
+ BOOST_CHECK(p.second);
+ test_recursive_element(t);
+ BOOST_CHECK(!strcmp((*p.first).word.c_str(), word));
+ BOOST_CHECK((*p.first).number == n);
+ BOOST_CHECK((*p.first).letter == letter);
+ BOOST_CHECK((*p.first).flag == b);
+ BOOST_CHECK(t.next_level.size() == old_size + 1);
+}
+
+template <typename Selector>
+struct test_mri_element
+{
+ template <typename T>
+ T& operator()(T& t)
+ {
+ return t.next_level.back();
+ }
+};
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+template <>
+struct test_mri_element<boost::slistS>
+{
+ template <typename T>
+ T& operator()(T& t)
+ {
+ return t.next_level.front();
+ }
+};
+
+template <>
+struct test_mri_element<boost::stable_vecS>
+{
+ template <typename T>
+ T& operator()(T& t)
+ {
+ return *(t.next_level.begin() + t.next_level.size() - 1);
+ }
+};
+#endif
+
+template <typename Selector>
+void test_emplace_function_gen_recursive()
+{
+ test_recursive_data<Selector> top;
+ typename boost::emplace_function_gen<Selector>::type emplacer;
+
+ test_emplacer_recursive(emplacer, top);
+ test_emplacer_recursive(emplacer, top, "sol");
+
+ {
+ test_recursive_data<Selector>& t = test_mri_element<Selector>()(top);
+ test_emplacer_recursive(emplacer, t, "sol", 42);
+ }
+
+ {
+ test_recursive_data<Selector>& t = test_mri_element<Selector>()(top);
+ test_emplacer_recursive(emplacer, t, "sol", 42, 'X');
+ }
+
+ test_emplacer_recursive(emplacer, top, "sol", 42, 'X', true);
+}
+
+template <typename Pair1, typename Pair2>
+void test_emplace_results(Pair1 const& p1, Pair2 const& p2)
+{
+ BOOST_CHECK(p1.second == p2.second);
+
+ if (p1.second)
+ {
+ BOOST_CHECK(*p1.first == *p2.first);
+ }
+}
+
+template <typename Selector1, typename Selector2>
+void test_emplace_function_gens()
+{
+ typename boost::container_gen<Selector1,test_string>::type container_1;
+ typename boost::container_gen<Selector2,test_string>::type container_2;
+ typename boost::emplace_function_gen<Selector1>::type emplacer_1;
+ typename boost::emplace_function_gen<Selector2>::type emplacer_2;
+
+ test_emplace_results(
+ emplacer_1(container_1, "able")
+ , emplacer_2(container_2, "able")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "fox")
+ , emplacer_2(container_2, "fox")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "easy")
+ , emplacer_2(container_2, "easy")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "baker")
+ , emplacer_2(container_2, "baker")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "charlie")
+ , emplacer_2(container_2, "charlie")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "dog")
+ , emplacer_2(container_2, "dog")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "able")
+ , emplacer_2(container_2, "able")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "fox")
+ , emplacer_2(container_2, "fox")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "easy")
+ , emplacer_2(container_2, "easy")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "baker")
+ , emplacer_2(container_2, "baker")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "charlie")
+ , emplacer_2(container_2, "charlie")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+ test_emplace_results(
+ emplacer_1(container_1, "dog")
+ , emplacer_2(container_2, "dog")
+ );
+ BOOST_CHECK(boost::range::equal(container_1, container_2));
+}
+
+#if defined BOOST_MSVC
+ #pragma warning (pop)
+#endif
+
+int test_main(int argc, char** argv)
+{
+ test_emplace_function_gen<boost::vecS>();
+ test_emplace_function_gen<boost::dequeS>();
+ test_emplace_function_gen<boost::listS>();
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION \
+ || !defined BOOST_NO_SLIST
+ test_emplace_function_gen<boost::slistS>();
+#endif
+ test_emplace_function_gen<boost::setS>();
+ test_emplace_function_gen<boost::mapS>();
+ test_emplace_function_gen<boost::multisetS>();
+ test_emplace_function_gen<boost::multimapS>();
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION || defined BOOST_HAS_HASH
+ test_emplace_function_gen<boost::hash_setS>();
+ test_emplace_function_gen<boost::hash_mapS>();
+ test_emplace_function_gen<boost::hash_multisetS>();
+ test_emplace_function_gen<boost::hash_multimapS>();
+#endif
+ test_emplace_function_gen<boost::ptr_vecS>();
+ test_emplace_function_gen<boost::ptr_dequeS>();
+ test_emplace_function_gen<boost::ptr_listS>();
+ test_emplace_function_gen<boost::ptr_setS>();
+ test_emplace_function_gen<boost::ptr_mapS>();
+ test_emplace_function_gen<boost::ptr_multisetS>();
+ test_emplace_function_gen<boost::ptr_multimapS>();
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ test_emplace_function_gen<boost::ptr_hash_setS>();
+ test_emplace_function_gen<boost::ptr_hash_mapS>();
+ test_emplace_function_gen<boost::ptr_hash_multisetS>();
+ test_emplace_function_gen<boost::ptr_hash_multimapS>();
+ test_emplace_function_gen<boost::vector_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<boost::stable_vecS>();
+ test_emplace_function_gen<boost::deque_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<boost::list_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<boost::set_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<boost::map_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<boost::multiset_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<boost::multimap_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<boost::hash_set_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<boost::hash_map_selector<boost::mpl::true_> >();
+ test_emplace_function_gen<
+ boost::hash_multiset_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gen<
+ boost::hash_multimap_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gen<boost::flat_setS>();
+ test_emplace_function_gen<boost::flat_mapS>();
+ test_emplace_function_gen<boost::flat_multisetS>();
+ test_emplace_function_gen<boost::flat_multimapS>();
+#endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+ test_emplace_function_gen_recursive<boost::ptr_vecS>();
+ test_emplace_function_gen_recursive<boost::ptr_dequeS>();
+ test_emplace_function_gen_recursive<boost::ptr_listS>();
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ test_emplace_function_gen_recursive<boost::stable_vecS>();
+ test_emplace_function_gen_recursive<
+ boost::vector_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gen_recursive<
+ boost::deque_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gen_recursive<
+ boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gen_recursive<boost::slistS>();
+#endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+ test_emplace_function_gens<boost::vecS,boost::dequeS>();
+ test_emplace_function_gens<boost::vecS,boost::listS>();
+ test_emplace_function_gens<boost::vecS,boost::ptr_vecS>();
+ test_emplace_function_gens<boost::vecS,boost::ptr_dequeS>();
+ test_emplace_function_gens<boost::vecS,boost::ptr_listS>();
+ test_emplace_function_gens<boost::dequeS,boost::listS>();
+ test_emplace_function_gens<boost::dequeS,boost::ptr_vecS>();
+ test_emplace_function_gens<boost::dequeS,boost::ptr_dequeS>();
+ test_emplace_function_gens<boost::dequeS,boost::ptr_listS>();
+ test_emplace_function_gens<boost::listS,boost::ptr_vecS>();
+ test_emplace_function_gens<boost::listS,boost::ptr_dequeS>();
+ test_emplace_function_gens<boost::listS,boost::ptr_listS>();
+ test_emplace_function_gens<boost::ptr_vecS,boost::ptr_dequeS>();
+ test_emplace_function_gens<boost::ptr_vecS,boost::ptr_listS>();
+ test_emplace_function_gens<boost::ptr_dequeS,boost::ptr_listS>();
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ test_emplace_function_gens<boost::vecS,boost::stable_vecS>();
+ test_emplace_function_gens<boost::dequeS,boost::stable_vecS>();
+ test_emplace_function_gens<boost::listS,boost::stable_vecS>();
+ test_emplace_function_gens<boost::ptr_vecS,boost::stable_vecS>();
+ test_emplace_function_gens<boost::ptr_dequeS,boost::stable_vecS>();
+ test_emplace_function_gens<
+ boost::vecS
+ , boost::vector_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::vecS
+ , boost::deque_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::vecS
+ , boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::dequeS
+ , boost::vector_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::dequeS
+ , boost::deque_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::dequeS
+ , boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::listS
+ , boost::vector_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::listS
+ , boost::deque_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::listS
+ , boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::ptr_vecS
+ , boost::vector_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::ptr_vecS
+ , boost::deque_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::ptr_vecS
+ , boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::ptr_dequeS
+ , boost::vector_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::ptr_dequeS
+ , boost::deque_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::ptr_dequeS
+ , boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::stable_vecS
+ , boost::vector_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::stable_vecS
+ , boost::deque_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::stable_vecS
+ , boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::vector_selector<boost::mpl::true_>
+ , boost::deque_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::vector_selector<boost::mpl::true_>
+ , boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::deque_selector<boost::mpl::true_>
+ , boost::list_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<boost::setS,boost::flat_setS>();
+ test_emplace_function_gens<boost::mapS,boost::flat_mapS>();
+ test_emplace_function_gens<boost::multisetS,boost::flat_multisetS>();
+ test_emplace_function_gens<boost::multimapS,boost::flat_multimapS>();
+ test_emplace_function_gens<
+ boost::setS
+ , boost::set_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::mapS
+ , boost::map_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::multisetS
+ , boost::multiset_selector<boost::mpl::true_>
+ >();
+ test_emplace_function_gens<
+ boost::multimapS
+ , boost::multimap_selector<boost::mpl::true_>
+ >();
+#endif // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+ return 0;
+}
+
Added: sandbox/tree_node/boost/tree_node/nary_node.hpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/boost/tree_node/nary_node.hpp 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
@@ -0,0 +1,647 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_TREE_NODE_NARY_NODE_HPP_INCLUDED
+#define BOOST_TREE_NODE_NARY_NODE_HPP_INCLUDED
+
+#include <utility>
+#include <boost/config.hpp>
+#include <boost/mpl/assert.hpp>
+#include <boost/mpl/bool.hpp>
+#include <boost/noncopyable.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/container_gen/selectors.hpp>
+#include <boost/container_gen/container_gen.hpp>
+#include <boost/container_gen/emplace_function_gen.hpp>
+#include <boost/container_gen/is_recursive_selector.hpp>
+#include <boost/container_gen/has_stable_iters_selector.hpp>
+#include <boost/tree_node/preprocessor.hpp>
+#include <boost/tree_node/base.hpp>
+#include <boost/assert.hpp>
+
+#if !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#include <boost/preprocessor/repetition/enum_trailing.hpp>
+#include <boost/preprocessor/repetition/repeat.hpp>
+#endif
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#include <boost/move/move.hpp>
+#endif
+
+#include <boost/tree_node/_detail/config_begin.hpp>
+
+namespace boost { namespace tree_node {
+
+ template <typename Derived, typename T, typename Selector>
+ class nary_node_base
+ : public
+ //[reference__nary_node_base__bases
+ tree_node_base<Derived>
+ //]
+ , private ::boost::noncopyable
+ {
+ BOOST_MPL_ASSERT((::boost::is_recursive_selector<Selector>));
+
+ typedef typename ::boost::container_gen<Selector,Derived>::type
+ children;
+
+ public:
+ //[reference__nary_node_base__traits
+ struct traits
+ {
+ typedef T data_type;
+ };
+ //]
+
+ //[reference__nary_node_base__pointer
+ typedef typename tree_node_base<Derived>::pointer
+ pointer;
+ //]
+
+ //[reference__nary_node_base__const_pointer
+ typedef typename tree_node_base<Derived>::const_pointer
+ const_pointer;
+ //]
+
+ //[reference__nary_node_base__iterator
+ typedef // implementation_defined
+ //<-
+ typename children::iterator
+ //->
+ iterator;
+ //]
+
+ //[reference__nary_node_base__const_iterator
+ typedef // implementation_defined
+ //<-
+ typename children::const_iterator
+ //->
+ const_iterator;
+ //]
+
+ //[reference__nary_node_base__size_type
+ typedef // implementation_defined
+ //<-
+ typename children::size_type
+ //->
+ size_type;
+ //]
+
+ private:
+ children _children;
+ typename traits::data_type _data;
+ pointer _parent;
+
+ protected:
+ //[reference__nary_node_base__derived_copy_ctor
+ nary_node_base(Derived const& copy);
+ //]
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ nary_node_base(BOOST_RV_REF(Derived) source);
+#endif
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ //[reference__nary_node_base__emplacement_ctor
+ template <typename ...Args>
+ explicit nary_node_base(Args&& ...args);
+ //]
+#else
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_EMPLACEMENT_CTOR_FWD_DECL
+ , nary_node_base
+ )
+#endif
+
+ ~nary_node_base();
+
+ //[reference__nary_node_base__on_post_copy_or_move
+ void on_post_copy_or_move();
+ //]
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ //[reference__nary_node_base__copy_assign
+ void copy_assign(Derived const& copy);
+ //]
+#else
+ void copy_assign(BOOST_COPY_ASSIGN_REF(Derived) copy);
+
+ void move_assign(BOOST_RV_REF(Derived) source);
+#endif
+
+ public:
+ //[reference__nary_node_base__get_data__const
+ typename traits::data_type const& get_data() const;
+ //]
+
+ //[reference__nary_node_base__get_data
+ typename traits::data_type& get_data();
+ //]
+
+ //[reference__nary_node_base__get_parent_ptr__const
+ const_pointer get_parent_ptr() const;
+ //]
+
+ //[reference__nary_node_base__get_parent_ptr
+ pointer get_parent_ptr();
+ //]
+
+ //[reference__nary_node_base__insert
+ iterator insert(Derived const& child);
+ //]
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ //[reference__nary_node_base__emplace
+ template <typename ...Args>
+ iterator emplace(Args&& ...args);
+ //]
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_NARY_NODE_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_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_NARY_NODE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_NARY_NODE_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ //[reference__nary_node_base__begin__const
+ const_iterator begin() const;
+ //]
+
+ //[reference__nary_node_base__begin
+ iterator begin();
+ //]
+
+ //[reference__nary_node_base__end__const
+ const_iterator end() const;
+ //]
+
+ //[reference__nary_node_base__end
+ iterator end();
+ //]
+
+ //[reference__nary_node_base__size
+ size_type size() const;
+ //]
+
+ //[reference__nary_node_base__empty
+ bool empty() const;
+ //]
+
+ //[reference__nary_node_base__clear
+ void clear();
+ //]
+
+ private:
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename ...Args>
+ iterator _add_child(Args&& ...args);
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_NARY_NODE_MACRO(z, n, _) \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ iterator \
+ _add_child( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ); \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_NARY_NODE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_NARY_NODE_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ void _initialize(iterator& to_child);
+
+ void _link_children_to_parent();
+ };
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>::nary_node_base(Derived const& copy)
+ : _children(copy._children)
+ , _data(copy.get_data())
+ , _parent(copy._parent)
+ {
+ }
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>::nary_node_base(
+ BOOST_RV_REF(Derived) source
+ ) : _children(::boost::move(source._children))
+ , _data(::boost::move(source._data))
+ , _parent(source._parent)
+ {
+ }
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename Derived, typename T, typename Selector>
+ template <typename ...Args>
+ nary_node_base<Derived,T,Selector>::nary_node_base(Args&& ...args)
+ : _children(), _data(::boost::forward<Args>(args)...), _parent()
+ {
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_NARY_NODE_MACRO(z, n, _) \
+ template <typename Derived, typename T, typename Selector> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ nary_node_base<Derived,T,Selector>::nary_node_base( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) : _children() \
+ , _data( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ) \
+ , _parent() \
+ { \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_NARY_NODE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_NARY_NODE_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template <typename Derived, typename T, typename Selector>
+ nary_node_base<Derived,T,Selector>::~nary_node_base()
+ {
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline void nary_node_base<Derived,T,Selector>::on_post_copy_or_move()
+ {
+ this->_link_children_to_parent();
+ }
+
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <typename Derived, typename T, typename Selector>
+ void nary_node_base<Derived,T,Selector>::copy_assign(Derived const& copy)
+ {
+ Derived twin(copy);
+
+ this->_children = twin._children;
+ this->_data = twin._data;
+ }
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ template <typename Derived, typename T, typename Selector>
+ void
+ nary_node_base<Derived,T,Selector>::copy_assign(
+ BOOST_COPY_ASSIGN_REF(Derived) copy
+ )
+ {
+ Derived twin(static_cast<Derived const&>(copy));
+
+ this->_children = ::boost::move(twin._children);
+ this->_data = ::boost::move(twin._data);
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline void
+ nary_node_base<Derived,T,Selector>::move_assign(
+ BOOST_RV_REF(Derived) source
+ )
+ {
+ this->_children = ::boost::move(source._children);
+ this->_data = ::boost::move(source._data);
+ }
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<
+ Derived
+ , T
+ , Selector
+ >::traits::data_type const&
+ nary_node_base<Derived,T,Selector>::get_data() const
+ {
+ return this->_data;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::traits::data_type&
+ nary_node_base<Derived,T,Selector>::get_data()
+ {
+ return this->_data;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::const_pointer
+ nary_node_base<Derived,T,Selector>::get_parent_ptr() const
+ {
+ return this->_parent;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::pointer
+ nary_node_base<Derived,T,Selector>::get_parent_ptr()
+ {
+ return this->_parent;
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::insert(Derived const& child)
+ {
+#if defined BOOST_MSVC
+ Derived twin(child);
+ iterator result(this->_add_child(twin));
+#else
+ iterator result(this->_add_child(Derived(child)));
+#endif
+ BOOST_ASSERT((*result)._parent == this->get_derived());
+ return result;
+ }
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename Derived, typename T, typename Selector>
+ template <typename ...Args>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::emplace(Args&& ...args)
+ {
+ iterator result(this->_add_child(::boost::forward<Args>(args)...));
+ BOOST_ASSERT((*result)._parent == this->get_derived());
+ return result;
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_NARY_NODE_MACRO(z, n, _) \
+ template <typename Derived, typename T, typename Selector> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ inline typename nary_node_base<Derived,T,Selector>::iterator \
+ nary_node_base<Derived,T,Selector>::emplace( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ iterator result = this->_add_child( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ BOOST_ASSERT((*result)._parent == this->get_derived()); \
+ return result; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_NARY_NODE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_NARY_NODE_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::const_iterator
+ nary_node_base<Derived,T,Selector>::begin() const
+ {
+ return this->_children.begin();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::begin()
+ {
+ return this->_children.begin();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::const_iterator
+ nary_node_base<Derived,T,Selector>::end() const
+ {
+ return this->_children.end();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::end()
+ {
+ return this->_children.end();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline typename nary_node_base<Derived,T,Selector>::size_type
+ nary_node_base<Derived,T,Selector>::size() const
+ {
+ return this->_children.size();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline bool nary_node_base<Derived,T,Selector>::empty() const
+ {
+ return this->_children.empty();
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ inline void nary_node_base<Derived,T,Selector>::clear()
+ {
+ this->_children.clear();
+ this->on_post_clear();
+ }
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename Derived, typename T, typename Selector>
+ template <typename ...Args>
+ inline typename nary_node_base<Derived,T,Selector>::iterator
+ nary_node_base<Derived,T,Selector>::_add_child(Args&& ...args)
+ {
+ typename ::boost::emplace_function_gen<Selector>::type emplacer;
+ ::std::pair<iterator,bool> p = emplacer(
+ this->_children
+ , ::boost::forward<Args>(args)...
+ );
+
+ if (p.second)
+ {
+ this->_initialize(p.first);
+ }
+
+ return p.first;
+ }
+#else // !defined BOOST_CONTAINER_PERFECT_FORWARDING
+#define BOOST_TREE_NODE_NARY_NODE_MACRO(z, n, _) \
+ template <typename Derived, typename T, typename Selector> \
+ BOOST_PP_EXPR_IF(n, template <) \
+ BOOST_PP_ENUM_PARAMS_Z(z, n, typename P) \
+ BOOST_PP_EXPR_IF(n, >) \
+ inline typename nary_node_base<Derived,T,Selector>::iterator \
+ nary_node_base<Derived,T,Selector>::_add_child( \
+ BOOST_PP_CAT(BOOST_PP_ENUM_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_LIST \
+ , _ \
+ ) \
+ ) \
+ { \
+ typename ::boost::emplace_function_gen<Selector>::type emplacer; \
+ ::std::pair<iterator,bool> p = emplacer( \
+ this->_children \
+ BOOST_PP_CAT(BOOST_PP_ENUM_TRAILING_, z)( \
+ n \
+ , BOOST_CONTAINER_PP_PARAM_FORWARD \
+ , _ \
+ ) \
+ ); \
+ if (p.second) \
+ { \
+ this->_initialize(p.first); \
+ } \
+ return p.first; \
+ } \
+//!
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_NARY_NODE_MACRO
+ , _
+ )
+#undef BOOST_TREE_NODE_NARY_NODE_MACRO
+#endif // BOOST_CONTAINER_PERFECT_FORWARDING
+
+ template <typename Derived, typename T, typename Selector>
+ inline void
+ nary_node_base<Derived,T,Selector>::_initialize(iterator& to_child)
+ {
+ (*to_child)._parent = this->get_derived();
+ (*to_child).on_post_inserted(
+ to_child
+ , ::boost::has_stable_iterators_selector<Selector>()
+ );
+ }
+
+ template <typename Derived, typename T, typename Selector>
+ void nary_node_base<Derived,T,Selector>::_link_children_to_parent()
+ {
+ iterator itr_end = this->end();
+
+ for (iterator itr = this->begin(); itr != itr_end; ++itr)
+ {
+ (*itr)._parent = this->get_derived();
+ }
+ }
+}} // namespace boost::tree_node
+
+namespace boost { namespace tree_node {
+
+ template <typename T, typename Selector = ::boost::ptr_dequeS>
+ class nary_node
+ : public
+ //[reference__nary_node__bases
+ nary_node_base<nary_node<T,Selector>,T,Selector>
+ //]
+ {
+ //[reference__nary_node__super_t
+ typedef nary_node_base<nary_node,T,Selector> super_t;
+ //]
+
+ public:
+ //[reference__nary_node__traits
+ typedef typename super_t::traits traits;
+ //]
+
+ //[reference__nary_node__pointer
+ typedef typename super_t::pointer pointer;
+ //]
+
+ //[reference__nary_node__const_pointer
+ typedef typename super_t::const_pointer const_pointer;
+ //]
+
+ //[reference__nary_node__iterator
+ typedef typename super_t::iterator iterator;
+ //]
+
+ //[reference__nary_node__const_iterator
+ typedef typename super_t::const_iterator const_iterator;
+ //]
+
+ //[reference__nary_node__size_type
+ typedef typename super_t::size_type size_type;
+ //]
+
+ BOOST_TREE_NODE_COPYABLE_AND_MOVABLE(nary_node, super_t)
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ //[reference__nary_node__emplacement_ctor
+ template <typename ...Args>
+ explicit nary_node(Args&& ...args);
+ //]
+#else
+ BOOST_PP_REPEAT(
+ BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS
+ , BOOST_TREE_NODE_EMPLACEMENT_CTOR_INLINE_DEF
+ , (nary_node, super_t)
+ )
+#endif
+ };
+
+#if defined BOOST_CONTAINER_PERFECT_FORWARDING
+ template <typename T, typename Selector>
+ template <typename ...Args>
+ inline nary_node<T,Selector>::nary_node(Args&& ...args)
+ : super_t(::boost::forward<Args>(args)...)
+ {
+ }
+#endif
+}} // namespace boost::tree_node
+
+//[reference__nary_node_gen
+namespace boost { namespace tree_node {
+
+ template <typename Selector = ::boost::ptr_dequeS>
+ struct nary_node_gen
+ {
+ template <typename Derived, typename T>
+ struct apply
+ {
+ typedef nary_node_base<Derived,T,Selector> type;
+ };
+ };
+
+ typedef nary_node_gen<> nary_node_default_gen;
+}} // namespace boost::tree_node
+//]
+
+#include <boost/tree_node/_detail/config_end.hpp>
+
+#endif // BOOST_TREE_NODE_NARY_NODE_HPP_INCLUDED
+
Added: sandbox/tree_node/libs/tree_node/example/nary_node.cpp
==============================================================================
--- (empty file)
+++ sandbox/tree_node/libs/tree_node/example/nary_node.cpp 2012-11-08 00:18:13 EST (Thu, 08 Nov 2012)
@@ -0,0 +1,266 @@
+// Copyright (C) 2011-2012 Cromwell D. Enage
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#define BOOST_TYPEOF_COMPLIANT
+
+#include <iostream>
+#include <iterator>
+#include <boost/config.hpp>
+#include <boost/assert.hpp>
+#include <boost/typeof/typeof.hpp>
+#include <boost/tr1/type_traits.hpp>
+#include <boost/container_gen/selectors_typeof.hpp>
+#include <boost/tree_node/typeof/nary_node.hpp>
+#include <boost/tree_node/typeof/with_count.hpp>
+#include <boost/tree_node/typeof/with_height.hpp>
+#include <boost/tree_node/typeof/with_position.hpp>
+#include <boost/tree_node/typeof/breadth_first_iterator.hpp>
+#include <boost/tree_node/typeof/pre_order_desc_iterator.hpp>
+#include <boost/tree_node/typeof/post_order_iterator.hpp>
+#include "default_unconstruct_type.hpp"
+#include "show_functions.hpp"
+#include "showcase_iterators.hpp"
+
+template <typename Selector>
+void example()
+{
+ typedef boost::tree_node::nary_node<
+ default_unconstructible_example_type
+ , Selector
+ >
+ DNode;
+ typedef boost::tree_node::with_height<
+ boost::tree_node::with_count_gen<
+ boost::tree_node::with_position_gen<
+ boost::tree_node::nary_node_gen<Selector>
+ >
+ >
+ , char*
+ >
+ ANode;
+
+ DNode d_root(5);
+ ANode a_root;
+
+ BOOST_ASSERT_MSG(
+ !d_root.get_parent_ptr()
+ , "Parent member uninitialized."
+ );
+ BOOST_ASSERT_MSG(
+ !a_root.get_data()
+ , "Data member not default-constructed."
+ );
+
+ for (
+ BOOST_AUTO_TPL(
+ itr
+ , boost::tree_node::make_breadth_first_iterator(d_root)
+ );
+ itr;
+ ++itr
+ )
+ {
+ std::size_t const count = (*itr).get_data().number;
+
+ if (1 < count)
+ {
+ for (std::size_t i = 0; i < count; ++i)
+ {
+ typename DNode::iterator child_itr((*itr).emplace(i));
+ typename DNode::const_pointer const_child(&*child_itr);
+
+ BOOST_ASSERT_MSG(
+ ((*child_itr).get_parent_ptr() == &*itr)
+ , "Ctor not linking child to parent."
+ );
+ BOOST_ASSERT_MSG(
+ (
+ (*child_itr).get_parent_ptr()
+ == const_child->get_parent_ptr()
+ )
+ , "Why are these pointers different?"
+ );
+
+ {
+ typename DNode::iterator c_itr((*itr).begin());
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ if (!std::tr1::is_same<Selector,boost::slistS>::value)
+#endif
+ std::advance(c_itr, i);
+ BOOST_ASSERT_MSG(
+ (&*child_itr == &*c_itr)
+ , "Ctor not linking parent to child."
+ );
+ }
+ }
+ }
+ }
+
+ std::cout << "After d_root tree construction," << std::endl;
+ showcase_iterators(d_root, show_number<DNode>, show_number_tree());
+
+ {
+ DNode d_copy(d_root);
+
+ std::cout << "After d_copy construction," << std::endl;
+ showcase_iterators(d_copy, show_number<DNode>, show_number_tree());
+ }
+
+ {
+ typename DNode::iterator d_child(
+ (*(++(++d_root.begin()))).insert(d_root)
+ );
+
+ std::cout << "After insert call," << std::endl;
+ showcase_iterators(d_root, show_number<DNode>, show_number_tree());
+
+ d_root = *d_child;
+ std::cout << "After assignment to descendant," << std::endl;
+ showcase_iterators(d_root, show_number<DNode>, show_number_tree());
+ }
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ if (!std::tr1::is_same<Selector,boost::slistS>::value)
+ *(d_root.begin()) = d_root;
+ else
+#endif
+ *(++(++(++(++d_root.begin())))) = d_root;
+ std::cout << "After assignment to ancestor," << std::endl;
+ showcase_iterators(d_root, show_number<DNode>, show_number_tree());
+
+ {
+ char* root_data = new char[2];
+
+ root_data[0] = '5';
+ root_data[1] = '\0';
+ a_root.get_data() = root_data;
+ }
+
+ for (
+ BOOST_AUTO_TPL(
+ itr
+ , boost::tree_node::make_breadth_first_iterator(a_root)
+ );
+ itr;
+ ++itr
+ )
+ {
+ char digit = (*itr).get_data()[0];
+
+ if ('1' < digit)
+ {
+ char numchar = digit;
+
+ while (numchar != '0')
+ {
+ typename ANode::iterator child_itr((*itr).insert(ANode()));
+ char*& data = (*child_itr).get_data();
+
+ BOOST_ASSERT_MSG(
+ !data
+ , "Data member not default-constructed."
+ );
+ data = new char[2];
+ data[0] = --numchar;
+ data[1] = '\0';
+ BOOST_ASSERT_MSG(
+ ((*child_itr).get_parent_ptr() == &*itr)
+ , "Ctor not linking child to parent."
+ );
+ BOOST_ASSERT_MSG(
+ ((*child_itr).get_position() == child_itr)
+ , "Position iterator incorrect."
+ );
+
+ {
+ typename ANode::iterator c_itr = (*itr).begin();
+
+#if !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ if (!std::tr1::is_same<Selector,boost::slistS>::value)
+#endif
+ std::advance(c_itr, digit - (numchar + 1));
+ BOOST_ASSERT_MSG(
+ (child_itr == c_itr)
+ , "Ctor not linking parent to child."
+ );
+ }
+ }
+ }
+ }
+
+ std::cout << "After a_root tree construction," << std::endl;
+ showcase_iterators(a_root, show_data<ANode>, show_data_tree());
+
+ {
+ typename ANode::iterator a_child_itr(
+ (*(++(++a_root.begin()))).emplace()
+ );
+
+ (*a_child_itr).get_data() = new char[2];
+ (*a_child_itr).get_data()[0] = '7';
+ (*a_child_itr).get_data()[1] = '\0';
+ BOOST_ASSERT_MSG(
+ ((*a_child_itr).get_position() == a_child_itr)
+ , "Position iterator incorrect."
+ );
+ std::cout << "After emplace call," << std::endl;
+ showcase_iterators(a_root, show_data<ANode>, show_data_tree());
+ }
+
+ {
+ typename ANode::iterator leaf = a_root.begin();
+
+ for (
+ BOOST_AUTO_TPL(
+ itr
+ , boost::tree_node::make_pre_order_descendant_iterator(*leaf)
+ );
+ itr;
+ ++itr
+ )
+ {
+ delete[] (*itr).get_data();
+ }
+
+ (*leaf).clear();
+ std::cout << "After clear call," << std::endl;
+ showcase_iterators(a_root, show_data<ANode>, show_data_tree());
+ }
+
+ for (
+ BOOST_AUTO_TPL(
+ itr
+ , boost::tree_node::make_post_order_iterator(a_root)
+ );
+ itr;
+ ++itr
+ )
+ {
+ delete[] (*itr).get_data();
+ }
+}
+
+#if defined BOOST_TYPEOF_EMULATION
+#include <boost/container_gen/selectors_typeof.hpp>
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#include <boost/typeof/boost/ptr_container/ptr_vector.hpp>
+#else // !defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#include <boost/typeof/boost/container/slist.hpp>
+#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+#else // !defined BOOST_TYPEOF_EMULATION
+#include <boost/container_gen/selectors.hpp>
+#endif // BOOST_TYPEOF_EMULATION
+
+int main()
+{
+#if defined BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
+ example<boost::ptr_vecS>();
+#else
+ example<boost::slistS>();
+#endif
+ return 0;
+}
+