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
29namespace boost { namespace accumulators
30{
31///////////////////////////////////////////////////////////////////////////////
32// cache_size named parameters
33BOOST_PARAMETER_NESTED_KEYWORD(tag, right_tail_cache_size, cache_size)
34BOOST_PARAMETER_NESTED_KEYWORD(tag, left_tail_cache_size, cache_size)
35
36BOOST_ACCUMULATORS_IGNORE_GLOBAL(right_tail_cache_size)
37BOOST_ACCUMULATORS_IGNORE_GLOBAL(left_tail_cache_size)
38
39namespace 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
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 {
78 stat_assign_visitor(Args const &a, std::size_t i)
79 : args(a)
80 , index(i)
81 {
82 }
83
84 template<typename Stat>
85 void operator ()(Stat &stat) const
86 {
87 stat.assign(this->args, this->index);
88 }
89
90 private:
91 BOOST_DELETED_FUNCTION(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>
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
134namespace 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>
162 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(n: this->samples.size());
168 }
169
170 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(n: 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>
191 void operator ()(Args const &args)
192 {
193 if(this->indices.size() < this->samples.size())
194 {
195 this->indices.push_back(x: 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
205 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(first: this->indices.begin(), last: 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>
238 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
256 indirect_cmp(std::vector<Sample> const &s)
257 : samples(s)
258 {
259 }
260
261 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 BOOST_DELETED_FUNCTION(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>
274 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.
291template<typename T>
292struct tail_cache_size_named_arg
293{
294};
295template<>
296struct tail_cache_size_named_arg<left>
297 : tag::left_tail_cache_size
298{
299};
300template<>
301struct tail_cache_size_named_arg<right>
302 : tag::right_tail_cache_size
303{
304};
305
306///////////////////////////////////////////////////////////////////////////////
307// tag::tail<>
308//
309namespace 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//
335namespace extract
336{
337 extractor<tag::abstract_tail> const tail = {};
338
339 BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail)
340}
341
342using extract::tail;
343
344template<typename LeftRight>
345struct feature_of<tag::tail<LeftRight> >
346 : feature_of<tag::abstract_tail>
347{
348};
349
350}} // namespace boost::accumulators
351
352#endif
353

source code of boost/libs/accumulators/include/boost/accumulators/statistics/tail.hpp