1 /////////////////////////////////////////////////////////////////////////////// 2 // tail_quantile.hpp 3 // 4 // Copyright 2006 Daniel Egloff, Olivier Gygi. Distributed under the Boost 5 // Software License, Version 1.0. (See accompanying file 6 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 7 8 #ifndef BOOST_ACCUMULATORS_STATISTICS_TAIL_QUANTILE_HPP_DE_01_01_2006 9 #define BOOST_ACCUMULATORS_STATISTICS_TAIL_QUANTILE_HPP_DE_01_01_2006 10 11 #include <vector> 12 #include <limits> 13 #include <functional> 14 #include <sstream> 15 #include <stdexcept> 16 #include <boost/config/no_tr1/cmath.hpp> // For ceil 17 #include <boost/throw_exception.hpp> 18 #include <boost/parameter/keyword.hpp> 19 #include <boost/mpl/placeholders.hpp> 20 #include <boost/mpl/if.hpp> 21 #include <boost/type_traits/is_same.hpp> 22 #include <boost/accumulators/framework/depends_on.hpp> 23 #include <boost/accumulators/framework/accumulator_base.hpp> 24 #include <boost/accumulators/framework/extractor.hpp> 25 #include <boost/accumulators/numeric/functional.hpp> 26 #include <boost/accumulators/framework/parameters/sample.hpp> 27 #include <boost/accumulators/statistics_fwd.hpp> 28 #include <boost/accumulators/statistics/tail.hpp> 29 #include <boost/accumulators/statistics/count.hpp> 30 #include <boost/accumulators/statistics/parameters/quantile_probability.hpp> 31 32 #ifdef _MSC_VER 33 # pragma warning(push) 34 # pragma warning(disable: 4127) // conditional expression is constant 35 #endif 36 37 namespace boost { namespace accumulators 38 { 39 40 namespace impl 41 { 42 /////////////////////////////////////////////////////////////////////////////// 43 // tail_quantile_impl 44 // Tail quantile estimation based on order statistics 45 /** 46 @brief Tail quantile estimation based on order statistics (for both left and right tails) 47 48 The estimation of a tail quantile \f$\hat{q}\f$ with level \f$\alpha\f$ based on order statistics requires the 49 caching of at least the \f$\lceil n\alpha\rceil\f$ smallest or the \f$\lceil n(1-\alpha)\rceil\f$ largest samples, 50 \f$n\f$ being the total number of samples. The largest of the \f$\lceil n\alpha\rceil\f$ smallest samples or the 51 smallest of the \f$\lceil n(1-\alpha)\rceil\f$ largest samples provides an estimate for the quantile: 52 53 \f[ 54 \hat{q}_{n,\alpha} = X_{\lceil \alpha n \rceil:n} 55 \f] 56 57 @param quantile_probability 58 */ 59 template<typename Sample, typename LeftRight> 60 struct tail_quantile_impl 61 : accumulator_base 62 { 63 // for boost::result_of 64 typedef Sample result_type; 65 tail_quantile_implboost::accumulators::impl::tail_quantile_impl66 tail_quantile_impl(dont_care) {} 67 68 template<typename Args> resultboost::accumulators::impl::tail_quantile_impl69 result_type result(Args const &args) const 70 { 71 std::size_t cnt = count(args); 72 73 std::size_t n = static_cast<std::size_t>( 74 std::ceil( 75 cnt * ( ( is_same<LeftRight, left>::value ) ? args[quantile_probability] : 1. - args[quantile_probability] ) 76 ) 77 ); 78 79 // If n is in a valid range, return result, otherwise return NaN or throw exception 80 if ( n < static_cast<std::size_t>(tail(args).size())) 81 { 82 // Note that the cached samples of the left are sorted in ascending order, 83 // whereas the samples of the right tail are sorted in descending order 84 return *(boost::begin(tail(args)) + n - 1); 85 } 86 else 87 { 88 if (std::numeric_limits<result_type>::has_quiet_NaN) 89 { 90 return std::numeric_limits<result_type>::quiet_NaN(); 91 } 92 else 93 { 94 std::ostringstream msg; 95 msg << "index n = " << n << " is not in valid range [0, " << tail(args).size() << ")"; 96 boost::throw_exception(std::runtime_error(msg.str())); 97 return Sample(0); 98 } 99 } 100 } 101 102 // serialization is done by accumulators it depends on 103 template<class Archive> serializeboost::accumulators::impl::tail_quantile_impl104 void serialize(Archive & ar, const unsigned int file_version) {} 105 }; 106 } // namespace impl 107 108 /////////////////////////////////////////////////////////////////////////////// 109 // tag::tail_quantile<> 110 // 111 namespace tag 112 { 113 template<typename LeftRight> 114 struct tail_quantile 115 : depends_on<count, tail<LeftRight> > 116 { 117 /// INTERNAL ONLY 118 /// 119 typedef accumulators::impl::tail_quantile_impl<mpl::_1, LeftRight> impl; 120 }; 121 } 122 123 /////////////////////////////////////////////////////////////////////////////// 124 // extract::tail_quantile 125 // 126 namespace extract 127 { 128 extractor<tag::quantile> const tail_quantile = {}; 129 130 BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail_quantile) 131 } 132 133 using extract::tail_quantile; 134 135 // for the purposes of feature-based dependency resolution, 136 // tail_quantile<LeftRight> provide the same feature as quantile 137 template<typename LeftRight> 138 struct feature_of<tag::tail_quantile<LeftRight> > 139 : feature_of<tag::quantile> 140 { 141 }; 142 143 // So that tail_quantile can be automatically substituted with 144 // weighted_tail_quantile when the weight parameter is non-void. 145 template<typename LeftRight> 146 struct as_weighted_feature<tag::tail_quantile<LeftRight> > 147 { 148 typedef tag::weighted_tail_quantile<LeftRight> type; 149 }; 150 151 template<typename LeftRight> 152 struct feature_of<tag::weighted_tail_quantile<LeftRight> > 153 : feature_of<tag::tail_quantile<LeftRight> > 154 {}; 155 156 }} // namespace boost::accumulators 157 158 #ifdef _MSC_VER 159 # pragma warning(pop) 160 #endif 161 162 #endif 163