Statistics
| Revision:

root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / accumulators / statistics / tail.hpp @ 2486

History | View | Annotate | Download (10.4 kB)

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