1 ///////////////////////////////////////////////////////////////////////////////
2 // extended_p_square_quantile.hpp
4 // Copyright 2005 Daniel Egloff. 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)
8 #ifndef BOOST_ACCUMULATORS_STATISTICS_EXTENDED_SINGLE_QUANTILE_HPP_DE_01_01_2006
9 #define BOOST_ACCUMULATORS_STATISTICS_EXTENDED_SINGLE_QUANTILE_HPP_DE_01_01_2006
13 #include <boost/throw_exception.hpp>
14 #include <boost/range/begin.hpp>
15 #include <boost/range/end.hpp>
16 #include <boost/range/iterator_range.hpp>
17 #include <boost/iterator/transform_iterator.hpp>
18 #include <boost/iterator/counting_iterator.hpp>
19 #include <boost/iterator/permutation_iterator.hpp>
20 #include <boost/parameter/keyword.hpp>
21 #include <boost/mpl/placeholders.hpp>
22 #include <boost/type_traits/is_same.hpp>
23 #include <boost/accumulators/framework/accumulator_base.hpp>
24 #include <boost/accumulators/framework/extractor.hpp>
25 #include <boost/accumulators/numeric/functional.hpp>
26 #include <boost/accumulators/framework/parameters/sample.hpp>
27 #include <boost/accumulators/framework/depends_on.hpp>
28 #include <boost/accumulators/statistics_fwd.hpp>
29 #include <boost/accumulators/statistics/count.hpp>
30 #include <boost/accumulators/statistics/parameters/quantile_probability.hpp>
31 #include <boost/accumulators/statistics/extended_p_square.hpp>
32 #include <boost/accumulators/statistics/weighted_extended_p_square.hpp>
33 #include <boost/accumulators/statistics/times2_iterator.hpp>
36 # pragma warning(push)
37 # pragma warning(disable: 4127) // conditional expression is constant
40 namespace boost { namespace accumulators
45 ///////////////////////////////////////////////////////////////////////////////
46 // extended_p_square_quantile_impl
47 // single quantile estimation
49 @brief Quantile estimation using the extended \f$P^2\f$ algorithm for weighted and unweighted samples
51 Uses the quantile estimates calculated by the extended \f$P^2\f$ algorithm to compute
52 intermediate quantile estimates by means of quadratic interpolation.
54 @param quantile_probability The probability of the quantile to be estimated.
56 template<typename Sample, typename Impl1, typename Impl2> // Impl1: weighted/unweighted // Impl2: linear/quadratic
57 struct extended_p_square_quantile_impl
60 typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
61 typedef std::vector<float_type> array_type;
62 typedef iterator_range<
63 detail::lvalue_index_iterator<
65 typename array_type::const_iterator
66 , detail::times2_iterator
70 // for boost::result_of
71 typedef float_type result_type;
73 template<typename Args>
74 extended_p_square_quantile_impl(Args const &args)
76 boost::begin(args[extended_p_square_probabilities])
77 , boost::end(args[extended_p_square_probabilities])
82 template<typename Args>
83 result_type result(Args const &args) const
87 is_same<Impl1, weighted>
88 , tag::weighted_extended_p_square
89 , tag::extended_p_square
91 extended_p_square_tag;
93 extractor<extended_p_square_tag> const some_extended_p_square = {};
95 array_type heights(some_extended_p_square(args).size());
96 std::copy(some_extended_p_square(args).begin(), some_extended_p_square(args).end(), heights.begin());
98 this->probability = args[quantile_probability];
100 typename array_type::const_iterator iter_probs = std::lower_bound(this->probabilities.begin(), this->probabilities.end(), this->probability);
101 std::size_t dist = std::distance(this->probabilities.begin(), iter_probs);
102 typename array_type::const_iterator iter_heights = heights.begin() + dist;
104 // If this->probability is not in a valid range return NaN or throw exception
105 if (this->probability < *this->probabilities.begin() || this->probability > *(this->probabilities.end() - 1))
107 if (std::numeric_limits<result_type>::has_quiet_NaN)
109 return std::numeric_limits<result_type>::quiet_NaN();
113 std::ostringstream msg;
114 msg << "probability = " << this->probability << " is not in valid range (";
115 msg << *this->probabilities.begin() << ", " << *(this->probabilities.end() - 1) << ")";
116 boost::throw_exception(std::runtime_error(msg.str()));
122 if (*iter_probs == this->probability)
124 return heights[dist];
130 if (is_same<Impl2, linear>::value)
132 /////////////////////////////////////////////////////////////////////////////////
133 // LINEAR INTERPOLATION
135 float_type p1 = *iter_probs;
136 float_type p0 = *(iter_probs - 1);
137 float_type h1 = *iter_heights;
138 float_type h0 = *(iter_heights - 1);
140 float_type a = numeric::fdiv(h1 - h0, p1 - p0);
141 float_type b = h1 - p1 * a;
143 res = a * this->probability + b;
147 /////////////////////////////////////////////////////////////////////////////////
148 // QUADRATIC INTERPOLATION
150 float_type p0, p1, p2;
151 float_type h0, h1, h2;
153 if ( (dist == 1 || *iter_probs - this->probability <= this->probability - *(iter_probs - 1) ) && dist != this->probabilities.size() - 1 )
155 p0 = *(iter_probs - 1);
157 p2 = *(iter_probs + 1);
158 h0 = *(iter_heights - 1);
160 h2 = *(iter_heights + 1);
164 p0 = *(iter_probs - 2);
165 p1 = *(iter_probs - 1);
167 h0 = *(iter_heights - 2);
168 h1 = *(iter_heights - 1);
172 float_type hp21 = numeric::fdiv(h2 - h1, p2 - p1);
173 float_type hp10 = numeric::fdiv(h1 - h0, p1 - p0);
174 float_type p21 = numeric::fdiv(p2 * p2 - p1 * p1, p2 - p1);
175 float_type p10 = numeric::fdiv(p1 * p1 - p0 * p0, p1 - p0);
177 float_type a = numeric::fdiv(hp21 - hp10, p21 - p10);
178 float_type b = hp21 - a * p21;
179 float_type c = h2 - a * p2 * p2 - b * p2;
181 res = a * this->probability * this-> probability + b * this->probability + c;
190 array_type probabilities;
191 mutable float_type probability;
197 ///////////////////////////////////////////////////////////////////////////////
198 // tag::extended_p_square_quantile
202 struct extended_p_square_quantile
203 : depends_on<extended_p_square>
205 typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, unweighted, linear> impl;
207 struct extended_p_square_quantile_quadratic
208 : depends_on<extended_p_square>
210 typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, unweighted, quadratic> impl;
212 struct weighted_extended_p_square_quantile
213 : depends_on<weighted_extended_p_square>
215 typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, weighted, linear> impl;
217 struct weighted_extended_p_square_quantile_quadratic
218 : depends_on<weighted_extended_p_square>
220 typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, weighted, quadratic> impl;
224 ///////////////////////////////////////////////////////////////////////////////
225 // extract::extended_p_square_quantile
226 // extract::weighted_extended_p_square_quantile
230 extractor<tag::extended_p_square_quantile> const extended_p_square_quantile = {};
231 extractor<tag::extended_p_square_quantile_quadratic> const extended_p_square_quantile_quadratic = {};
232 extractor<tag::weighted_extended_p_square_quantile> const weighted_extended_p_square_quantile = {};
233 extractor<tag::weighted_extended_p_square_quantile_quadratic> const weighted_extended_p_square_quantile_quadratic = {};
235 BOOST_ACCUMULATORS_IGNORE_GLOBAL(extended_p_square_quantile)
236 BOOST_ACCUMULATORS_IGNORE_GLOBAL(extended_p_square_quantile_quadratic)
237 BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_extended_p_square_quantile)
238 BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_extended_p_square_quantile_quadratic)
241 using extract::extended_p_square_quantile;
242 using extract::extended_p_square_quantile_quadratic;
243 using extract::weighted_extended_p_square_quantile;
244 using extract::weighted_extended_p_square_quantile_quadratic;
246 // extended_p_square_quantile(linear) -> extended_p_square_quantile
248 struct as_feature<tag::extended_p_square_quantile(linear)>
250 typedef tag::extended_p_square_quantile type;
253 // extended_p_square_quantile(quadratic) -> extended_p_square_quantile_quadratic
255 struct as_feature<tag::extended_p_square_quantile(quadratic)>
257 typedef tag::extended_p_square_quantile_quadratic type;
260 // weighted_extended_p_square_quantile(linear) -> weighted_extended_p_square_quantile
262 struct as_feature<tag::weighted_extended_p_square_quantile(linear)>
264 typedef tag::weighted_extended_p_square_quantile type;
267 // weighted_extended_p_square_quantile(quadratic) -> weighted_extended_p_square_quantile_quadratic
269 struct as_feature<tag::weighted_extended_p_square_quantile(quadratic)>
271 typedef tag::weighted_extended_p_square_quantile_quadratic type;
274 // for the purposes of feature-based dependency resolution,
275 // extended_p_square_quantile and weighted_extended_p_square_quantile
276 // provide the same feature as quantile
278 struct feature_of<tag::extended_p_square_quantile>
279 : feature_of<tag::quantile>
283 struct feature_of<tag::extended_p_square_quantile_quadratic>
284 : feature_of<tag::quantile>
287 // So that extended_p_square_quantile can be automatically substituted with
288 // weighted_extended_p_square_quantile when the weight parameter is non-void
290 struct as_weighted_feature<tag::extended_p_square_quantile>
292 typedef tag::weighted_extended_p_square_quantile type;
296 struct feature_of<tag::weighted_extended_p_square_quantile>
297 : feature_of<tag::extended_p_square_quantile>
301 // So that extended_p_square_quantile_quadratic can be automatically substituted with
302 // weighted_extended_p_square_quantile_quadratic when the weight parameter is non-void
304 struct as_weighted_feature<tag::extended_p_square_quantile_quadratic>
306 typedef tag::weighted_extended_p_square_quantile_quadratic type;
309 struct feature_of<tag::weighted_extended_p_square_quantile_quadratic>
310 : feature_of<tag::extended_p_square_quantile_quadratic>
314 }} // namespace boost::accumulators
317 # pragma warning(pop)