boost/bimap/bimap.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 bimap.hpp
  10 /// \brief Includes the basic bimap container
  11
  12 /** \mainpage notitle
  13 \n
  14 \image html http://matias.capeletto.googlepages.com/boost.bimap.reference.logo.png
  15
  16 \section Introduction
  17
  18 This is the complete reference of Boost.Bimap.
  19
  20 After getting a good understanding of the library from a user perspective
  21 the next step will be:
  22
  23     - Understand the tagged idiom. (boost::bimaps::tags)
  24     - Understand the internals of the relation class (boost::bimaps::relation)
  25     - Read the container_adaptor toolbox docs (boost::bimaps::container_adaptor)
  26     - Understand the internals of the bimap class. (boost::bimaps, boost::bimaps::views
  27       and boost::bimaps::detail)
  28
  29
  30                                                                         **/
  31
  32 /** \defgroup mutant_group mutant idiom
  33 \brief A safe wrapper around reinterpret_cast
  34                                                                         **/
  35
  36 /** \defgroup relation_group relation
  37 \brief The relation
  38                                                                         **/
  39
  40 /** \defgroup tags_group tagged idiom
  41 \brief The tagged idiom
  42                                                                         **/
  43
  44
  45 #ifndef BOOST_BIMAP_BIMAP_HPP
  46 #define BOOST_BIMAP_BIMAP_HPP
  47
  48 #if defined(_MSC_VER) && (_MSC_VER>=1200)
  49 #pragma once
  50 #endif
  51
  52 #include <boost/config.hpp>
  53 #include <boost/bimap/detail/user_interface_config.hpp>
  54 #include <boost/mpl/aux_/na.hpp>
  55
  56 #ifndef BOOST_BIMAP_DISABLE_SERIALIZATION
  57     #include <boost/serialization/nvp.hpp>
  58 #endif // BOOST_BIMAP_DISABLE_SERIALIZATION
  59
  60 // Boost.Bimap
  61 #include <boost/bimap/detail/bimap_core.hpp>
  62 #include <boost/bimap/detail/map_view_base.hpp>
  63 #include <boost/bimap/detail/modifier_adaptor.hpp>
  64 #include <boost/bimap/relation/support/data_extractor.hpp>
  65 #include <boost/bimap/relation/support/member_with_tag.hpp>
  66
  67 #include <boost/bimap/support/map_type_by.hpp>
  68 #include <boost/bimap/support/map_by.hpp>
  69 #include <boost/bimap/support/iterator_type_by.hpp>
  70
  71 /// \brief The namespace where all the boost libraries lives.
  72
  73 namespace boost {
  74
  75 /// \brief Boost.Bimap library namespace
  76 /**
  77 All the entities in the library are defined in this namespace.
  78                                                                     **/
  79 namespace bimaps {
  80
  81 /// \brief The bimap class is the entry point to the library.
  82 /**
  83 This class manages the instantiation of the desired bimap type.
  84 As there are several types of bidirectional maps that can be
  85 created using it. the main job of it is to find the desired
  86 type. This is done using metaprogramming to obtain the relation
  87 type that will be stored, the map_view type of each side and
  88 the set_view type of the general relationship. The instantiation
  89 is kept simple using an extended standard set theory, where a
  90 bidirectional map type is defined by the set types it relates.
  91 For example, a bidirectional map that has multimap semantics
  92 viewed from both sides is defined by specifying that the two
  93 keys sets are of \c multiset_of<Key> type.
  94 This allows the bimap class to support seamingless N-N, 1-N,
  95 ordered/unordered and even vector-list types of mapping.
  96 The three last parameters are used to specify the set type of
  97 the relation, an inplace hooked data class and the allocator
  98 type. As a help to the bimap user, these parameters support
  99 default types but use a special idiom that allow them to be
 100 specified without interleaving the usual use_default keyword.
 101 The possible bimap instantiation are enumerated here:
 102 \c {Side}KeyType can be directly a type, this is default to
 103 \c set_of<{Side}KeyType>, or can be a \c {SetType}_of<Type>
 104 specification. Additionally this two parameters can be tagged
 105 to specify others tags instead of the usual \c member_at::{Side}
 106 ones.
 107
 108
 109 \code
 110
 111     typedef bimap
 112     <
 113         LeftCollectionType, RightCollectionType
 114
 115         [ , SetTypeOfRelation  ]  // Default to left_based
 116         [ , info_hook< Info >  ]  // Default to no info
 117         [ , Allocator          ]  // Default to std::allocator<>
 118
 119     > bm;
 120
 121 \endcode
 122
 123                                                                        **/
 124
 125
 126 template
 127 <
 128     class KeyTypeA, class KeyTypeB,
 129     class AP1 = ::boost::mpl::na,
 130     class AP2 = ::boost::mpl::na,
 131     class AP3 = ::boost::mpl::na
 132 >
 133 class bimap
 134 :
 135     // Bimap Core, use mpl magic to find the desired bimap type
 136
 137     public ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>,
 138
 139     // You can use bimap as a collection of relations
 140
 141     public ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>
 142                 ::relation_set,
 143
 144     // Include extra typedefs (i.e. left_local_iterator for unordered_map)
 145
 146     public ::boost::bimaps::detail:: left_map_view_extra_typedefs<
 147         BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::left_map_view_type<
 148             ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>
 149         >::type
 150     >,
 151     public ::boost::bimaps::detail::right_map_view_extra_typedefs<
 152         BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::right_map_view_type<
 153             ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>
 154         >::type
 155     >
 156 {
 157     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::
 158         bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3> base_;
 159
 160     BOOST_DEDUCED_TYPENAME base_::core_type core;
 161
 162     public:
 163
 164     // metadata --------------------------------------------------------
 165
 166     /*
 167     // The rest is computed in the core, because it is quite difficult to
 168     // expose a nice interface with so many metaprogramming stuff.
 169     // Here it is the complete metadat list.
 170
 171     // Map by {side} metadata
 172
 173     typedef -unspecified- {side}_tag;
 174     typedef -unspecified- {side}_data_type;
 175     typedef -unspecified- {side}_value_type;
 176     typedef -unspecified- {side}_key_type;
 177     typedef -unspecified- {side}_iterator;
 178     typedef -unspecified- {side}_const_iterator;
 179
 180     ------------------------------------------------------------------*/
 181
 182     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::
 183           left_map_view_type<base_>::type  left_map;
 184     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::
 185          right_map_view_type<base_>::type right_map;
 186
 187     typedef BOOST_DEDUCED_TYPENAME
 188          left_map::reference        left_reference;
 189     typedef BOOST_DEDUCED_TYPENAME
 190          left_map::const_reference  left_const_reference;
 191
 192     typedef BOOST_DEDUCED_TYPENAME
 193         right_map::reference       right_reference;
 194     typedef BOOST_DEDUCED_TYPENAME
 195         right_map::const_reference right_const_reference;
 196
 197     typedef BOOST_DEDUCED_TYPENAME base_::relation::info_type info_type;
 198
 199     /// Left map view
 200     left_map  left;
 201
 202     /// Right map view
 203     right_map right;
 204
 205     bimap() :
 206
 207         base_::relation_set(
 208             ::boost::multi_index::get<
 209                 BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag
 210             >(core)
 211         ),
 212         left (
 213             ::boost::multi_index::get<
 214                 BOOST_DEDUCED_TYPENAME base_::logic_left_tag
 215             >(core)
 216         ),
 217         right (
 218             ::boost::multi_index::get<
 219                 BOOST_DEDUCED_TYPENAME base_::logic_right_tag
 220             >(core)
 221         )
 222
 223     {}
 224
 225     template< class InputIterator >
 226     bimap(InputIterator first,InputIterator last) :
 227
 228         base_::relation_set(
 229             ::boost::multi_index::get<
 230                 BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag
 231             >(core)
 232         ),
 233
 234         core(first,last),
 235
 236         left (
 237             ::boost::multi_index::get<
 238                 BOOST_DEDUCED_TYPENAME base_::logic_left_tag
 239             >(core)
 240         ),
 241         right (
 242             ::boost::multi_index::get<
 243                 BOOST_DEDUCED_TYPENAME base_::logic_right_tag
 244             >(core)
 245         )
 246
 247     {}
 248
 249     bimap(const bimap& x) :
 250
 251         base_::relation_set(
 252             ::boost::multi_index::get<
 253                 BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag
 254             >(core)
 255         ),
 256
 257         core(x.core),
 258
 259         left (
 260             ::boost::multi_index::get<
 261                 BOOST_DEDUCED_TYPENAME base_::logic_left_tag
 262             >(core)
 263         ),
 264         right (
 265             ::boost::multi_index::get<
 266                 BOOST_DEDUCED_TYPENAME base_::logic_right_tag
 267             >(core)
 268         )
 269
 270     {}
 271
 272     bimap& operator=(const bimap& x)
 273     {
 274         core = x.core;
 275         return *this;
 276     }
 277
 278     // Projection of iterators
 279
 280     template< class IteratorType >
 281     BOOST_DEDUCED_TYPENAME base_::left_iterator
 282         project_left(IteratorType iter)
 283     {
 284         return core.template project<
 285             BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(iter.base());
 286     }
 287
 288     template< class IteratorType >
 289     BOOST_DEDUCED_TYPENAME base_::left_const_iterator
 290         project_left(IteratorType iter) const
 291     {
 292         return core.template project<
 293             BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(iter.base());
 294     }
 295
 296     template< class IteratorType >
 297     BOOST_DEDUCED_TYPENAME base_::right_iterator
 298         project_right(IteratorType iter)
 299     {
 300         return core.template project<
 301             BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(iter.base());
 302     }
 303
 304     template< class IteratorType >
 305     BOOST_DEDUCED_TYPENAME base_::right_const_iterator
 306         project_right(IteratorType iter) const
 307     {
 308         return core.template project<
 309             BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(iter.base());
 310     }
 311
 312     template< class IteratorType >
 313     BOOST_DEDUCED_TYPENAME base_::relation_set::iterator
 314         project_up(IteratorType iter)
 315     {
 316         return core.template project<
 317             BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(iter.base());
 318     }
 319
 320     template< class IteratorType >
 321     BOOST_DEDUCED_TYPENAME base_::relation_set::const_iterator
 322         project_up(IteratorType iter) const
 323     {
 324         return core.template project<
 325             BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(iter.base());
 326     }
 327
 328     // Support for tags
 329
 330     template< class Tag, class IteratorType >
 331     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
 332     iterator_type_by<Tag,bimap>::type
 333         project(IteratorType iter
 334                 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tag))
 335     {
 336         return core.template project<Tag>(iter.base());
 337     }
 338
 339     template< class Tag, class IteratorType >
 340     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
 341     const_iterator_type_by<Tag,bimap>::type
 342         project(IteratorType iter
 343                 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Tag)) const
 344     {
 345         return core.template project<Tag>(iter.base());
 346     }
 347
 348     template< class Tag >
 349     struct map_by :
 350         public ::boost::bimaps::support::map_type_by<Tag,bimap>::type
 351     {
 352         typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
 353             map_type_by<Tag,bimap>::type type;
 354
 355         private: map_by() {}
 356     };
 357
 358     template< class Tag >
 359     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
 360     map_type_by<Tag,bimap>::type &
 361         by(BOOST_EXPLICIT_TEMPLATE_TYPE(Tag))
 362     {
 363         return ::boost::bimaps::support::map_by<Tag>(*this);
 364     }
 365
 366     template< class Tag >
 367     const BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
 368     map_type_by<Tag,bimap>::type &
 369         by(BOOST_EXPLICIT_TEMPLATE_TYPE(Tag)) const
 370     {
 371         return ::boost::bimaps::support::map_by<Tag>(*this);
 372     }
 373
 374
 375     #ifndef BOOST_BIMAP_DISABLE_SERIALIZATION
 376
 377     // Serialization support
 378
 379     private:
 380
 381     friend class boost::serialization::access;
 382
 383     template<class Archive>
 384     void serialize(Archive & ar, const unsigned int version)
 385     {
 386         ar & serialization::make_nvp("mi_core",core);
 387     }
 388
 389     #endif // BOOST_BIMAP_DISABLE_SERIALIZATION
 390 };
 391
 392 } // namespace bimaps
 393 } // namespace boost
 394
 395
 396 /** \namespace boost::bimaps::support
 397 \brief Metafunctions to help working with bimaps.
 398                                                             **/
 399
 400 /** \namespace boost::bimaps::views
 401 \brief Bimap views.
 402                                                             **/
 403
 404 /** \namespace boost::bimaps::views::detail
 405 \brief Bimap views details.
 406                                                             **/
 407
 408
 409
 410 // Include basic tools for user commodity
 411
 412 #include <boost/bimap/tags/tagged.hpp>
 413 #include <boost/bimap/relation/member_at.hpp>
 414 #include <boost/multi_index/detail/unbounded.hpp>
 415
 416 // Bring the most used namespaces directly to the user main namespace
 417 namespace boost {
 418 namespace bimaps {
 419
 420 using ::boost::bimaps::tags::tagged;
 421
 422 namespace member_at = ::boost::bimaps::relation::member_at;
 423
 424 using ::boost::multi_index::unbounded;
 425
 426 } // namespace bimaps
 427 } // namespace boost
 428
 429
 430 #endif // BOOST_BIMAP_BIMAP_HPP