/////////////////////////////////////////////////////////////////////////////// // 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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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) BOOST_ACCUMULATORS_IGNORE_GLOBAL(right_tail_cache_size) BOOST_ACCUMULATORS_IGNORE_GLOBAL(left_tail_cache_size) namespace detail { /////////////////////////////////////////////////////////////////////////////// // tail_range /// INTERNAL ONLY /// template struct tail_range { typedef boost::iterator_range< boost::reverse_iterator > > type; }; /////////////////////////////////////////////////////////////////////////////// // make_tail_range /// INTERNAL ONLY /// template typename tail_range::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 struct stat_assign_visitor { stat_assign_visitor(Args const &a, std::size_t i) : args(a) , index(i) { } template 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 inline stat_assign_visitor const stat_assign(Args const &args, std::size_t index) { return stat_assign_visitor(args, index); } /////////////////////////////////////////////////////////////////////////////// // is_tail_variate_feature /// INTERNAL ONLY /// template struct is_tail_variate_feature : mpl::false_ { }; /// INTERNAL ONLY /// template struct is_tail_variate_feature, LeftRight> : mpl::true_ { }; /// INTERNAL ONLY /// template struct is_tail_variate_feature, LeftRight> : mpl::true_ { }; } // namespace detail namespace impl { /////////////////////////////////////////////////////////////////////////////// // tail_impl template struct tail_impl : accumulator_base { // LeftRight must be either right or left BOOST_MPL_ASSERT(( mpl::or_, is_same > )); typedef typename mpl::if_< is_same , numeric::functional::greater , numeric::functional::less >::type predicate_type; // for boost::result_of typedef typename detail::tail_range< typename std::vector::const_iterator , std::vector::iterator >::type result_type; template tail_impl(Args const &args) : is_sorted(false) , indices() , samples(args[tag::tail::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 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 struct apply : detail::is_tail_variate_feature< typename detail::feature_tag::type , LeftRight > {}; }; template 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(detail::stat_assign(args, index)); } /////////////////////////////////////////////////////////////////////////////// // struct indirect_cmp { typedef std::size_t first_argument_type; typedef std::size_t second_argument_type; typedef bool result_type; indirect_cmp(std::vector 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 const &samples; }; public: // make this accumulator serializeable template void serialize(Archive & ar, const unsigned int file_version) { ar & is_sorted; ar & indices; ar & samples; } private: mutable bool is_sorted; mutable std::vector indices; std::vector 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 struct tail_cache_size_named_arg { }; template<> struct tail_cache_size_named_arg : tag::left_tail_cache_size { }; template<> struct tail_cache_size_named_arg : tag::right_tail_cache_size { }; /////////////////////////////////////////////////////////////////////////////// // tag::tail<> // namespace tag { template struct tail : depends_on<> , tail_cache_size_named_arg { /// INTERNAL ONLY /// typedef accumulators::impl::tail_impl impl; #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED /// tag::tail::cache_size named parameter static boost::parameter::keyword > const cache_size; #endif }; struct abstract_tail : depends_on<> { }; } /////////////////////////////////////////////////////////////////////////////// // extract::tail // namespace extract { extractor const tail = {}; BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail) } using extract::tail; template struct feature_of > : feature_of { }; }} // namespace boost::accumulators #endif