boost/accumulators/statistics/extended_p_square_quantile.hpp

   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/range/begin.hpp>
  14 #include <boost/range/end.hpp>
  15 #include <boost/range/iterator_range.hpp>
  16 #include <boost/iterator/transform_iterator.hpp>
  17 #include <boost/iterator/counting_iterator.hpp>
  18 #include <boost/iterator/permutation_iterator.hpp>
  19 #include <boost/parameter/keyword.hpp>
  20 #include <boost/mpl/placeholders.hpp>
  21 #include <boost/type_traits/is_same.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 #include <boost/accumulators/statistics/count.hpp>
  29 #include <boost/accumulators/statistics/parameters/quantile_probability.hpp>
  30 #include <boost/accumulators/statistics/extended_p_square.hpp>
  31 #include <boost/accumulators/statistics/weighted_extended_p_square.hpp>
  32 #include <boost/accumulators/statistics/times2_iterator.hpp>
  33
  34 #ifdef _MSC_VER
  35 # pragma warning(push)
  36 # pragma warning(disable: 4127) // conditional expression is constant
  37 #endif
  38
  39 namespace boost { namespace accumulators
  40 {
  41
  42 namespace impl
  43 {
  44     ///////////////////////////////////////////////////////////////////////////////
  45     // extended_p_square_quantile_impl
  46     //  single quantile estimation
  47     /**
  48         @brief Quantile estimation using the extended \f$P^2\f$ algorithm for weighted and unweighted samples
  49
  50         Uses the quantile estimates calculated by the extended \f$P^2\f$ algorithm to compute
  51         intermediate quantile estimates by means of quadratic interpolation.
  52
  53         @param quantile_probability The probability of the quantile to be estimated.
  54     */
  55     template<typename Sample, typename Impl1, typename Impl2> // Impl1: weighted/unweighted // Impl2: linear/quadratic
  56     struct extended_p_square_quantile_impl
  57       : accumulator_base
  58     {
  59         typedef typename numeric::functional::average<Sample, std::size_t>::result_type float_type;
  60         typedef std::vector<float_type> array_type;
  61         typedef iterator_range<
  62             detail::lvalue_index_iterator<
  63                 permutation_iterator<
  64                     typename array_type::const_iterator
  65                   , detail::times2_iterator
  66                 >
  67             >
  68         > range_type;
  69         // for boost::result_of
  70         typedef float_type result_type;
  71
  72         template<typename Args>
  73         extended_p_square_quantile_impl(Args const &args)
  74           : probabilities(
  75                 boost::begin(args[extended_p_square_probabilities])
  76               , boost::end(args[extended_p_square_probabilities])
  77             )
  78         {
  79         }
  80
  81         template<typename Args>
  82         result_type result(Args const &args) const
  83         {
  84             typedef
  85                 typename mpl::if_<
  86                     is_same<Impl1, weighted>
  87                   , tag::weighted_extended_p_square
  88                   , tag::extended_p_square
  89                 >::type
  90             extended_p_square_tag;
  91
  92             extractor<extended_p_square_tag> const some_extended_p_square = {};
  93
  94             array_type heights(some_extended_p_square(args).size());
  95             std::copy(some_extended_p_square(args).begin(), some_extended_p_square(args).end(), heights.begin());
  96
  97             this->probability = args[quantile_probability];
  98
  99             typename array_type::const_iterator iter_probs = std::lower_bound(this->probabilities.begin(), this->probabilities.end(), this->probability);
 100             std::size_t dist = std::distance(this->probabilities.begin(), iter_probs);
 101             typename array_type::const_iterator iter_heights = heights.begin() + dist;
 102
 103             // If this->probability is not in a valid range return NaN or throw exception
 104             if (this->probability < *this->probabilities.begin() || this->probability > *(this->probabilities.end() - 1))
 105             {
 106                 if (std::numeric_limits<result_type>::has_quiet_NaN)
 107                 {
 108                     return std::numeric_limits<result_type>::quiet_NaN();
 109                 }
 110                 else
 111                 {
 112                     std::ostringstream msg;
 113                     msg << "probability = " << this->probability << " is not in valid range (";
 114                     msg << *this->probabilities.begin() << ", " << *(this->probabilities.end() - 1) << ")";
 115                     boost::throw_exception(std::runtime_error(msg.str()));
 116                     return Sample(0);
 117                 }
 118
 119             }
 120
 121             if (*iter_probs == this->probability)
 122             {
 123                 return heights[dist];
 124             }
 125             else
 126             {
 127                 result_type result;
 128
 129                 if (is_same<Impl2, linear>::value)
 130                 {
 131                     /////////////////////////////////////////////////////////////////////////////////
 132                     // LINEAR INTERPOLATION
 133                     //
 134                     float_type p1 = *iter_probs;
 135                     float_type p0 = *(iter_probs - 1);
 136                     float_type h1 = *iter_heights;
 137                     float_type h0 = *(iter_heights - 1);
 138
 139                     float_type a = numeric::average(h1 - h0, p1 - p0);
 140                     float_type b = h1 - p1 * a;
 141
 142                     result = a * this->probability + b;
 143                 }
 144                 else
 145                 {
 146                     /////////////////////////////////////////////////////////////////////////////////
 147                     // QUADRATIC INTERPOLATION
 148                     //
 149                     float_type p0, p1, p2;
 150                     float_type h0, h1, h2;
 151
 152                     if ( (dist == 1 || *iter_probs - this->probability <= this->probability - *(iter_probs - 1) ) && dist != this->probabilities.size() - 1 )
 153                     {
 154                         p0 = *(iter_probs - 1);
 155                         p1 = *iter_probs;
 156                         p2 = *(iter_probs + 1);
 157                         h0 = *(iter_heights - 1);
 158                         h1 = *iter_heights;
 159                         h2 = *(iter_heights + 1);
 160                     }
 161                     else
 162                     {
 163                         p0 = *(iter_probs - 2);
 164                         p1 = *(iter_probs - 1);
 165                         p2 = *iter_probs;
 166                         h0 = *(iter_heights - 2);
 167                         h1 = *(iter_heights - 1);
 168                         h2 = *iter_heights;
 169                     }
 170
 171                     float_type hp21 = numeric::average(h2 - h1, p2 - p1);
 172                     float_type hp10 = numeric::average(h1 - h0, p1 - p0);
 173                     float_type p21  = numeric::average(p2 * p2 - p1 * p1, p2 - p1);
 174                     float_type p10  = numeric::average(p1 * p1 - p0 * p0, p1 - p0);
 175
 176                     float_type a = numeric::average(hp21 - hp10, p21 - p10);
 177                     float_type b = hp21 - a * p21;
 178                     float_type c = h2 - a * p2 * p2 - b * p2;
 179
 180                     result = a * this->probability * this-> probability + b * this->probability + c;
 181                 }
 182
 183                 return result;
 184             }
 185
 186         }
 187     private:
 188
 189         array_type probabilities;
 190         mutable float_type probability;
 191
 192     };
 193
 194 } // namespace impl
 195
 196 ///////////////////////////////////////////////////////////////////////////////
 197 // tag::extended_p_square_quantile
 198 //
 199 namespace tag
 200 {
 201     struct extended_p_square_quantile
 202       : depends_on<extended_p_square>
 203     {
 204         typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, unweighted, linear> impl;
 205     };
 206     struct extended_p_square_quantile_quadratic
 207       : depends_on<extended_p_square>
 208     {
 209         typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, unweighted, quadratic> impl;
 210     };
 211     struct weighted_extended_p_square_quantile
 212       : depends_on<weighted_extended_p_square>
 213     {
 214         typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, weighted, linear> impl;
 215     };
 216     struct weighted_extended_p_square_quantile_quadratic
 217       : depends_on<weighted_extended_p_square>
 218     {
 219         typedef accumulators::impl::extended_p_square_quantile_impl<mpl::_1, weighted, quadratic> impl;
 220     };
 221 }
 222
 223 ///////////////////////////////////////////////////////////////////////////////
 224 // extract::extended_p_square_quantile
 225 // extract::weighted_extended_p_square_quantile
 226 //
 227 namespace extract
 228 {
 229     extractor<tag::extended_p_square_quantile> const extended_p_square_quantile = {};
 230     extractor<tag::extended_p_square_quantile_quadratic> const extended_p_square_quantile_quadratic = {};
 231     extractor<tag::weighted_extended_p_square_quantile> const weighted_extended_p_square_quantile = {};
 232     extractor<tag::weighted_extended_p_square_quantile_quadratic> const weighted_extended_p_square_quantile_quadratic = {};
 233 }
 234
 235 using extract::extended_p_square_quantile;
 236 using extract::extended_p_square_quantile_quadratic;
 237 using extract::weighted_extended_p_square_quantile;
 238 using extract::weighted_extended_p_square_quantile_quadratic;
 239
 240 // extended_p_square_quantile(linear) -> extended_p_square_quantile
 241 template<>
 242 struct as_feature<tag::extended_p_square_quantile(linear)>
 243 {
 244     typedef tag::extended_p_square_quantile type;
 245 };
 246
 247 // extended_p_square_quantile(quadratic) -> extended_p_square_quantile_quadratic
 248 template<>
 249 struct as_feature<tag::extended_p_square_quantile(quadratic)>
 250 {
 251     typedef tag::extended_p_square_quantile_quadratic type;
 252 };
 253
 254 // weighted_extended_p_square_quantile(linear) -> weighted_extended_p_square_quantile
 255 template<>
 256 struct as_feature<tag::weighted_extended_p_square_quantile(linear)>
 257 {
 258     typedef tag::weighted_extended_p_square_quantile type;
 259 };
 260
 261 // weighted_extended_p_square_quantile(quadratic) -> weighted_extended_p_square_quantile_quadratic
 262 template<>
 263 struct as_feature<tag::weighted_extended_p_square_quantile(quadratic)>
 264 {
 265     typedef tag::weighted_extended_p_square_quantile_quadratic type;
 266 };
 267
 268 // for the purposes of feature-based dependency resolution,
 269 // extended_p_square_quantile and weighted_extended_p_square_quantile
 270 // provide the same feature as quantile
 271 template<>
 272 struct feature_of<tag::extended_p_square_quantile>
 273   : feature_of<tag::quantile>
 274 {
 275 };
 276 template<>
 277 struct feature_of<tag::extended_p_square_quantile_quadratic>
 278   : feature_of<tag::quantile>
 279 {
 280 };
 281 // So that extended_p_square_quantile can be automatically substituted with
 282 // weighted_extended_p_square_quantile when the weight parameter is non-void
 283 template<>
 284 struct as_weighted_feature<tag::extended_p_square_quantile>
 285 {
 286     typedef tag::weighted_extended_p_square_quantile type;
 287 };
 288
 289 template<>
 290 struct feature_of<tag::weighted_extended_p_square_quantile>
 291   : feature_of<tag::extended_p_square_quantile>
 292 {
 293 };
 294
 295 // So that extended_p_square_quantile_quadratic can be automatically substituted with
 296 // weighted_extended_p_square_quantile_quadratic when the weight parameter is non-void
 297 template<>
 298 struct as_weighted_feature<tag::extended_p_square_quantile_quadratic>
 299 {
 300     typedef tag::weighted_extended_p_square_quantile_quadratic type;
 301 };
 302 template<>
 303 struct feature_of<tag::weighted_extended_p_square_quantile_quadratic>
 304   : feature_of<tag::extended_p_square_quantile_quadratic>
 305 {
 306 };
 307
 308 }} // namespace boost::accumulators
 309
 310 #ifdef _MSC_VER
 311 # pragma warning(pop)
 312 #endif
 313
 314 #endif