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

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

change template name to RandomAccessIterator? to clarify that percentile only works with random access iterators (sice std::sort is used)

  • 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 1323 2008-05-24 00:25:07Z 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 RandomAccessIterator>
67    double operator()(RandomAccessIterator first, 
68                      RandomAccessIterator last) const;
69    /*
70    {
71      return calculate(first, last, sorted_,
72            typename utility::weighted_iterator_traits<RandomAccessIterator>::type());
73    }
74    */
75  private:
76    double perc_;
77    bool sorted_;
78
79    // unweighted version - NOTE range must be sorted
80    template<typename RandomAccessIterator>
81    double calculate(RandomAccessIterator first, RandomAccessIterator last,
82                     utility::unweighted_iterator_tag tag) const;
83
84    // weighted version - NOTE range must be sorted
85    template<typename RandomAccessIterator>
86    double calculate(RandomAccessIterator first, RandomAccessIterator last,
87                     utility::weighted_iterator_tag tag) const;
88
89    // using compiler generated copy
90    //Percentiler(const Percentiler&);
91    //Percentiler& operator=(const Percentiler&);
92
93  };
94
95  // template implementations
96  // /////////////////////////
97
98  // unweighted version
99  template<typename RandomAccessIterator>
100  double Percentiler::operator()(RandomAccessIterator first, 
101                                 RandomAccessIterator last) const
102  {
103    // range is one value only is a special case
104    if (first+1 == last)
105      return *first;
106    // just for convenience
107    typedef 
108      typename utility::weighted_iterator_traits<RandomAccessIterator>::type
109      weighted_tag;
110
111    if (sorted_){
112      if (perc_>=100)
113        return *(--last);
114      return calculate(first, last, weighted_tag());
115    }
116
117    std::vector<typename std::iterator_traits<RandomAccessIterator>::value_type> 
118      v_copy;
119    v_copy.reserve(std::distance(first,last));
120    std::copy(first, last, std::back_inserter(v_copy));
121    size_t i = static_cast<size_t>(perc_/100 * (v_copy.size()-1));
122    if (i+2 < v_copy.size()) {
123      std::partial_sort(v_copy.begin(), v_copy.begin()+i+2, v_copy.end());
124    }
125    else
126      std::sort(v_copy.begin(), v_copy.end());
127    return calculate(v_copy.begin(), v_copy.end(), weighted_tag());
128  }
129 
130  // unweighted version
131  template<typename RandomAccessIterator>
132  double Percentiler::calculate(RandomAccessIterator first, 
133                                RandomAccessIterator last,
134                                utility::unweighted_iterator_tag tag) const
135  {
136    double j = perc_/100 * (std::distance(first,last)-1);
137    int i = static_cast<int>(j);
138    return (1-j+floor(j))*first[i] + (j-floor(j))*first[i+1];
139  }
140
141
142  // weighted version
143  template<typename RandomAccessIterator>
144  double Percentiler::calculate(RandomAccessIterator first, 
145                                RandomAccessIterator last,
146                                utility::weighted_iterator_tag tag) const
147  {
148    assert(false && "not implemented");
149    return 0;
150  }
151
152
153}}} // of namespace statistics, yat, and theplu
154
155#endif
Note: See TracBrowser for help on using the repository browser.