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 |
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 | 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 | |
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> |
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(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(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(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(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> |
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 | : std::binary_function<std::size_t, std::size_t, bool> |
252 | { |
253 | indirect_cmp(std::vector<Sample> const &s) |
254 | : samples(s) |
255 | { |
256 | } |
257 | |
258 | bool operator ()(std::size_t left, std::size_t right) const |
259 | { |
260 | return predicate_type()(this->samples[left], this->samples[right]); |
261 | } |
262 | |
263 | private: |
264 | indirect_cmp &operator =(indirect_cmp const &); |
265 | std::vector<Sample> const &samples; |
266 | }; |
267 | |
268 | mutable bool is_sorted; |
269 | mutable std::vector<std::size_t> indices; |
270 | std::vector<Sample> samples; |
271 | }; |
272 | |
273 | } // namespace impl |
274 | |
275 | // TODO The templatized tag::tail below should inherit from the correct named parameter. |
276 | // The following lines provide a workaround, but there must be a better way of doing this. |
277 | template<typename T> |
278 | struct tail_cache_size_named_arg |
279 | { |
280 | }; |
281 | template<> |
282 | struct tail_cache_size_named_arg<left> |
283 | : tag::left_tail_cache_size |
284 | { |
285 | }; |
286 | template<> |
287 | struct tail_cache_size_named_arg<right> |
288 | : tag::right_tail_cache_size |
289 | { |
290 | }; |
291 | |
292 | /////////////////////////////////////////////////////////////////////////////// |
293 | // tag::tail<> |
294 | // |
295 | namespace tag |
296 | { |
297 | template<typename LeftRight> |
298 | struct tail |
299 | : depends_on<> |
300 | , tail_cache_size_named_arg<LeftRight> |
301 | { |
302 | /// INTERNAL ONLY |
303 | /// |
304 | typedef accumulators::impl::tail_impl<mpl::_1, LeftRight> impl; |
305 | |
306 | #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED |
307 | /// tag::tail<LeftRight>::cache_size named parameter |
308 | static boost::parameter::keyword<tail_cache_size_named_arg<LeftRight> > const cache_size; |
309 | #endif |
310 | }; |
311 | |
312 | struct abstract_tail |
313 | : depends_on<> |
314 | { |
315 | }; |
316 | } |
317 | |
318 | /////////////////////////////////////////////////////////////////////////////// |
319 | // extract::tail |
320 | // |
321 | namespace extract |
322 | { |
323 | extractor<tag::abstract_tail> const = {}; |
324 | |
325 | BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail) |
326 | } |
327 | |
328 | using extract::tail; |
329 | |
330 | template<typename LeftRight> |
331 | struct feature_of<tag::tail<LeftRight> > |
332 | : feature_of<tag::abstract_tail> |
333 | { |
334 | }; |
335 | |
336 | }} // namespace boost::accumulators |
337 | |
338 | #endif |
339 | |