ceph/src/boost/libs/accumulators/include/boost/accumulators/statistics/median.hpp

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // median.hpp
   3 //
   4 //  Copyright 2006 Eric Niebler, Olivier Gygi. 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_MEDIAN_HPP_EAN_28_10_2005
   9 #define BOOST_ACCUMULATORS_STATISTICS_MEDIAN_HPP_EAN_28_10_2005
  10
  11 #include <boost/mpl/placeholders.hpp>
  12 #include <boost/range/iterator_range.hpp>
  13 #include <boost/accumulators/framework/accumulator_base.hpp>
  14 #include <boost/accumulators/framework/extractor.hpp>
  15 #include <boost/accumulators/numeric/functional.hpp>
  16 #include <boost/accumulators/framework/parameters/sample.hpp>
  17 #include <boost/accumulators/framework/depends_on.hpp>
  18 #include <boost/accumulators/statistics_fwd.hpp>
  19 #include <boost/accumulators/statistics/count.hpp>
  20 #include <boost/accumulators/statistics/p_square_quantile.hpp>
  21 #include <boost/accumulators/statistics/density.hpp>
  22 #include <boost/accumulators/statistics/p_square_cumul_dist.hpp>
  23
  24 namespace boost { namespace accumulators
  25 {
  26
  27 namespace impl
  28 {
  29     ///////////////////////////////////////////////////////////////////////////////
  30     // median_impl
  31     //
  32     /**
  33         @brief Median estimation based on the \f$P^2\f$ quantile estimator
  34
  35         The \f$P^2\f$ algorithm is invoked with a quantile probability of 0.5.
  36     */
  37     template<typename Sample>
  38     struct median_impl
  39       : accumulator_base
  40     {
  41         // for boost::result_of
  42         typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type result_type;
  43
  44         median_impl(dont_care) {}
  45
  46         template<typename Args>
  47         result_type result(Args const &args) const
  48         {
  49             return p_square_quantile_for_median(args);
  50         }
  51     };
  52     ///////////////////////////////////////////////////////////////////////////////
  53     // with_density_median_impl
  54     //
  55     /**
  56         @brief Median estimation based on the density estimator
  57
  58         The algorithm determines the bin in which the \f$0.5*cnt\f$-th sample lies, \f$cnt\f$ being
  59         the total number of samples. It returns the approximate horizontal position of this sample,
  60         based on a linear interpolation inside the bin.
  61     */
  62     template<typename Sample>
  63     struct with_density_median_impl
  64       : accumulator_base
  65     {
  66         typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
  67         typedef std::vector<std::pair<float_type, float_type> > histogram_type;
  68         typedef iterator_range<typename histogram_type::iterator> range_type;
  69         // for boost::result_of
  70         typedef float_type result_type;
  71
  72         template<typename Args>
  73         with_density_median_impl(Args const &args)
  74           : sum(numeric::fdiv(args[sample | Sample()], (std::size_t)1))
  75           , is_dirty(true)
  76         {
  77         }
  78
  79         void operator ()(dont_care)
  80         {
  81             this->is_dirty = true;
  82         }
  83
  84
  85         template<typename Args>
  86         result_type result(Args const &args) const
  87         {
  88             if (this->is_dirty)
  89             {
  90                 this->is_dirty = false;
  91
  92                 std::size_t cnt = count(args);
  93                 range_type histogram = density(args);
  94                 typename range_type::iterator it = histogram.begin();
  95                 while (this->sum < 0.5 * cnt)
  96                 {
  97                     this->sum += it->second * cnt;
  98                     ++it;
  99                 }
 100                 --it;
 101                 float_type over = numeric::fdiv(this->sum - 0.5 * cnt, it->second * cnt);
 102                 this->median = it->first * over + (it + 1)->first * (1. - over);
 103             }
 104
 105             return this->median;
 106         }
 107
 108     private:
 109         mutable float_type sum;
 110         mutable bool is_dirty;
 111         mutable float_type median;
 112     };
 113
 114     ///////////////////////////////////////////////////////////////////////////////
 115     // with_p_square_cumulative_distribution_median_impl
 116     //
 117     /**
 118         @brief Median estimation based on the \f$P^2\f$ cumulative distribution estimator
 119
 120         The algorithm determines the first (leftmost) bin with a height exceeding 0.5. It
 121         returns the approximate horizontal position of where the cumulative distribution
 122         equals 0.5, based on a linear interpolation inside the bin.
 123     */
 124     template<typename Sample>
 125     struct with_p_square_cumulative_distribution_median_impl
 126       : accumulator_base
 127     {
 128         typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
 129         typedef std::vector<std::pair<float_type, float_type> > histogram_type;
 130         typedef iterator_range<typename histogram_type::iterator> range_type;
 131         // for boost::result_of
 132         typedef float_type result_type;
 133
 134         with_p_square_cumulative_distribution_median_impl(dont_care)
 135           : is_dirty(true)
 136         {
 137         }
 138
 139         void operator ()(dont_care)
 140         {
 141             this->is_dirty = true;
 142         }
 143
 144         template<typename Args>
 145         result_type result(Args const &args) const
 146         {
 147             if (this->is_dirty)
 148             {
 149                 this->is_dirty = false;
 150
 151                 range_type histogram = p_square_cumulative_distribution(args);
 152                 typename range_type::iterator it = histogram.begin();
 153                 while (it->second < 0.5)
 154                 {
 155                     ++it;
 156                 }
 157                 float_type over = numeric::fdiv(it->second - 0.5, it->second - (it - 1)->second);
 158                 this->median = it->first * over + (it + 1)->first * ( 1. - over );
 159             }
 160
 161             return this->median;
 162         }
 163     private:
 164
 165         mutable bool is_dirty;
 166         mutable float_type median;
 167     };
 168
 169 } // namespace impl
 170
 171 ///////////////////////////////////////////////////////////////////////////////
 172 // tag::median
 173 // tag::with_densisty_median
 174 // tag::with_p_square_cumulative_distribution_median
 175 //
 176 namespace tag
 177 {
 178     struct median
 179       : depends_on<p_square_quantile_for_median>
 180     {
 181         /// INTERNAL ONLY
 182         ///
 183         typedef accumulators::impl::median_impl<mpl::_1> impl;
 184     };
 185     struct with_density_median
 186       : depends_on<count, density>
 187     {
 188         /// INTERNAL ONLY
 189         ///
 190         typedef accumulators::impl::with_density_median_impl<mpl::_1> impl;
 191     };
 192     struct with_p_square_cumulative_distribution_median
 193       : depends_on<p_square_cumulative_distribution>
 194     {
 195         /// INTERNAL ONLY
 196         ///
 197         typedef accumulators::impl::with_p_square_cumulative_distribution_median_impl<mpl::_1> impl;
 198     };
 199 }
 200
 201 ///////////////////////////////////////////////////////////////////////////////
 202 // extract::median
 203 // extract::with_density_median
 204 // extract::with_p_square_cumulative_distribution_median
 205 //
 206 namespace extract
 207 {
 208     extractor<tag::median> const median = {};
 209     extractor<tag::with_density_median> const with_density_median = {};
 210     extractor<tag::with_p_square_cumulative_distribution_median> const with_p_square_cumulative_distribution_median = {};
 211
 212     BOOST_ACCUMULATORS_IGNORE_GLOBAL(median)
 213     BOOST_ACCUMULATORS_IGNORE_GLOBAL(with_density_median)
 214     BOOST_ACCUMULATORS_IGNORE_GLOBAL(with_p_square_cumulative_distribution_median)
 215 }
 216
 217 using extract::median;
 218 using extract::with_density_median;
 219 using extract::with_p_square_cumulative_distribution_median;
 220
 221 // median(with_p_square_quantile) -> median
 222 template<>
 223 struct as_feature<tag::median(with_p_square_quantile)>
 224 {
 225     typedef tag::median type;
 226 };
 227
 228 // median(with_density) -> with_density_median
 229 template<>
 230 struct as_feature<tag::median(with_density)>
 231 {
 232     typedef tag::with_density_median type;
 233 };
 234
 235 // median(with_p_square_cumulative_distribution) -> with_p_square_cumulative_distribution_median
 236 template<>
 237 struct as_feature<tag::median(with_p_square_cumulative_distribution)>
 238 {
 239     typedef tag::with_p_square_cumulative_distribution_median type;
 240 };
 241
 242 // for the purposes of feature-based dependency resolution,
 243 // with_density_median and with_p_square_cumulative_distribution_median
 244 // provide the same feature as median
 245 template<>
 246 struct feature_of<tag::with_density_median>
 247   : feature_of<tag::median>
 248 {
 249 };
 250
 251 template<>
 252 struct feature_of<tag::with_p_square_cumulative_distribution_median>
 253   : feature_of<tag::median>
 254 {
 255 };
 256
 257 // So that median can be automatically substituted with
 258 // weighted_median when the weight parameter is non-void.
 259 template<>
 260 struct as_weighted_feature<tag::median>
 261 {
 262     typedef tag::weighted_median type;
 263 };
 264
 265 template<>
 266 struct feature_of<tag::weighted_median>
 267   : feature_of<tag::median>
 268 {
 269 };
 270
 271 // So that with_density_median can be automatically substituted with
 272 // with_density_weighted_median when the weight parameter is non-void.
 273 template<>
 274 struct as_weighted_feature<tag::with_density_median>
 275 {
 276     typedef tag::with_density_weighted_median type;
 277 };
 278
 279 template<>
 280 struct feature_of<tag::with_density_weighted_median>
 281   : feature_of<tag::with_density_median>
 282 {
 283 };
 284
 285 // So that with_p_square_cumulative_distribution_median can be automatically substituted with
 286 // with_p_square_cumulative_distribution_weighted_median when the weight parameter is non-void.
 287 template<>
 288 struct as_weighted_feature<tag::with_p_square_cumulative_distribution_median>
 289 {
 290     typedef tag::with_p_square_cumulative_distribution_weighted_median type;
 291 };
 292
 293 template<>
 294 struct feature_of<tag::with_p_square_cumulative_distribution_weighted_median>
 295   : feature_of<tag::with_p_square_cumulative_distribution_median>
 296 {
 297 };
 298
 299 }} // namespace boost::accumulators
 300
 301 #endif