Spearman.h

#ifndef _theplu_yat_normalizer_spearman_
#define _theplu_yat_normalizer_spearman_

// $Id: Spearman.h 3330 2014-10-14 08:03:25Z peter $

/*
  Copyright (C) 2008 Jari Häkkinen, Peter Johansson
  Copyright (C) 2009, 2010, 2014 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 "utility.h"

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

#include <boost/concept_check.hpp>

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

namespace theplu {
namespace yat {
namespace normalizer {

  class Spearman
  {
  public:
    Spearman(void){}

    template<typename RandomAccessIter1, typename RandomAccessIter2>
    void operator()(RandomAccessIter1 first, RandomAccessIter1 last,
                    RandomAccessIter2 result) const
    {
      using boost_concepts::ReadableIterator;
      BOOST_CONCEPT_ASSERT((ReadableIterator<RandomAccessIter1>));
      using boost_concepts::RandomAccessTraversal;
      BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIter1>));
      using utility::DataIteratorConcept;
      BOOST_CONCEPT_ASSERT((DataIteratorConcept<RandomAccessIter1>));

      BOOST_CONCEPT_ASSERT((ReadableIterator<RandomAccessIter2>));
      using boost_concepts::WritableIterator;
      BOOST_CONCEPT_ASSERT((WritableIterator<RandomAccessIter2>));
      BOOST_CONCEPT_ASSERT((RandomAccessTraversal<RandomAccessIter2>));
      BOOST_CONCEPT_ASSERT((DataIteratorConcept<RandomAccessIter2>));

      using utility::weighted_if_any2;
      typename weighted_if_any2<RandomAccessIter1,RandomAccessIter2>::type tag;
      normalize(first, last, result, tag);
    }


  private:
    // unweighted version
    template<typename RandomAccessIter1, typename RandomAccessIter2>
    void normalize(RandomAccessIter1 first, RandomAccessIter1 last,
                   RandomAccessIter2 result,
                   utility::unweighted_iterator_tag) const
    {
      std::vector<size_t> perm;
      utility::sort_index(first, last, perm);
      double n = perm.size();
      size_t i=0;
      while ( i<perm.size() ) {
        size_t min_i = i;
        while (i<perm.size() && first[perm[i]]<=first[perm[min_i]])
          ++i;
        double res = (i + min_i)/(2.0*n);
        for ( ; min_i < i; ++min_i)
          result[perm[min_i]] = res;
      }
    }


    // weighted version
    template<typename RandomAccessIter1, typename RandomAccessIter2>
    void normalize(RandomAccessIter1 first, RandomAccessIter1 last,
                   RandomAccessIter2 result,
                   utility::weighted_iterator_tag) const
    {
      detail::copy_weight_if_weighted(first, last, result);
      std::vector<size_t> perm;
      utility::sort_index(first, last, perm);
      utility::iterator_traits<RandomAccessIter1> trait;
      utility::iterator_traits<RandomAccessIter2> rtrait;

      double total_w = utility::sum_weight(first, last);
      double sum_w=0;
      size_t i=0;
      while ( i<perm.size() ) {
        double w=0;
        size_t min_i = i;
        while (i<perm.size() && (trait.weight(first+perm[i])==0 ||
                                 trait.data(first+perm[i]) <=
                                 trait.data(first+perm[min_i])) ) {
          w += trait.weight(first+perm[i]);
          ++i;
        }
        double res = (sum_w + 0.5*w)/total_w;
        for ( size_t j=min_i; j<i; ++j)
          rtrait.data(result+perm[j]) = res;
        sum_w += w;
      }
    }
  };

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