Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-01-18 09:28:19

0001 
0002 ///////////////////////////////////////////////////////////////////////////////
0003 // density.hpp
0004 //
0005 //  Copyright 2006 Daniel Egloff, Olivier Gygi. Distributed under the Boost
0006 //  Software License, Version 1.0. (See accompanying file
0007 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0008 
0009 #ifndef BOOST_ACCUMULATORS_STATISTICS_DENSITY_HPP_DE_01_01_2006
0010 #define BOOST_ACCUMULATORS_STATISTICS_DENSITY_HPP_DE_01_01_2006
0011 
0012 #include <vector>
0013 #include <limits>
0014 #include <functional>
0015 #include <boost/range.hpp>
0016 #include <boost/parameter/keyword.hpp>
0017 #include <boost/mpl/placeholders.hpp>
0018 #include <boost/accumulators/accumulators_fwd.hpp>
0019 #include <boost/accumulators/framework/accumulator_base.hpp>
0020 #include <boost/accumulators/framework/extractor.hpp>
0021 #include <boost/accumulators/numeric/functional.hpp>
0022 #include <boost/accumulators/framework/parameters/sample.hpp>
0023 #include <boost/accumulators/framework/depends_on.hpp>
0024 #include <boost/accumulators/statistics_fwd.hpp>
0025 #include <boost/accumulators/statistics/count.hpp>
0026 #include <boost/accumulators/statistics/max.hpp>
0027 #include <boost/accumulators/statistics/min.hpp>
0028 #include <boost/serialization/vector.hpp>
0029 #include <boost/serialization/utility.hpp>
0030 
0031 namespace boost { namespace accumulators
0032 {
0033 
0034 ///////////////////////////////////////////////////////////////////////////////
0035 // cache_size and num_bins named parameters
0036 //
0037 BOOST_PARAMETER_NESTED_KEYWORD(tag, density_cache_size, cache_size)
0038 BOOST_PARAMETER_NESTED_KEYWORD(tag, density_num_bins, num_bins)
0039 
0040 BOOST_ACCUMULATORS_IGNORE_GLOBAL(density_cache_size)
0041 BOOST_ACCUMULATORS_IGNORE_GLOBAL(density_num_bins)
0042 
0043 namespace impl
0044 {
0045     ///////////////////////////////////////////////////////////////////////////////
0046     // density_impl
0047     //  density histogram
0048     /**
0049         @brief Histogram density estimator
0050 
0051         The histogram density estimator returns a histogram of the sample distribution. The positions and sizes of the bins
0052         are determined using a specifiable number of cached samples (cache_size). The range between the minimum and the
0053         maximum of the cached samples is subdivided into a specifiable number of bins (num_bins) of same size. Additionally,
0054         an under- and an overflow bin is added to capture future under- and overflow samples. Once the bins are determined,
0055         the cached samples and all subsequent samples are added to the correct bins. At the end, a range of std::pair is
0056         return, where each pair contains the position of the bin (lower bound) and the samples count (normalized with the
0057         total number of samples).
0058 
0059         @param  density_cache_size Number of first samples used to determine min and max.
0060         @param  density_num_bins Number of bins (two additional bins collect under- and overflow samples).
0061     */
0062     template<typename Sample>
0063     struct density_impl
0064       : accumulator_base
0065     {
0066         typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
0067         typedef std::vector<std::pair<float_type, float_type> > histogram_type;
0068         typedef std::vector<float_type> array_type;
0069         // for boost::result_of
0070         typedef iterator_range<typename histogram_type::iterator> result_type;
0071 
0072         template<typename Args>
0073         density_impl(Args const &args)
0074             : cache_size(args[density_cache_size])
0075             , cache(cache_size)
0076             , num_bins(args[density_num_bins])
0077             , samples_in_bin(num_bins + 2, 0.)
0078             , bin_positions(num_bins + 2)
0079             , histogram(
0080                 num_bins + 2
0081               , std::make_pair(
0082                     numeric::fdiv(args[sample | Sample()],(std::size_t)1)
0083                   , numeric::fdiv(args[sample | Sample()],(std::size_t)1)
0084                 )
0085               )
0086             , is_dirty(true)
0087         {
0088         }
0089 
0090         template<typename Args>
0091         void operator ()(Args const &args)
0092         {
0093             this->is_dirty = true;
0094 
0095             std::size_t cnt = count(args);
0096 
0097             // Fill up cache with cache_size first samples
0098             if (cnt <= this->cache_size)
0099             {
0100                 this->cache[cnt - 1] = args[sample];
0101             }
0102 
0103             // Once cache_size samples have been accumulated, create num_bins bins of same size between
0104             // the minimum and maximum of the cached samples as well as under and overflow bins.
0105             // Store their lower bounds (bin_positions) and fill the bins with the cached samples (samples_in_bin).
0106             if (cnt == this->cache_size)
0107             {
0108                 float_type minimum = numeric::fdiv((min)(args), (std::size_t)1);
0109                 float_type maximum = numeric::fdiv((max)(args), (std::size_t)1);
0110                 float_type bin_size = numeric::fdiv(maximum - minimum, this->num_bins );
0111 
0112                 // determine bin positions (their lower bounds)
0113                 for (std::size_t i = 0; i < this->num_bins + 2; ++i)
0114                 {
0115                     this->bin_positions[i] = minimum + (i - 1.) * bin_size;
0116                 }
0117 
0118                 for (typename array_type::const_iterator iter = this->cache.begin(); iter != this->cache.end(); ++iter)
0119                 {
0120                     if (*iter < this->bin_positions[1])
0121                     {
0122                         ++(this->samples_in_bin[0]);
0123                     }
0124                     else if (*iter >= this->bin_positions[this->num_bins + 1])
0125                     {
0126                         ++(this->samples_in_bin[this->num_bins + 1]);
0127                     }
0128                     else
0129                     {
0130                         typename array_type::iterator it = std::upper_bound(
0131                             this->bin_positions.begin()
0132                           , this->bin_positions.end()
0133                           , *iter
0134                         );
0135 
0136                         std::size_t d = std::distance(this->bin_positions.begin(), it);
0137                         ++(this->samples_in_bin[d - 1]);
0138                     }
0139                 }
0140             }
0141             // Add each subsequent sample to the correct bin
0142             else if (cnt > this->cache_size)
0143             {
0144                 if (args[sample] < this->bin_positions[1])
0145                 {
0146                     ++(this->samples_in_bin[0]);
0147                 }
0148                 else if (args[sample] >= this->bin_positions[this->num_bins + 1])
0149                 {
0150                     ++(this->samples_in_bin[this->num_bins + 1]);
0151                 }
0152                 else
0153                 {
0154                     typename array_type::iterator it = std::upper_bound(
0155                         this->bin_positions.begin()
0156                       , this->bin_positions.end()
0157                       , args[sample]
0158                     );
0159 
0160                     std::size_t d = std::distance(this->bin_positions.begin(), it);
0161                     ++(this->samples_in_bin[d - 1]);
0162                 }
0163             }
0164         }
0165 
0166         /**
0167             @pre The number of samples must meet or exceed the cache size
0168         */
0169         template<typename Args>
0170         result_type result(Args const &args) const
0171         {
0172             if (this->is_dirty)
0173             {
0174                 this->is_dirty = false;
0175 
0176                 // creates a vector of std::pair where each pair i holds
0177                 // the values bin_positions[i] (x-axis of histogram) and
0178                 // samples_in_bin[i] / cnt (y-axis of histogram).
0179 
0180                 for (std::size_t i = 0; i < this->num_bins + 2; ++i)
0181                 {
0182                     this->histogram[i] = std::make_pair(this->bin_positions[i], numeric::fdiv(this->samples_in_bin[i], count(args)));
0183                 }
0184             }
0185             // returns a range of pairs
0186             return make_iterator_range(this->histogram);
0187         }
0188 
0189         // make this accumulator serializeable
0190         // TODO split to save/load and check on parameters provided in ctor
0191         template<class Archive>
0192         void serialize(Archive & ar, const unsigned int file_version)
0193         {
0194             ar & cache_size;
0195             ar & cache;
0196             ar & num_bins;
0197             ar & samples_in_bin;
0198             ar & bin_positions;
0199             ar & histogram;
0200             ar & is_dirty; 
0201         }
0202 
0203     private:
0204         std::size_t            cache_size;      // number of cached samples
0205         array_type             cache;           // cache to store the first cache_size samples
0206         std::size_t            num_bins;        // number of bins
0207         array_type             samples_in_bin;  // number of samples in each bin
0208         array_type             bin_positions;   // lower bounds of bins
0209         mutable histogram_type histogram;       // histogram
0210         mutable bool is_dirty;
0211     };
0212 
0213 } // namespace impl
0214 
0215 ///////////////////////////////////////////////////////////////////////////////
0216 // tag::density
0217 //
0218 namespace tag
0219 {
0220     struct density
0221       : depends_on<count, min, max>
0222       , density_cache_size
0223       , density_num_bins
0224     {
0225         /// INTERNAL ONLY
0226         ///
0227         typedef accumulators::impl::density_impl<mpl::_1> impl;
0228 
0229         #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED
0230         /// tag::density::cache_size named parameter
0231         /// tag::density::num_bins named parameter
0232         static boost::parameter::keyword<density_cache_size> const cache_size;
0233         static boost::parameter::keyword<density_num_bins> const num_bins;
0234         #endif
0235     };
0236 }
0237 
0238 ///////////////////////////////////////////////////////////////////////////////
0239 // extract::density
0240 //
0241 namespace extract
0242 {
0243     extractor<tag::density> const density = {};
0244 
0245     BOOST_ACCUMULATORS_IGNORE_GLOBAL(density)
0246 }
0247 
0248 using extract::density;
0249 
0250 // So that density can be automatically substituted
0251 // with weighted_density when the weight parameter is non-void.
0252 template<>
0253 struct as_weighted_feature<tag::density>
0254 {
0255     typedef tag::weighted_density type;
0256 };
0257 
0258 template<>
0259 struct feature_of<tag::weighted_density>
0260   : feature_of<tag::density>
0261 {
0262 };
0263 
0264 }} // namespace boost::accumulators
0265 
0266 #endif