yat/random/copy_k_of_n.h

Code
Comments
Other
Rev Date Author Line
3454 09 Dec 15 peter 1 #ifndef theplu_yat_random_copy_k_of_n
3454 09 Dec 15 peter 2 #define theplu_yat_random_copy_k_of_n
3454 09 Dec 15 peter 3
3454 09 Dec 15 peter 4 // $Id$
3454 09 Dec 15 peter 5
3454 09 Dec 15 peter 6 /*
3792 12 Apr 19 peter 7   Copyright (C) 2015, 2019 Peter Johansson
3454 09 Dec 15 peter 8
3454 09 Dec 15 peter 9   This file is part of the yat library, http://dev.thep.lu.se/yat
3454 09 Dec 15 peter 10
3454 09 Dec 15 peter 11   The yat library is free software; you can redistribute it and/or
3454 09 Dec 15 peter 12   modify it under the terms of the GNU General Public License as
3454 09 Dec 15 peter 13   published by the Free Software Foundation; either version 3 of the
3454 09 Dec 15 peter 14   License, or (at your option) any later version.
3454 09 Dec 15 peter 15
3454 09 Dec 15 peter 16   The yat library is distributed in the hope that it will be useful,
3454 09 Dec 15 peter 17   but WITHOUT ANY WARRANTY; without even the implied warranty of
3454 09 Dec 15 peter 18   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
3454 09 Dec 15 peter 19   General Public License for more details.
3454 09 Dec 15 peter 20
3454 09 Dec 15 peter 21   You should have received a copy of the GNU General Public License
3454 09 Dec 15 peter 22   along with yat. If not, see <http://www.gnu.org/licenses/>.
3454 09 Dec 15 peter 23 */
3454 09 Dec 15 peter 24
3454 09 Dec 15 peter 25 #include "random.h"
3454 09 Dec 15 peter 26
3454 09 Dec 15 peter 27 #include <yat/utility/yat_assert.h>
3454 09 Dec 15 peter 28
3454 09 Dec 15 peter 29 #include <boost/concept_check.hpp>
3454 09 Dec 15 peter 30 #include <boost/iterator/iterator_concepts.hpp>
3454 09 Dec 15 peter 31 #include <boost/iterator/iterator_traits.hpp>
3454 09 Dec 15 peter 32
3454 09 Dec 15 peter 33 namespace theplu {
3454 09 Dec 15 peter 34 namespace yat {
3454 09 Dec 15 peter 35 namespace random {
3454 09 Dec 15 peter 36
3454 09 Dec 15 peter 37   /**
3454 09 Dec 15 peter 38      Copy k random element out of range [it, it+n) into output range
3454 09 Dec 15 peter 39      [out, out+k).
3454 09 Dec 15 peter 40
3454 09 Dec 15 peter 41      Each element in the input range is copied with equal probability:
3454 09 Dec 15 peter 42      k/n.
3454 09 Dec 15 peter 43
3454 09 Dec 15 peter 44      Type Requirements:
3454 09 Dec 15 peter 45      - \c InputIterator is \readable_iterator
3454 09 Dec 15 peter 46      - \c InputIterator is \single_pass_iterator
3454 09 Dec 15 peter 47      - \c OutputIterator is \writable_iterator
3454 09 Dec 15 peter 48      - \c OutputIterator is \incrementable_iterator
3454 09 Dec 15 peter 49
3454 09 Dec 15 peter 50      *out = *it is a valid expression if it is referencable.
3454 09 Dec 15 peter 51
3454 09 Dec 15 peter 52      \return iterator one-passed the last element copied
3454 09 Dec 15 peter 53
3454 09 Dec 15 peter 54      \since New in yat 0.14
3454 09 Dec 15 peter 55    */
3454 09 Dec 15 peter 56   template<typename InputIterator, typename Size1, typename Size2,
3454 09 Dec 15 peter 57            typename OutputIterator>
3454 09 Dec 15 peter 58   OutputIterator copy_k_of_n(InputIterator it, Size1 k, Size2 n,
3454 09 Dec 15 peter 59                              OutputIterator out)
3454 09 Dec 15 peter 60   {
3454 09 Dec 15 peter 61     BOOST_CONCEPT_ASSERT((boost_concepts::ReadableIterator<InputIterator>));
3454 09 Dec 15 peter 62     BOOST_CONCEPT_ASSERT((boost_concepts::SinglePassIterator<InputIterator>));
3454 09 Dec 15 peter 63
3454 09 Dec 15 peter 64     typedef typename boost::iterator_value<InputIterator>::type value_type;
3454 09 Dec 15 peter 65     // check that *out = *it is valid
3454 09 Dec 15 peter 66     BOOST_CONCEPT_ASSERT((boost_concepts::WritableIterator<OutputIterator, value_type>));
3454 09 Dec 15 peter 67     BOOST_CONCEPT_ASSERT((boost_concepts::IncrementableIterator<OutputIterator>));
3454 09 Dec 15 peter 68
3454 09 Dec 15 peter 69     YAT_ASSERT( k <= n);
3454 09 Dec 15 peter 70
3454 09 Dec 15 peter 71     DiscreteUniform rnd;
3454 09 Dec 15 peter 72     while (n) {
3788 29 Jan 19 peter 73       if (rnd(n)<static_cast<unsigned long int>(k)) {
3454 09 Dec 15 peter 74         --k;
3454 09 Dec 15 peter 75         *out = *it;
3454 09 Dec 15 peter 76         ++out;
3454 09 Dec 15 peter 77       }
3454 09 Dec 15 peter 78       --n;
3454 09 Dec 15 peter 79       ++it;
3454 09 Dec 15 peter 80     }
3454 09 Dec 15 peter 81     return out;
3454 09 Dec 15 peter 82   }
3454 09 Dec 15 peter 83
3454 09 Dec 15 peter 84
3454 09 Dec 15 peter 85 }}} // of namespace random, yat, and theplu
3454 09 Dec 15 peter 86
3454 09 Dec 15 peter 87 #endif

Generated on Sat Oct 14 02:23:01 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)