00001 #ifndef _theplu_yat_normalizer_spearman_
00002 #define _theplu_yat_normalizer_spearman_
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #include "yat/utility/DataIterator.h"
00027 #include "yat/utility/iterator_traits.h"
00028 #include "yat/utility/sort_index.h"
00029 #include "yat/utility/WeightIterator.h"
00030
00031 #include <algorithm>
00032 #include <functional>
00033 #include <vector>
00034
00035 namespace theplu {
00036 namespace yat {
00037 namespace normalizer {
00038
00048 class Spearman
00049 {
00050 public:
00054 Spearman(void){}
00055
00061 template<typename ForwardIterator, typename RandomAccessIterator>
00062 void operator()(ForwardIterator first, ForwardIterator last,
00063 RandomAccessIterator result) const
00064 {
00065 typename utility::weighted_iterator_traits<ForwardIterator>::type tag;
00066 normalize(first, last, result, tag);
00067 }
00068
00069
00070 private:
00071
00072 template<typename ForwardIterator, typename RandomAccessIterator>
00073 void normalize(ForwardIterator first, ForwardIterator last,
00074 RandomAccessIterator result,
00075 utility::unweighted_iterator_tag) const
00076 {
00077 std::vector<size_t> perm;
00078 utility::sort_index(first, last, perm);
00079 double n = perm.size();
00080 size_t i=0;
00081 while ( i<perm.size() ) {
00082 size_t min_i = i;
00083 while (i<perm.size() && first[perm[i]]<=first[perm[min_i]])
00084 ++i;
00085 double res = static_cast<double>(i + min_i)/(2*n);
00086 for ( ; min_i < i; ++min_i)
00087 result[perm[min_i]] = res;
00088 }
00089 }
00090
00091
00092
00093 template<typename ForwardIterator, typename RandomAccessIterator>
00094 void normalize(ForwardIterator first, ForwardIterator last,
00095 RandomAccessIterator result,
00096 utility::weighted_iterator_tag) const
00097 {
00098 std::copy(utility::weight_iterator(first),
00099 utility::weight_iterator(last),
00100 utility::weight_iterator(result));
00101
00102 utility::iterator_traits<ForwardIterator> trait;
00103 for (ForwardIterator i=first; i!=last; ++i)
00104 if (trait.weight(i)==0)
00105 trait.data(i)=0.0;
00106
00107 std::vector<size_t> perm(std::distance(first, last));
00108 utility::sort_index(utility::data_iterator(first),
00109 utility::data_iterator(last), perm);
00110 utility::iterator_traits<RandomAccessIterator> rtrait;
00111
00112 double sum_w=0;
00113 size_t i=0;
00114 while ( i<perm.size() ) {
00115 double w=0;
00116 size_t min_i = i;
00117 while (i<perm.size() && (trait.weight(first+perm[i])==0 ||
00118 trait.data(first+perm[i]) <=
00119 trait.data(first+perm[min_i])) ) {
00120 w += trait.weight(first+perm[i]);
00121 ++i;
00122 }
00123 double res=sum_w + 0.5*w;
00124 for ( size_t j=min_i; j<i; ++j)
00125 rtrait.data(result+perm[j]) = res;
00126 sum_w += w;
00127 }
00128
00129 size_t n = std::distance(first, last);
00130 std::transform(utility::data_iterator(result),
00131 utility::data_iterator(result+n),
00132 utility::data_iterator(result),
00133 std::bind2nd(std::divides<double>(), sum_w));
00134 }
00135
00136 };
00137
00138 }}}
00139 #endif