source: trunk/yat/statistics/Percentiler.h @ 1317

Last change on this file since 1317 was 1317, checked in by Peter, 13 years ago

moving implementation of percentile to a functor: Percentiler

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.0 KB
Line 
1#ifndef _theplu_yat_statistics_percentiler_
2#define _theplu_yat_statistics_percentiler_
3
4// $Id: Percentiler.h 1317 2008-05-21 12:23:18Z peter $
5
6/*
7  Copyright (C) 2008 Peter Johansson
8
9  This file is part of the yat library, http://trac.thep.lu.se/yat
10
11  The yat library is free software; you can redistribute it and/or
12  modify it under the terms of the GNU General Public License as
13  published by the Free Software Foundation; either version 2 of the
14  License, or (at your option) any later version.
15
16  The yat library is distributed in the hope that it will be useful,
17  but WITHOUT ANY WARRANTY; without even the implied warranty of
18  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19  General Public License for more details.
20
21  You should have received a copy of the GNU General Public License
22  along with this program; if not, write to the Free Software
23  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
24  02111-1307, USA.
25*/
26
27#include "yat/utility/iterator_traits.h"
28
29#include <algorithm>
30#include <cmath>
31#include <vector>
32
33namespace theplu {
34namespace yat {
35namespace statistics { 
36
37  /**
38     \brief Functor to calculate percentile of a range
39   */
40  class Percentiler
41  {
42  public:
43    /**
44       \param perc percentile to calculate [0,100]. Defaule value is
45       50, which implies class will calculate median.
46       \param sorted if true class assues that ranges are already
47       sorted, if false the range will copied to a new range which is
48       sorted.
49     */
50    Percentiler(double perc=50, bool sorted=false);
51
52    /**
53       The percentile is found by interpolation, using the formula \f$
54       percentile = (1 - \delta) x_i + \delta x_{i+1} \f$ where \a p
55       is floor\f$((n - 1)p/100)\f$ and \f$ \delta \f$ is \f$
56       (n-1)p/100 - i \f$. Thus the minimum value of the range is
57       given by perc equal to zero, the maximum is given by perc equal
58       to 100 and the median value is given by perc equal to 50.
59
60       Function is a non-mutable function, i.e., \a first and \a last
61       can be const_iterators.
62
63       \return percentile of range
64     */
65    template<typename ForwardIterator>
66    inline double operator()(ForwardIterator first, ForwardIterator last) const
67    {
68      return calculate(first, last, sorted_, 
69            typename utility::weighted_iterator_traits<ForwardIterator>::type());
70    }
71  private:
72    double perc_;
73    bool sorted_;
74
75    // unweighted version
76    template<typename ForwardIterator>
77    double calculate(ForwardIterator first, ForwardIterator last,
78                     bool sorted, utility::unweighted_iterator_tag tag) const;
79
80    // weighted version
81    template<typename ForwardIterator>
82    double calculate(ForwardIterator first, ForwardIterator last,
83                     bool sorted, utility::weighted_iterator_tag tag) const;
84
85    // using compiler generated copy
86    //Percentiler(const Percentiler&);
87    //Percentiler& operator=(const Percentiler&);
88
89  };
90
91  // template implementations
92  // /////////////////////////
93
94  // unweighted version
95  template<typename ForwardIterator>
96  double Percentiler::calculate(ForwardIterator first, ForwardIterator last,
97                                bool sorted, 
98                                utility::unweighted_iterator_tag tag) const
99  {
100    if (sorted){
101      if (perc_>=100)
102        return *(--last);
103      // range is one value only is a special case
104      if (first+1 == last)
105        return *first;
106      double j = perc_/100 * (std::distance(first,last)-1);
107      int i = static_cast<int>(j);
108      return (1-j+floor(j))*first[i] + (j-floor(j))*first[i+1];
109    }
110
111    std::vector<double> v_copy;
112    v_copy.reserve(std::distance(first,last));
113    std::copy(first, last, std::back_inserter(v_copy));
114    size_t i = static_cast<size_t>(perc_/100 * (v_copy.size()-1));
115    if (i+2 < v_copy.size()) {
116      std::partial_sort(v_copy.begin(), v_copy.begin()+i+2, v_copy.end());
117    }
118    else
119      std::sort(v_copy.begin(), v_copy.end());
120    return calculate(v_copy.begin(), v_copy.end(), true, tag);
121  }
122 
123  // weighted version
124  template<typename ForwardIterator>
125  double Percentiler::calculate(ForwardIterator first, ForwardIterator last,
126                                bool sorted, 
127                                utility::weighted_iterator_tag tag) const
128  {
129    assert(false && "not implemented");
130  }
131
132
133}}} // of namespace statistics, yat, and theplu
134
135#endif
Note: See TracBrowser for help on using the repository browser.