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 & seq,Args const & args)269         make_acc_list(Sequence &seq, Args const &args)
270         {
271             return meta::make_acc_list<Sequence>::call(args, fusion::begin(seq), fusion::end(seq));
272         }
273 
274         template<typename Sequence, typename Args>
275         typename meta::make_acc_list<Sequence>::type
make_acc_list(Sequence const & seq,Args const & args)276         make_acc_list(Sequence const &seq, Args const &args)
277         {
278             return meta::make_acc_list<Sequence const>::call(args, fusion::begin(seq), fusion::end(seq));
279         }
280 
281         ///////////////////////////////////////////////////////////////////////////
282         // checked_as_weighted_feature
283         template<typename Feature>
284         struct checked_as_weighted_feature
285         {
286             typedef typename as_feature<Feature>::type feature_type;
287             typedef typename as_weighted_feature<feature_type>::type type;
288             // weighted and non-weighted flavors should provide the same feature.
289             BOOST_MPL_ASSERT((
290                 is_same<
291                     typename feature_of<feature_type>::type
292                   , typename feature_of<type>::type
293                 >
294             ));
295         };
296 
297         ///////////////////////////////////////////////////////////////////////////
298         // as_feature_list
299         template<typename Features, typename Weight>
300         struct as_feature_list
301           : mpl::transform_view<Features, checked_as_weighted_feature<mpl::_1> >
302         {
303         };
304 
305         template<typename Features>
306         struct as_feature_list<Features, void>
307           : mpl::transform_view<Features, as_feature<mpl::_1> >
308         {
309         };
310 
311         ///////////////////////////////////////////////////////////////////////////
312         // accumulator_wrapper
313         template<typename Accumulator, typename Feature>
314         struct accumulator_wrapper
315           : Accumulator
316         {
317             typedef Feature feature_tag;
318 
accumulator_wrapperboost::accumulators::detail::accumulator_wrapper319             accumulator_wrapper(accumulator_wrapper const &that)
320               : Accumulator(*static_cast<Accumulator const *>(&that))
321             {
322             }
323 
324             template<typename Args>
accumulator_wrapperboost::accumulators::detail::accumulator_wrapper325             accumulator_wrapper(Args const &args)
326               : Accumulator(args)
327             {
328             }
329         };
330 
331         ///////////////////////////////////////////////////////////////////////////
332         // to_accumulator
333         template<typename Feature, typename Sample, typename Weight>
334         struct to_accumulator
335         {
336             typedef
337                 accumulator_wrapper<
338                     typename mpl::apply2<typename Feature::impl, Sample, Weight>::type
339                   , Feature
340                 >
341             type;
342         };
343 
344         template<typename Feature, typename Sample, typename Weight, typename Tag, typename AccumulatorSet>
345         struct to_accumulator<Feature, Sample, tag::external<Weight, Tag, AccumulatorSet> >
346         {
347             BOOST_MPL_ASSERT((is_same<Tag, void>));
348             BOOST_MPL_ASSERT((is_same<AccumulatorSet, void>));
349 
350             typedef
351                 accumulator_wrapper<
352                     typename mpl::apply2<typename Feature::impl, Sample, Weight>::type
353                   , Feature
354                 >
355             accumulator_type;
356 
357             typedef
358                 typename mpl::if_<
359                     typename Feature::is_weight_accumulator
360                   , accumulator_wrapper<impl::external_impl<accumulator_type, tag::weights>, Feature>
361                   , accumulator_type
362                 >::type
363             type;
364         };
365 
366         // BUGBUG work around an MPL bug wrt map insertion
367         template<typename FeatureMap, typename Feature>
368         struct insert_feature
369           : mpl::eval_if<
370                 mpl::has_key<FeatureMap, typename feature_of<Feature>::type>
371               , mpl::identity<FeatureMap>
372               , mpl::insert<FeatureMap, mpl::pair<typename feature_of<Feature>::type, Feature> >
373             >
374         {
375         };
376 
377         template<typename FeatureMap, typename Feature, typename Weight>
378         struct insert_dependencies
379           : mpl::fold<
380                 as_feature_list<typename Feature::dependencies, Weight>
381               , FeatureMap
382               , insert_dependencies<
383                     insert_feature<mpl::_1, mpl::_2>
384                   , mpl::_2
385                   , Weight
386                 >
387             >
388         {
389         };
390 
391         template<typename FeatureMap, typename Features, typename Weight>
392         struct insert_sequence
393           : mpl::fold< // BUGBUG should use insert_range, but doesn't seem to work for maps
394                 as_feature_list<Features, Weight>
395               , FeatureMap
396               , insert_feature<mpl::_1, mpl::_2>
397             >
398         {
399         };
400 
401         template<typename Features, typename Sample, typename Weight>
402         struct make_accumulator_tuple
403         {
404             typedef
405                 typename mpl::fold<
406                     as_feature_list<Features, Weight>
407                   , mpl::map0<>
408                   , mpl::if_<
409                         mpl::is_sequence<mpl::_2>
410                       , insert_sequence<mpl::_1, mpl::_2, Weight>
411                       , insert_feature<mpl::_1, mpl::_2>
412                     >
413                 >::type
414             feature_map;
415 
416             // for each element in the map, add its dependencies also
417             typedef
418                 typename mpl::fold<
419                     feature_map
420                   , feature_map
421                   , insert_dependencies<mpl::_1, mpl::second<mpl::_2>, Weight>
422                 >::type
423             feature_map_with_dependencies;
424 
425             // turn the map into a vector so we can sort it
426             typedef
427                 typename mpl::insert_range<
428                     mpl::vector<>
429                   , mpl::end<mpl::vector<> >::type
430                   , mpl::transform_view<feature_map_with_dependencies, mpl::second<mpl::_1> >
431                 >::type
432             feature_vector_with_dependencies;
433 
434             // sort the features according to which is derived from which
435             typedef
436                 typename mpl::sort<
437                     feature_vector_with_dependencies
438                   , is_dependent_on<mpl::_2, mpl::_1>
439                 >::type
440             sorted_feature_vector;
441 
442             // From the vector of features, construct a vector of accumulators
443             typedef
444                 typename mpl::transform<
445                     sorted_feature_vector
446                   , to_accumulator<mpl::_1, Sample, Weight>
447                 >::type
448             type;
449         };
450 
451     } // namespace detail
452 
453 }} // namespace boost::accumulators
454 
455 #endif
456