source: trunk/yat/random/copy_k_of_n.h @ 4117

#ifndef theplu_yat_random_copy_k_of_n
#define theplu_yat_random_copy_k_of_n

// $Id: copy_k_of_n.h 3792 2019-04-12 07:15:09Z peter $

/*
  Copyright (C) 2015, 2019 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 {

  /**
     Copy k random element out of range [it, it+n) into output range
     [out, out+k).

     Each element in the input range is copied with equal probability:
     k/n.

     Type Requirements:
     - \c InputIterator is \readable_iterator
     - \c InputIterator is \single_pass_iterator
     - \c OutputIterator is \writable_iterator
     - \c OutputIterator is \incrementable_iterator

     *out = *it is a valid expression if it is referencable.

     \return iterator one-passed the last element copied

     \since New in yat 0.14
   */
  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)<static_cast<unsigned long int>(k)) {
        --k;
        *out = *it;
        ++out;
      }
      --n;
      ++it;
    }
    return out;
  }


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

#endif