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