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
38 The permutation generator is intended for <tt>do {} while</tt> loop:
40 permutation_generator gen( 16 );
45 } while ( gen.next() );
47 // Get other permutation
52 } while ( gen.next() );
55 The following \p Generator defined:
56 - opt::v::random_permutation
57 - opt::v::random2_permutation
58 - opt::v::random_shuffle_permutation
59 - opt::v::skew_permutation
61 template <typename Generator>
62 struct permutation_generator {
64 template <typename Base> struct pack: public Base
66 typedef Generator permutation_generator;
73 /// Permutation generator of arbitrary length based on \p rand()
75 The class is suitable for \p opt::permutation_generator option.
77 The generator calculates <tt>n = rand()</tt> and produces the sequence
78 <tt>[n % nLen, (n + 1) % nLen, ..., (n + nLen - 1) % nLen]</tt>.
79 The generator does not allocate any memory.
81 \p Int template argument specifies the type of generated value, it should be any integer.
83 template <typename Int=int>
84 class random_permutation
87 typedef Int integer_type; ///< Type of generated value
91 integer_type m_nStart;
92 integer_type const m_nMod;
96 /// Initializes the generator of arbitrary length \p nLength
97 random_permutation( size_t nLength )
100 , m_nMod( integer_type(nLength) )
105 /// Returns the curent value
106 operator integer_type() const
108 return m_nCur % m_nMod;
111 /// Goes to next value. Returns \p false if the sequence is exhausted
114 return (++m_nCur % m_nMod) != m_nStart;
117 /// Resets the generator to produce new sequence
120 m_nCur = m_nStart = integer_type( rand() ) % m_nMod;
124 /// Permutation generator of power-of-2 length based on \p rand()
126 The class is suitable for \p opt::permutation_generator option.
128 The generator calculates <tt>n = rand()</tt> and produces the sequence
129 <tt>[n % nLen, (n + 1) % nLen, ..., (n + nLen - 1) % nLen]</tt>.
130 The generator does not allocate any memory.
131 \p nLen must be power of two.
133 \p Int template argument specifies the type of generated value, it should be any integer.
135 template <typename Int=int>
136 class random2_permutation
139 typedef Int integer_type; ///< Type of generated value
144 integer_type m_nStart;
145 integer_type const m_nMask;
149 /// Initializes the generator of length \p nLength
151 An assertion is raised if \p nLength is not a power of two.
153 random2_permutation( size_t nLength )
156 , m_nMask( integer_type(nLength) - 1 )
158 // nLength must be power of two
159 assert( (nLength & (nLength - 1)) == 0 );
163 /// Returns the current value
164 operator integer_type() const
166 return m_nCur & m_nMask;
169 /// Goes to next value. Returns \p false if the sequence is exhausted
172 return (++m_nCur & m_nMask) != m_nStart;
175 /// Resets the generator to produce new sequence
178 m_nCur = m_nStart = integer_type( rand() ) & m_nMask;
182 /// Permutation generator based on \p std::shuffle
184 The class is suitable for \p opt::permutation_generator option.
186 The generator produces a permutation of <tt>[0, nLen)</tt> sequence.
187 The generator instance allocates a memory block.
190 - \p Int - specifies the type of generated value, it should be any integer.
191 - \p RandomGenerator - random generator, default is \p std::mt19937
192 - \p RandomDevice - random device, default is \p std::random_device
194 template <typename Int=int, class RandomGenerator = std::mt19937, class RandomDevice = std::random_device >
195 class random_shuffle_permutation
198 typedef Int integer_type; ///< Type of generated value
199 typedef RandomGenerator random_generator; ///< random generator
200 typedef RandomDevice random_device; ///< random device
204 integer_type * m_pCur;
205 integer_type * m_pFirst;
206 integer_type * m_pLast;
210 /// Initializes the generator of arbitrary length \p nLength
211 random_shuffle_permutation( size_t nLength )
214 m_pFirst = new integer_type[nLength];
215 m_pLast = m_pFirst + nLength;
216 std::iota(m_pFirst, m_pLast, integer_type{0} );
220 ~random_shuffle_permutation()
225 /// Returns the current value
226 operator integer_type() const
231 /// Goes to next value. Returns \p false if the sequence is exhausted
234 return ++m_pCur < m_pLast;
237 /// Resets the generator to produce new sequence
240 std::shuffle( m_pFirst, m_pLast, random_generator{ random_device{}() });
245 /// Skew permutation generator
247 This generator produces offset permutation based on \p Generator:
248 <tt>int(Generator) + nOffset</tt>
249 where \p Generator - a permutation generator.
251 The class is suitable for \p opt::permutation_generator option
252 if the goal sequence should be a permutation of <tt>[nOffset, nOffset + nLength)</tt>
254 template <typename Generator>
255 class skew_permutation
258 typedef Generator base_generator; ///< Original permutation generator
259 typedef typename base_generator::integer_type integer_type; ///< Type of generated value
263 base_generator m_Gen;
264 integer_type const m_nOffset;
268 /// Initializes the generator
270 integer_type nOffset, ///< The offset, i.e. first value of generated sequence
271 size_t nLength ///< The length of sequence
274 , m_nOffset( nOffset )
277 /// Returns the current value
278 operator integer_type() const
280 return integer_type(m_Gen) + m_nOffset;
283 /// Goes to next value. Returns \p false if the sequence is exhausted
289 /// Resets the generator to produce new sequence
298 }} // namespace cds::opt
300 #endif // #ifndef CDSLIB_OPT_PERMUTATION_H