accumulators/statistics/tail.hpp

0001 ///////////////////////////////////////////////////////////////////////////////
0002 // tail.hpp
0003 //
0004 //  Copyright 2005 Eric Niebler, Michael Gauckler. Distributed under the Boost
0005 //  Software License, Version 1.0. (See accompanying file
0006 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0007
0008 #ifndef BOOST_ACCUMULATORS_STATISTICS_TAIL_HPP_EAN_28_10_2005
0009 #define BOOST_ACCUMULATORS_STATISTICS_TAIL_HPP_EAN_28_10_2005
0010
0011 #include <vector>
0012 #include <functional>
0013 #include <boost/assert.hpp>
0014 #include <boost/range.hpp>
0015 #include <boost/mpl/if.hpp>
0016 #include <boost/mpl/or.hpp>
0017 #include <boost/mpl/placeholders.hpp>
0018 #include <boost/parameter/keyword.hpp>
0019 #include <boost/iterator/reverse_iterator.hpp>
0020 #include <boost/iterator/permutation_iterator.hpp>
0021 #include <boost/accumulators/accumulators_fwd.hpp>
0022 #include <boost/accumulators/framework/accumulator_base.hpp>
0023 #include <boost/accumulators/framework/extractor.hpp>
0024 #include <boost/accumulators/numeric/functional.hpp>
0025 #include <boost/accumulators/framework/parameters/sample.hpp>
0026 #include <boost/accumulators/framework/depends_on.hpp>
0027 #include <boost/accumulators/statistics_fwd.hpp>
0028
0029 namespace boost { namespace accumulators
0030 {
0031 ///////////////////////////////////////////////////////////////////////////////
0032 // cache_size named parameters
0033 BOOST_PARAMETER_NESTED_KEYWORD(tag, right_tail_cache_size, cache_size)
0034 BOOST_PARAMETER_NESTED_KEYWORD(tag, left_tail_cache_size, cache_size)
0035
0036 BOOST_ACCUMULATORS_IGNORE_GLOBAL(right_tail_cache_size)
0037 BOOST_ACCUMULATORS_IGNORE_GLOBAL(left_tail_cache_size)
0038
0039 namespace detail
0040 {
0041     ///////////////////////////////////////////////////////////////////////////////
0042     // tail_range
0043     /// INTERNAL ONLY
0044     ///
0045     template<typename ElementIterator, typename IndexIterator>
0046     struct tail_range
0047     {
0048         typedef boost::iterator_range<
0049             boost::reverse_iterator<boost::permutation_iterator<ElementIterator, IndexIterator> >
0050         > type;
0051     };
0052
0053     ///////////////////////////////////////////////////////////////////////////////
0054     // make_tail_range
0055     /// INTERNAL ONLY
0056     ///
0057     template<typename ElementIterator, typename IndexIterator>
0058     typename tail_range<ElementIterator, IndexIterator>::type
0059     make_tail_range(ElementIterator elem_begin, IndexIterator index_begin, IndexIterator index_end)
0060     {
0061         return boost::make_iterator_range(
0062             boost::make_reverse_iterator(
0063                 boost::make_permutation_iterator(elem_begin, index_end)
0064             )
0065           , boost::make_reverse_iterator(
0066                 boost::make_permutation_iterator(elem_begin, index_begin)
0067             )
0068         );
0069     }
0070
0071     ///////////////////////////////////////////////////////////////////////////////
0072     // stat_assign_visitor
0073     /// INTERNAL ONLY
0074     ///
0075     template<typename Args>
0076     struct stat_assign_visitor
0077     {
0078         stat_assign_visitor(Args const &a, std::size_t i)
0079           : args(a)
0080           , index(i)
0081         {
0082         }
0083
0084         template<typename Stat>
0085         void operator ()(Stat &stat) const
0086         {
0087             stat.assign(this->args, this->index);
0088         }
0089
0090     private:
0091         BOOST_DELETED_FUNCTION(stat_assign_visitor &operator =(stat_assign_visitor const &))
0092         Args const &args;
0093         std::size_t index;
0094     };
0095
0096     ///////////////////////////////////////////////////////////////////////////////
0097     // stat_assign
0098     /// INTERNAL ONLY
0099     ///
0100     template<typename Args>
0101     inline stat_assign_visitor<Args> const stat_assign(Args const &args, std::size_t index)
0102     {
0103         return stat_assign_visitor<Args>(args, index);
0104     }
0105
0106     ///////////////////////////////////////////////////////////////////////////////
0107     // is_tail_variate_feature
0108     /// INTERNAL ONLY
0109     ///
0110     template<typename Stat, typename LeftRight>
0111     struct is_tail_variate_feature
0112       : mpl::false_
0113     {
0114     };
0115
0116     /// INTERNAL ONLY
0117     ///
0118     template<typename VariateType, typename VariateTag, typename LeftRight>
0119     struct is_tail_variate_feature<tag::tail_variate<VariateType, VariateTag, LeftRight>, LeftRight>
0120       : mpl::true_
0121     {
0122     };
0123
0124     /// INTERNAL ONLY
0125     ///
0126     template<typename LeftRight>
0127     struct is_tail_variate_feature<tag::tail_weights<LeftRight>, LeftRight>
0128       : mpl::true_
0129     {
0130     };
0131
0132 } // namespace detail
0133
0134 namespace impl
0135 {
0136     ///////////////////////////////////////////////////////////////////////////////
0137     // tail_impl
0138     template<typename Sample, typename LeftRight>
0139     struct tail_impl
0140       : accumulator_base
0141     {
0142         // LeftRight must be either right or left
0143         BOOST_MPL_ASSERT((
0144             mpl::or_<is_same<LeftRight, right>, is_same<LeftRight, left> >
0145         ));
0146
0147         typedef
0148             typename mpl::if_<
0149                 is_same<LeftRight, right>
0150               , numeric::functional::greater<Sample const, Sample const>
0151               , numeric::functional::less<Sample const, Sample const>
0152             >::type
0153         predicate_type;
0154
0155         // for boost::result_of
0156         typedef typename detail::tail_range<
0157             typename std::vector<Sample>::const_iterator
0158           , std::vector<std::size_t>::iterator
0159         >::type result_type;
0160
0161         template<typename Args>
0162         tail_impl(Args const &args)
0163           : is_sorted(false)
0164           , indices()
0165           , samples(args[tag::tail<LeftRight>::cache_size], args[sample | Sample()])
0166         {
0167             this->indices.reserve(this->samples.size());
0168         }
0169
0170         tail_impl(tail_impl const &that)
0171           : is_sorted(that.is_sorted)
0172           , indices(that.indices)
0173           , samples(that.samples)
0174         {
0175             this->indices.reserve(this->samples.size());
0176         }
0177
0178         // This just stores the heap and the samples.
0179         // In operator()() below, if we are adding a new sample
0180         // to the sample cache, we force all the
0181         // tail_variates to update also. (It's not
0182         // good enough to wait for the accumulator_set to do it
0183         // for us because then information about whether a sample
0184         // was stored and where is lost, and would need to be
0185         // queried at runtime, which would be slow.) This is
0186         // implemented as a filtered visitation over the stats,
0187         // which we can access because args[accumulator] gives us
0188         // all the stats.
0189
0190         template<typename Args>
0191         void operator ()(Args const &args)
0192         {
0193             if(this->indices.size() < this->samples.size())
0194             {
0195                 this->indices.push_back(this->indices.size());
0196                 this->assign(args, this->indices.back());
0197             }
0198             else if(predicate_type()(args[sample], this->samples[this->indices[0]]))
0199             {
0200                 std::pop_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples));
0201                 this->assign(args, this->indices.back());
0202             }
0203         }
0204
0205         result_type result(dont_care) const
0206         {
0207             if(!this->is_sorted)
0208             {
0209                 // Must use the same predicate here as in push_heap/pop_heap above.
0210                 std::sort_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples));
0211                 // sort_heap puts elements in reverse order. Calling std::reverse
0212                 // turns the sorted sequence back into a valid heap.
0213                 std::reverse(this->indices.begin(), this->indices.end());
0214                 this->is_sorted = true;
0215             }
0216
0217             return detail::make_tail_range(
0218                 this->samples.begin()
0219               , this->indices.begin()
0220               , this->indices.end()
0221             );
0222         }
0223
0224     private:
0225
0226         struct is_tail_variate
0227         {
0228             template<typename T>
0229             struct apply
0230               : detail::is_tail_variate_feature<
0231                     typename detail::feature_tag<T>::type
0232                   , LeftRight
0233                 >
0234             {};
0235         };
0236
0237         template<typename Args>
0238         void assign(Args const &args, std::size_t index)
0239         {
0240             BOOST_ASSERT(index < this->samples.size());
0241             this->samples[index] = args[sample];
0242             std::push_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples));
0243             this->is_sorted = false;
0244             // Tell the tail variates to store their values also
0245             args[accumulator].template visit_if<is_tail_variate>(detail::stat_assign(args, index));
0246         }
0247
0248         ///////////////////////////////////////////////////////////////////////////////
0249         //
0250         struct indirect_cmp
0251         {
0252             typedef std::size_t first_argument_type;
0253             typedef std::size_t second_argument_type;
0254             typedef bool result_type;
0255
0256             indirect_cmp(std::vector<Sample> const &s)
0257               : samples(s)
0258             {
0259             }
0260
0261             bool operator ()(std::size_t left, std::size_t right) const
0262             {
0263                 return predicate_type()(this->samples[left], this->samples[right]);
0264             }
0265
0266         private:
0267             BOOST_DELETED_FUNCTION(indirect_cmp &operator =(indirect_cmp const &))
0268             std::vector<Sample> const &samples;
0269         };
0270
0271     public:
0272         // make this accumulator serializeable
0273         template<class Archive>
0274         void serialize(Archive & ar, const unsigned int file_version)
0275         {
0276             ar & is_sorted;
0277             ar & indices;
0278             ar & samples;
0279         }
0280
0281     private:
0282         mutable bool is_sorted;
0283         mutable std::vector<std::size_t> indices;
0284         std::vector<Sample> samples;
0285     };
0286
0287 } // namespace impl
0288
0289 // TODO The templatized tag::tail below should inherit from the correct named parameter.
0290 // The following lines provide a workaround, but there must be a better way of doing this.
0291 template<typename T>
0292 struct tail_cache_size_named_arg
0293 {
0294 };
0295 template<>
0296 struct tail_cache_size_named_arg<left>
0297   : tag::left_tail_cache_size
0298 {
0299 };
0300 template<>
0301 struct tail_cache_size_named_arg<right>
0302   : tag::right_tail_cache_size
0303 {
0304 };
0305
0306 ///////////////////////////////////////////////////////////////////////////////
0307 // tag::tail<>
0308 //
0309 namespace tag
0310 {
0311     template<typename LeftRight>
0312     struct tail
0313       : depends_on<>
0314       , tail_cache_size_named_arg<LeftRight>
0315     {
0316         /// INTERNAL ONLY
0317         ///
0318         typedef accumulators::impl::tail_impl<mpl::_1, LeftRight> impl;
0319
0320         #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED
0321         /// tag::tail<LeftRight>::cache_size named parameter
0322         static boost::parameter::keyword<tail_cache_size_named_arg<LeftRight> > const cache_size;
0323         #endif
0324     };
0325
0326     struct abstract_tail
0327       : depends_on<>
0328     {
0329     };
0330 }
0331
0332 ///////////////////////////////////////////////////////////////////////////////
0333 // extract::tail
0334 //
0335 namespace extract
0336 {
0337     extractor<tag::abstract_tail> const tail = {};
0338
0339     BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail)
0340 }
0341
0342 using extract::tail;
0343
0344 template<typename LeftRight>
0345 struct feature_of<tag::tail<LeftRight> >
0346   : feature_of<tag::abstract_tail>
0347 {
0348 };
0349
0350 }} // namespace boost::accumulators
0351
0352 #endif