boost/bimap/detail/bimap_core.hpp

   1 // Boost.Bimap
   2 //
   3 // Copyright (c) 2006-2007 Matias Capeletto
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 // (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 /// \file detail/bimap_core.hpp
  10 /// \brief Bimap base definition.
  11
  12 #ifndef BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP
  13 #define BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP
  14
  15 #if defined(_MSC_VER) && (_MSC_VER>=1200)
  16 #pragma once
  17 #endif
  18
  19 #include <boost/config.hpp>
  20
  21 #include <boost/mpl/placeholders.hpp>
  22 #include <boost/mpl/push_front.hpp>
  23 #include <boost/mpl/if.hpp>
  24 #include <boost/mpl/and.hpp>
  25 #include <boost/mpl/not.hpp>
  26 #include <boost/mpl/vector.hpp>
  27
  28 #include <boost/type_traits/add_const.hpp>
  29 #include <boost/type_traits/is_same.hpp>
  30
  31 #include <boost/concept_check.hpp>
  32
  33 // Boost.MultiIndex
  34 #include <boost/multi_index_container.hpp>
  35 #include <boost/multi_index/member.hpp>
  36
  37 // Boost.Bimap
  38 #include <boost/bimap/relation/mutant_relation.hpp>
  39 #include <boost/bimap/relation/member_at.hpp>
  40 #include <boost/bimap/relation/support/data_extractor.hpp>
  41 #include <boost/bimap/tags/support/default_tagged.hpp>
  42 #include <boost/bimap/tags/tagged.hpp>
  43 #include <boost/bimap/detail/manage_bimap_key.hpp>
  44 #include <boost/bimap/detail/manage_additional_parameters.hpp>
  45 #include <boost/bimap/detail/map_view_iterator.hpp>
  46 #include <boost/bimap/detail/set_view_iterator.hpp>
  47
  48 #include <boost/bimap/set_of.hpp>
  49 #include <boost/bimap/unconstrained_set_of.hpp>
  50
  51 namespace boost {
  52 namespace bimaps {
  53
  54 /// \brief Library details
  55
  56 namespace detail {
  57
  58 #ifndef BOOST_BIMAP_DOXYGEN_WILL_NOT_PROCESS_THE_FOLLOWING_LINES
  59
  60 template< class Type >
  61 struct get_value_type
  62 {
  63     typedef BOOST_DEDUCED_TYPENAME Type::value_type type;
  64 };
  65
  66 struct independent_index_tag {};
  67
  68 #endif // BOOST_BIMAP_DOXYGEN_WILL_NOT_PROCESS_THE_FOLLOWING_LINES
  69
  70
  71 /// \brief Base for the bimap class.
  72 /**
  73
  74
  75 See also bimap.
  76                                                                         **/
  77
  78
  79 template< class LeftSetType, class RightSetType, class AP1, class AP2, class AP3 >
  80 class bimap_core
  81 {
  82     // Manage bimap key instantiation
  83     // --------------------------------------------------------------------
  84     public:
  85
  86     typedef BOOST_DEDUCED_TYPENAME manage_bimap_key
  87     <
  88         LeftSetType
  89
  90     >::type left_set_type;
  91
  92     typedef BOOST_DEDUCED_TYPENAME manage_bimap_key
  93     <
  94         RightSetType
  95
  96         >::type right_set_type;
  97
  98
  99         private:
 100
 101         typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::tags::support::default_tagged
 102         <
 103                 BOOST_DEDUCED_TYPENAME left_set_type::user_type,
 104                 ::boost::bimaps::relation::member_at::left
 105
 106         >::type left_tagged_type;
 107
 108         typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::tags::support::default_tagged
 109         <
 110                 BOOST_DEDUCED_TYPENAME right_set_type::user_type,
 111                 ::boost::bimaps::relation::member_at::right
 112
 113         >::type right_tagged_type;
 114
 115         public:
 116
 117         //@{
 118
 119                 typedef BOOST_DEDUCED_TYPENAME  left_tagged_type::tag  left_tag;
 120                 typedef BOOST_DEDUCED_TYPENAME right_tagged_type::tag right_tag;
 121
 122         //@}
 123
 124     //@{
 125
 126         typedef BOOST_DEDUCED_TYPENAME  left_set_type::value_type  left_key_type;
 127         typedef BOOST_DEDUCED_TYPENAME right_set_type::value_type right_key_type;
 128
 129     //@}
 130
 131     //@{
 132
 133         typedef right_key_type  left_data_type;
 134         typedef  left_key_type right_data_type;
 135
 136     //@}
 137
 138     // Manage the additional parameters
 139     // --------------------------------------------------------------------
 140     private:
 141
 142     typedef BOOST_DEDUCED_TYPENAME manage_additional_parameters<AP1,AP2,AP3>::type parameters;
 143
 144     /// \brief Relation type stored by the bimap.
 145     // --------------------------------------------------------------------
 146     public:
 147
 148     typedef ::boost::bimaps::relation::mutant_relation
 149     <
 150
 151         ::boost::bimaps::tags::tagged<
 152             BOOST_DEDUCED_TYPENAME mpl::if_<
 153                 mpl::and_
 154                 <
 155                     BOOST_DEDUCED_TYPENAME left_set_type::mutable_key,
 156                     BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation::left_mutable_key
 157                 >,
 158             // {
 159                     left_key_type,
 160             // }
 161             // else
 162             // {
 163                     BOOST_DEDUCED_TYPENAME ::boost::add_const< left_key_type >::type
 164             // }
 165
 166             >::type,
 167             left_tag
 168         >,
 169
 170         ::boost::bimaps::tags::tagged<
 171             BOOST_DEDUCED_TYPENAME mpl::if_<
 172                 mpl::and_
 173                 <
 174                     BOOST_DEDUCED_TYPENAME right_set_type::mutable_key,
 175                     BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation::right_mutable_key
 176                 >,
 177             // {
 178                     right_key_type,
 179             // }
 180             // else
 181             // {
 182                     BOOST_DEDUCED_TYPENAME ::boost::add_const< right_key_type >::type
 183             // }
 184
 185             >::type,
 186             right_tag
 187         >,
 188
 189         // It is ::boost::mpl::na if no info_hook was included
 190         BOOST_DEDUCED_TYPENAME parameters::additional_info,
 191
 192         // Force mutable keys
 193         true
 194
 195     > relation;
 196
 197     //@{
 198
 199         typedef BOOST_DEDUCED_TYPENAME relation::left_pair  left_value_type;
 200         typedef BOOST_DEDUCED_TYPENAME relation::right_pair right_value_type;
 201
 202     //@}
 203
 204     // Bind the member of the relation, so multi_index can manage them
 205     // --------------------------------------------------------------------
 206     private:
 207
 208     typedef BOOST_DEDUCED_TYPENAME relation::storage_base relation_storage_base;
 209
 210     typedef BOOST_MULTI_INDEX_MEMBER(relation_storage_base, left_key_type, left)
 211         left_member_extractor;
 212
 213     typedef BOOST_MULTI_INDEX_MEMBER(relation_storage_base,right_key_type,right)
 214         right_member_extractor;
 215
 216     // The core indices are somewhat complicated to calculate, because they
 217     // can be zero, one, two or three indices, depending on the use of
 218     // {side}_based set type of relations and unconstrained_set_of and
 219     // unconstrained_set_of_relation specifications.
 220
 221     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
 222         ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
 223     // {
 224             mpl::vector<>,
 225     // }
 226     // else
 227     // {
 228             mpl::vector
 229             <
 230                 BOOST_DEDUCED_TYPENAME left_set_type::
 231                 BOOST_NESTED_TEMPLATE index_bind
 232                 <
 233                     left_member_extractor,
 234                     left_tag
 235
 236                 >::type
 237             >
 238     // }
 239     >::type left_core_indices;
 240
 241     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
 242         ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
 243     // {
 244             left_core_indices,
 245     // }
 246     // else
 247     // {
 248             BOOST_DEDUCED_TYPENAME mpl::push_front
 249             <
 250                 left_core_indices,
 251
 252                 BOOST_DEDUCED_TYPENAME right_set_type::
 253                 BOOST_NESTED_TEMPLATE index_bind
 254                 <
 255                     right_member_extractor,
 256                     right_tag
 257
 258                 >::type
 259
 260             >::type
 261     // }
 262     >::type basic_core_indices;
 263
 264     // If it is based either on the left or on the right, then only the side
 265     // indices are needed. But the set type of the relation can be completely
 266     // diferent from the one used for the sides in wich case we have to add yet
 267     // another index to the core.
 268
 269     // TODO
 270     // If all the set types are unsconstrained there must be readable compile
 271     // time error.
 272
 273     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
 274
 275         is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, left_based >,
 276     // {
 277             ::boost::bimaps::tags::tagged< left_set_type, left_tag >,
 278     // }
 279     /* else */ BOOST_DEDUCED_TYPENAME mpl::if_<
 280             is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, right_based >,
 281     // {
 282                         ::boost::bimaps::tags::tagged< right_set_type, right_tag >,
 283     // }
 284     // else
 285     // {
 286             tags::tagged
 287             <
 288                 BOOST_DEDUCED_TYPENAME parameters::
 289                 set_type_of_relation::BOOST_NESTED_TEMPLATE bind_to
 290                 <
 291                     relation
 292
 293                 >::type,
 294                 independent_index_tag
 295             >
 296     // }
 297     >::type
 298     >::type tagged_set_of_relation_type;
 299
 300     protected:
 301
 302     typedef BOOST_DEDUCED_TYPENAME tagged_set_of_relation_type::tag
 303                         relation_set_tag;
 304
 305     typedef BOOST_DEDUCED_TYPENAME tagged_set_of_relation_type::value_type
 306                         relation_set_type_of;
 307
 308     // Logic tags
 309     // This is a necesary extra level of indirection to allow unconstrained
 310     // sets to be plug in the design. The bimap constructors use this logic
 311     // tags.
 312
 313     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
 314         ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
 315
 316         BOOST_DEDUCED_TYPENAME mpl::if_<
 317             ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
 318
 319             independent_index_tag,
 320             right_tag
 321
 322         >::type,
 323
 324         left_tag
 325
 326     >::type logic_left_tag;
 327
 328     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
 329         ::boost::bimaps::detail::is_unconstrained_set_of< right_set_type >,
 330
 331         BOOST_DEDUCED_TYPENAME mpl::if_<
 332             ::boost::bimaps::detail::is_unconstrained_set_of< left_set_type >,
 333
 334             independent_index_tag,
 335             left_tag
 336
 337         >::type,
 338
 339         right_tag
 340
 341     >::type logic_right_tag;
 342
 343     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
 344         is_same< relation_set_tag, independent_index_tag >,
 345
 346         BOOST_DEDUCED_TYPENAME mpl::if_<
 347             ::boost::bimaps::detail::
 348                 is_unconstrained_set_of< relation_set_type_of >,
 349
 350             logic_left_tag,
 351             independent_index_tag
 352
 353         >::type,
 354
 355         BOOST_DEDUCED_TYPENAME mpl::if_<
 356             is_same< BOOST_DEDUCED_TYPENAME parameters::set_type_of_relation, left_based >,
 357
 358             logic_left_tag,
 359             logic_right_tag
 360
 361         >::type
 362
 363     >::type logic_relation_set_tag;
 364
 365     private:
 366
 367     typedef BOOST_DEDUCED_TYPENAME mpl::if_<
 368         mpl::and_< is_same< relation_set_tag, independent_index_tag >,
 369                    mpl::not_<
 370                        ::boost::bimaps::detail::
 371                             is_unconstrained_set_of< relation_set_type_of >
 372                    >
 373         >,
 374     // {
 375             BOOST_DEDUCED_TYPENAME mpl::push_front
 376             <
 377                 basic_core_indices,
 378
 379                 BOOST_DEDUCED_TYPENAME relation_set_type_of::
 380                 BOOST_NESTED_TEMPLATE index_bind
 381                 <
 382                     ::boost::bimaps::relation::support::both_keys_extractor<relation>,
 383                     independent_index_tag
 384
 385                 >::type
 386
 387             >::type,
 388     // }
 389     // else
 390     // {
 391             basic_core_indices
 392     // }
 393
 394     >::type complete_core_indices;
 395
 396     struct core_indices : public complete_core_indices {};
 397
 398     // Define the core using compute_index_type to translate the
 399     // set type to an multi-index specification
 400     // --------------------------------------------------------------------
 401     public:
 402
 403     typedef multi_index::multi_index_container
 404     <
 405         relation,
 406         core_indices,
 407         BOOST_DEDUCED_TYPENAME parameters::allocator::
 408             BOOST_NESTED_TEMPLATE rebind<relation>::other
 409
 410     > core_type;
 411
 412     // Core metadata
 413     // --------------------------------------------------------------------
 414     public:
 415
 416     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::
 417         index<core_type, logic_left_tag>::type  left_index;
 418
 419     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::
 420         index<core_type,logic_right_tag>::type right_index;
 421
 422     typedef BOOST_DEDUCED_TYPENAME  left_index::iterator        left_core_iterator;
 423     typedef BOOST_DEDUCED_TYPENAME  left_index::const_iterator  left_core_const_iterator;
 424
 425     typedef BOOST_DEDUCED_TYPENAME right_index::iterator       right_core_iterator;
 426     typedef BOOST_DEDUCED_TYPENAME right_index::const_iterator right_core_const_iterator;
 427
 428     // Map by {side} iterator metadata
 429     // --------------------------------------------------------------------
 430     public:
 431
 432     //@{
 433
 434         typedef ::boost::bimaps::detail::map_view_iterator
 435         <
 436             left_tag,
 437             relation,
 438             left_core_iterator
 439
 440         > left_iterator;
 441
 442         typedef ::boost::bimaps::detail::map_view_iterator
 443         <
 444             right_tag,
 445             relation,
 446             right_core_iterator
 447
 448         > right_iterator;
 449
 450     //@}
 451
 452     //@{
 453
 454         typedef ::boost::bimaps::detail::const_map_view_iterator
 455         <
 456             left_tag,
 457             relation,
 458             left_core_const_iterator
 459
 460         > left_const_iterator;
 461
 462         typedef ::boost::bimaps::detail::const_map_view_iterator
 463         <
 464             right_tag,
 465             relation,
 466             right_core_const_iterator
 467
 468         > right_const_iterator;
 469
 470     //@}
 471
 472     // Relation set view
 473
 474     typedef BOOST_DEDUCED_TYPENAME ::boost::multi_index::index
 475     <
 476         core_type, logic_relation_set_tag
 477
 478     >::type relation_set_core_index;
 479
 480     typedef BOOST_DEDUCED_TYPENAME relation_set_type_of::
 481     BOOST_NESTED_TEMPLATE set_view_bind
 482     <
 483         relation_set_core_index
 484
 485     >::type relation_set;
 486
 487     public:
 488
 489     typedef bimap_core bimap_core_;
 490 };
 491
 492 // Two auxiliar metafunctions to compute the map view types
 493 // The map view type can not be computed inside the bimap core because a
 494 // they need the bimap core to be parsed first.
 495
 496 template< class BimapBaseType >
 497 struct left_map_view_type
 498 {
 499         typedef BOOST_DEDUCED_TYPENAME BimapBaseType::left_set_type left_set_type;
 500     typedef BOOST_DEDUCED_TYPENAME
 501         left_set_type::BOOST_NESTED_TEMPLATE map_view_bind<
 502             BOOST_DEDUCED_TYPENAME BimapBaseType::left_tag, BimapBaseType
 503         >::type type;
 504 };
 505
 506 template< class BimapBaseType >
 507 struct right_map_view_type
 508 {
 509         typedef BOOST_DEDUCED_TYPENAME BimapBaseType::right_set_type right_set_type;
 510     typedef BOOST_DEDUCED_TYPENAME
 511         right_set_type::BOOST_NESTED_TEMPLATE map_view_bind<
 512             BOOST_DEDUCED_TYPENAME BimapBaseType::right_tag, BimapBaseType
 513         >::type type;
 514 };
 515
 516 } // namespace detail
 517 } // namespace bimaps
 518 } // namespace boost
 519
 520 #endif // BOOST_BIMAP_DETAIL_BIMAP_CORE_HPP