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
///////////////////////////////////////////////////////////////////////////////
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
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
    {
78
        stat_assign_visitor(Args const &a, std::size_t i)
79
          : args(a)
80
          , index(i)
81
        {
82
        }
83

    
84
        template<typename Stat>
85
        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>
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>
162
        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

    
170
        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>
191
        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

    
205
        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>
238
        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
          : std::binary_function<std::size_t, std::size_t, bool>
252
        {
253
            indirect_cmp(std::vector<Sample> const &s)
254
              : samples(s)
255
            {
256
            }
257

    
258
            bool operator ()(std::size_t left, std::size_t right) const
259
            {
260
                return predicate_type()(this->samples[left], this->samples[right]);
261
            }
262

    
263
        private:
264
            indirect_cmp &operator =(indirect_cmp const &);
265
            std::vector<Sample> const &samples;
266
        };
267

    
268
        mutable bool is_sorted;
269
        mutable std::vector<std::size_t> indices;
270
        std::vector<Sample> samples;
271
    };
272

    
273
} // namespace impl
274

    
275
// TODO The templatized tag::tail below should inherit from the correct named parameter.
276
// The following lines provide a workaround, but there must be a better way of doing this.
277
template<typename T>
278
struct tail_cache_size_named_arg
279
{
280
};
281
template<>
282
struct tail_cache_size_named_arg<left>
283
  : tag::left_tail_cache_size
284
{
285
};
286
template<>
287
struct tail_cache_size_named_arg<right>
288
  : tag::right_tail_cache_size
289
{
290
};
291

    
292
///////////////////////////////////////////////////////////////////////////////
293
// tag::tail<>
294
//
295
namespace tag
296
{
297
    template<typename LeftRight>
298
    struct tail
299
      : depends_on<>
300
      , tail_cache_size_named_arg<LeftRight>
301
    {
302
        /// INTERNAL ONLY
303
        ///
304
        typedef accumulators::impl::tail_impl<mpl::_1, LeftRight> impl;
305

    
306
        #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED
307
        /// tag::tail<LeftRight>::cache_size named parameter
308
        static boost::parameter::keyword<tail_cache_size_named_arg<LeftRight> > const cache_size;
309
        #endif
310
    };
311

    
312
    struct abstract_tail
313
      : depends_on<>
314
    {
315
    };
316
}
317

    
318
///////////////////////////////////////////////////////////////////////////////
319
// extract::tail
320
//
321
namespace extract
322
{
323
    extractor<tag::abstract_tail> const tail = {};
324

    
325
    BOOST_ACCUMULATORS_IGNORE_GLOBAL(tail)
326
}
327

    
328
using extract::tail;
329

    
330
template<typename LeftRight>
331
struct feature_of<tag::tail<LeftRight> >
332
  : feature_of<tag::abstract_tail>
333
{
334
};
335

    
336
}} // namespace boost::accumulators
337

    
338
#endif