boost/bimap/bimap.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 bimap.hpp
0010 /// \brief Includes the basic bimap container
0011
0012 /** \mainpage notitle
0013 \n
0014 \image html http://matias.capeletto.googlepages.com/boost.bimap.reference.logo.png
0015
0016 \section Introduction
0017
0018 This is the complete reference of Boost.Bimap.
0019
0020 After getting a good understanding of the library from a user perspective
0021 the next step will be:
0022
0023     - Understand the tagged idiom. (boost::bimaps::tags)
0024     - Understand the internals of the relation class (boost::bimaps::relation)
0025     - Read the container_adaptor toolbox docs (boost::bimaps::container_adaptor)
0026     - Understand the internals of the bimap class. (boost::bimaps, boost::bimaps::views
0027       and boost::bimaps::detail)
0028
0029
0030                                                                         **/
0031
0032 /** \defgroup mutant_group mutant idiom
0033 \brief A safe wrapper around reinterpret_cast
0034                                                                         **/
0035
0036 /** \defgroup relation_group relation
0037 \brief The relation
0038                                                                         **/
0039
0040 /** \defgroup tags_group tagged idiom
0041 \brief The tagged idiom
0042                                                                         **/
0043
0044
0045 #ifndef BOOST_BIMAP_BIMAP_HPP
0046 #define BOOST_BIMAP_BIMAP_HPP
0047
0048 #if defined(_MSC_VER)
0049 #pragma once
0050 #endif
0051
0052 #include <boost/config.hpp>
0053 #include <boost/bimap/detail/user_interface_config.hpp>
0054 #include <boost/mpl/aux_/na.hpp>
0055
0056 #ifndef BOOST_BIMAP_DISABLE_SERIALIZATION
0057     #include <boost/core/serialization.hpp>
0058 #endif // BOOST_BIMAP_DISABLE_SERIALIZATION
0059
0060 // Boost.Bimap
0061 #include <boost/bimap/detail/bimap_core.hpp>
0062 #include <boost/bimap/detail/map_view_base.hpp>
0063 #include <boost/bimap/detail/modifier_adaptor.hpp>
0064 #include <boost/bimap/relation/support/data_extractor.hpp>
0065 #include <boost/bimap/relation/support/member_with_tag.hpp>
0066
0067 #include <boost/bimap/support/map_type_by.hpp>
0068 #include <boost/bimap/support/map_by.hpp>
0069 #include <boost/bimap/support/iterator_type_by.hpp>
0070
0071 /// \brief The namespace where all the boost libraries lives.
0072
0073 namespace boost {
0074
0075 /// \brief Boost.Bimap library namespace
0076 /**
0077 All the entities in the library are defined in this namespace.
0078                                                                     **/
0079 namespace bimaps {
0080
0081 /// \brief The bimap class is the entry point to the library.
0082 /**
0083 This class manages the instantiation of the desired bimap type.
0084 As there are several types of bidirectional maps that can be
0085 created using it. the main job of it is to find the desired
0086 type. This is done using metaprogramming to obtain the relation
0087 type that will be stored, the map_view type of each side and
0088 the set_view type of the general relationship. The instantiation
0089 is kept simple using an extended standard set theory, where a
0090 bidirectional map type is defined by the set types it relates.
0091 For example, a bidirectional map that has multimap semantics
0092 viewed from both sides is defined by specifying that the two
0093 keys sets are of \c multiset_of<Key> type.
0094 This allows the bimap class to support seamingless N-N, 1-N,
0095 ordered/unordered and even vector-list types of mapping.
0096 The three last parameters are used to specify the set type of
0097 the relation, an inplace hooked data class and the allocator
0098 type. As a help to the bimap user, these parameters support
0099 default types but use a special idiom that allow them to be
0100 specified without interleaving the usual use_default keyword.
0101 The possible bimap instantiation are enumerated here:
0102 \c {Side}KeyType can be directly a type, this is default to
0103 \c set_of<{Side}KeyType>, or can be a \c {SetType}_of<Type>
0104 specification. Additionally this two parameters can be tagged
0105 to specify others tags instead of the usual \c member_at::{Side}
0106 ones.
0107
0108
0109 \code
0110
0111     typedef bimap
0112     <
0113         LeftCollectionType, RightCollectionType
0114
0115         [ , SetTypeOfRelation  ]  // Default to left_based
0116         [ , info_hook< Info >  ]  // Default to no info
0117         [ , Allocator          ]  // Default to std::allocator<>
0118
0119     > bm;
0120
0121 \endcode
0122
0123                                                                        **/
0124
0125
0126 template
0127 <
0128     class KeyTypeA, class KeyTypeB,
0129     class AP1 = ::boost::mpl::na,
0130     class AP2 = ::boost::mpl::na,
0131     class AP3 = ::boost::mpl::na
0132 >
0133 class bimap
0134 :
0135     // Bimap Core, use mpl magic to find the desired bimap type
0136
0137     public ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>,
0138
0139     // You can use bimap as a collection of relations
0140
0141     public ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>
0142                 ::relation_set,
0143
0144     // Include extra typedefs (i.e. left_local_iterator for unordered_map)
0145
0146     public ::boost::bimaps::detail:: left_map_view_extra_typedefs<
0147         BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::left_map_view_type<
0148             ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>
0149         >::type
0150     >,
0151     public ::boost::bimaps::detail::right_map_view_extra_typedefs<
0152         BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::right_map_view_type<
0153             ::boost::bimaps::detail::bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3>
0154         >::type
0155     >
0156 {
0157     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::
0158         bimap_core<KeyTypeA,KeyTypeB,AP1,AP2,AP3> base_;
0159
0160     BOOST_DEDUCED_TYPENAME base_::core_type core;
0161
0162     public:
0163
0164     // metadata --------------------------------------------------------
0165
0166     /*
0167     // The rest is computed in the core, because it is quite difficult to
0168     // expose a nice interface with so many metaprogramming stuff.
0169
0170     // Map by {side} metadata
0171
0172     typedef -unspecified- {side}_tag;
0173     typedef -unspecified- {side}_data_type;
0174     typedef -unspecified- {side}_value_type;
0175     typedef -unspecified- {side}_key_type;
0176
0177     // There are other typedefs for definitions of different map views
0178
0179     ------------------------------------------------------------------*/
0180
0181     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::
0182           left_map_view_type<base_>::type  left_map;
0183     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::
0184          right_map_view_type<base_>::type right_map;
0185
0186     typedef BOOST_DEDUCED_TYPENAME
0187          left_map::iterator        left_iterator;
0188     typedef BOOST_DEDUCED_TYPENAME
0189          left_map::const_iterator  left_const_iterator;
0190
0191     typedef BOOST_DEDUCED_TYPENAME
0192          right_map::iterator       right_iterator;
0193     typedef BOOST_DEDUCED_TYPENAME
0194          right_map::const_iterator right_const_iterator;
0195
0196     typedef BOOST_DEDUCED_TYPENAME
0197          left_map::reference       left_reference;
0198     typedef BOOST_DEDUCED_TYPENAME
0199          left_map::const_reference left_const_reference;
0200
0201     typedef BOOST_DEDUCED_TYPENAME
0202         right_map::reference       right_reference;
0203     typedef BOOST_DEDUCED_TYPENAME
0204         right_map::const_reference right_const_reference;
0205
0206     typedef BOOST_DEDUCED_TYPENAME base_::relation::info_type info_type;
0207
0208     typedef BOOST_DEDUCED_TYPENAME base_::core_type::allocator_type allocator_type;
0209
0210     /// Left map view
0211     left_map  left;
0212
0213     /// Right map view
0214     right_map right;
0215
0216     typedef BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag
0217                                           logic_relation_set_tag;
0218     typedef BOOST_DEDUCED_TYPENAME base_::logic_left_tag logic_left_tag;
0219     typedef BOOST_DEDUCED_TYPENAME base_::logic_right_tag logic_right_tag;
0220     typedef BOOST_DEDUCED_TYPENAME base_::core_type::ctor_args_list
0221                                                      ctor_args_list;
0222
0223    bimap(const allocator_type& al = allocator_type()) :
0224
0225        base_::relation_set(
0226            ::boost::multi_index::get<
0227                logic_relation_set_tag
0228            >(core)
0229        ),
0230
0231        core(al),
0232
0233        left (
0234            ::boost::multi_index::get<
0235                logic_left_tag
0236            >(core)
0237        ),
0238        right (
0239            ::boost::multi_index::get<
0240                logic_right_tag
0241            >(core)
0242        )
0243
0244    {}
0245
0246    template< class InputIterator >
0247    bimap(InputIterator first,InputIterator last,
0248          const allocator_type& al = allocator_type()) :
0249
0250        base_::relation_set(
0251            ::boost::multi_index::get<
0252                BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(core)
0253        ),
0254
0255        core(first,last,ctor_args_list(),al),
0256
0257        left (
0258            ::boost::multi_index::get<
0259                BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(core)
0260        ),
0261        right (
0262            ::boost::multi_index::get<
0263                BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(core)
0264        )
0265
0266    {}
0267
0268    bimap(const bimap& x) :
0269
0270        base_::relation_set(
0271            ::boost::multi_index::get<
0272                BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(core)
0273        ),
0274
0275        core(x.core),
0276
0277        left (
0278            ::boost::multi_index::get<
0279                BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(core)
0280        ),
0281        right (
0282            ::boost::multi_index::get<
0283                BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(core)
0284        )
0285
0286    {}
0287
0288     bimap& operator=(const bimap& x)
0289     {
0290         core = x.core;
0291         return *this;
0292     }
0293
0294     // Projection of iterators
0295
0296     template< class IteratorType >
0297     left_iterator project_left(IteratorType iter)
0298     {
0299         return core.template project<
0300             BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(iter.base());
0301     }
0302
0303     template< class IteratorType >
0304     left_const_iterator project_left(IteratorType iter) const
0305     {
0306         return core.template project<
0307             BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(iter.base());
0308     }
0309
0310     template< class IteratorType >
0311     right_iterator project_right(IteratorType iter)
0312     {
0313         return core.template project<
0314             BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(iter.base());
0315     }
0316
0317     template< class IteratorType >
0318     right_const_iterator project_right(IteratorType iter) const
0319     {
0320         return core.template project<
0321             BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(iter.base());
0322     }
0323
0324     template< class IteratorType >
0325     BOOST_DEDUCED_TYPENAME base_::relation_set::iterator
0326         project_up(IteratorType iter)
0327     {
0328         return core.template project<
0329             BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(iter.base());
0330     }
0331
0332     template< class IteratorType >
0333     BOOST_DEDUCED_TYPENAME base_::relation_set::const_iterator
0334         project_up(IteratorType iter) const
0335     {
0336         return core.template project<
0337             BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(iter.base());
0338     }
0339
0340     // Support for tags
0341
0342     template< class Tag, class IteratorType >
0343     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
0344     iterator_type_by<Tag,bimap>::type
0345         project(IteratorType iter)
0346     {
0347         return core.template project<Tag>(iter.base());
0348     }
0349
0350     template< class Tag, class IteratorType >
0351     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
0352     const_iterator_type_by<Tag,bimap>::type
0353         project(IteratorType iter) const
0354     {
0355         return core.template project<Tag>(iter.base());
0356     }
0357
0358     template< class Tag >
0359     struct map_by :
0360         public ::boost::bimaps::support::map_type_by<Tag,bimap>::type
0361     {
0362         typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
0363             map_type_by<Tag,bimap>::type type;
0364
0365         private: map_by() {}
0366     };
0367
0368     template< class Tag >
0369     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
0370     map_type_by<Tag,bimap>::type &by()
0371     {
0372         return ::boost::bimaps::support::map_by<Tag>(*this);
0373     }
0374
0375     template< class Tag >
0376     const BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
0377     map_type_by<Tag,bimap>::type &by() const
0378     {
0379         return ::boost::bimaps::support::map_by<Tag>(*this);
0380     }
0381
0382
0383     #ifndef BOOST_BIMAP_DISABLE_SERIALIZATION
0384
0385     // Serialization support
0386
0387     private:
0388
0389     friend class boost::serialization::access;
0390
0391     template<class Archive>
0392     void serialize(Archive & ar, const unsigned int)
0393     {
0394         ar & serialization::make_nvp("mi_core",core);
0395     }
0396
0397     #endif // BOOST_BIMAP_DISABLE_SERIALIZATION
0398 };
0399
0400 } // namespace bimaps
0401 } // namespace boost
0402
0403
0404 /** \namespace boost::bimaps::support
0405 \brief Metafunctions to help working with bimaps.
0406                                                             **/
0407
0408 /** \namespace boost::bimaps::views
0409 \brief Bimap views.
0410                                                             **/
0411
0412 /** \namespace boost::bimaps::views::detail
0413 \brief Bimap views details.
0414                                                             **/
0415
0416
0417
0418 // Include basic tools for user commodity
0419
0420 #include <boost/bimap/tags/tagged.hpp>
0421 #include <boost/bimap/relation/member_at.hpp>
0422 #include <boost/multi_index/detail/unbounded.hpp>
0423
0424 // Bring the most used namespaces directly to the user main namespace
0425 namespace boost {
0426 namespace bimaps {
0427
0428 using ::boost::bimaps::tags::tagged;
0429
0430 namespace member_at = ::boost::bimaps::relation::member_at;
0431
0432 using ::boost::multi_index::unbounded;
0433
0434 } // namespace bimaps
0435 } // namespace boost
0436
0437
0438 #endif // BOOST_BIMAP_BIMAP_HPP