KolmogorovSmirnov.h

#ifndef _theplu_yat_statistics_kolmogorov_smirnov_
#define _theplu_yat_statistics_kolmogorov_smirnov_

// $Id: KolmogorovSmirnov.h 4260 2022-12-21 02:03:20Z peter $

/*
  Copyright (C) 2008 Jari Häkkinen, Peter Johansson
  Copyright (C) 2009, 2010, 2011, 2012, 2013, 2016 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/concept_check.h"

#include <boost/concept_check.hpp>
#include <boost/iterator/iterator_concepts.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 remove(double value, bool class_label, double weight=1.0);

    void reset(void);

    double score(void) const;

    //       \f$ F_{\textrm{True}}(x) - F_{\textrm{False}}(x) | \f$ where
    //   \f$ F(x) = \frac{\sum_{i:x_i\le x}w_i}{ \sum w_i} \f$
    void scores(std::vector<double>&) const;

    void shuffle(void);

    double signed_score(void) const;

  private:
    // 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_;

    // 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_concepts::ForwardTraversal<ForwardIterator>));
    BOOST_CONCEPT_ASSERT((boost_concepts::ReadableIterator<ForwardIterator>));
    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