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/map_view_base.hpp
10 /// \brief Helper base for the construction of the bimap views types.
11
12 #ifndef BOOST_BIMAP_DETAIL_MAP_VIEW_BASE_HPP
13 #define BOOST_BIMAP_DETAIL_MAP_VIEW_BASE_HPP
14
15 #if defined(_MSC_VER)
16 #pragma once
17 #endif
18
19 #include <boost/config.hpp>
20
21 #include <stdexcept>
22 #include <utility>
23
24 #include <boost/throw_exception.hpp>
25 #include <boost/type_traits/is_const.hpp>
26 #include <boost/mpl/if.hpp>
27
28 #include <boost/bimap/relation/support/get_pair_functor.hpp>
29 #include <boost/bimap/relation/detail/to_mutable_relation_functor.hpp>
30 #include <boost/bimap/container_adaptor/support/iterator_facade_converters.hpp>
31 #include <boost/bimap/relation/support/data_extractor.hpp>
32 #include <boost/bimap/relation/support/opposite_tag.hpp>
33 #include <boost/bimap/relation/support/pair_type_by.hpp>
34 //#include <boost/bimap/support/iterator_type_by.hpp>
35 #include <boost/bimap/support/key_type_by.hpp>
36 #include <boost/bimap/support/data_type_by.hpp>
37 #include <boost/bimap/support/value_type_by.hpp>
38 #include <boost/bimap/detail/modifier_adaptor.hpp>
39 #include <boost/bimap/detail/debug/static_error.hpp>
40 #include <boost/bimap/detail/map_view_iterator.hpp>
41
42 namespace boost {
43 namespace bimaps {
44
45 namespace detail {
46
47
48 // The next macro can be converted in a metafunctor to gain code robustness.
49 /*===========================================================================*/
50 #define BOOST_BIMAP_MAP_VIEW_CONTAINER_ADAPTOR( \
51 CONTAINER_ADAPTOR, TAG, BIMAP, OTHER_ITER, CONST_OTHER_ITER \
52 ) \
53 ::boost::bimaps::container_adaptor::CONTAINER_ADAPTOR \
54 < \
55 BOOST_DEDUCED_TYPENAME BIMAP::core_type:: \
56 BOOST_NESTED_TEMPLATE index<TAG>::type, \
57 ::boost::bimaps::detail:: map_view_iterator<TAG,BIMAP>, \
58 ::boost::bimaps::detail::const_map_view_iterator<TAG,BIMAP>, \
59 ::boost::bimaps::detail:: OTHER_ITER<TAG,BIMAP>, \
60 ::boost::bimaps::detail::CONST_OTHER_ITER<TAG,BIMAP>, \
61 ::boost::bimaps::container_adaptor::support::iterator_facade_to_base \
62 < \
63 ::boost::bimaps::detail:: map_view_iterator<TAG,BIMAP>, \
64 ::boost::bimaps::detail::const_map_view_iterator<TAG,BIMAP> \
65 >, \
66 ::boost::mpl::na, \
67 ::boost::mpl::na, \
68 ::boost::bimaps::relation::detail:: \
69 pair_to_relation_functor<TAG,BOOST_DEDUCED_TYPENAME BIMAP::relation>, \
70 ::boost::bimaps::relation::support:: \
71 get_pair_functor<TAG, BOOST_DEDUCED_TYPENAME BIMAP::relation > \
72 >
73 /*===========================================================================*/
74
75
76 #if defined(BOOST_MSVC)
77 /*===========================================================================*/
78 #define BOOST_BIMAP_MAP_VIEW_BASE_FRIEND(TYPE,TAG,BIMAP) \
79 typedef ::boost::bimaps::detail::map_view_base< \
80 TYPE<TAG,BIMAP>,TAG,BIMAP > friend_map_view_base; \
81 friend class friend_map_view_base;
82 /*===========================================================================*/
83 #else
84 /*===========================================================================*/
85 #define BOOST_BIMAP_MAP_VIEW_BASE_FRIEND(TYPE,TAG,BIMAP) \
86 friend class ::boost::bimaps::detail::map_view_base< \
87 TYPE<TAG,BIMAP>,TAG,BIMAP >;
88 /*===========================================================================*/
89 #endif
90
91
92 /// \brief Common base for map views.
93
94 template< class Derived, class Tag, class BimapType>
95 class map_view_base
96 {
97 typedef ::boost::bimaps::container_adaptor::support::
98 iterator_facade_to_base<
99 ::boost::bimaps::detail:: map_view_iterator<Tag,BimapType>,
100 ::boost::bimaps::detail::const_map_view_iterator<Tag,BimapType>
101 > iterator_to_base_;
102
103 typedef ::boost::bimaps::relation::detail::
104 pair_to_relation_functor<Tag,
105 BOOST_DEDUCED_TYPENAME BimapType::relation> value_to_base_;
106
107 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
108 key_type_by<Tag,BimapType>::type key_type_;
109
110 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
111 data_type_by<Tag,BimapType>::type data_type_;
112
113 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::relation::support::
114 pair_type_by<Tag,
115 BOOST_DEDUCED_TYPENAME BimapType::relation>::type value_type_;
116
117 typedef
118 ::boost::bimaps::detail::map_view_iterator<Tag,BimapType> iterator_;
119
120 public:
121
replace(iterator_ position,const value_type_ & x)122 bool replace(iterator_ position, const value_type_ & x)
123 {
124 return derived().base().replace(
125 derived().template functor<iterator_to_base_>()(position),
126 derived().template functor<value_to_base_>()(x)
127 );
128 }
129
130 template< class CompatibleKey >
replace_key(iterator_ position,const CompatibleKey & k)131 bool replace_key(iterator_ position, const CompatibleKey & k)
132 {
133 return derived().base().replace(
134 derived().template functor<iterator_to_base_>()(position),
135 derived().template functor<value_to_base_>()(
136 ::boost::bimaps::relation::detail::
137 copy_with_first_replaced(*position,k)
138 )
139 );
140 }
141
142 template< class CompatibleData >
replace_data(iterator_ position,const CompatibleData & d)143 bool replace_data(iterator_ position, const CompatibleData & d)
144 {
145 return derived().base().replace(
146 derived().template functor<iterator_to_base_>()(position),
147 derived().template functor<value_to_base_>()(
148 ::boost::bimaps::relation::detail::
149 copy_with_second_replaced(*position,d)
150 )
151 );
152 }
153
154 /* This function may be provided in the future
155
156 template< class Modifier >
157 bool modify(iterator_ position, Modifier mod)
158 {
159 return derived().base().modify(
160
161 derived().template functor<iterator_to_base_>()(position),
162
163 ::boost::bimaps::detail::relation_modifier_adaptor
164 <
165 Modifier,
166 BOOST_DEDUCED_TYPENAME BimapType::relation,
167 BOOST_DEDUCED_TYPENAME ::boost::bimaps::relation::support::
168 data_extractor
169 <
170 Tag, BOOST_DEDUCED_TYPENAME BimapType::relation
171
172 >::type,
173 BOOST_DEDUCED_TYPENAME ::boost::bimaps::relation::support::
174 data_extractor
175 <
176 BOOST_DEDUCED_TYPENAME ::boost::bimaps::relation::support::
177 opossite_tag<Tag,BimapType>::type,
178 BOOST_DEDUCED_TYPENAME BimapType::relation
179
180 >::type
181
182 >(mod)
183 );
184 }
185 */
186
187 template< class Modifier >
modify_key(iterator_ position,Modifier mod)188 bool modify_key(iterator_ position, Modifier mod)
189 {
190 return derived().base().modify_key(
191 derived().template functor<iterator_to_base_>()(position), mod
192 );
193 }
194
195 template< class Modifier >
modify_data(iterator_ position,Modifier mod)196 bool modify_data(iterator_ position, Modifier mod)
197 {
198 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::relation::support::
199 data_extractor
200 <
201 BOOST_DEDUCED_TYPENAME ::boost::bimaps::relation::support::
202 opossite_tag<Tag,BimapType>::type,
203 BOOST_DEDUCED_TYPENAME BimapType::relation
204
205 >::type data_extractor_;
206
207 return derived().base().modify(
208
209 derived().template functor<iterator_to_base_>()(position),
210
211 // this may be replaced later by
212 // ::boost::bind( mod, ::boost::bind(data_extractor_(),_1) )
213
214 ::boost::bimaps::detail::unary_modifier_adaptor
215 <
216 Modifier,
217 BOOST_DEDUCED_TYPENAME BimapType::relation,
218 data_extractor_
219
220 >(mod)
221 );
222 }
223
224 protected:
225
226 typedef map_view_base map_view_base_;
227
228 private:
229
230 // Curiously Recurring Template interface.
231
derived()232 Derived& derived()
233 {
234 return *static_cast<Derived*>(this);
235 }
236
derived() const237 Derived const& derived() const
238 {
239 return *static_cast<Derived const*>(this);
240 }
241 };
242
243
244
245
246 template< class Derived, class Tag, class BimapType>
247 class mutable_data_unique_map_view_access
248 {
249 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
250 data_type_by<Tag,BimapType>::type data_type_;
251
252 public:
253
254 template< class CompatibleKey >
at(const CompatibleKey & k)255 data_type_ & at(const CompatibleKey& k)
256 {
257 typedef ::boost::bimaps::detail::
258 map_view_iterator<Tag,BimapType> iterator;
259
260 iterator iter = derived().find(k);
261 if( iter == derived().end() )
262 {
263 ::boost::throw_exception(
264 std::out_of_range("bimap<>: invalid key")
265 );
266 }
267 return iter->second;
268 }
269
270 template< class CompatibleKey >
at(const CompatibleKey & k) const271 const data_type_ & at(const CompatibleKey& k) const
272 {
273 typedef ::boost::bimaps::detail::
274 const_map_view_iterator<Tag,BimapType> const_iterator;
275
276 const_iterator iter = derived().find(k);
277 if( iter == derived().end() )
278 {
279 ::boost::throw_exception(
280 std::out_of_range("bimap<>: invalid key")
281 );
282 }
283 return iter->second;
284 }
285
286 template< class CompatibleKey >
operator [](const CompatibleKey & k)287 data_type_ & operator[](const CompatibleKey& k)
288 {
289 typedef ::boost::bimaps::detail::
290 map_view_iterator<Tag,BimapType> iterator;
291
292 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
293 value_type_by<Tag,BimapType>::type value_type;
294
295 iterator iter = derived().find(k);
296 if( iter == derived().end() )
297 {
298 iter = derived().insert( value_type(k,data_type_()) ).first;
299 }
300 return iter->second;
301 }
302
303 protected:
304
305 typedef mutable_data_unique_map_view_access
306 mutable_data_unique_map_view_access_;
307
308 private:
309
310 // Curiously Recurring Template interface.
311
derived()312 Derived& derived()
313 {
314 return *static_cast<Derived*>(this);
315 }
316
derived() const317 Derived const& derived() const
318 {
319 return *static_cast<Derived const*>(this);
320 }
321 };
322
323
324 template< class Derived, class Tag, class BimapType>
325 class non_mutable_data_unique_map_view_access
326 {
327 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
328 data_type_by<Tag,BimapType>::type data_type_;
329
330 public:
331
332 template< class CompatibleKey >
at(const CompatibleKey & k) const333 const data_type_ & at(const CompatibleKey& k) const
334 {
335 typedef ::boost::bimaps::detail::
336 const_map_view_iterator<Tag,BimapType> const_iterator;
337
338 const_iterator iter = derived().find(k);
339 if( iter == derived().end() )
340 {
341 ::boost::throw_exception(
342 std::out_of_range("bimap<>: invalid key")
343 );
344 }
345 return iter->second;
346 }
347
348 template< class CompatibleKey >
operator [](const CompatibleKey &)349 data_type_ & operator[](const CompatibleKey&)
350 {
351 BOOST_BIMAP_STATIC_ERROR( OPERATOR_BRACKET_IS_NOT_SUPPORTED, (Derived));
352 }
353
354 protected:
355
356 typedef non_mutable_data_unique_map_view_access
357 non_mutable_data_unique_map_view_access_;
358
359 private:
360
361 // Curiously Recurring Template interface.
362
derived()363 Derived& derived()
364 {
365 return *static_cast<Derived*>(this);
366 }
367
derived() const368 Derived const& derived() const
369 {
370 return *static_cast<Derived const*>(this);
371 }
372 };
373
374
375 template< class Derived, class Tag, class BimapType>
376 struct unique_map_view_access
377 {
378 private:
379 typedef BOOST_DEDUCED_TYPENAME ::boost::bimaps::support::
380 value_type_by<Tag,BimapType>::type value_type;
381
382 public:
383 typedef BOOST_DEDUCED_TYPENAME ::boost::mpl::if_
384 <
385 typename ::boost::is_const<
386 BOOST_DEDUCED_TYPENAME value_type::second_type >::type,
387
388 non_mutable_data_unique_map_view_access<Derived,Tag,BimapType>,
389 mutable_data_unique_map_view_access<Derived,Tag,BimapType>
390
391 >::type type;
392 };
393
394 // Map views specialize the following structs to provide to the bimap class
395 // the extra side typedefs (i.e. left_local_iterator for unordered_maps,
396 // right_range_type for maps)
397
398 template< class MapView >
399 struct left_map_view_extra_typedefs {};
400
401 template< class MapView >
402 struct right_map_view_extra_typedefs {};
403
404 } // namespace detail
405
406 // This function is already part of Boost.Lambda.
407 // They may be moved to Boost.Utility.
408
make_const(const T & t)409 template <class T> inline const T& make_const(const T& t) { return t; }
410
411 } // namespace bimaps
412 } // namespace boost
413
414
415 // The following macros avoids code duplication in map views
416 // Maybe this can be changed in the future using a scheme similar to
417 // the one used with map_view_base.
418
419 /*===========================================================================*/
420 #define BOOST_BIMAP_MAP_VIEW_RANGE_IMPLEMENTATION(BASE) \
421 \
422 typedef std::pair< \
423 BOOST_DEDUCED_TYPENAME base_::iterator, \
424 BOOST_DEDUCED_TYPENAME base_::iterator> range_type; \
425 \
426 typedef std::pair< \
427 BOOST_DEDUCED_TYPENAME base_::const_iterator, \
428 BOOST_DEDUCED_TYPENAME base_::const_iterator> const_range_type; \
429 \
430 \
431 template< class LowerBounder, class UpperBounder> \
432 range_type range(LowerBounder lower,UpperBounder upper) \
433 { \
434 std::pair< \
435 \
436 BOOST_DEDUCED_TYPENAME BASE::base_type::iterator, \
437 BOOST_DEDUCED_TYPENAME BASE::base_type::iterator \
438 \
439 > r( this->base().range(lower,upper) ); \
440 \
441 return range_type( \
442 this->template functor< \
443 BOOST_DEDUCED_TYPENAME BASE::iterator_from_base \
444 >() ( r.first ), \
445 this->template functor< \
446 BOOST_DEDUCED_TYPENAME BASE::iterator_from_base \
447 >() ( r.second ) \
448 ); \
449 } \
450 \
451 template< class LowerBounder, class UpperBounder> \
452 const_range_type range(LowerBounder lower,UpperBounder upper) const \
453 { \
454 std::pair< \
455 \
456 BOOST_DEDUCED_TYPENAME BASE::base_type::const_iterator, \
457 BOOST_DEDUCED_TYPENAME BASE::base_type::const_iterator \
458 \
459 > r( this->base().range(lower,upper) ); \
460 \
461 return const_range_type( \
462 this->template functor< \
463 BOOST_DEDUCED_TYPENAME BASE::iterator_from_base \
464 >() ( r.first ), \
465 this->template functor< \
466 BOOST_DEDUCED_TYPENAME BASE::iterator_from_base \
467 >() ( r.second ) \
468 ); \
469 }
470 /*===========================================================================*/
471
472
473 /*===========================================================================*/
474 #define BOOST_BIMAP_VIEW_ASSIGN_IMPLEMENTATION(BASE) \
475 \
476 template< class InputIterator > \
477 void assign(InputIterator first,InputIterator last) \
478 { \
479 this->clear(); \
480 this->insert(this->end(),first,last); \
481 } \
482 \
483 void assign(BOOST_DEDUCED_TYPENAME BASE::size_type n, \
484 const BOOST_DEDUCED_TYPENAME BASE::value_type& v) \
485 { \
486 this->clear(); \
487 for(BOOST_DEDUCED_TYPENAME BASE::size_type i = 0 ; i < n ; ++i) \
488 { \
489 this->push_back(v); \
490 } \
491 }
492 /*===========================================================================*/
493
494
495 /*===========================================================================*/
496 #define BOOST_BIMAP_VIEW_FRONT_BACK_IMPLEMENTATION(BASE) \
497 \
498 BOOST_DEDUCED_TYPENAME BASE::reference front() \
499 { \
500 return this->template functor< \
501 BOOST_DEDUCED_TYPENAME base_::value_from_base>() \
502 ( \
503 const_cast \
504 < \
505 BOOST_DEDUCED_TYPENAME BASE::base_type::value_type & \
506 \
507 > ( this->base().front() ) \
508 ); \
509 } \
510 \
511 BOOST_DEDUCED_TYPENAME BASE::reference back() \
512 { \
513 return this->template functor< \
514 BOOST_DEDUCED_TYPENAME base_::value_from_base>() \
515 ( \
516 const_cast \
517 < \
518 BOOST_DEDUCED_TYPENAME BASE::base_type::value_type & \
519 \
520 >( this->base().back() ) \
521 ); \
522 } \
523 \
524 BOOST_DEDUCED_TYPENAME BASE::const_reference front() const \
525 { \
526 return this->template functor< \
527 BOOST_DEDUCED_TYPENAME BASE::value_from_base>() \
528 ( \
529 this->base().front() \
530 ); \
531 } \
532 \
533 BOOST_DEDUCED_TYPENAME BASE::const_reference back() const \
534 { \
535 return this->template functor< \
536 BOOST_DEDUCED_TYPENAME BASE::value_from_base>() \
537 ( \
538 this->base().back() \
539 ); \
540 }
541 /*===========================================================================*/
542
543
544 #endif // BOOST_BIMAP_DETAIL_MAP_VIEW_BASE_HPP
545