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

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

Adding \since tag for new classes and functions

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