source: trunk/yat/normalizer/Spearman.h @ 1510

#ifndef _theplu_yat_normalizer_spearman_
#define _theplu_yat_normalizer_spearman_

/*
  Copyright (C) 2008 Peter Johansson

  This file is part of the yat library, http://dev.thep.lu.se/yat

  The yat library is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License as
  published by the Free Software Foundation; either version 3 of the
  License, or (at your option) any later version.

  The yat library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with yat. If not, see <http://www.gnu.org/licenses/>.
*/

#include "yat/utility/DataIterator.h"
#include "yat/utility/iterator_traits.h"
#include "yat/utility/sort_index.h"
#include "yat/utility/WeightIterator.h"

#include <algorithm>
#include <functional>
#include <vector>

namespace theplu {
namespace yat {
namespace normalizer {

  /**
     \brief Replace elements with normalized rank

     \since New in yat 0.5
   */
  class Spearman
  {
  public:
    /**
       \brief default constructor
     */
    Spearman(void){}

    /**
       It is possible to centralize a range "in place"; it is
       permissible for the iterators \a first and \a result to be the
       same.

       Each element x is replaced by \f$ sum(w_i)/sum(w) \f$ where the
       first sum runs over elements for which \f$ x_i < x \f$. 

       In the unweighted case that can be simplified to \f$ rank/n
       \f$, i.e., the samllest element is assigned to 0, next smallest
       \f$ 1/n \f$ etc.
       
       \return result + (last-first)
     */
    template<typename ForwardIterator, typename RandomAccessIterator>
    RandomAccessIterator operator()(ForwardIterator first, ForwardIterator last,
                                    RandomAccessIterator result) const
    {
      typename utility::weighted_iterator_traits<ForwardIterator>::type tag;
      return normalize(first, last, result, tag);
    }


  private:
    // unweighted version
    template<typename ForwardIterator, typename RandomAccessIterator>
    RandomAccessIterator normalize(ForwardIterator first, ForwardIterator last,
                                   RandomAccessIterator result, 
                                   utility::unweighted_iterator_tag) const
    {
      std::vector<size_t> perm;
      utility::sort_index(first, last, perm);
      double n = perm.size();
      for ( size_t i=0; i<perm.size(); ++i)
        result[perm[i]] = static_cast<double>(i)/n;
      return result + std::distance(first, last);
    }


    // weighted version
    template<typename ForwardIterator, typename RandomAccessIterator>
    RandomAccessIterator normalize(ForwardIterator first, ForwardIterator last,
                                   RandomAccessIterator result, 
                                   utility::weighted_iterator_tag) const
    {
      std::copy(utility::weight_iterator(first), 
                utility::weight_iterator(last),
                utility::weight_iterator(result));
      // set values with w=0 to 0 to avoid problems with NaNs
      utility::iterator_traits<ForwardIterator> forward_trait;
      for (ForwardIterator i=first; i!=last; ++i)
        if (forward_trait.weight(i)==0)
          forward_trait.data(i)=0.0;

      std::vector<size_t> index(std::distance(first, last));
      utility::sort_index(utility::data_iterator(first), 
                          utility::data_iterator(last), index);
      utility::iterator_traits<RandomAccessIterator> trait;
      trait.data(result+index[0])=0;
      for (size_t i=1; i<index.size(); ++i)
        trait.data(result+index[i]) = 
          trait.data(result+index[i-1]) + trait.weight(result+index[i-1]);
      size_t n = std::distance(first, last);
      double w_sum = trait.data(result+index.back()) + 
        trait.weight(result+index.back());
      std::transform(utility::data_iterator(result),
                     utility::data_iterator(result+n),
                     utility::data_iterator(result),
                     std::bind2nd(std::divides<double>(), w_sum));
      return result + n;
    }

  };

}}} // end of namespace normalizer, yat and thep
#endif