KolmogorovSmirnov.h

#ifndef _theplu_yat_statistics_kolmogorov_smirnov_ 
#define _theplu_yat_statistics_kolmogorov_smirnov_ 

// $Id: KolmogorovSmirnov.h 2526 2011-07-25 02:03:35Z peter $

/*
  Copyright (C) 2008 Jari Häkkinen, Peter Johansson
  Copyright (C) 2009, 2010, 2011 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 <boost/concept_check.hpp>

#include <iosfwd>
#include <set>
#include <vector>

namespace theplu {
namespace yat {
namespace statistics {  

  class KolmogorovSmirnov
  {
  public:
    struct Element
    {
      Element(void);

      Element(double x, bool class_label, double w=1.0);

      double value;
      
      bool label;

      double weight;

      bool operator<(const Element& rhs) const;
    };

    KolmogorovSmirnov(void);

    void add(double value, bool class_label, double weight=1.0);

    template <typename ForwardIterator>
    void add(ForwardIterator first, ForwardIterator last); 

    double p_value(void) const;

    double p_value(size_t perm) const;

    void reset(void);

    double score(void) const;

    void shuffle(void);

    double signed_score(void) const;

  private:
    void scores(std::vector<double>&) const;
    // add weights to sum_w1 and sum_w2 respectively depending on
    // label in element.
    template <typename ForwardIterator>
    void add_sum_w(ForwardIterator first, ForwardIterator last);
    
    mutable bool cached_;
    mutable double score_;
    typedef std::multiset<Element> data_w;
    data_w data_;
    double sum_w1_;
    double sum_w2_;

    friend std::ostream& operator<<(std::ostream&, const KolmogorovSmirnov&);

    // using compiler generated copy and assignment
    //KolmogorovSmirnov(const KolmogorovSmirnov&);
    //KolmogorovSmirnov& operator=(const KolmogorovSmirnov&);
  };

  std::ostream& operator<<(std::ostream&, const KolmogorovSmirnov&);


  //  template implementations

  template <typename ForwardIterator>
  void KolmogorovSmirnov::add(ForwardIterator first, ForwardIterator last)
  {
    BOOST_CONCEPT_ASSERT((boost::ForwardIterator<ForwardIterator>));
    typedef typename std::iterator_traits<ForwardIterator>::reference ref;
    BOOST_CONCEPT_ASSERT((boost::Convertible<ref, KolmogorovSmirnov::Element>));
    ForwardIterator iter(first);
    typename data_w::const_iterator hint(data_.begin());
    for ( ; iter!=last; ++iter) 
      if ((*iter).weight) // ignore data points with zero weight
        hint = data_.insert(hint, *iter);
    add_sum_w(first, last);
    cached_=false;
  }


  template <typename ForwardIterator>
  void KolmogorovSmirnov::add_sum_w(ForwardIterator first, 
                                    ForwardIterator last)
  {
    while (first!=last) {
      if ((*first).label)
        sum_w1_ += (*first).weight;
      else
        sum_w2_ += (*first).weight;
      ++first;
    }
  }

}}} // of namespace theplu yat statistics

#endif