3 #ifndef CDSLIB_OPT_PERMUTATION_H
4 #define CDSLIB_OPT_PERMUTATION_H
6 #include <stdlib.h> // rand, srand
8 #include <algorithm> // std::shuffle
9 #include <numeric> // std::iota
11 #include <cds/opt/options.h>
13 namespace cds { namespace opt {
15 /// [type-option] Random permutation generator option setter
17 The class represents permutation generator of unique integers from <tt> [0, nLength) </tt>
18 (\p nLenght is not included) in random order.
20 The generator interface is:
23 // Initializes the generator of length nLength
24 generator( size_t nLength );
26 // Returns current value
29 // Goes to next value. Returns false if the permutation is exchausted
32 // Resets the generator to produce the new sequence
39 The permutation generator is intended for <tt>do {} while</tt> loop:
41 permutation_generator gen( 16 );
46 } while ( gen.next() );
48 // Get other permutation
53 } while ( gen.next() );
56 The following \p Generator defined:
57 - \p opt::v::random_permutation
58 - \p opt::v::random2_permutation
59 - \p opt::v::random_shuffle_permutation
60 - \p opt::v::skew_permutation
62 template <typename Generator>
63 struct permutation_generator {
65 template <typename Base> struct pack: public Base
67 typedef Generator permutation_generator;
74 /// Permutation generator of arbitrary length based on \p rand()
76 The class is suitable for \p opt::permutation_generator option.
78 The generator calculates <tt>n = rand()</tt> and produces the sequence
79 <tt>[n % nLen, (n + 1) % nLen, ..., (n + nLen - 1) % nLen]</tt>.
80 The generator does not allocate any memory.
82 \p Int template argument specifies the type of generated value, it should be any integer.
84 template <typename Int=int>
85 class random_permutation
88 typedef Int integer_type; ///< Type of generated value
92 integer_type m_nStart;
93 integer_type const m_nMod;
97 /// Initializes the generator of arbitrary length \p nLength
98 random_permutation( size_t nLength )
101 , m_nMod( integer_type(nLength) )
106 /// Returns the curent value
107 operator integer_type() const
109 return m_nCur % m_nMod;
112 /// Goes to next value. Returns \p false if the sequence is exhausted
115 return (++m_nCur % m_nMod) != m_nStart;
118 /// Resets the generator to produce new sequence
121 m_nCur = m_nStart = integer_type( rand() ) % m_nMod;
125 /// Permutation generator of power-of-2 length based on \p rand()
127 The class is suitable for \p opt::permutation_generator option.
129 The generator calculates <tt>n = rand()</tt> and produces the sequence
130 <tt>[n % nLen, (n + 1) % nLen, ..., (n + nLen - 1) % nLen]</tt>.
131 The generator does not allocate any memory.
132 \p nLen must be power of two.
134 \p Int template argument specifies the type of generated value, it should be any integer.
136 template <typename Int=int>
137 class random2_permutation
140 typedef Int integer_type; ///< Type of generated value
145 integer_type m_nStart;
146 integer_type const m_nMask;
150 /// Initializes the generator of length \p nLength
152 An assertion is raised if \p nLength is not a power of two.
154 random2_permutation( size_t nLength )
157 , m_nMask( integer_type(nLength) - 1 )
159 // nLength must be power of two
160 assert( (nLength & (nLength - 1)) == 0 );
164 /// Returns the current value
165 operator integer_type() const
167 return m_nCur & m_nMask;
170 /// Goes to next value. Returns \p false if the sequence is exhausted
173 return (++m_nCur & m_nMask) != m_nStart;
176 /// Resets the generator to produce new sequence
179 m_nCur = m_nStart = integer_type( rand() ) & m_nMask;
183 /// Permutation generator based on \p std::shuffle
185 The class is suitable for \p opt::permutation_generator option.
187 The generator produces a permutation of <tt>[0, nLen)</tt> sequence.
188 The generator instance allocates a memory block.
191 - \p Int - specifies the type of generated value, it should be any integer.
192 - \p RandomGenerator - random generator, default is \p std::mt19937
193 - \p RandomDevice - random device, default is \p std::random_device
195 template <typename Int=int, class RandomGenerator = std::mt19937, class RandomDevice = std::random_device >
196 class random_shuffle_permutation
199 typedef Int integer_type; ///< Type of generated value
200 typedef RandomGenerator random_generator; ///< random generator
201 typedef RandomDevice random_device; ///< random device
205 integer_type * m_pCur;
206 integer_type * m_pFirst;
207 integer_type * m_pLast;
211 /// Initializes the generator of arbitrary length \p nLength
212 random_shuffle_permutation( size_t nLength )
215 m_pFirst = new integer_type[nLength];
216 m_pLast = m_pFirst + nLength;
217 std::iota(m_pFirst, m_pLast, integer_type{0} );
221 ~random_shuffle_permutation()
226 /// Returns the current value
227 operator integer_type() const
232 /// Goes to next value. Returns \p false if the sequence is exhausted
235 return ++m_pCur < m_pLast;
238 /// Resets the generator to produce new sequence
241 std::shuffle( m_pFirst, m_pLast, random_generator{ random_device{}() });
246 /// Skew permutation generator
248 This generator produces offset permutation based on \p Generator:
249 <tt>int(Generator) + nOffset</tt>
250 where \p Generator - a permutation generator.
252 The class is suitable for \p opt::permutation_generator option
253 if the goal sequence should be a permutation of <tt>[nOffset, nOffset + nLength)</tt>
255 template <typename Generator>
256 class skew_permutation
259 typedef Generator base_generator; ///< Original permutation generator
260 typedef typename base_generator::integer_type integer_type; ///< Type of generated value
264 base_generator m_Gen;
265 integer_type const m_nOffset;
269 /// Initializes the generator
271 integer_type nOffset, ///< The offset, i.e. first value of generated sequence
272 size_t nLength ///< The length of sequence
275 , m_nOffset( nOffset )
278 /// Returns the current value
279 operator integer_type() const
281 return integer_type(m_Gen) + m_nOffset;
284 /// Goes to next value. Returns \p false if the sequence is exhausted
290 /// Resets the generator to produce new sequence
299 }} // namespace cds::opt
301 #endif // #ifndef CDSLIB_OPT_PERMUTATION_H