1 /////////////////////////////////////////////////////////////////////////////// 2 // extended_p_square_quantile.hpp 3 // 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) 7 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 10 11 #include <vector> 12 #include <functional> 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> 34 35 #ifdef _MSC_VER 36 # pragma warning(push) 37 # pragma warning(disable: 4127) // conditional expression is constant 38 #endif 39 40 namespace boost { namespace accumulators 41 { 42 43 namespace impl 44 { 45 /////////////////////////////////////////////////////////////////////////////// 46 // extended_p_square_quantile_impl 47 // single quantile estimation 48 /** 49 @brief Quantile estimation using the extended \f$P^2\f$ algorithm for weighted and unweighted samples 50 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. 53 54 @param quantile_probability The probability of the quantile to be estimated. 55 */ 56 template<typename Sample, typename Impl1, typename Impl2> // Impl1: weighted/unweighted // Impl2: linear/quadratic 57 struct extended_p_square_quantile_impl 58 : accumulator_base 59 { 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< 64 permutation_iterator< 65 typename array_type::const_iterator 66 , detail::times2_iterator 67 > 68 > 69 > range_type; 70 // for boost::result_of 71 typedef float_type result_type; 72 73 template<typename Args> extended_p_square_quantile_implboost::accumulators::impl::extended_p_square_quantile_impl74 extended_p_square_quantile_impl(Args const &args) 75 : probabilities( 76 boost::begin(args[extended_p_square_probabilities]) 77 , boost::end(args[extended_p_square_probabilities]) 78 ) 79 { 80 } 81 82 template<typename Args> resultboost::accumulators::impl::extended_p_square_quantile_impl83 result_type result(Args const &args) const 84 { 85 typedef 86 typename mpl::if_< 87 is_same<Impl1, weighted> 88 , tag::weighted_extended_p_square 89 , tag::extended_p_square 90 >::type 91 extended_p_square_tag; 92 93 extractor<extended_p_square_tag> const some_extended_p_square = {}; 94 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()); 97 98 this->probability = args[quantile_probability]; 99 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; 103 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)) 106 { 107 if (std::numeric_limits<result_type>::has_quiet_NaN) 108 { 109 return std::numeric_limits<result_type>::quiet_NaN(); 110 } 111 else 112 { 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())); 117 return Sample(0); 118 } 119 120 } 121 122 if (*iter_probs == this->probability) 123 { 124 return heights[dist]; 125 } 126 else 127 { 128 result_type res; 129 130 if (is_same<Impl2, linear>::value) 131 { 132 ///////////////////////////////////////////////////////////////////////////////// 133 // LINEAR INTERPOLATION 134 // 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); 139 140 float_type a = numeric::fdiv(h1 - h0, p1 - p0); 141 float_type b = h1 - p1 * a; 142 143 res = a * this->probability + b; 144 } 145 else 146 { 147 ///////////////////////////////////////////////////////////////////////////////// 148 // QUADRATIC INTERPOLATION 149 // 150 float_type p0, p1, p2; 151 float_type h0, h1, h2; 152 153 if ( (dist == 1 || *iter_probs - this->probability <= this->probability - *(iter_probs - 1) ) && dist != this->probabilities.size() - 1 ) 154 { 155 p0 = *(iter_probs - 1); 156 p1 = *iter_probs; 157 p2 = *(iter_probs + 1); 158 h0 = *(iter_heights - 1); 159 h1 = *iter_heights; 160 h2 = *(iter_heights + 1); 161 } 162 else 163 { 164 p0 = *(iter_probs - 2); 165 p1 = *(iter_probs - 1); 166 p2 = *iter_probs; 167 h0 = *(iter_heights - 2); 168 h1 = *(iter_heights - 1); 169 h2 = *iter_heights; 170 } 171 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); 176 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; 180 181 res = a * this->probability * this-> probability + b * this->probability + c; 182 } 183 184 return res; 185 } 186 187 } 188 189 public: 190 // make this accumulator serializeable 191 // TODO: do we need to split to load/save and verify that the parameters did not change? 192 template<class Archive> serializeboost::accumulators::impl::extended_p_square_quantile_impl193 void serialize(Archive & ar, const unsigned int file_version) 194 { 195 ar & probabilities; 196 ar & probability; 197 } 198 199 private: 200 201 array_type probabilities; 202 mutable float_type probability; 203 204 }; 205 206 } // namespace impl 207 208 /////////////////////////////////////////////////////////////////////////////// 209 // tag::extended_p_square_quantile 210 // 211 namespace tag 212 { 213 struct extended_p_square_quantile 214 : depends_on<extended_p_square> 215 { 216 typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, unweighted, linear> impl; 217 }; 218 struct extended_p_square_quantile_quadratic 219 : depends_on<extended_p_square> 220 { 221 typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, unweighted, quadratic> impl; 222 }; 223 struct weighted_extended_p_square_quantile 224 : depends_on<weighted_extended_p_square> 225 { 226 typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, weighted, linear> impl; 227 }; 228 struct weighted_extended_p_square_quantile_quadratic 229 : depends_on<weighted_extended_p_square> 230 { 231 typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, weighted, quadratic> impl; 232 }; 233 } 234 235 /////////////////////////////////////////////////////////////////////////////// 236 // extract::extended_p_square_quantile 237 // extract::weighted_extended_p_square_quantile 238 // 239 namespace extract 240 { 241 extractor<tag::extended_p_square_quantile> const extended_p_square_quantile = {}; 242 extractor<tag::extended_p_square_quantile_quadratic> const extended_p_square_quantile_quadratic = {}; 243 extractor<tag::weighted_extended_p_square_quantile> const weighted_extended_p_square_quantile = {}; 244 extractor<tag::weighted_extended_p_square_quantile_quadratic> const weighted_extended_p_square_quantile_quadratic = {}; 245 246 BOOST_ACCUMULATORS_IGNORE_GLOBAL(extended_p_square_quantile) 247 BOOST_ACCUMULATORS_IGNORE_GLOBAL(extended_p_square_quantile_quadratic) 248 BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_extended_p_square_quantile) 249 BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_extended_p_square_quantile_quadratic) 250 } 251 252 using extract::extended_p_square_quantile; 253 using extract::extended_p_square_quantile_quadratic; 254 using extract::weighted_extended_p_square_quantile; 255 using extract::weighted_extended_p_square_quantile_quadratic; 256 257 // extended_p_square_quantile(linear) -> extended_p_square_quantile 258 template<> 259 struct as_feature<tag::extended_p_square_quantile(linear)> 260 { 261 typedef tag::extended_p_square_quantile type; 262 }; 263 264 // extended_p_square_quantile(quadratic) -> extended_p_square_quantile_quadratic 265 template<> 266 struct as_feature<tag::extended_p_square_quantile(quadratic)> 267 { 268 typedef tag::extended_p_square_quantile_quadratic type; 269 }; 270 271 // weighted_extended_p_square_quantile(linear) -> weighted_extended_p_square_quantile 272 template<> 273 struct as_feature<tag::weighted_extended_p_square_quantile(linear)> 274 { 275 typedef tag::weighted_extended_p_square_quantile type; 276 }; 277 278 // weighted_extended_p_square_quantile(quadratic) -> weighted_extended_p_square_quantile_quadratic 279 template<> 280 struct as_feature<tag::weighted_extended_p_square_quantile(quadratic)> 281 { 282 typedef tag::weighted_extended_p_square_quantile_quadratic type; 283 }; 284 285 // for the purposes of feature-based dependency resolution, 286 // extended_p_square_quantile and weighted_extended_p_square_quantile 287 // provide the same feature as quantile 288 template<> 289 struct feature_of<tag::extended_p_square_quantile> 290 : feature_of<tag::quantile> 291 { 292 }; 293 template<> 294 struct feature_of<tag::extended_p_square_quantile_quadratic> 295 : feature_of<tag::quantile> 296 { 297 }; 298 // So that extended_p_square_quantile can be automatically substituted with 299 // weighted_extended_p_square_quantile when the weight parameter is non-void 300 template<> 301 struct as_weighted_feature<tag::extended_p_square_quantile> 302 { 303 typedef tag::weighted_extended_p_square_quantile type; 304 }; 305 306 template<> 307 struct feature_of<tag::weighted_extended_p_square_quantile> 308 : feature_of<tag::extended_p_square_quantile> 309 { 310 }; 311 312 // So that extended_p_square_quantile_quadratic can be automatically substituted with 313 // weighted_extended_p_square_quantile_quadratic when the weight parameter is non-void 314 template<> 315 struct as_weighted_feature<tag::extended_p_square_quantile_quadratic> 316 { 317 typedef tag::weighted_extended_p_square_quantile_quadratic type; 318 }; 319 template<> 320 struct feature_of<tag::weighted_extended_p_square_quantile_quadratic> 321 : feature_of<tag::extended_p_square_quantile_quadratic> 322 { 323 }; 324 325 }} // namespace boost::accumulators 326 327 #ifdef _MSC_VER 328 # pragma warning(pop) 329 #endif 330 331 #endif 332