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