1 ///////////////////////////////////////////////////////////////////////////////
2 // depends_on.hpp
3 //
4 //  Copyright 2005 Eric Niebler. Distributed under the Boost
5 //  Software License, Version 1.0. (See accompanying file
6 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
7 
8 #ifndef BOOST_ACCUMULATORS_FRAMEWORK_DEPENDS_ON_HPP_EAN_28_10_2005
9 #define BOOST_ACCUMULATORS_FRAMEWORK_DEPENDS_ON_HPP_EAN_28_10_2005
10 
11 #include <boost/version.hpp>
12 #include <boost/mpl/end.hpp>
13 #include <boost/mpl/map.hpp>
14 #include <boost/mpl/set.hpp>
15 #include <boost/mpl/copy.hpp>
16 #include <boost/mpl/fold.hpp>
17 #include <boost/mpl/size.hpp>
18 #include <boost/mpl/sort.hpp>
19 #include <boost/mpl/insert.hpp>
20 #include <boost/mpl/assert.hpp>
21 #include <boost/mpl/remove.hpp>
22 #include <boost/mpl/vector.hpp>
23 #include <boost/mpl/inherit.hpp>
24 #include <boost/mpl/identity.hpp>
25 #include <boost/mpl/equal_to.hpp>
26 #include <boost/mpl/contains.hpp>
27 #include <boost/mpl/transform.hpp>
28 #include <boost/mpl/is_sequence.hpp>
29 #include <boost/mpl/placeholders.hpp>
30 #include <boost/mpl/insert_range.hpp>
31 #include <boost/mpl/back_inserter.hpp>
32 #include <boost/mpl/transform_view.hpp>
33 #include <boost/mpl/inherit_linearly.hpp>
34 #include <boost/type_traits/is_base_and_derived.hpp>
35 #include <boost/preprocessor/repetition/repeat.hpp>
36 #include <boost/preprocessor/repetition/enum_params.hpp>
37 #include <boost/preprocessor/facilities/intercept.hpp>
38 #include <boost/accumulators/accumulators_fwd.hpp>
39 #include <boost/fusion/include/next.hpp>
40 #include <boost/fusion/include/equal_to.hpp>
41 #include <boost/fusion/include/value_of.hpp>
42 #include <boost/fusion/include/mpl.hpp>
43 #include <boost/fusion/include/end.hpp>
44 #include <boost/fusion/include/begin.hpp>
45 #include <boost/fusion/include/cons.hpp>
46 
47 namespace boost { namespace accumulators
48 {
49     ///////////////////////////////////////////////////////////////////////////
50     // as_feature
51     template<typename Feature>
52     struct as_feature
53     {
54         typedef Feature type;
55     };
56 
57     ///////////////////////////////////////////////////////////////////////////
58     // weighted_feature
59     template<typename Feature>
60     struct as_weighted_feature
61     {
62         typedef Feature type;
63     };
64 
65     ///////////////////////////////////////////////////////////////////////////
66     // feature_of
67     template<typename Feature>
68     struct feature_of
69     {
70         typedef Feature type;
71     };
72 
73     namespace detail
74     {
75         ///////////////////////////////////////////////////////////////////////////
76         // feature_tag
77         template<typename Accumulator>
78         struct feature_tag
79         {
80             typedef typename Accumulator::feature_tag type;
81         };
82 
83         template<typename Feature>
84         struct undroppable
85         {
86             typedef Feature type;
87         };
88 
89         template<typename Feature>
90         struct undroppable<tag::droppable<Feature> >
91         {
92             typedef Feature type;
93         };
94 
95         // For the purpose of determining whether one feature depends on another,
96         // disregard whether the feature is droppable or not.
97         template<typename A, typename B>
98         struct is_dependent_on
99           : is_base_and_derived<
100                 typename feature_of<typename undroppable<B>::type>::type
101               , typename undroppable<A>::type
102             >
103         {};
104 
105         template<typename Feature>
106         struct dependencies_of
107         {
108             typedef typename Feature::dependencies type;
109         };
110 
111         // Should use mpl::insert_range, but doesn't seem to work with mpl sets
112         template<typename Set, typename Range>
113         struct set_insert_range
114           : mpl::fold<
115                 Range
116               , Set
117               , mpl::insert<mpl::_1, mpl::_2>
118             >
119         {};
120 
121         template<typename Features>
122         struct collect_abstract_features
123           : mpl::fold<
124                 Features
125               , mpl::set0<>
126               , set_insert_range<
127                     mpl::insert<mpl::_1, feature_of<mpl::_2> >
128                   , collect_abstract_features<dependencies_of<mpl::_2> >
129                 >
130             >
131         {};
132 
133         template<typename Features>
134         struct depends_on_base
135           : mpl::inherit_linearly<
136                 typename mpl::sort<
137                     typename mpl::copy<
138                         typename collect_abstract_features<Features>::type
139                       , mpl::back_inserter<mpl::vector0<> >
140                     >::type
141                   , is_dependent_on<mpl::_1, mpl::_2>
142                 >::type
143                 // Don't inherit multiply from a feature
144               , mpl::if_<
145                     is_dependent_on<mpl::_1, mpl::_2>
146                   , mpl::_1
147                   , mpl::inherit<mpl::_1, mpl::_2>
148                 >
149             >::type
150         {
151         };
152     }
153 
154     ///////////////////////////////////////////////////////////////////////////
155     /// depends_on
156     template<BOOST_PP_ENUM_PARAMS(BOOST_ACCUMULATORS_MAX_FEATURES, typename Feature)>
157     struct depends_on
158       : detail::depends_on_base<
159             typename mpl::transform<
160                 mpl::vector<BOOST_PP_ENUM_PARAMS(BOOST_ACCUMULATORS_MAX_FEATURES, Feature)>
161               , as_feature<mpl::_1>
162             >::type
163         >
164     {
165         typedef mpl::false_ is_weight_accumulator;
166         typedef
167             typename mpl::transform<
168                 mpl::vector<BOOST_PP_ENUM_PARAMS(BOOST_ACCUMULATORS_MAX_FEATURES, Feature)>
169               , as_feature<mpl::_1>
170             >::type
171         dependencies;
172     };
173 
174     namespace detail
175     {
176         template<typename Feature>
177         struct matches_feature
178         {
179             template<typename Accumulator>
180             struct apply
181               : is_same<
182                     typename feature_of<typename as_feature<Feature>::type>::type
183                   , typename feature_of<typename as_feature<typename feature_tag<Accumulator>::type>::type>::type
184                 >
185             {};
186         };
187 
188         template<typename Features, typename Accumulator>
189         struct contains_feature_of
190         {
191             typedef
192                 mpl::transform_view<Features, feature_of<as_feature<mpl::_> > >
193             features_list;
194 
195             typedef
196                 typename feature_of<typename feature_tag<Accumulator>::type>::type
197             the_feature;
198 
199             typedef
200                 typename mpl::contains<features_list, the_feature>::type
201             type;
202         };
203 
204         // This is to work around a bug in early versions of Fusion which caused
205         // a compile error if contains_feature_of<List, mpl::_> is used as a
206         // predicate to fusion::find_if
207         template<typename Features>
208         struct contains_feature_of_
209         {
210             template<typename Accumulator>
211             struct apply
212               : contains_feature_of<Features, Accumulator>
213             {};
214         };
215 
216         template<
217             typename First
218           , typename Last
219           , bool is_empty = fusion::result_of::equal_to<First, Last>::value
220         >
221         struct build_acc_list;
222 
223         template<typename First, typename Last>
224         struct build_acc_list<First, Last, true>
225         {
226             typedef fusion::nil_ type;
227 
228             template<typename Args>
229             static fusion::nil_
callboost::accumulators::detail::build_acc_list230             call(Args const &, First const&, Last const&)
231             {
232                 return fusion::nil_();
233             }
234         };
235 
236         template<typename First, typename Last>
237         struct build_acc_list<First, Last, false>
238         {
239             typedef
240                 build_acc_list<typename fusion::result_of::next<First>::type, Last>
241             next_build_acc_list;
242 
243             typedef fusion::cons<
244                 typename fusion::result_of::value_of<First>::type
245               , typename next_build_acc_list::type>
246             type;
247 
248             template<typename Args>
249             static type
callboost::accumulators::detail::build_acc_list250             call(Args const &args, First const& f, Last const& l)
251             {
252                 return type(args, next_build_acc_list::call(args, fusion::next(f), l));
253             }
254         };
255 
256         namespace meta
257         {
258             template<typename Sequence>
259             struct make_acc_list
260               : build_acc_list<
261                     typename fusion::result_of::begin<Sequence>::type
262                   , typename fusion::result_of::end<Sequence>::type
263                 >
264             {};
265         }
266 
267         template<typename Sequence, typename Args>
268         typename meta::make_acc_list<Sequence>::type
make_acc_list(Sequence const & seq,Args const & args)269         make_acc_list(Sequence const &seq, Args const &args)
270         {
271             return meta::make_acc_list<Sequence>::call(args, fusion::begin(seq), fusion::end(seq));
272         }
273 
274         ///////////////////////////////////////////////////////////////////////////
275         // checked_as_weighted_feature
276         template<typename Feature>
277         struct checked_as_weighted_feature
278         {
279             typedef typename as_feature<Feature>::type feature_type;
280             typedef typename as_weighted_feature<feature_type>::type type;
281             // weighted and non-weighted flavors should provide the same feature.
282             BOOST_MPL_ASSERT((
283                 is_same<
284                     typename feature_of<feature_type>::type
285                   , typename feature_of<type>::type
286                 >
287             ));
288         };
289 
290         ///////////////////////////////////////////////////////////////////////////
291         // as_feature_list
292         template<typename Features, typename Weight>
293         struct as_feature_list
294           : mpl::transform_view<Features, checked_as_weighted_feature<mpl::_1> >
295         {
296         };
297 
298         template<typename Features>
299         struct as_feature_list<Features, void>
300           : mpl::transform_view<Features, as_feature<mpl::_1> >
301         {
302         };
303 
304         ///////////////////////////////////////////////////////////////////////////
305         // accumulator_wrapper
306         template<typename Accumulator, typename Feature>
307         struct accumulator_wrapper
308           : Accumulator
309         {
310             typedef Feature feature_tag;
311 
accumulator_wrapperboost::accumulators::detail::accumulator_wrapper312             accumulator_wrapper(accumulator_wrapper const &that)
313               : Accumulator(*static_cast<Accumulator const *>(&that))
314             {
315             }
316 
317             template<typename Args>
accumulator_wrapperboost::accumulators::detail::accumulator_wrapper318             accumulator_wrapper(Args const &args)
319               : Accumulator(args)
320             {
321             }
322         };
323 
324         ///////////////////////////////////////////////////////////////////////////
325         // to_accumulator
326         template<typename Feature, typename Sample, typename Weight>
327         struct to_accumulator
328         {
329             typedef
330                 accumulator_wrapper<
331                     typename mpl::apply2<typename Feature::impl, Sample, Weight>::type
332                   , Feature
333                 >
334             type;
335         };
336 
337         template<typename Feature, typename Sample, typename Weight, typename Tag, typename AccumulatorSet>
338         struct to_accumulator<Feature, Sample, tag::external<Weight, Tag, AccumulatorSet> >
339         {
340             BOOST_MPL_ASSERT((is_same<Tag, void>));
341             BOOST_MPL_ASSERT((is_same<AccumulatorSet, void>));
342 
343             typedef
344                 accumulator_wrapper<
345                     typename mpl::apply2<typename Feature::impl, Sample, Weight>::type
346                   , Feature
347                 >
348             accumulator_type;
349 
350             typedef
351                 typename mpl::if_<
352                     typename Feature::is_weight_accumulator
353                   , accumulator_wrapper<impl::external_impl<accumulator_type, tag::weights>, Feature>
354                   , accumulator_type
355                 >::type
356             type;
357         };
358 
359         // BUGBUG work around an MPL bug wrt map insertion
360         template<typename FeatureMap, typename Feature>
361         struct insert_feature
362           : mpl::eval_if<
363                 mpl::has_key<FeatureMap, typename feature_of<Feature>::type>
364               , mpl::identity<FeatureMap>
365               , mpl::insert<FeatureMap, mpl::pair<typename feature_of<Feature>::type, Feature> >
366             >
367         {
368         };
369 
370         template<typename FeatureMap, typename Feature, typename Weight>
371         struct insert_dependencies
372           : mpl::fold<
373                 as_feature_list<typename Feature::dependencies, Weight>
374               , FeatureMap
375               , insert_dependencies<
376                     insert_feature<mpl::_1, mpl::_2>
377                   , mpl::_2
378                   , Weight
379                 >
380             >
381         {
382         };
383 
384         template<typename FeatureMap, typename Features, typename Weight>
385         struct insert_sequence
386           : mpl::fold< // BUGBUG should use insert_range, but doesn't seem to work for maps
387                 as_feature_list<Features, Weight>
388               , FeatureMap
389               , insert_feature<mpl::_1, mpl::_2>
390             >
391         {
392         };
393 
394         template<typename Features, typename Sample, typename Weight>
395         struct make_accumulator_tuple
396         {
397             typedef
398                 typename mpl::fold<
399                     as_feature_list<Features, Weight>
400                   , mpl::map0<>
401                   , mpl::if_<
402                         mpl::is_sequence<mpl::_2>
403                       , insert_sequence<mpl::_1, mpl::_2, Weight>
404                       , insert_feature<mpl::_1, mpl::_2>
405                     >
406                 >::type
407             feature_map;
408 
409             // for each element in the map, add its dependencies also
410             typedef
411                 typename mpl::fold<
412                     feature_map
413                   , feature_map
414                   , insert_dependencies<mpl::_1, mpl::second<mpl::_2>, Weight>
415                 >::type
416             feature_map_with_dependencies;
417 
418             // turn the map into a vector so we can sort it
419             typedef
420                 typename mpl::insert_range<
421                     mpl::vector<>
422                   , mpl::end<mpl::vector<> >::type
423                   , mpl::transform_view<feature_map_with_dependencies, mpl::second<mpl::_1> >
424                 >::type
425             feature_vector_with_dependencies;
426 
427             // sort the features according to which is derived from which
428             typedef
429                 typename mpl::sort<
430                     feature_vector_with_dependencies
431                   , is_dependent_on<mpl::_2, mpl::_1>
432                 >::type
433             sorted_feature_vector;
434 
435             // From the vector of features, construct a vector of accumulators
436             typedef
437                 typename mpl::transform<
438                     sorted_feature_vector
439                   , to_accumulator<mpl::_1, Sample, Weight>
440                 >::type
441             type;
442         };
443 
444     } // namespace detail
445 
446 }} // namespace boost::accumulators
447 
448 #endif
449