1 /////////////////////////////////////////////////////////////////////////////// 2 // tail.hpp 3 // 4 // Copyright 2005 Eric Niebler, Michael Gauckler. 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_HPP_EAN_28_10_2005 9 #define BOOST_ACCUMULATORS_STATISTICS_TAIL_HPP_EAN_28_10_2005 10 11 #include <vector> 12 #include <functional> 13 #include <boost/assert.hpp> 14 #include <boost/range.hpp> 15 #include <boost/mpl/if.hpp> 16 #include <boost/mpl/or.hpp> 17 #include <boost/mpl/placeholders.hpp> 18 #include <boost/parameter/keyword.hpp> 19 #include <boost/iterator/reverse_iterator.hpp> 20 #include <boost/iterator/permutation_iterator.hpp> 21 #include <boost/accumulators/accumulators_fwd.hpp> 22 #include <boost/accumulators/framework/accumulator_base.hpp> 23 #include <boost/accumulators/framework/extractor.hpp> 24 #include <boost/accumulators/numeric/functional.hpp> 25 #include <boost/accumulators/framework/parameters/sample.hpp> 26 #include <boost/accumulators/framework/depends_on.hpp> 27 #include <boost/accumulators/statistics_fwd.hpp> 28 29 namespace boost { namespace accumulators 30 { 31 /////////////////////////////////////////////////////////////////////////////// 32 // cache_size named parameters 33 BOOST_PARAMETER_NESTED_KEYWORD(tag, right_tail_cache_size, cache_size) 34 BOOST_PARAMETER_NESTED_KEYWORD(tag, left_tail_cache_size, cache_size) 35 36 BOOST_ACCUMULATORS_IGNORE_GLOBAL(right_tail_cache_size) 37 BOOST_ACCUMULATORS_IGNORE_GLOBAL(left_tail_cache_size) 38 39 namespace detail 40 { 41 /////////////////////////////////////////////////////////////////////////////// 42 // tail_range 43 /// INTERNAL ONLY 44 /// 45 template<typename ElementIterator, typename IndexIterator> 46 struct tail_range 47 { 48 typedef boost::iterator_range< 49 boost::reverse_iterator<boost::permutation_iterator<ElementIterator, IndexIterator> > 50 > type; 51 }; 52 53 /////////////////////////////////////////////////////////////////////////////// 54 // make_tail_range 55 /// INTERNAL ONLY 56 /// 57 template<typename ElementIterator, typename IndexIterator> 58 typename tail_range<ElementIterator, IndexIterator>::type make_tail_range(ElementIterator elem_begin,IndexIterator index_begin,IndexIterator index_end)59 make_tail_range(ElementIterator elem_begin, IndexIterator index_begin, IndexIterator index_end) 60 { 61 return boost::make_iterator_range( 62 boost::make_reverse_iterator( 63 boost::make_permutation_iterator(elem_begin, index_end) 64 ) 65 , boost::make_reverse_iterator( 66 boost::make_permutation_iterator(elem_begin, index_begin) 67 ) 68 ); 69 } 70 71 /////////////////////////////////////////////////////////////////////////////// 72 // stat_assign_visitor 73 /// INTERNAL ONLY 74 /// 75 template<typename Args> 76 struct stat_assign_visitor 77 { stat_assign_visitorboost::accumulators::detail::stat_assign_visitor78 stat_assign_visitor(Args const &a, std::size_t i) 79 : args(a) 80 , index(i) 81 { 82 } 83 84 template<typename Stat> operator ()boost::accumulators::detail::stat_assign_visitor85 void operator ()(Stat &stat) const 86 { 87 stat.assign(this->args, this->index); 88 } 89 90 private: 91 stat_assign_visitor &operator =(stat_assign_visitor const &); 92 Args const &args; 93 std::size_t index; 94 }; 95 96 /////////////////////////////////////////////////////////////////////////////// 97 // stat_assign 98 /// INTERNAL ONLY 99 /// 100 template<typename Args> stat_assign(Args const & args,std::size_t index)101 inline stat_assign_visitor<Args> const stat_assign(Args const &args, std::size_t index) 102 { 103 return stat_assign_visitor<Args>(args, index); 104 } 105 106 /////////////////////////////////////////////////////////////////////////////// 107 // is_tail_variate_feature 108 /// INTERNAL ONLY 109 /// 110 template<typename Stat, typename LeftRight> 111 struct is_tail_variate_feature 112 : mpl::false_ 113 { 114 }; 115 116 /// INTERNAL ONLY 117 /// 118 template<typename VariateType, typename VariateTag, typename LeftRight> 119 struct is_tail_variate_feature<tag::tail_variate<VariateType, VariateTag, LeftRight>, LeftRight> 120 : mpl::true_ 121 { 122 }; 123 124 /// INTERNAL ONLY 125 /// 126 template<typename LeftRight> 127 struct is_tail_variate_feature<tag::tail_weights<LeftRight>, LeftRight> 128 : mpl::true_ 129 { 130 }; 131 132 } // namespace detail 133 134 namespace impl 135 { 136 /////////////////////////////////////////////////////////////////////////////// 137 // tail_impl 138 template<typename Sample, typename LeftRight> 139 struct tail_impl 140 : accumulator_base 141 { 142 // LeftRight must be either right or left 143 BOOST_MPL_ASSERT(( 144 mpl::or_<is_same<LeftRight, right>, is_same<LeftRight, left> > 145 )); 146 147 typedef 148 typename mpl::if_< 149 is_same<LeftRight, right> 150 , numeric::functional::greater<Sample const, Sample const> 151 , numeric::functional::less<Sample const, Sample const> 152 >::type 153 predicate_type; 154 155 // for boost::result_of 156 typedef typename detail::tail_range< 157 typename std::vector<Sample>::const_iterator 158 , std::vector<std::size_t>::iterator 159 >::type result_type; 160 161 template<typename Args> tail_implboost::accumulators::impl::tail_impl162 tail_impl(Args const &args) 163 : is_sorted(false) 164 , indices() 165 , samples(args[tag::tail<LeftRight>::cache_size], args[sample | Sample()]) 166 { 167 this->indices.reserve(this->samples.size()); 168 } 169 tail_implboost::accumulators::impl::tail_impl170 tail_impl(tail_impl const &that) 171 : is_sorted(that.is_sorted) 172 , indices(that.indices) 173 , samples(that.samples) 174 { 175 this->indices.reserve(this->samples.size()); 176 } 177 178 // This just stores the heap and the samples. 179 // In operator()() below, if we are adding a new sample 180 // to the sample cache, we force all the 181 // tail_variates to update also. (It's not 182 // good enough to wait for the accumulator_set to do it 183 // for us because then information about whether a sample 184 // was stored and where is lost, and would need to be 185 // queried at runtime, which would be slow.) This is 186 // implemented as a filtered visitation over the stats, 187 // which we can access because args[accumulator] gives us 188 // all the stats. 189 190 template<typename Args> operator ()boost::accumulators::impl::tail_impl191 void operator ()(Args const &args) 192 { 193 if(this->indices.size() < this->samples.size()) 194 { 195 this->indices.push_back(this->indices.size()); 196 this->assign(args, this->indices.back()); 197 } 198 else if(predicate_type()(args[sample], this->samples[this->indices[0]])) 199 { 200 std::pop_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples)); 201 this->assign(args, this->indices.back()); 202 } 203 } 204 resultboost::accumulators::impl::tail_impl205 result_type result(dont_care) const 206 { 207 if(!this->is_sorted) 208 { 209 // Must use the same predicate here as in push_heap/pop_heap above. 210 std::sort_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples)); 211 // sort_heap puts elements in reverse order. Calling std::reverse 212 // turns the sorted sequence back into a valid heap. 213 std::reverse(this->indices.begin(), this->indices.end()); 214 this->is_sorted = true; 215 } 216 217 return detail::make_tail_range( 218 this->samples.begin() 219 , this->indices.begin() 220 , this->indices.end() 221 ); 222 } 223 224 private: 225 226 struct is_tail_variate 227 { 228 template<typename T> 229 struct apply 230 : detail::is_tail_variate_feature< 231 typename detail::feature_tag<T>::type 232 , LeftRight 233 > 234 {}; 235 }; 236 237 template<typename Args> assignboost::accumulators::impl::tail_impl238 void assign(Args const &args, std::size_t index) 239 { 240 BOOST_ASSERT(index < this->samples.size()); 241 this->samples[index] = args[sample]; 242 std::push_heap(this->indices.begin(), this->indices.end(), indirect_cmp(this->samples)); 243 this->is_sorted = false; 244 // Tell the tail variates to store their values also 245 args[accumulator].template visit_if<is_tail_variate>(detail::stat_assign(args, index)); 246 } 247 248 /////////////////////////////////////////////////////////////////////////////// 249 // 250 struct indirect_cmp 251 { 252 typedef std::size_t first_argument_type; 253 typedef std::size_t second_argument_type; 254 typedef bool result_type; 255 indirect_cmpboost::accumulators::impl::tail_impl::indirect_cmp256 indirect_cmp(std::vector<Sample> const &s) 257 : samples(s) 258 { 259 } 260 operator ()boost::accumulators::impl::tail_impl::indirect_cmp261 bool operator ()(std::size_t left, std::size_t right) const 262 { 263 return predicate_type()(this->samples[left], this->samples[right]); 264 } 265 266 private: 267 indirect_cmp &operator =(indirect_cmp const &); 268 std::vector<Sample> const &samples; 269 }; 270 271 public: 272 // make this accumulator serializeable 273 template<class Archive> serializeboost::accumulators::impl::tail_impl274 void serialize(Archive & ar, const unsigned int file_version) 275 { 276 ar & is_sorted; 277 ar & indices; 278 ar & samples; 279 } 280 281 private: 282 mutable bool is_sorted; 283 mutable std::vector<std::size_t> indices; 284 std::vector<Sample> samples; 285 }; 286 287 } // namespace impl 288 289 // TODO The templatized tag::tail below should inherit from the correct named parameter. 290 // The following lines provide a workaround, but there must be a better way of doing this. 291 template<typename T> 292 struct tail_cache_size_named_arg 293 { 294 }; 295 template<> 296 struct tail_cache_size_named_arg<left> 297 : tag::left_tail_cache_size 298 { 299 }; 300 template<> 301 struct tail_cache_size_named_arg<right> 302 : tag::right_tail_cache_size 303 { 304 }; 305 306 /////////////////////////////////////////////////////////////////////////////// 307 // tag::tail<> 308 // 309 namespace tag 310 { 311 template<typename LeftRight> 312 struct tail 313 : depends_on<> 314 , tail_cache_size_named_arg<LeftRight> 315 { 316 /// INTERNAL ONLY 317 /// 318 typedef accumulators::impl::tail_impl<mpl::_1, LeftRight> impl; 319 320 #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED 321 /// tag::tail<LeftRight>::cache_size named parameter 322 static boost::parameter::keyword<tail_cache_size_named_arg<LeftRight> > const cache_size; 323 #endif 324 }; 325 326 struct abstract_tail 327 : depends_on<> 328 { 329 }; 330 } 331 332 /////////////////////////////////////////////////////////////////////////////// 333 // extract::tail 334 // 335 namespace extract 336 { 337 extractor<tag::abstract_tail> const tail = {}; 338 339 BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail) 340 } 341 342 using extract::tail; 343 344 template<typename LeftRight> 345 struct feature_of<tag::tail<LeftRight> > 346 : feature_of<tag::abstract_tail> 347 { 348 }; 349 350 }} // namespace boost::accumulators 351 352 #endif 353