bimap/detail/bimap_core.hpp

0001 // Boost.Bimap
0002 //
0003 // Copyright (c) 2006-2007 Matias Capeletto
0004 //
0005 // Distributed under the Boost Software License, Version 1.0.
0006 // (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 /// \file detail/bimap_core.hpp
0010 /// \brief Bimap base definition.
0011
0012 #ifndef BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP
0013 #define BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP
0014
0015 #if defined(_MSC_VER)
0016 #pragma once
0017 #endif
0018
0019 #include <boost/config.hpp>
0020
0021 #include <boost/mpl/placeholders.hpp>
0022 #include <boost/mpl/push_front.hpp>
0023 #include <boost/mpl/if.hpp>
0024 #include <boost/mpl/and.hpp>
0025 #include <boost/mpl/not.hpp>
0026 #include <boost/mpl/vector.hpp>
0027
0028 #include <boost/type_traits/add_const.hpp>
0029 #include <boost/type_traits/is_same.hpp>
0030
0031 #include <boost/concept_check.hpp>
0032
0033 // Boost.MultiIndex
0034 #include <boost/multi_index_container.hpp>
0035 #include <boost/multi_index/member.hpp>
0036
0037 // Boost.Bimap
0038 #include <boost/bimap/relation/mutant_relation.hpp>
0039 #include <boost/bimap/relation/member_at.hpp>
0040 #include <boost/bimap/relation/support/data_extractor.hpp>
0041 #include <boost/bimap/tags/support/default_tagged.hpp>
0042 #include <boost/bimap/tags/tagged.hpp>
0043 #include <boost/bimap/detail/manage_bimap_key.hpp>
0044 #include <boost/bimap/detail/manage_additional_parameters.hpp>
0045 #include <boost/bimap/detail/map_view_iterator.hpp>
0046 #include <boost/bimap/detail/set_view_iterator.hpp>
0047
0048 #include <boost/bimap/set_of.hpp>
0049 #include <boost/bimap/unconstrained_set_of.hpp>
0050 #include <boost/core/allocator_access.hpp>
0051
0052 namespace boost {
0053 namespace bimaps {
0054
0055 /// \brief Library details
0056
0057 namespace detail {
0058
0059 #ifndef BOOST_BIMAP_DOXYGEN_WILL_NOT_PROCESS_THE_FOLLOWING_LINES
0060
0061 template< class Type >
0062 struct get_value_type
0063 {
0064     typedef BOOST_DEDUCED_TYPENAME Type::value_type type;
0065 };
0066
0067 struct independent_index_tag {};
0068
0069 #endif // BOOST_BIMAP_DOXYGEN_WILL_NOT_PROCESS_THE_FOLLOWING_LINES
0070
0071
0072 /// \brief Base for the bimap class.
0073 /**
0074
0075
0076 See also bimap.
0077                                                                         **/
0078
0079
0080 template< class LeftSetType, class RightSetType, class AP1, class AP2, class AP3 >
0081 class bimap_core
0082 {
0083     // Manage bimap key instantiation
0084     // --------------------------------------------------------------------
0085     public:
0086
0087     typedef BOOST_DEDUCED_TYPENAME manage_bimap_key
0088     <
0089         LeftSetType
0090
0091     >::type left_set_type;
0092
0093     typedef BOOST_DEDUCED_TYPENAME manage_bimap_key
0094     <
0095         RightSetType
0096
0097     >::type right_set_type;
0098
0099
0100     private:
0101
0102     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::tags::support::default_tagged
0103     <
0104         BOOST_DEDUCED_TYPENAME left_set_type::user_type,
0105         ::boost::bimaps::relation::member_at::left
0106
0107     >::type left_tagged_type;
0108
0109     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::tags::support::default_tagged
0110     <
0111         BOOST_DEDUCED_TYPENAME right_set_type::user_type,
0112         ::boost::bimaps::relation::member_at::right
0113
0114     >::type right_tagged_type;
0115
0116     public:
0117
0118     //@{
0119
0120         typedef BOOST_DEDUCED_TYPENAME  left_tagged_type::tag  left_tag;
0121         typedef BOOST_DEDUCED_TYPENAME right_tagged_type::tag right_tag;
0122
0123     //@}
0124
0125     //@{
0126
0127         typedef BOOST_DEDUCED_TYPENAME  left_set_type::value_type  left_key_type;
0128         typedef BOOST_DEDUCED_TYPENAME right_set_type::value_type right_key_type;
0129
0130     //@}
0131
0132     //@{
0133
0134         typedef right_key_type  left_data_type;
0135         typedef  left_key_type right_data_type;
0136
0137     //@}
0138
0139     // Manage the additional parameters
0140     // --------------------------------------------------------------------
0141     private:
0142
0143     typedef BOOST_DEDUCED_TYPENAME manage_additional_parameters<AP1,AP2,AP3>::type parameters;
0144
0145     /// \brief Relation type stored by the bimap.
0146     // --------------------------------------------------------------------
0147     public:
0148
0149     typedef ::boost::bimaps::relation::mutant_relation
0150     <
0151
0152         ::boost::bimaps::tags::tagged<
0153             BOOST_DEDUCED_TYPENAME mpl::if_<
0154                 mpl::and_
0155                 <
0156                     BOOST_DEDUCED_TYPENAME left_set_type::mutable_key,
0157                     BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation::left_mutable_key
0158                 >,
0159             // {
0160                     left_key_type,
0161             // }
0162             // else
0163             // {
0164                     BOOST_DEDUCED_TYPENAME ::boost::add_const< left_key_type >::type
0165             // }
0166
0167             >::type,
0168             left_tag
0169         >,
0170
0171         ::boost::bimaps::tags::tagged<
0172             BOOST_DEDUCED_TYPENAME mpl::if_<
0173                 mpl::and_
0174                 <
0175                     BOOST_DEDUCED_TYPENAME right_set_type::mutable_key,
0176                     BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation::right_mutable_key
0177                 >,
0178             // {
0179                     right_key_type,
0180             // }
0181             // else
0182             // {
0183                     BOOST_DEDUCED_TYPENAME ::boost::add_const< right_key_type >::type
0184             // }
0185
0186             >::type,
0187             right_tag
0188         >,
0189
0190         // It is ::boost::mpl::na if no info_hook was included
0191         BOOST_DEDUCED_TYPENAME parameters::additional_info,
0192
0193         // Force mutable keys
0194         true
0195
0196     > relation;
0197
0198     //@{
0199
0200         typedef BOOST_DEDUCED_TYPENAME relation::left_pair  left_value_type;
0201         typedef BOOST_DEDUCED_TYPENAME relation::right_pair right_value_type;
0202
0203     //@}
0204
0205     // Bind the member of the relation, so multi_index can manage them
0206     // --------------------------------------------------------------------
0207     private:
0208
0209     typedef BOOST_DEDUCED_TYPENAME relation::storage_base relation_storage_base;
0210
0211     typedef BOOST_MULTI_INDEX_MEMBER(relation_storage_base, left_key_type, left)
0212         left_member_extractor;
0213
0214     typedef BOOST_MULTI_INDEX_MEMBER(relation_storage_base,right_key_type,right)
0215         right_member_extractor;
0216
0217     // The core indices are somewhat complicated to calculate, because they
0218     // can be zero, one, two or three indices, depending on the use of
0219     // {side}_based set type of relations and unconstrained_set_of and
0220     // unconstrained_set_of_relation specifications.
0221
0222     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
0223         ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
0224     // {
0225             mpl::vector<>,
0226     // }
0227     // else
0228     // {
0229             mpl::vector
0230             <
0231                 BOOST_DEDUCED_TYPENAME left_set_type::
0232                 BOOST_NESTED_TEMPLATE index_bind
0233                 <
0234                     left_member_extractor,
0235                     left_tag
0236
0237                 >::type
0238             >
0239     // }
0240     >::type left_core_indices;
0241
0242     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
0243         ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
0244     // {
0245             left_core_indices,
0246     // }
0247     // else
0248     // {
0249             BOOST_DEDUCED_TYPENAME mpl::push_front
0250             <
0251                 left_core_indices,
0252
0253                 BOOST_DEDUCED_TYPENAME right_set_type::
0254                 BOOST_NESTED_TEMPLATE index_bind
0255                 <
0256                     right_member_extractor,
0257                     right_tag
0258
0259                 >::type
0260
0261             >::type
0262     // }
0263     >::type basic_core_indices;
0264
0265     // If it is based either on the left or on the right, then only the side
0266     // indices are needed. But the set type of the relation can be completely
0267     // different from the one used for the sides in which case we have to add yet
0268     // another index to the core.
0269
0270     // TODO
0271     // If all the set types are unsconstrained there must be readable compile
0272     // time error.
0273
0274     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
0275
0276         is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, left_based >,
0277     // {
0278             ::boost::bimaps::tags::tagged< left_set_type, left_tag >,
0279     // }
0280     /* else */ BOOST_DEDUCED_TYPENAME mpl::if_<
0281             is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, right_based >,
0282     // {
0283             ::boost::bimaps::tags::tagged< right_set_type, right_tag >,
0284     // }
0285     // else
0286     // {
0287             tags::tagged
0288             <
0289                 BOOST_DEDUCED_TYPENAME parameters::
0290                 set_type_of_relation::BOOST_NESTED_TEMPLATE bind_to
0291                 <
0292                     relation
0293
0294                 >::type,
0295                 independent_index_tag
0296             >
0297     // }
0298     >::type
0299     >::type tagged_set_of_relation_type;
0300
0301     protected:
0302
0303     typedef BOOST_DEDUCED_TYPENAME tagged_set_of_relation_type::tag
0304                         relation_set_tag;
0305
0306     typedef BOOST_DEDUCED_TYPENAME tagged_set_of_relation_type::value_type
0307                         relation_set_type_of;
0308
0309     // Logic tags
0310     // This is a necessary extra level of indirection to allow unconstrained
0311     // sets to be plug in the design. The bimap constructors use this logic
0312     // tags.
0313
0314     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
0315         ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
0316
0317         BOOST_DEDUCED_TYPENAME mpl::if_<
0318             ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
0319
0320             independent_index_tag,
0321             right_tag
0322
0323         >::type,
0324
0325         left_tag
0326
0327     >::type logic_left_tag;
0328
0329     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
0330         ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
0331
0332         BOOST_DEDUCED_TYPENAME mpl::if_<
0333             ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
0334
0335             independent_index_tag,
0336             left_tag
0337
0338         >::type,
0339
0340         right_tag
0341
0342     >::type logic_right_tag;
0343
0344     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
0345         is_same< relation_set_tag, independent_index_tag >,
0346
0347         BOOST_DEDUCED_TYPENAME mpl::if_<
0348             ::boost::bimaps::detail::
0349                 is_unconstrained_set_of< relation_set_type_of >,
0350
0351             logic_left_tag,
0352             independent_index_tag
0353
0354         >::type,
0355
0356         BOOST_DEDUCED_TYPENAME mpl::if_<
0357             is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, left_based >,
0358
0359             logic_left_tag,
0360             logic_right_tag
0361
0362         >::type
0363
0364     >::type logic_relation_set_tag;
0365
0366     private:
0367
0368     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
0369         mpl::and_< is_same< relation_set_tag, independent_index_tag >,
0370                    mpl::not_<
0371                        ::boost::bimaps::detail::
0372                             is_unconstrained_set_of< relation_set_type_of >
0373                    >
0374         >,
0375     // {
0376             BOOST_DEDUCED_TYPENAME mpl::push_front
0377             <
0378                 basic_core_indices,
0379
0380                 BOOST_DEDUCED_TYPENAME relation_set_type_of::
0381                 BOOST_NESTED_TEMPLATE index_bind
0382                 <
0383                     ::boost::bimaps::relation::support::both_keys_extractor<relation>,
0384                     independent_index_tag
0385
0386                 >::type
0387
0388             >::type,
0389     // }
0390     // else
0391     // {
0392             basic_core_indices
0393     // }
0394
0395     >::type complete_core_indices;
0396
0397     struct core_indices : public complete_core_indices {};
0398
0399     // Define the core using compute_index_type to translate the
0400     // set type to an multi-index specification
0401     // --------------------------------------------------------------------
0402     public:
0403
0404     typedef multi_index::multi_index_container
0405     <
0406         relation,
0407         core_indices,
0408         BOOST_DEDUCED_TYPENAME boost::allocator_rebind<BOOST_DEDUCED_TYPENAME
0409             parameters::allocator, relation>::type
0410
0411     > core_type;
0412
0413     // Core metadata
0414     // --------------------------------------------------------------------
0415     public:
0416
0417     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::
0418         index<core_type, logic_left_tag>::type  left_index;
0419
0420     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::
0421         index<core_type,logic_right_tag>::type right_index;
0422
0423     typedef BOOST_DEDUCED_TYPENAME  left_index::iterator        left_core_iterator;
0424     typedef BOOST_DEDUCED_TYPENAME  left_index::const_iterator  left_core_const_iterator;
0425
0426     typedef BOOST_DEDUCED_TYPENAME right_index::iterator       right_core_iterator;
0427     typedef BOOST_DEDUCED_TYPENAME right_index::const_iterator right_core_const_iterator;
0428
0429     // Relation set view
0430
0431     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::index
0432     <
0433         core_type, logic_relation_set_tag
0434
0435     >::type relation_set_core_index;
0436
0437     typedef BOOST_DEDUCED_TYPENAME relation_set_type_of::
0438     BOOST_NESTED_TEMPLATE set_view_bind
0439     <
0440         relation_set_core_index
0441
0442     >::type relation_set;
0443
0444     public:
0445
0446     typedef bimap_core bimap_core_;
0447 };
0448
0449 // Two auxiliary metafunctions to compute the map view types
0450 // The map view type can not be computed inside the bimap core because a
0451 // they need the bimap core to be parsed first.
0452
0453 template< class BimapBaseType >
0454 struct left_map_view_type
0455 {
0456     typedef BOOST_DEDUCED_TYPENAME BimapBaseType::left_set_type left_set_type;
0457     typedef BOOST_DEDUCED_TYPENAME
0458         left_set_type::BOOST_NESTED_TEMPLATE map_view_bind<
0459             BOOST_DEDUCED_TYPENAME BimapBaseType::left_tag, BimapBaseType
0460         >::type type;
0461 };
0462
0463 template< class BimapBaseType >
0464 struct right_map_view_type
0465 {
0466     typedef BOOST_DEDUCED_TYPENAME BimapBaseType::right_set_type right_set_type;
0467     typedef BOOST_DEDUCED_TYPENAME
0468         right_set_type::BOOST_NESTED_TEMPLATE map_view_bind<
0469             BOOST_DEDUCED_TYPENAME BimapBaseType::right_tag, BimapBaseType
0470         >::type type;
0471 };
0472
0473
0474 } // namespace detail
0475 } // namespace bimaps
0476 } // namespace boost
0477
0478 #endif // BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP