Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // density.hpp
Chris@16: //
Chris@16: //  Copyright 2006 Daniel Egloff, Olivier Gygi. Distributed under the Boost
Chris@16: //  Software License, Version 1.0. (See accompanying file
Chris@16: //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_ACCUMULATORS_STATISTICS_DENSITY_HPP_DE_01_01_2006
Chris@16: #define BOOST_ACCUMULATORS_STATISTICS_DENSITY_HPP_DE_01_01_2006
Chris@16: 
Chris@16: #include <vector>
Chris@16: #include <limits>
Chris@16: #include <functional>
Chris@16: #include <boost/range.hpp>
Chris@16: #include <boost/parameter/keyword.hpp>
Chris@16: #include <boost/mpl/placeholders.hpp>
Chris@16: #include <boost/accumulators/accumulators_fwd.hpp>
Chris@16: #include <boost/accumulators/framework/accumulator_base.hpp>
Chris@16: #include <boost/accumulators/framework/extractor.hpp>
Chris@16: #include <boost/accumulators/numeric/functional.hpp>
Chris@16: #include <boost/accumulators/framework/parameters/sample.hpp>
Chris@16: #include <boost/accumulators/framework/depends_on.hpp>
Chris@16: #include <boost/accumulators/statistics_fwd.hpp>
Chris@16: #include <boost/accumulators/statistics/count.hpp>
Chris@16: #include <boost/accumulators/statistics/max.hpp>
Chris@16: #include <boost/accumulators/statistics/min.hpp>
Chris@16: 
Chris@16: namespace boost { namespace accumulators
Chris@16: {
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // cache_size and num_bins named parameters
Chris@16: //
Chris@16: BOOST_PARAMETER_NESTED_KEYWORD(tag, density_cache_size, cache_size)
Chris@16: BOOST_PARAMETER_NESTED_KEYWORD(tag, density_num_bins, num_bins)
Chris@16: 
Chris@16: BOOST_ACCUMULATORS_IGNORE_GLOBAL(density_cache_size)
Chris@16: BOOST_ACCUMULATORS_IGNORE_GLOBAL(density_num_bins)
Chris@16: 
Chris@16: namespace impl
Chris@16: {
Chris@16:     ///////////////////////////////////////////////////////////////////////////////
Chris@16:     // density_impl
Chris@16:     //  density histogram
Chris@16:     /**
Chris@16:         @brief Histogram density estimator
Chris@16: 
Chris@16:         The histogram density estimator returns a histogram of the sample distribution. The positions and sizes of the bins
Chris@16:         are determined using a specifiable number of cached samples (cache_size). The range between the minimum and the
Chris@16:         maximum of the cached samples is subdivided into a specifiable number of bins (num_bins) of same size. Additionally,
Chris@16:         an under- and an overflow bin is added to capture future under- and overflow samples. Once the bins are determined,
Chris@16:         the cached samples and all subsequent samples are added to the correct bins. At the end, a range of std::pair is
Chris@16:         return, where each pair contains the position of the bin (lower bound) and the samples count (normalized with the
Chris@16:         total number of samples).
Chris@16: 
Chris@16:         @param  density_cache_size Number of first samples used to determine min and max.
Chris@16:         @param  density_num_bins Number of bins (two additional bins collect under- and overflow samples).
Chris@16:     */
Chris@16:     template<typename Sample>
Chris@16:     struct density_impl
Chris@16:       : accumulator_base
Chris@16:     {
Chris@16:         typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
Chris@16:         typedef std::vector<std::pair<float_type, float_type> > histogram_type;
Chris@16:         typedef std::vector<float_type> array_type;
Chris@16:         // for boost::result_of
Chris@16:         typedef iterator_range<typename histogram_type::iterator> result_type;
Chris@16: 
Chris@16:         template<typename Args>
Chris@16:         density_impl(Args const &args)
Chris@16:             : cache_size(args[density_cache_size])
Chris@16:             , cache(cache_size)
Chris@16:             , num_bins(args[density_num_bins])
Chris@16:             , samples_in_bin(num_bins + 2, 0.)
Chris@16:             , bin_positions(num_bins + 2)
Chris@16:             , histogram(
Chris@16:                 num_bins + 2
Chris@16:               , std::make_pair(
Chris@16:                     numeric::fdiv(args[sample | Sample()],(std::size_t)1)
Chris@16:                   , numeric::fdiv(args[sample | Sample()],(std::size_t)1)
Chris@16:                 )
Chris@16:               )
Chris@16:             , is_dirty(true)
Chris@16:         {
Chris@16:         }
Chris@16: 
Chris@16:         template<typename Args>
Chris@16:         void operator ()(Args const &args)
Chris@16:         {
Chris@16:             this->is_dirty = true;
Chris@16: 
Chris@16:             std::size_t cnt = count(args);
Chris@16: 
Chris@16:             // Fill up cache with cache_size first samples
Chris@16:             if (cnt <= this->cache_size)
Chris@16:             {
Chris@16:                 this->cache[cnt - 1] = args[sample];
Chris@16:             }
Chris@16: 
Chris@16:             // Once cache_size samples have been accumulated, create num_bins bins of same size between
Chris@16:             // the minimum and maximum of the cached samples as well as under and overflow bins.
Chris@16:             // Store their lower bounds (bin_positions) and fill the bins with the cached samples (samples_in_bin).
Chris@16:             if (cnt == this->cache_size)
Chris@16:             {
Chris@16:                 float_type minimum = numeric::fdiv((min)(args), (std::size_t)1);
Chris@16:                 float_type maximum = numeric::fdiv((max)(args), (std::size_t)1);
Chris@16:                 float_type bin_size = numeric::fdiv(maximum - minimum, this->num_bins );
Chris@16: 
Chris@16:                 // determine bin positions (their lower bounds)
Chris@16:                 for (std::size_t i = 0; i < this->num_bins + 2; ++i)
Chris@16:                 {
Chris@16:                     this->bin_positions[i] = minimum + (i - 1.) * bin_size;
Chris@16:                 }
Chris@16: 
Chris@16:                 for (typename array_type::const_iterator iter = this->cache.begin(); iter != this->cache.end(); ++iter)
Chris@16:                 {
Chris@16:                     if (*iter < this->bin_positions[1])
Chris@16:                     {
Chris@16:                         ++(this->samples_in_bin[0]);
Chris@16:                     }
Chris@16:                     else if (*iter >= this->bin_positions[this->num_bins + 1])
Chris@16:                     {
Chris@16:                         ++(this->samples_in_bin[this->num_bins + 1]);
Chris@16:                     }
Chris@16:                     else
Chris@16:                     {
Chris@16:                         typename array_type::iterator it = std::upper_bound(
Chris@16:                             this->bin_positions.begin()
Chris@16:                           , this->bin_positions.end()
Chris@16:                           , *iter
Chris@16:                         );
Chris@16: 
Chris@16:                         std::size_t d = std::distance(this->bin_positions.begin(), it);
Chris@16:                         ++(this->samples_in_bin[d - 1]);
Chris@16:                     }
Chris@16:                 }
Chris@16:             }
Chris@16:             // Add each subsequent sample to the correct bin
Chris@16:             else if (cnt > this->cache_size)
Chris@16:             {
Chris@16:                 if (args[sample] < this->bin_positions[1])
Chris@16:                 {
Chris@16:                     ++(this->samples_in_bin[0]);
Chris@16:                 }
Chris@16:                 else if (args[sample] >= this->bin_positions[this->num_bins + 1])
Chris@16:                 {
Chris@16:                     ++(this->samples_in_bin[this->num_bins + 1]);
Chris@16:                 }
Chris@16:                 else
Chris@16:                 {
Chris@16:                     typename array_type::iterator it = std::upper_bound(
Chris@16:                         this->bin_positions.begin()
Chris@16:                       , this->bin_positions.end()
Chris@16:                       , args[sample]
Chris@16:                     );
Chris@16: 
Chris@16:                     std::size_t d = std::distance(this->bin_positions.begin(), it);
Chris@16:                     ++(this->samples_in_bin[d - 1]);
Chris@16:                 }
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         /**
Chris@16:             @pre The number of samples must meet or exceed the cache size
Chris@16:         */
Chris@16:         template<typename Args>
Chris@16:         result_type result(Args const &args) const
Chris@16:         {
Chris@16:             if (this->is_dirty)
Chris@16:             {
Chris@16:                 this->is_dirty = false;
Chris@16: 
Chris@16:                 // creates a vector of std::pair where each pair i holds
Chris@16:                 // the values bin_positions[i] (x-axis of histogram) and
Chris@16:                 // samples_in_bin[i] / cnt (y-axis of histogram).
Chris@16: 
Chris@16:                 for (std::size_t i = 0; i < this->num_bins + 2; ++i)
Chris@16:                 {
Chris@16:                     this->histogram[i] = std::make_pair(this->bin_positions[i], numeric::fdiv(this->samples_in_bin[i], count(args)));
Chris@16:                 }
Chris@16:             }
Chris@16:             // returns a range of pairs
Chris@16:             return make_iterator_range(this->histogram);
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         std::size_t            cache_size;      // number of cached samples
Chris@16:         array_type             cache;           // cache to store the first cache_size samples
Chris@16:         std::size_t            num_bins;        // number of bins
Chris@16:         array_type             samples_in_bin;  // number of samples in each bin
Chris@16:         array_type             bin_positions;   // lower bounds of bins
Chris@16:         mutable histogram_type histogram;       // histogram
Chris@16:         mutable bool is_dirty;
Chris@16:     };
Chris@16: 
Chris@16: } // namespace impl
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // tag::density
Chris@16: //
Chris@16: namespace tag
Chris@16: {
Chris@16:     struct density
Chris@16:       : depends_on<count, min, max>
Chris@16:       , density_cache_size
Chris@16:       , density_num_bins
Chris@16:     {
Chris@16:         /// INTERNAL ONLY
Chris@16:         ///
Chris@16:         typedef accumulators::impl::density_impl<mpl::_1> impl;
Chris@16: 
Chris@16:         #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED
Chris@16:         /// tag::density::cache_size named parameter
Chris@16:         /// tag::density::num_bins named parameter
Chris@16:         static boost::parameter::keyword<density_cache_size> const cache_size;
Chris@16:         static boost::parameter::keyword<density_num_bins> const num_bins;
Chris@16:         #endif
Chris@16:     };
Chris@16: }
Chris@16: 
Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // extract::density
Chris@16: //
Chris@16: namespace extract
Chris@16: {
Chris@16:     extractor<tag::density> const density = {};
Chris@16: 
Chris@16:     BOOST_ACCUMULATORS_IGNORE_GLOBAL(density)
Chris@16: }
Chris@16: 
Chris@16: using extract::density;
Chris@16: 
Chris@16: // So that density can be automatically substituted
Chris@16: // with weighted_density when the weight parameter is non-void.
Chris@16: template<>
Chris@16: struct as_weighted_feature<tag::density>
Chris@16: {
Chris@16:     typedef tag::weighted_density type;
Chris@16: };
Chris@16: 
Chris@16: template<>
Chris@16: struct feature_of<tag::weighted_density>
Chris@16:   : feature_of<tag::density>
Chris@16: {
Chris@16: };
Chris@16: 
Chris@16: }} // namespace boost::accumulators
Chris@16: 
Chris@16: #endif