00001 // Boost.Bimap
00002 //
00003 // Copyright (c) 2006-2007 Matias Capeletto
00004 //
00005 // Distributed under the Boost Software License, Version 1.0.
00006 // (See accompanying file LICENSE_1_0.txt or copy at
00007 // http://www.boost.org/LICENSE_1_0.txt)
00008 
00009 /// \file detail/bimap_core.hpp
00010 /// \brief Bimap base definition.
00011 
00012 #ifndef BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP
00013 #define BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP
00014 
00015 #if defined(_MSC_VER) && (_MSC_VER>=1200)
00016 #pragma once
00017 #endif
00018 
00019 #include <boost/config.hpp>
00020 
00021 // Boost.MPL
00022 #include <boost/mpl/placeholders.hpp>
00023 #include <boost/mpl/push_front.hpp>
00024 #include <boost/mpl/if.hpp>
00025 #include <boost/mpl/and.hpp>
00026 #include <boost/mpl/not.hpp>
00027 #include <boost/mpl/vector.hpp>
00028 
00029 #include <boost/type_traits/add_const.hpp>
00030 #include <boost/type_traits/is_same.hpp>
00031 
00032 // Boost.MultiIndex
00033 #include <boost/multi_index_container.hpp>
00034 #include <boost/multi_index/member.hpp>
00035 
00036 // Boost.Bimap.Relation
00037 #include <boost/bimap/relation/relation.hpp>
00038 #include <boost/bimap/relation/member_at.hpp>
00039 
00040 // Boost.Bimap.Tags
00041 #include <boost/bimap/tags/support/apply_to_value_type.hpp>
00042 
00043 // Boost.Bimap
00044 #include <boost/bimap/detail/manage_bimap_key.hpp>
00045 #include <boost/bimap/detail/manage_additional_parameters.hpp>
00046 #include <boost/bimap/detail/map_view_iterator.hpp>
00047 #include <boost/bimap/detail/set_view_iterator.hpp>
00048 
00049 #include <boost/bimap/set_of.hpp>
00050 #include <boost/bimap/unconstrained_set_of.hpp>
00051 
00052 namespace boost {
00053 namespace bimaps {
00054 
00055 /// \brief Library details
00056 
00057 namespace detail {
00058 
00059 #ifndef BOOST_BIMAP_DOXYGEN_WILL_NOT_PROCESS_THE_FOLLOWING_LINES
00060 
00061 template< class Type >
00062 struct get_value_type
00063 {
00064     typedef BOOST_DEDUCED_TYPENAME Type::value_type type;
00065 };
00066 
00067 struct independent_index_tag {};
00068 
00069 #endif // BOOST_BIMAP_DOXYGEN_WILL_NOT_PROCESS_THE_FOLLOWING_LINES
00070 
00071 
00072 /// \brief Base for the bimap class.
00073 /**
00074 
00075 
00076 See also bimap.
00077                                                                         **/
00078 
00079 
00080 template< class LeftSetType, class RightSetType, class AP1, class AP2, class AP3 >
00081 struct bimap_core
00082 {
00083     // Manage bimap key instantiation
00084     // --------------------------------------------------------------------
00085     private:
00086 
00087     typedef BOOST_DEDUCED_TYPENAME manage_bimap_key
00088     <
00089         LeftSetType,
00090         ::boost::bimaps::relation::member_at::left
00091 
00092     >::type left_tagged_set_type;
00093 
00094     typedef BOOST_DEDUCED_TYPENAME manage_bimap_key
00095     <
00096         RightSetType,
00097         ::boost::bimaps::relation::member_at::right
00098 
00099     >::type right_tagged_set_type;
00100 
00101     // Construct the relation type to be used
00102     // --------------------------------------------------------------------
00103     public:
00104 
00105     //@{
00106 
00107         typedef BOOST_DEDUCED_TYPENAME  left_tagged_set_type::value_type  left_set_type;
00108         typedef BOOST_DEDUCED_TYPENAME right_tagged_set_type::value_type right_set_type;
00109 
00110     //@}
00111 
00112     //@{
00113 
00114         typedef BOOST_DEDUCED_TYPENAME  left_tagged_set_type::tag  left_tag;
00115         typedef BOOST_DEDUCED_TYPENAME right_tagged_set_type::tag right_tag;
00116 
00117     //@}
00118 
00119     //@{
00120 
00121         typedef BOOST_DEDUCED_TYPENAME  left_set_type::value_type  left_key_type;
00122         typedef BOOST_DEDUCED_TYPENAME right_set_type::value_type right_key_type;
00123 
00124     //@}
00125 
00126     //@{
00127 
00128         typedef right_key_type  left_data_type;
00129         typedef  left_key_type right_data_type;
00130 
00131     //@}
00132 
00133     // Manage the additional parameters
00134     // --------------------------------------------------------------------
00135     private:
00136 
00137     typedef BOOST_DEDUCED_TYPENAME manage_additional_parameters<AP1,AP2,AP3>::type parameters;
00138 
00139 
00140 
00141     /// \brief Relation type stored by the bimap.
00142     // --------------------------------------------------------------------
00143     public:
00144 
00145     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::relation::select_relation
00146     <
00147 
00148         ::boost::bimaps::tags::tagged<
00149             BOOST_DEDUCED_TYPENAME mpl::if_<
00150                 mpl::and_
00151                 <
00152                     BOOST_DEDUCED_TYPENAME left_set_type::mutable_key,
00153                     BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation::left_mutable_key
00154                 >,
00155             // {
00156                     left_key_type,
00157             // }
00158             // else
00159             // {
00160                     BOOST_DEDUCED_TYPENAME ::boost::add_const< left_key_type >::type
00161             // }
00162 
00163             >::type,
00164             left_tag
00165         >,
00166 
00167         ::boost::bimaps::tags::tagged<
00168             BOOST_DEDUCED_TYPENAME mpl::if_<
00169                 mpl::and_
00170                 <
00171                     BOOST_DEDUCED_TYPENAME right_set_type::mutable_key,
00172                     BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation::right_mutable_key
00173                 >,
00174             // {
00175                     right_key_type,
00176             // }
00177             // else
00178             // {
00179                     BOOST_DEDUCED_TYPENAME ::boost::add_const< right_key_type >::type
00180             // }
00181 
00182             >::type,
00183             right_tag
00184         >,
00185 
00186         // Force mutable keys
00187         true
00188 
00189     >::type relation;
00190 
00191     //@{
00192 
00193         typedef BOOST_DEDUCED_TYPENAME relation::left_pair  left_value_type;
00194         typedef BOOST_DEDUCED_TYPENAME relation::right_pair right_value_type;
00195 
00196     //@}
00197 
00198     // Bind the member of the relation, so multi_index can manage them
00199     // --------------------------------------------------------------------
00200     private:
00201 
00202     typedef BOOST_MULTI_INDEX_MEMBER(relation, left_key_type, left)
00203         left_member_extractor;
00204 
00205     typedef BOOST_MULTI_INDEX_MEMBER(relation,right_key_type,right)
00206         right_member_extractor;
00207 
00208     // The core indices are somewhat complicated to calculate, because they
00209     // can be zero, one, two or three indices, depending on the use of
00210     // {side}_based set type of relations and unconstrained_set_of and
00211     // unconstrained_set_of_relation specifications.
00212 
00213     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
00214         ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
00215     // {
00216             mpl::vector<>,
00217     // }
00218     // else
00219     // {
00220             mpl::vector
00221             <
00222                 BOOST_DEDUCED_TYPENAME left_set_type::
00223                 BOOST_NESTED_TEMPLATE index_bind
00224                 <
00225                     left_member_extractor,
00226                     left_tag
00227 
00228                 >::type
00229             >
00230     // }
00231     >::type left_core_indices;
00232 
00233     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
00234         ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
00235     // {
00236             left_core_indices,
00237     // }
00238     // else
00239     // {
00240             BOOST_DEDUCED_TYPENAME mpl::push_front
00241             <
00242                 left_core_indices,
00243 
00244                 BOOST_DEDUCED_TYPENAME right_set_type::
00245                 BOOST_NESTED_TEMPLATE index_bind
00246                 <
00247                     right_member_extractor,
00248                     right_tag
00249 
00250                 >::type
00251 
00252             >::type
00253     // }
00254     >::type basic_core_indices;
00255 
00256     // If it is based either on the left or on the right, then only the side
00257     // indices are needed. But the set type of the relation can be completely
00258     // diferent from the one used for the sides in wich case we have to add yet
00259     // another index to the core.
00260 
00261     // TODO
00262     // If all the set types are unsconstrained there must be readable compile
00263     // time error.
00264 
00265     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
00266 
00267         is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, left_based >,
00268     // {
00269             left_tagged_set_type,
00270     // }
00271     /* else */ BOOST_DEDUCED_TYPENAME mpl::if_<
00272             is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, right_based >,
00273     // {
00274             right_tagged_set_type,
00275     // }
00276     // else
00277     // {
00278             tags::tagged
00279             <
00280                 BOOST_DEDUCED_TYPENAME parameters::
00281                 set_type_of_relation::BOOST_NESTED_TEMPLATE bind_to
00282                 <
00283                     relation
00284 
00285                 >::type,
00286                 independent_index_tag
00287             >
00288     // }
00289     >::type
00290     >::type tagged_set_of_relation_type;
00291 
00292     protected:
00293 
00294     typedef BOOST_DEDUCED_TYPENAME tagged_set_of_relation_type::tag
00295                         relation_set_tag;
00296 
00297     typedef BOOST_DEDUCED_TYPENAME tagged_set_of_relation_type::value_type
00298                         relation_set_type_of;
00299 
00300     // Logic tags
00301     // This is a necesary extra level of indirection to allow unconstrained
00302     // sets to be plug in the design. The bimap constructors use this logic
00303     // tags.
00304 
00305     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
00306         ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
00307 
00308         BOOST_DEDUCED_TYPENAME mpl::if_<
00309             ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
00310 
00311             independent_index_tag,
00312             right_tag
00313 
00314         >::type,
00315 
00316         left_tag
00317 
00318     >::type logic_left_tag;
00319 
00320     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
00321         ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
00322 
00323         BOOST_DEDUCED_TYPENAME mpl::if_< 
00324             ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
00325 
00326             independent_index_tag,
00327             left_tag
00328 
00329         >::type,
00330 
00331         right_tag
00332 
00333     >::type logic_right_tag;
00334 
00335     typedef BOOST_DEDUCED_TYPENAME mpl::if_< 
00336         is_same< relation_set_tag, independent_index_tag >,
00337 
00338         BOOST_DEDUCED_TYPENAME mpl::if_< 
00339             ::boost::bimaps::detail::
00340                 is_unconstrained_set_of< relation_set_type_of >,
00341 
00342             logic_left_tag,
00343             independent_index_tag
00344 
00345         >::type,
00346 
00347         BOOST_DEDUCED_TYPENAME mpl::if_<
00348             is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, left_based >,
00349 
00350             logic_left_tag,
00351             logic_right_tag
00352 
00353         >::type
00354 
00355     >::type logic_relation_set_tag;
00356 
00357     private:
00358 
00359     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
00360         mpl::and_< is_same< relation_set_tag, independent_index_tag >,
00361                    mpl::not_<
00362                        ::boost::bimaps::detail::
00363                             is_unconstrained_set_of< relation_set_type_of > 
00364                    >
00365         >,
00366     // {
00367             BOOST_DEDUCED_TYPENAME mpl::push_front
00368             <
00369                 basic_core_indices,
00370 
00371                 BOOST_DEDUCED_TYPENAME relation_set_type_of::
00372                 BOOST_NESTED_TEMPLATE index_bind
00373                 <
00374                     multi_index::identity<relation>,
00375                     independent_index_tag
00376 
00377                 >::type
00378 
00379             >::type,
00380     // }
00381     // else
00382     // {
00383             basic_core_indices
00384     // }
00385 
00386     >::type complete_core_indices;
00387 
00388     struct core_indices : public complete_core_indices {};
00389 
00390     // Define the core using compute_index_type to translate the
00391     // set type to an multi-index specification
00392     // --------------------------------------------------------------------
00393     public:
00394 
00395     typedef multi_index::multi_index_container
00396     <
00397         relation,
00398         core_indices,
00399         BOOST_DEDUCED_TYPENAME parameters::allocator::
00400             BOOST_NESTED_TEMPLATE rebind<relation>::other
00401 
00402     > core_type;
00403 
00404     // Core metadata
00405     // --------------------------------------------------------------------
00406     public:
00407 
00408     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::
00409         index<core_type, logic_left_tag>::type  left_index;
00410 
00411     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::
00412         index<core_type,logic_right_tag>::type right_index;
00413 
00414     typedef BOOST_DEDUCED_TYPENAME  left_index::iterator        left_core_iterator;
00415     typedef BOOST_DEDUCED_TYPENAME  left_index::const_iterator  left_core_const_iterator;
00416 
00417     typedef BOOST_DEDUCED_TYPENAME right_index::iterator       right_core_iterator;
00418     typedef BOOST_DEDUCED_TYPENAME right_index::const_iterator right_core_const_iterator;
00419 
00420     // Map by {side} iterator metadata
00421     // --------------------------------------------------------------------
00422     public:
00423 
00424     //@{
00425 
00426         typedef ::boost::bimaps::detail::map_view_iterator
00427         <
00428             left_tag,
00429             relation,
00430             left_core_iterator
00431 
00432         > left_iterator;
00433 
00434         typedef ::boost::bimaps::detail::map_view_iterator
00435         <
00436             right_tag,
00437             relation,
00438             right_core_iterator
00439 
00440         > right_iterator;
00441 
00442     //@}
00443 
00444     //@{
00445 
00446         typedef ::boost::bimaps::detail::const_map_view_iterator
00447         <
00448             left_tag,
00449             relation,
00450             left_core_const_iterator
00451 
00452         > left_const_iterator;
00453 
00454         typedef ::boost::bimaps::detail::const_map_view_iterator
00455         <
00456             right_tag,
00457             relation,
00458             right_core_const_iterator
00459 
00460         > right_const_iterator;
00461 
00462     //@}
00463 
00464     // Relation set view
00465 
00466     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::index
00467     <
00468         core_type, logic_relation_set_tag
00469 
00470     >::type relation_set_core_index;
00471 
00472     typedef BOOST_DEDUCED_TYPENAME relation_set_type_of::
00473     BOOST_NESTED_TEMPLATE set_view_bind
00474     <
00475         relation_set_core_index
00476 
00477     >::type relation_set;
00478 
00479     public:
00480 
00481     typedef bimap_core bimap_core_;
00482 };
00483 
00484 } // namespace detail
00485 } // namespace bimaps
00486 } // namespace boost
00487 
00488 #endif // BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP