Statistics
| Revision:

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

History | View | Annotate | Download (9.4 kB)

1
///////////////////////////////////////////////////////////////////////////////
2
// median.hpp
3
//
4
//  Copyright 2006 Eric Niebler, 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_MEDIAN_HPP_EAN_28_10_2005
9
#define BOOST_ACCUMULATORS_STATISTICS_MEDIAN_HPP_EAN_28_10_2005
10

    
11
#include <boost/mpl/placeholders.hpp>
12
#include <boost/range/iterator_range.hpp>
13
#include <boost/accumulators/framework/accumulator_base.hpp>
14
#include <boost/accumulators/framework/extractor.hpp>
15
#include <boost/accumulators/numeric/functional.hpp>
16
#include <boost/accumulators/framework/parameters/sample.hpp>
17
#include <boost/accumulators/framework/depends_on.hpp>
18
#include <boost/accumulators/statistics_fwd.hpp>
19
#include <boost/accumulators/statistics/count.hpp>
20
#include <boost/accumulators/statistics/p_square_quantile.hpp>
21
#include <boost/accumulators/statistics/density.hpp>
22
#include <boost/accumulators/statistics/p_square_cumul_dist.hpp>
23

    
24
namespace boost { namespace accumulators
25
{
26

    
27
namespace impl
28
{
29
    ///////////////////////////////////////////////////////////////////////////////
30
    // median_impl
31
    //
32
    /**
33
        @brief Median estimation based on the \f$P^2\f$ quantile estimator
34

35
        The \f$P^2\f$ algorithm is invoked with a quantile probability of 0.5.
36
    */
37
    template<typename Sample>
38
    struct median_impl
39
      : accumulator_base
40
    {
41
        // for boost::result_of
42
        typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type result_type;
43

    
44
        median_impl(dont_care) {}
45

    
46
        template<typename Args>
47
        result_type result(Args const &args) const
48
        {
49
            return p_square_quantile_for_median(args);
50
        }
51
    };
52
    ///////////////////////////////////////////////////////////////////////////////
53
    // with_density_median_impl
54
    //
55
    /**
56
        @brief Median estimation based on the density estimator
57

58
        The algorithm determines the bin in which the \f$0.5*cnt\f$-th sample lies, \f$cnt\f$ being
59
        the total number of samples. It returns the approximate horizontal position of this sample,
60
        based on a linear interpolation inside the bin.
61
    */
62
    template<typename Sample>
63
    struct with_density_median_impl
64
      : accumulator_base
65
    {
66
        typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
67
        typedef std::vector<std::pair<float_type, float_type> > histogram_type;
68
        typedef iterator_range<typename histogram_type::iterator> range_type;
69
        // for boost::result_of
70
        typedef float_type result_type;
71

    
72
        template<typename Args>
73
        with_density_median_impl(Args const &args)
74
          : sum(numeric::fdiv(args[sample | Sample()], (std::size_t)1))
75
          , is_dirty(true)
76
        {
77
        }
78

    
79
        void operator ()(dont_care)
80
        {
81
            this->is_dirty = true;
82
        }
83

    
84

    
85
        template<typename Args>
86
        result_type result(Args const &args) const
87
        {
88
            if (this->is_dirty)
89
            {
90
                this->is_dirty = false;
91

    
92
                std::size_t cnt = count(args);
93
                range_type histogram = density(args);
94
                typename range_type::iterator it = histogram.begin();
95
                while (this->sum < 0.5 * cnt)
96
                {
97
                    this->sum += it->second * cnt;
98
                    ++it;
99
                }
100
                --it;
101
                float_type over = numeric::fdiv(this->sum - 0.5 * cnt, it->second * cnt);
102
                this->median = it->first * over + (it + 1)->first * (1. - over);
103
            }
104

    
105
            return this->median;
106
        }
107

    
108
    private:
109
        mutable float_type sum;
110
        mutable bool is_dirty;
111
        mutable float_type median;
112
    };
113

    
114
    ///////////////////////////////////////////////////////////////////////////////
115
    // with_p_square_cumulative_distribution_median_impl
116
    //
117
    /**
118
        @brief Median estimation based on the \f$P^2\f$ cumulative distribution estimator
119

120
        The algorithm determines the first (leftmost) bin with a height exceeding 0.5. It
121
        returns the approximate horizontal position of where the cumulative distribution
122
        equals 0.5, based on a linear interpolation inside the bin.
123
    */
124
    template<typename Sample>
125
    struct with_p_square_cumulative_distribution_median_impl
126
      : accumulator_base
127
    {
128
        typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
129
        typedef std::vector<std::pair<float_type, float_type> > histogram_type;
130
        typedef iterator_range<typename histogram_type::iterator> range_type;
131
        // for boost::result_of
132
        typedef float_type result_type;
133

    
134
        with_p_square_cumulative_distribution_median_impl(dont_care)
135
          : is_dirty(true)
136
        {
137
        }
138

    
139
        void operator ()(dont_care)
140
        {
141
            this->is_dirty = true;
142
        }
143

    
144
        template<typename Args>
145
        result_type result(Args const &args) const
146
        {
147
            if (this->is_dirty)
148
            {
149
                this->is_dirty = false;
150

    
151
                range_type histogram = p_square_cumulative_distribution(args);
152
                typename range_type::iterator it = histogram.begin();
153
                while (it->second < 0.5)
154
                {
155
                    ++it;
156
                }
157
                float_type over = numeric::fdiv(it->second - 0.5, it->second - (it - 1)->second);
158
                this->median = it->first * over + (it + 1)->first * ( 1. - over );
159
            }
160

    
161
            return this->median;
162
        }
163
    private:
164

    
165
        mutable bool is_dirty;
166
        mutable float_type median;
167
    };
168

    
169
} // namespace impl
170

    
171
///////////////////////////////////////////////////////////////////////////////
172
// tag::median
173
// tag::with_densisty_median
174
// tag::with_p_square_cumulative_distribution_median
175
//
176
namespace tag
177
{
178
    struct median
179
      : depends_on<p_square_quantile_for_median>
180
    {
181
        /// INTERNAL ONLY
182
        ///
183
        typedef accumulators::impl::median_impl<mpl::_1> impl;
184
    };
185
    struct with_density_median
186
      : depends_on<count, density>
187
    {
188
        /// INTERNAL ONLY
189
        ///
190
        typedef accumulators::impl::with_density_median_impl<mpl::_1> impl;
191
    };
192
    struct with_p_square_cumulative_distribution_median
193
      : depends_on<p_square_cumulative_distribution>
194
    {
195
        /// INTERNAL ONLY
196
        ///
197
        typedef accumulators::impl::with_p_square_cumulative_distribution_median_impl<mpl::_1> impl;
198
    };
199
}
200

    
201
///////////////////////////////////////////////////////////////////////////////
202
// extract::median
203
// extract::with_density_median
204
// extract::with_p_square_cumulative_distribution_median
205
//
206
namespace extract
207
{
208
    extractor<tag::median> const median = {};
209
    extractor<tag::with_density_median> const with_density_median = {};
210
    extractor<tag::with_p_square_cumulative_distribution_median> const with_p_square_cumulative_distribution_median = {};
211

    
212
    BOOST_ACCUMULATORS_IGNORE_GLOBAL(median)
213
    BOOST_ACCUMULATORS_IGNORE_GLOBAL(with_density_median)
214
    BOOST_ACCUMULATORS_IGNORE_GLOBAL(with_p_square_cumulative_distribution_median)
215
}
216

    
217
using extract::median;
218
using extract::with_density_median;
219
using extract::with_p_square_cumulative_distribution_median;
220

    
221
// median(with_p_square_quantile) -> median
222
template<>
223
struct as_feature<tag::median(with_p_square_quantile)>
224
{
225
    typedef tag::median type;
226
};
227

    
228
// median(with_density) -> with_density_median
229
template<>
230
struct as_feature<tag::median(with_density)>
231
{
232
    typedef tag::with_density_median type;
233
};
234

    
235
// median(with_p_square_cumulative_distribution) -> with_p_square_cumulative_distribution_median
236
template<>
237
struct as_feature<tag::median(with_p_square_cumulative_distribution)>
238
{
239
    typedef tag::with_p_square_cumulative_distribution_median type;
240
};
241

    
242
// for the purposes of feature-based dependency resolution,
243
// with_density_median and with_p_square_cumulative_distribution_median
244
// provide the same feature as median
245
template<>
246
struct feature_of<tag::with_density_median>
247
  : feature_of<tag::median>
248
{
249
};
250

    
251
template<>
252
struct feature_of<tag::with_p_square_cumulative_distribution_median>
253
  : feature_of<tag::median>
254
{
255
};
256

    
257
// So that median can be automatically substituted with
258
// weighted_median when the weight parameter is non-void.
259
template<>
260
struct as_weighted_feature<tag::median>
261
{
262
    typedef tag::weighted_median type;
263
};
264

    
265
template<>
266
struct feature_of<tag::weighted_median>
267
  : feature_of<tag::median>
268
{
269
};
270

    
271
// So that with_density_median can be automatically substituted with
272
// with_density_weighted_median when the weight parameter is non-void.
273
template<>
274
struct as_weighted_feature<tag::with_density_median>
275
{
276
    typedef tag::with_density_weighted_median type;
277
};
278

    
279
template<>
280
struct feature_of<tag::with_density_weighted_median>
281
  : feature_of<tag::with_density_median>
282
{
283
};
284

    
285
// So that with_p_square_cumulative_distribution_median can be automatically substituted with
286
// with_p_square_cumulative_distribution_weighted_median when the weight parameter is non-void.
287
template<>
288
struct as_weighted_feature<tag::with_p_square_cumulative_distribution_median>
289
{
290
    typedef tag::with_p_square_cumulative_distribution_weighted_median type;
291
};
292

    
293
template<>
294
struct feature_of<tag::with_p_square_cumulative_distribution_weighted_median>
295
  : feature_of<tag::with_p_square_cumulative_distribution_median>
296
{
297
};
298

    
299
}} // namespace boost::accumulators
300

    
301
#endif