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

Last change on this file since 4117 was 3792, checked in by Peter, 3 years ago

update copyright years

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