copy_k_of_n.h

#ifndef theplu_yat_random_copy_k_of_n
#define theplu_yat_random_copy_k_of_n

// $Id: copy_k_of_n.h 3454 2015-12-09 08:29:30Z peter $

/*
  Copyright (C) 2015 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 "random.h"

#include <yat/utility/yat_assert.h>

#include <boost/concept_check.hpp>
#include <boost/iterator/iterator_concepts.hpp>
#include <boost/iterator/iterator_traits.hpp>

namespace theplu {
namespace yat {
namespace random {

  template<typename InputIterator, typename Size1, typename Size2,
           typename OutputIterator>
  OutputIterator copy_k_of_n(InputIterator it, Size1 k, Size2 n,
                             OutputIterator out)
  {
    BOOST_CONCEPT_ASSERT((boost_concepts::ReadableIterator<InputIterator>));
    BOOST_CONCEPT_ASSERT((boost_concepts::SinglePassIterator<InputIterator>));

    typedef typename boost::iterator_value<InputIterator>::type value_type;
    // check that *out = *it is valid
    BOOST_CONCEPT_ASSERT((boost_concepts::WritableIterator<OutputIterator, value_type>));
    BOOST_CONCEPT_ASSERT((boost_concepts::IncrementableIterator<OutputIterator>));

    YAT_ASSERT( k <= n);

    DiscreteUniform rnd;
    while (n) {
      if (rnd(n)<k) {
        --k;
        *out = *it;
        ++out;
      }
      --n;
      ++it;
    }
    return out;
  }


}}} // of namespace random, yat, and theplu

#endif