• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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)
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 
170     // Map by {side} metadata
171 
172     typedef -unspecified- {side}_tag;
173     typedef -unspecified- {side}_data_type;
174     typedef -unspecified- {side}_value_type;
175     typedef -unspecified- {side}_key_type;
176 
177     // There are other typedefs for definitions of different map views
178 
179     ------------------------------------------------------------------*/
180 
181     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::
182           left_map_view_type<base_>::type  left_map;
183     typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::detail::
184          right_map_view_type<base_>::type right_map;
185 
186     typedef BOOST_DEDUCED_TYPENAME
187          left_map::iterator        left_iterator;
188     typedef BOOST_DEDUCED_TYPENAME
189          left_map::const_iterator  left_const_iterator;
190 
191     typedef BOOST_DEDUCED_TYPENAME
192          right_map::iterator       right_iterator;
193     typedef BOOST_DEDUCED_TYPENAME
194          right_map::const_iterator right_const_iterator;
195 
196     typedef BOOST_DEDUCED_TYPENAME
197          left_map::reference       left_reference;
198     typedef BOOST_DEDUCED_TYPENAME
199          left_map::const_reference left_const_reference;
200 
201     typedef BOOST_DEDUCED_TYPENAME
202         right_map::reference       right_reference;
203     typedef BOOST_DEDUCED_TYPENAME
204         right_map::const_reference right_const_reference;
205 
206     typedef BOOST_DEDUCED_TYPENAME base_::relation::info_type info_type;
207 
208     typedef BOOST_DEDUCED_TYPENAME base_::core_type::allocator_type allocator_type;
209 
210     /// Left map view
211     left_map  left;
212 
213     /// Right map view
214     right_map right;
215 
216     typedef BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag
217                                           logic_relation_set_tag;
218     typedef BOOST_DEDUCED_TYPENAME base_::logic_left_tag logic_left_tag;
219     typedef BOOST_DEDUCED_TYPENAME base_::logic_right_tag logic_right_tag;
220     typedef BOOST_DEDUCED_TYPENAME base_::core_type::ctor_args_list
221                                                      ctor_args_list;
222 
bimap(const allocator_type & al=allocator_type ())223    bimap(const allocator_type& al = allocator_type()) :
224 
225        base_::relation_set(
226            ::boost::multi_index::get<
227                logic_relation_set_tag
228            >(core)
229        ),
230 
231        core(al),
232 
233        left (
234            ::boost::multi_index::get<
235                logic_left_tag
236            >(core)
237        ),
238        right (
239            ::boost::multi_index::get<
240                logic_right_tag
241            >(core)
242        )
243 
244    {}
245 
246    template< class InputIterator >
bimap(InputIterator first,InputIterator last,const allocator_type & al=allocator_type ())247    bimap(InputIterator first,InputIterator last,
248          const allocator_type& al = allocator_type()) :
249 
250        base_::relation_set(
251            ::boost::multi_index::get<
252                BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(core)
253        ),
254 
255        core(first,last,ctor_args_list(),al),
256 
257        left (
258            ::boost::multi_index::get<
259                BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(core)
260        ),
261        right (
262            ::boost::multi_index::get<
263                BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(core)
264        )
265 
266    {}
267 
bimap(const bimap & x)268    bimap(const bimap& x) :
269 
270        base_::relation_set(
271            ::boost::multi_index::get<
272                BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(core)
273        ),
274 
275        core(x.core),
276 
277        left (
278            ::boost::multi_index::get<
279                BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(core)
280        ),
281        right (
282            ::boost::multi_index::get<
283                BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(core)
284        )
285 
286    {}
287 
operator =(const bimap & x)288     bimap& operator=(const bimap& x)
289     {
290         core = x.core;
291         return *this;
292     }
293 
294     // Projection of iterators
295 
296     template< class IteratorType >
project_left(IteratorType iter)297     left_iterator project_left(IteratorType iter)
298     {
299         return core.template project<
300             BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(iter.base());
301     }
302 
303     template< class IteratorType >
project_left(IteratorType iter) const304     left_const_iterator project_left(IteratorType iter) const
305     {
306         return core.template project<
307             BOOST_DEDUCED_TYPENAME base_::logic_left_tag>(iter.base());
308     }
309 
310     template< class IteratorType >
project_right(IteratorType iter)311     right_iterator project_right(IteratorType iter)
312     {
313         return core.template project<
314             BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(iter.base());
315     }
316 
317     template< class IteratorType >
project_right(IteratorType iter) const318     right_const_iterator project_right(IteratorType iter) const
319     {
320         return core.template project<
321             BOOST_DEDUCED_TYPENAME base_::logic_right_tag>(iter.base());
322     }
323 
324     template< class IteratorType >
325     BOOST_DEDUCED_TYPENAME base_::relation_set::iterator
project_up(IteratorType iter)326         project_up(IteratorType iter)
327     {
328         return core.template project<
329             BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(iter.base());
330     }
331 
332     template< class IteratorType >
333     BOOST_DEDUCED_TYPENAME base_::relation_set::const_iterator
project_up(IteratorType iter) const334         project_up(IteratorType iter) const
335     {
336         return core.template project<
337             BOOST_DEDUCED_TYPENAME base_::logic_relation_set_tag>(iter.base());
338     }
339 
340     // Support for tags
341 
342     template< class Tag, class IteratorType >
343     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
344     iterator_type_by<Tag,bimap>::type
project(IteratorType iter)345         project(IteratorType iter)
346     {
347         return core.template project<Tag>(iter.base());
348     }
349 
350     template< class Tag, class IteratorType >
351     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
352     const_iterator_type_by<Tag,bimap>::type
project(IteratorType iter) const353         project(IteratorType iter) const
354     {
355         return core.template project<Tag>(iter.base());
356     }
357 
358     template< class Tag >
359     struct map_by :
360         public ::boost::bimaps::support::map_type_by<Tag,bimap>::type
361     {
362         typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
363             map_type_by<Tag,bimap>::type type;
364 
map_byboost::bimaps::bimap::map_by365         private: map_by() {}
366     };
367 
368     template< class Tag >
369     BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
by()370     map_type_by<Tag,bimap>::type &by()
371     {
372         return ::boost::bimaps::support::map_by<Tag>(*this);
373     }
374 
375     template< class Tag >
376     const BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
by() const377     map_type_by<Tag,bimap>::type &by() const
378     {
379         return ::boost::bimaps::support::map_by<Tag>(*this);
380     }
381 
382 
383     #ifndef BOOST_BIMAP_DISABLE_SERIALIZATION
384 
385     // Serialization support
386 
387     private:
388 
389     friend class boost::serialization::access;
390 
391     template<class Archive>
serialize(Archive & ar,const unsigned int)392     void serialize(Archive & ar, const unsigned int)
393     {
394         ar & serialization::make_nvp("mi_core",core);
395     }
396 
397     #endif // BOOST_BIMAP_DISABLE_SERIALIZATION
398 };
399 
400 } // namespace bimaps
401 } // namespace boost
402 
403 
404 /** \namespace boost::bimaps::support
405 \brief Metafunctions to help working with bimaps.
406                                                             **/
407 
408 /** \namespace boost::bimaps::views
409 \brief Bimap views.
410                                                             **/
411 
412 /** \namespace boost::bimaps::views::detail
413 \brief Bimap views details.
414                                                             **/
415 
416 
417 
418 // Include basic tools for user commodity
419 
420 #include <boost/bimap/tags/tagged.hpp>
421 #include <boost/bimap/relation/member_at.hpp>
422 #include <boost/multi_index/detail/unbounded.hpp>
423 
424 // Bring the most used namespaces directly to the user main namespace
425 namespace boost {
426 namespace bimaps {
427 
428 using ::boost::bimaps::tags::tagged;
429 
430 namespace member_at = ::boost::bimaps::relation::member_at;
431 
432 using ::boost::multi_index::unbounded;
433 
434 } // namespace bimaps
435 } // namespace boost
436 
437 
438 #endif // BOOST_BIMAP_BIMAP_HPP
439