]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 tail = {}; | |
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 |