• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 ///////////////////////////////////////////////////////////////////////////////
2 // tail.hpp
3 //
4 //  Copyright 2005 Eric Niebler, Michael Gauckler. 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_STATISTICS_TAIL_HPP_EAN_28_10_2005
9 #define BOOST_ACCUMULATORS_STATISTICS_TAIL_HPP_EAN_28_10_2005
10 
11 #include <vector>
12 #include <functional>
13 #include <boost/assert.hpp>
14 #include <boost/range.hpp>
15 #include <boost/mpl/if.hpp>
16 #include <boost/mpl/or.hpp>
17 #include <boost/mpl/placeholders.hpp>
18 #include <boost/parameter/keyword.hpp>
19 #include <boost/iterator/reverse_iterator.hpp>
20 #include <boost/iterator/permutation_iterator.hpp>
21 #include <boost/accumulators/accumulators_fwd.hpp>
22 #include <boost/accumulators/framework/accumulator_base.hpp>
23 #include <boost/accumulators/framework/extractor.hpp>
24 #include <boost/accumulators/numeric/functional.hpp>
25 #include <boost/accumulators/framework/parameters/sample.hpp>
26 #include <boost/accumulators/framework/depends_on.hpp>
27 #include <boost/accumulators/statistics_fwd.hpp>
28 
29 namespace boost { namespace accumulators
30 {
31 ///////////////////////////////////////////////////////////////////////////////
32 // cache_size named parameters
33 BOOST_PARAMETER_NESTED_KEYWORD(tag, right_tail_cache_size, cache_size)
34 BOOST_PARAMETER_NESTED_KEYWORD(tag, left_tail_cache_size, cache_size)
35 
36 BOOST_ACCUMULATORS_IGNORE_GLOBAL(right_tail_cache_size)
37 BOOST_ACCUMULATORS_IGNORE_GLOBAL(left_tail_cache_size)
38 
39 namespace detail
40 {
41     ///////////////////////////////////////////////////////////////////////////////
42     // tail_range
43     /// INTERNAL ONLY
44     ///
45     template<typename ElementIterator, typename IndexIterator>
46     struct tail_range
47     {
48         typedef boost::iterator_range<
49             boost::reverse_iterator<boost::permutation_iterator<ElementIterator, IndexIterator> >
50         > type;
51     };
52 
53     ///////////////////////////////////////////////////////////////////////////////
54     // make_tail_range
55     /// INTERNAL ONLY
56     ///
57     template<typename ElementIterator, typename IndexIterator>
58     typename tail_range<ElementIterator, IndexIterator>::type
make_tail_range(ElementIterator elem_begin,IndexIterator index_begin,IndexIterator index_end)59     make_tail_range(ElementIterator elem_begin, IndexIterator index_begin, IndexIterator index_end)
60     {
61         return boost::make_iterator_range(
62             boost::make_reverse_iterator(
63                 boost::make_permutation_iterator(elem_begin, index_end)
64             )
65           , boost::make_reverse_iterator(
66                 boost::make_permutation_iterator(elem_begin, index_begin)
67             )
68         );
69     }
70 
71     ///////////////////////////////////////////////////////////////////////////////
72     // stat_assign_visitor
73     /// INTERNAL ONLY
74     ///
75     template<typename Args>
76     struct stat_assign_visitor
77     {
stat_assign_visitorboost::accumulators::detail::stat_assign_visitor78         stat_assign_visitor(Args const &a, std::size_t i)
79           : args(a)
80           , index(i)
81         {
82         }
83 
84         template<typename Stat>
operator ()boost::accumulators::detail::stat_assign_visitor85         void operator ()(Stat &stat) const
86         {
87             stat.assign(this->args, this->index);
88         }
89 
90     private:
91         stat_assign_visitor &operator =(stat_assign_visitor const &);
92         Args const &args;
93         std::size_t index;
94     };
95 
96     ///////////////////////////////////////////////////////////////////////////////
97     // stat_assign
98     /// INTERNAL ONLY
99     ///
100     template<typename Args>
stat_assign(Args const & args,std::size_t index)101     inline stat_assign_visitor<Args> const stat_assign(Args const &args, std::size_t index)
102     {
103         return stat_assign_visitor<Args>(args, index);
104     }
105 
106     ///////////////////////////////////////////////////////////////////////////////
107     // is_tail_variate_feature
108     /// INTERNAL ONLY
109     ///
110     template<typename Stat, typename LeftRight>
111     struct is_tail_variate_feature
112       : mpl::false_
113     {
114     };
115 
116     /// INTERNAL ONLY
117     ///
118     template<typename VariateType, typename VariateTag, typename LeftRight>
119     struct is_tail_variate_feature<tag::tail_variate<VariateType, VariateTag, LeftRight>, LeftRight>
120       : mpl::true_
121     {
122     };
123 
124     /// INTERNAL ONLY
125     ///
126     template<typename LeftRight>
127     struct is_tail_variate_feature<tag::tail_weights<LeftRight>, LeftRight>
128       : mpl::true_
129     {
130     };
131 
132 } // namespace detail
133 
134 namespace impl
135 {
136     ///////////////////////////////////////////////////////////////////////////////
137     // tail_impl
138     template<typename Sample, typename LeftRight>
139     struct tail_impl
140       : accumulator_base
141     {
142         // LeftRight must be either right or left
143         BOOST_MPL_ASSERT((
144             mpl::or_<is_same<LeftRight, right>, is_same<LeftRight, left> >
145         ));
146 
147         typedef
148             typename mpl::if_<
149                 is_same<LeftRight, right>
150               , numeric::functional::greater<Sample const, Sample const>
151               , numeric::functional::less<Sample const, Sample const>
152             >::type
153         predicate_type;
154 
155         // for boost::result_of
156         typedef typename detail::tail_range<
157             typename std::vector<Sample>::const_iterator
158           , std::vector<std::size_t>::iterator
159         >::type result_type;
160 
161         template<typename Args>
tail_implboost::accumulators::impl::tail_impl162         tail_impl(Args const &args)
163           : is_sorted(false)
164           , indices()
165           , samples(args[tag::tail<LeftRight>::cache_size], args[sample | Sample()])
166         {
167             this->indices.reserve(this->samples.size());
168         }
169 
tail_implboost::accumulators::impl::tail_impl170         tail_impl(tail_impl const &that)
171           : is_sorted(that.is_sorted)
172           , indices(that.indices)
173           , samples(that.samples)
174         {
175             this->indices.reserve(this->samples.size());
176         }
177 
178         // This just stores the heap and the samples.
179         // In operator()() below, if we are adding a new sample
180         // to the sample cache, we force all the
181         // tail_variates to update also. (It's not
182         // good enough to wait for the accumulator_set to do it
183         // for us because then information about whether a sample
184         // was stored and where is lost, and would need to be
185         // queried at runtime, which would be slow.) This is
186         // implemented as a filtered visitation over the stats,
187         // which we can access because args[accumulator] gives us
188         // all the stats.
189 
190         template<typename Args>
operator ()boost::accumulators::impl::tail_impl191         void operator ()(Args const &args)
192         {
193             if(this->indices.size() < this->samples.size())
194             {
195                 this->indices.push_back(this->indices.size());
196                 this->assign(args, this->indices.back());
197             }
198             else if(predicate_type()(args[sample], this->samples[this->indices[0]]))
199             {
200                 std::pop_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples));
201                 this->assign(args, this->indices.back());
202             }
203         }
204 
resultboost::accumulators::impl::tail_impl205         result_type result(dont_care) const
206         {
207             if(!this->is_sorted)
208             {
209                 // Must use the same predicate here as in push_heap/pop_heap above.
210                 std::sort_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples));
211                 // sort_heap puts elements in reverse order. Calling std::reverse
212                 // turns the sorted sequence back into a valid heap.
213                 std::reverse(this->indices.begin(), this->indices.end());
214                 this->is_sorted = true;
215             }
216 
217             return detail::make_tail_range(
218                 this->samples.begin()
219               , this->indices.begin()
220               , this->indices.end()
221             );
222         }
223 
224     private:
225 
226         struct is_tail_variate
227         {
228             template<typename T>
229             struct apply
230               : detail::is_tail_variate_feature<
231                     typename detail::feature_tag<T>::type
232                   , LeftRight
233                 >
234             {};
235         };
236 
237         template<typename Args>
assignboost::accumulators::impl::tail_impl238         void assign(Args const &args, std::size_t index)
239         {
240             BOOST_ASSERT(index < this->samples.size());
241             this->samples[index] = args[sample];
242             std::push_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples));
243             this->is_sorted = false;
244             // Tell the tail variates to store their values also
245             args[accumulator].template visit_if<is_tail_variate>(detail::stat_assign(args, index));
246         }
247 
248         ///////////////////////////////////////////////////////////////////////////////
249         //
250         struct indirect_cmp
251         {
252             typedef std::size_t first_argument_type;
253             typedef std::size_t second_argument_type;
254             typedef bool result_type;
255 
indirect_cmpboost::accumulators::impl::tail_impl::indirect_cmp256             indirect_cmp(std::vector<Sample> const &s)
257               : samples(s)
258             {
259             }
260 
operator ()boost::accumulators::impl::tail_impl::indirect_cmp261             bool operator ()(std::size_t left, std::size_t right) const
262             {
263                 return predicate_type()(this->samples[left], this->samples[right]);
264             }
265 
266         private:
267             indirect_cmp &operator =(indirect_cmp const &);
268             std::vector<Sample> const &samples;
269         };
270 
271     public:
272         // make this accumulator serializeable
273         template<class Archive>
serializeboost::accumulators::impl::tail_impl274         void serialize(Archive & ar, const unsigned int file_version)
275         {
276             ar & is_sorted;
277             ar & indices;
278             ar & samples;
279         }
280 
281     private:
282         mutable bool is_sorted;
283         mutable std::vector<std::size_t> indices;
284         std::vector<Sample> samples;
285     };
286 
287 } // namespace impl
288 
289 // TODO The templatized tag::tail below should inherit from the correct named parameter.
290 // The following lines provide a workaround, but there must be a better way of doing this.
291 template<typename T>
292 struct tail_cache_size_named_arg
293 {
294 };
295 template<>
296 struct tail_cache_size_named_arg<left>
297   : tag::left_tail_cache_size
298 {
299 };
300 template<>
301 struct tail_cache_size_named_arg<right>
302   : tag::right_tail_cache_size
303 {
304 };
305 
306 ///////////////////////////////////////////////////////////////////////////////
307 // tag::tail<>
308 //
309 namespace tag
310 {
311     template<typename LeftRight>
312     struct tail
313       : depends_on<>
314       , tail_cache_size_named_arg<LeftRight>
315     {
316         /// INTERNAL ONLY
317         ///
318         typedef accumulators::impl::tail_impl<mpl::_1, LeftRight> impl;
319 
320         #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED
321         /// tag::tail<LeftRight>::cache_size named parameter
322         static boost::parameter::keyword<tail_cache_size_named_arg<LeftRight> > const cache_size;
323         #endif
324     };
325 
326     struct abstract_tail
327       : depends_on<>
328     {
329     };
330 }
331 
332 ///////////////////////////////////////////////////////////////////////////////
333 // extract::tail
334 //
335 namespace extract
336 {
337     extractor<tag::abstract_tail> const tail = {};
338 
339     BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail)
340 }
341 
342 using extract::tail;
343 
344 template<typename LeftRight>
345 struct feature_of<tag::tail<LeftRight> >
346   : feature_of<tag::abstract_tail>
347 {
348 };
349 
350 }} // namespace boost::accumulators
351 
352 #endif
353