yat  0.14.5pre
Spearman.h
1 #ifndef _theplu_yat_normalizer_spearman_
2 #define _theplu_yat_normalizer_spearman_
3 
4 // $Id: Spearman.h 3550 2017-01-03 05:41:02Z peter $
5 
6 /*
7  Copyright (C) 2008 Jari Häkkinen, Peter Johansson
8  Copyright (C) 2009, 2010, 2014, 2016 Peter Johansson
9 
10  This file is part of the yat library, http://dev.thep.lu.se/yat
11 
12  The yat library is free software; you can redistribute it and/or
13  modify it under the terms of the GNU General Public License as
14  published by the Free Software Foundation; either version 3 of the
15  License, or (at your option) any later version.
16 
17  The yat library is distributed in the hope that it will be useful,
18  but WITHOUT ANY WARRANTY; without even the implied warranty of
19  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20  General Public License for more details.
21 
22  You should have received a copy of the GNU General Public License
23  along with yat. If not, see <http://www.gnu.org/licenses/>.
24 */
25 
26 #include "utility.h"
27 
28 #include "yat/utility/concept_check.h"
29 #include "yat/utility/DataIterator.h"
30 #include "yat/utility/iterator_traits.h"
31 #include "yat/utility/sort_index.h"
33 #include "yat/utility/utility.h"
34 #include "yat/utility/WeightIterator.h"
35 
36 #include <boost/concept_check.hpp>
37 #include <boost/iterator/iterator_concepts.hpp>
38 
39 #include <algorithm>
40 #include <functional>
41 #include <numeric>
42 #include <vector>
43 
44 namespace theplu {
45 namespace yat {
46 namespace normalizer {
47 
57  class Spearman
58  {
59  public:
63  Spearman(void){}
64 
77  template<typename RandomAccessIter1, typename RandomAccessIter2>
78  void operator()(RandomAccessIter1 first, RandomAccessIter1 last,
79  RandomAccessIter2 result) const
80  {
81  using boost_concepts::RandomAccessTraversal;
82  BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIter1>));
84  BOOST_CONCEPT_ASSERT((DataIteratorConcept<RandomAccessIter1>));
85 
86  using boost_concepts::WritableIterator;
87  BOOST_CONCEPT_ASSERT((WritableIterator<RandomAccessIter2>));
88  BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIter2>));
89  BOOST_CONCEPT_ASSERT((DataIteratorConcept<RandomAccessIter2>));
90 
92  typename weighted_if_any2<RandomAccessIter1,RandomAccessIter2>::type tag;
93  normalize(first, last, result, tag);
94  }
95 
96 
97  private:
98  // unweighted version
99  template<typename RandomAccessIter1, typename RandomAccessIter2>
100  void normalize(RandomAccessIter1 first, RandomAccessIter1 last,
101  RandomAccessIter2 result,
103  {
104  std::vector<size_t> perm;
105  utility::sort_index(first, last, perm);
106  double n = perm.size();
107  size_t i=0;
108  while ( i<perm.size() ) {
109  size_t min_i = i;
110  while (i<perm.size() && first[perm[i]]<=first[perm[min_i]])
111  ++i;
112  double res = (i + min_i)/(2.0*n);
113  for ( ; min_i < i; ++min_i)
114  result[perm[min_i]] = res;
115  }
116  }
117 
118 
119  // weighted version
120  template<typename RandomAccessIter1, typename RandomAccessIter2>
121  void normalize(RandomAccessIter1 first, RandomAccessIter1 last,
122  RandomAccessIter2 result,
123  utility::weighted_iterator_tag) const
124  {
125  detail::copy_weight_if_weighted(first, last, result);
126  std::vector<size_t> perm;
127  utility::sort_index(first, last, perm);
128  utility::iterator_traits<RandomAccessIter1> trait;
129  utility::iterator_traits<RandomAccessIter2> rtrait;
130 
131  double total_w = utility::sum_weight(first, last);
132  double sum_w=0;
133  size_t i=0;
134  while ( i<perm.size() ) {
135  double w=0;
136  size_t min_i = i;
137  while (i<perm.size() && (trait.weight(first+perm[i])==0 ||
138  trait.data(first+perm[i]) <=
139  trait.data(first+perm[min_i])) ) {
140  w += trait.weight(first+perm[i]);
141  ++i;
142  }
143  double res = (sum_w + 0.5*w)/total_w;
144  for ( size_t j=min_i; j<i; ++j)
145  rtrait.data(result+perm[j]) = res;
146  sum_w += w;
147  }
148  }
149  };
150 
151 }}} // end of namespace normalizer, yat and thep
152 #endif
Concept check for Data Iterator.
Definition: concept_check.h:228
double sum_weight(Iterator first, Iterator last)
Definition: utility.h:543
Some useful functions are placed here.
Definition: iterator_traits.h:47
Spearman(void)
default constructor
Definition: Spearman.h:63
void operator()(RandomAccessIter1 first, RandomAccessIter1 last, RandomAccessIter2 result) const
Definition: Spearman.h:78
Replace elements with normalized rank.
Definition: Spearman.h:57
void sort_index(InputIterator first, InputIterator last, std::vector< size_t > &sort_index)
Definition: sort_index.h:146
Definition: iterator_traits.h:159

Generated on Tue Sep 26 2017 02:33:29 for yat by  doxygen 1.8.5