source: trunk/yat/normalizer/Spearman.h

Last change on this file was 3550, checked in by Peter, 5 years ago

Update copyright years. Happy New Year

  • Property svn:eol-style set to native
  • Property svn:keywords set to Id
File size: 4.6 KB
Line 
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"
32#include "yat/utility/stl_utility.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
44namespace theplu {
45namespace yat {
46namespace normalizer {
47
48  /**
49     \brief Replace elements with normalized rank
50
51     Each element x is replaced by \f$ \frac{\sum I(x_i-x) w_i}{\sum
52     w_i} \f$ where \f$ I(x) = 1 \f$ for \f$ x>0 \f$, \f$I(x) = 0.5
53     \f$ for \f$ x=0 \f$, and \f$ I(x) = 0 \f$ for \f$ x<0 \f$.
54
55     \since New in yat 0.5
56   */
57  class Spearman
58  {
59  public:
60    /**
61       \brief default constructor
62     */
63    Spearman(void){}
64
65    /**
66       It is possible to centralize a range "in place"; it is
67       permissible for the iterators \a first and \a result to be the
68       same.
69
70       Type Requirements:
71       - \c RandomAccessIter1 is \random_access_traversal_iterator
72       - \c RandomAccessIter1 is \ref concept_data_iterator
73       - \c RandomAccessIter2 is \writable_iterator
74       - \c RandomAccessIter2 is \random_access_traversal_iterator
75       - \c RandomAccessIter2 is \ref concept_data_iterator
76     */
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>));
83      using utility::DataIteratorConcept;
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
91      using utility::weighted_if_any2;
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,
102                   utility::unweighted_iterator_tag) const
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
Note: See TracBrowser for help on using the repository browser.