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

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

fixed compilation error

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.1 KB
Line 
1#ifndef _theplu_yat_statistics_percentiler_
2#define _theplu_yat_statistics_percentiler_
3
4// $Id: Percentiler.h 1318 2008-05-21 15:25:59Z 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 <cassert>
31#include <cmath>
32#include <vector>
33
34namespace theplu {
35namespace yat {
36namespace statistics { 
37
38  /**
39     \brief Functor to calculate percentile of a range
40   */
41  class Percentiler
42  {
43  public:
44    /**
45       \param perc percentile to calculate [0,100]. Defaule value is
46       50, which implies class will calculate median.
47       \param sorted if true class assues that ranges are already
48       sorted, if false the range will copied to a new range which is
49       sorted.
50     */
51    Percentiler(double perc=50, bool sorted=false);
52
53    /**
54       The percentile is found by interpolation, using the formula \f$
55       percentile = (1 - \delta) x_i + \delta x_{i+1} \f$ where \a p
56       is floor\f$((n - 1)p/100)\f$ and \f$ \delta \f$ is \f$
57       (n-1)p/100 - i \f$. Thus the minimum value of the range is
58       given by perc equal to zero, the maximum is given by perc equal
59       to 100 and the median value is given by perc equal to 50.
60
61       Function is a non-mutable function, i.e., \a first and \a last
62       can be const_iterators.
63
64       \return percentile of range
65     */
66    template<typename ForwardIterator>
67    inline double operator()(ForwardIterator first, ForwardIterator last) const
68    {
69      return calculate(first, last, sorted_, 
70            typename utility::weighted_iterator_traits<ForwardIterator>::type());
71    }
72  private:
73    double perc_;
74    bool sorted_;
75
76    // unweighted version
77    template<typename ForwardIterator>
78    double calculate(ForwardIterator first, ForwardIterator last,
79                     bool sorted, utility::unweighted_iterator_tag tag) const;
80
81    // weighted version
82    template<typename ForwardIterator>
83    double calculate(ForwardIterator first, ForwardIterator last,
84                     bool sorted, utility::weighted_iterator_tag tag) const;
85
86    // using compiler generated copy
87    //Percentiler(const Percentiler&);
88    //Percentiler& operator=(const Percentiler&);
89
90  };
91
92  // template implementations
93  // /////////////////////////
94
95  // unweighted version
96  template<typename ForwardIterator>
97  double Percentiler::calculate(ForwardIterator first, ForwardIterator last,
98                                bool sorted, 
99                                utility::unweighted_iterator_tag tag) const
100  {
101    if (sorted){
102      if (perc_>=100)
103        return *(--last);
104      // range is one value only is a special case
105      if (first+1 == last)
106        return *first;
107      double j = perc_/100 * (std::distance(first,last)-1);
108      int i = static_cast<int>(j);
109      return (1-j+floor(j))*first[i] + (j-floor(j))*first[i+1];
110    }
111
112    std::vector<double> v_copy;
113    v_copy.reserve(std::distance(first,last));
114    std::copy(first, last, std::back_inserter(v_copy));
115    size_t i = static_cast<size_t>(perc_/100 * (v_copy.size()-1));
116    if (i+2 < v_copy.size()) {
117      std::partial_sort(v_copy.begin(), v_copy.begin()+i+2, v_copy.end());
118    }
119    else
120      std::sort(v_copy.begin(), v_copy.end());
121    return calculate(v_copy.begin(), v_copy.end(), true, tag);
122  }
123 
124  // weighted version
125  template<typename ForwardIterator>
126  double Percentiler::calculate(ForwardIterator first, ForwardIterator last,
127                                bool sorted, 
128                                utility::weighted_iterator_tag tag) const
129  {
130    assert(false && "not implemented");
131    return 0;
132  }
133
134
135}}} // of namespace statistics, yat, and theplu
136
137#endif
Note: See TracBrowser for help on using the repository browser.