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