boost/accumulators/statistics/tail.hpp
/////////////////////////////////////////////////////////////////////////////// // tail.hpp // // Copyright 2005 Eric Niebler, Michael Gauckler. 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_TAIL_HPP_EAN_28_10_2005 #define BOOST_ACCUMULATORS_STATISTICS_TAIL_HPP_EAN_28_10_2005 #include <vector> #include <functional> #include <boost/assert.hpp> #include <boost/range.hpp> #include <boost/mpl/if.hpp> #include <boost/mpl/or.hpp> #include <boost/mpl/placeholders.hpp> #include <boost/parameter/keyword.hpp> #include <boost/iterator/reverse_iterator.hpp> #include <boost/iterator/permutation_iterator.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> namespace boost { namespace accumulators { /////////////////////////////////////////////////////////////////////////////// // cache_size named parameters BOOST_PARAMETER_NESTED_KEYWORD(tag, right_tail_cache_size, cache_size) BOOST_PARAMETER_NESTED_KEYWORD(tag, left_tail_cache_size, cache_size) namespace detail { /////////////////////////////////////////////////////////////////////////////// // tail_range /// INTERNAL ONLY /// template<typename ElementIterator, typename IndexIterator> struct tail_range { typedef boost::iterator_range< boost::reverse_iterator<boost::permutation_iterator<ElementIterator, IndexIterator> > > type; }; /////////////////////////////////////////////////////////////////////////////// // make_tail_range /// INTERNAL ONLY /// template<typename ElementIterator, typename IndexIterator> typename tail_range<ElementIterator, IndexIterator>::type make_tail_range(ElementIterator elem_begin, IndexIterator index_begin, IndexIterator index_end) { return boost::make_iterator_range( boost::make_reverse_iterator( boost::make_permutation_iterator(elem_begin, index_end) ) , boost::make_reverse_iterator( boost::make_permutation_iterator(elem_begin, index_begin) ) ); } /////////////////////////////////////////////////////////////////////////////// // stat_assign_visitor /// INTERNAL ONLY /// template<typename Args> struct stat_assign_visitor { stat_assign_visitor(Args const &a, std::size_t i) : args(a) , index(i) { } template<typename Stat> void operator ()(Stat &stat) const { stat.assign(this->args, this->index); } private: stat_assign_visitor &operator =(stat_assign_visitor const &); Args const &args; std::size_t index; }; /////////////////////////////////////////////////////////////////////////////// // stat_assign /// INTERNAL ONLY /// template<typename Args> inline stat_assign_visitor<Args> const stat_assign(Args const &args, std::size_t index) { return stat_assign_visitor<Args>(args, index); } /////////////////////////////////////////////////////////////////////////////// // is_tail_variate_feature /// INTERNAL ONLY /// template<typename Stat, typename LeftRight> struct is_tail_variate_feature : mpl::false_ { }; /// INTERNAL ONLY /// template<typename VariateType, typename VariateTag, typename LeftRight> struct is_tail_variate_feature<tag::tail_variate<VariateType, VariateTag, LeftRight>, LeftRight> : mpl::true_ { }; /// INTERNAL ONLY /// template<typename LeftRight> struct is_tail_variate_feature<tag::tail_weights<LeftRight>, LeftRight> : mpl::true_ { }; } // namespace detail namespace impl { /////////////////////////////////////////////////////////////////////////////// // tail_impl template<typename Sample, typename LeftRight> struct tail_impl : accumulator_base { // LeftRight must be either right or left BOOST_MPL_ASSERT(( mpl::or_<is_same<LeftRight, right>, is_same<LeftRight, left> > )); typedef typename mpl::if_< is_same<LeftRight, right> , numeric::functional::greater<Sample const, Sample const> , numeric::functional::less<Sample const, Sample const> >::type predicate_type; // for boost::result_of typedef typename detail::tail_range< typename std::vector<Sample>::const_iterator , std::vector<std::size_t>::iterator >::type result_type; template<typename Args> tail_impl(Args const &args) : is_sorted(false) , indices() , samples(args[tag::tail<LeftRight>::cache_size], args[sample | Sample()]) { this->indices.reserve(this->samples.size()); } tail_impl(tail_impl const &that) : is_sorted(that.is_sorted) , indices(that.indices) , samples(that.samples) { this->indices.reserve(this->samples.size()); } // This just stores the heap and the samples. // In operator()() below, if we are adding a new sample // to the sample cache, we force all the // tail_variates to update also. (It's not // good enough to wait for the accumulator_set to do it // for us because then information about whether a sample // was stored and where is lost, and would need to be // queried at runtime, which would be slow.) This is // implemented as a filtered visitation over the stats, // which we can access because args[accumulator] gives us // all the stats. template<typename Args> void operator ()(Args const &args) { if(this->indices.size() < this->samples.size()) { this->indices.push_back(this->indices.size()); this->assign(args, this->indices.back()); } else if(predicate_type()(args[sample], this->samples[this->indices[0]])) { std::pop_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples)); this->assign(args, this->indices.back()); } } result_type result(dont_care) const { if(!this->is_sorted) { // Must use the same predicate here as in push_heap/pop_heap above. std::sort_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples)); // sort_heap puts elements in reverse order. Calling std::reverse // turns the sorted sequence back into a valid heap. std::reverse(this->indices.begin(), this->indices.end()); this->is_sorted = true; } return detail::make_tail_range( this->samples.begin() , this->indices.begin() , this->indices.end() ); } private: struct is_tail_variate { template<typename T> struct apply : detail::is_tail_variate_feature< typename detail::feature_tag<T>::type , LeftRight > {}; }; template<typename Args> void assign(Args const &args, std::size_t index) { BOOST_ASSERT(index < this->samples.size()); this->samples[index] = args[sample]; std::push_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples)); this->is_sorted = false; // Tell the tail variates to store their values also args[accumulator].template visit_if<is_tail_variate>(detail::stat_assign(args, index)); } /////////////////////////////////////////////////////////////////////////////// // struct indirect_cmp : std::binary_function<std::size_t, std::size_t, bool> { indirect_cmp(std::vector<Sample> const &s) : samples(s) { } bool operator ()(std::size_t left, std::size_t right) const { return predicate_type()(this->samples[left], this->samples[right]); } private: indirect_cmp &operator =(indirect_cmp const &); std::vector<Sample> const &samples; }; mutable bool is_sorted; mutable std::vector<std::size_t> indices; std::vector<Sample> samples; }; } // namespace impl // TODO The templatized tag::tail below should inherit from the correct named parameter. // The following lines provide a workaround, but there must be a better way of doing this. template<typename T> struct tail_cache_size_named_arg { }; template<> struct tail_cache_size_named_arg<left> : tag::left_tail_cache_size { }; template<> struct tail_cache_size_named_arg<right> : tag::right_tail_cache_size { }; /////////////////////////////////////////////////////////////////////////////// // tag::tail<> // namespace tag { template<typename LeftRight> struct tail : depends_on<> , tail_cache_size_named_arg<LeftRight> { /// INTERNAL ONLY /// typedef accumulators::impl::tail_impl<mpl::_1, LeftRight> impl; #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED /// tag::tail<LeftRight>::cache_size named parameter static boost::parameter::keyword<tail_cache_size_named_arg<LeftRight> > const cache_size; #endif }; struct abstract_tail : depends_on<> { }; } /////////////////////////////////////////////////////////////////////////////// // extract::tail // namespace extract { extractor<tag::abstract_tail> const tail = {}; BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail) } using extract::tail; template<typename LeftRight> struct feature_of<tag::tail<LeftRight> > : feature_of<tag::abstract_tail> { }; }} // namespace boost::accumulators #endif