2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_OPT_PERMUTATION_H
32 #define CDSLIB_OPT_PERMUTATION_H
34 #include <stdlib.h> // rand, srand
36 #include <algorithm> // std::shuffle
37 #include <numeric> // std::iota
39 #include <cds/opt/options.h>
41 namespace cds { namespace opt {
43 /// [type-option] Random permutation generator option setter
45 The class represents permutation generator of unique integers from <tt> [0, nLength) </tt>
46 (\p nLenght is not included) in random order.
48 The generator interface is:
51 // Initializes the generator of length nLength
52 generator( size_t nLength );
54 // Returns current value
57 // Goes to next value. Returns false if the permutation is exchausted
60 // Resets the generator to produce the new sequence
67 The permutation generator is intended for <tt>do {} while</tt> loop:
69 permutation_generator gen( 16 );
74 } while ( gen.next() );
76 // Get other permutation
81 } while ( gen.next() );
84 The following \p Generator defined:
85 - \p opt::v::random_permutation
86 - \p opt::v::random2_permutation
87 - \p opt::v::random_shuffle_permutation
88 - \p opt::v::skew_permutation
90 template <typename Generator>
91 struct permutation_generator {
93 template <typename Base> struct pack: public Base
95 typedef Generator permutation_generator;
102 /// Permutation generator of arbitrary length based on \p rand()
104 The class is suitable for \p opt::permutation_generator option.
106 The generator calculates <tt>n = rand()</tt> and produces the sequence
107 <tt>[n % nLen, (n + 1) % nLen, ..., (n + nLen - 1) % nLen]</tt>.
108 The generator does not allocate any memory.
110 \p Int template argument specifies the type of generated value, it should be any integer.
112 template <typename Int=int>
113 class random_permutation
116 typedef Int integer_type; ///< Type of generated value
120 integer_type m_nStart;
121 integer_type const m_nMod;
125 /// Initializes the generator of arbitrary length \p nLength
126 random_permutation( size_t nLength )
129 , m_nMod( integer_type(nLength) )
134 /// Returns the curent value
135 operator integer_type() const
137 return m_nCur % m_nMod;
140 /// Goes to next value. Returns \p false if the sequence is exhausted
143 return (++m_nCur % m_nMod) != m_nStart;
146 /// Resets the generator to produce new sequence
149 m_nCur = m_nStart = integer_type( rand() ) % m_nMod;
153 /// Permutation generator of power-of-2 length based on \p rand()
155 The class is suitable for \p opt::permutation_generator option.
157 The generator calculates <tt>n = rand()</tt> and produces the sequence
158 <tt>[n % nLen, (n + 1) % nLen, ..., (n + nLen - 1) % nLen]</tt>.
159 The generator does not allocate any memory.
160 \p nLen must be power of two.
162 \p Int template argument specifies the type of generated value, it should be any integer.
164 template <typename Int=int>
165 class random2_permutation
168 typedef Int integer_type; ///< Type of generated value
173 integer_type m_nStart;
174 integer_type const m_nMask;
178 /// Initializes the generator of length \p nLength
180 An assertion is raised if \p nLength is not a power of two.
182 random2_permutation( size_t nLength )
185 , m_nMask( integer_type(nLength) - 1 )
187 // nLength must be power of two
188 assert( (nLength & (nLength - 1)) == 0 );
192 /// Returns the current value
193 operator integer_type() const
195 return m_nCur & m_nMask;
198 /// Goes to next value. Returns \p false if the sequence is exhausted
201 return (++m_nCur & m_nMask) != m_nStart;
204 /// Resets the generator to produce new sequence
207 m_nCur = m_nStart = integer_type( rand() ) & m_nMask;
211 /// Permutation generator based on \p std::shuffle
213 The class is suitable for \p opt::permutation_generator option.
215 The generator produces a permutation of <tt>[0, nLen)</tt> sequence.
216 The generator instance allocates a memory block.
219 - \p Int - specifies the type of generated value, it should be any integer.
220 - \p RandomGenerator - random generator, default is \p std::mt19937
221 - \p RandomDevice - random device, default is \p std::random_device
223 template <typename Int=int, class RandomGenerator = std::mt19937, class RandomDevice = std::random_device >
224 class random_shuffle_permutation
227 typedef Int integer_type; ///< Type of generated value
228 typedef RandomGenerator random_generator; ///< random generator
229 typedef RandomDevice random_device; ///< random device
233 integer_type * m_pCur;
234 integer_type * m_pFirst;
235 integer_type * m_pLast;
239 /// Initializes the generator of arbitrary length \p nLength
240 random_shuffle_permutation( size_t nLength )
243 m_pFirst = new integer_type[nLength];
244 m_pLast = m_pFirst + nLength;
245 std::iota(m_pFirst, m_pLast, integer_type{0} );
249 ~random_shuffle_permutation()
254 /// Returns the current value
255 operator integer_type() const
260 /// Goes to next value. Returns \p false if the sequence is exhausted
263 return ++m_pCur < m_pLast;
266 /// Resets the generator to produce new sequence
269 std::shuffle( m_pFirst, m_pLast, random_generator{ random_device{}() });
274 /// Skew permutation generator
276 This generator produces offset permutation based on \p Generator:
277 <tt>int(Generator) + nOffset</tt>
278 where \p Generator - a permutation generator.
280 The class is suitable for \p opt::permutation_generator option
281 if the goal sequence should be a permutation of <tt>[nOffset, nOffset + nLength)</tt>
283 template <typename Generator>
284 class skew_permutation
287 typedef Generator base_generator; ///< Original permutation generator
288 typedef typename base_generator::integer_type integer_type; ///< Type of generated value
292 base_generator m_Gen;
293 integer_type const m_nOffset;
297 /// Initializes the generator
299 integer_type nOffset, ///< The offset, i.e. first value of generated sequence
300 size_t nLength ///< The length of sequence
303 , m_nOffset( nOffset )
306 /// Returns the current value
307 operator integer_type() const
309 return integer_type(m_Gen) + m_nOffset;
312 /// Goes to next value. Returns \p false if the sequence is exhausted
318 /// Resets the generator to produce new sequence
327 }} // namespace cds::opt
329 #endif // #ifndef CDSLIB_OPT_PERMUTATION_H