cds/opt/permutation.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_OPT_PERMUTATION_H
   4 #define CDSLIB_OPT_PERMUTATION_H
   5
   6 #include <stdlib.h> // rand, srand
   7 #include <random>
   8 #include <algorithm> // std::shuffle
   9 #include <numeric>   // std::iota
  10
  11 #include <cds/opt/options.h>
  12
  13 namespace cds { namespace opt {
  14
  15     /// [type-option] Random permutation generator option setter
  16     /**
  17         The class represents permutation generator of unique integers from <tt> [0, nLength) </tt>
  18         (\p nLenght is not included) in random order.
  19
  20         The generator interface is:
  21         \code
  22         class generator {
  23             // Initializes the generator of length nLength
  24             generator( size_t nLength );
  25
  26             // Returns current value
  27             operator int();
  28
  29             // Goes to next value. Returns false if the permutation is exchausted
  30             bool next();
  31
  32             // Resets the generator to produce the new sequence
  33             void reset();
  34         };
  35         \endcode
  36
  37         Usage example:
  38         The permutation generator is intended for <tt>do {} while</tt> loop:
  39         \code
  40         permutation_generator gen( 16 );
  41         int i = gen.begin();
  42         do {
  43             int i = gen;
  44             //...
  45         } while ( gen.next() );
  46
  47         // Get other permutation
  48         gen.reset();
  49         do {
  50             int i = gen;
  51             //...
  52         } while ( gen.next() );
  53         \endcode
  54
  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
  60     */
  61     template <typename Generator>
  62     struct permutation_generator {
  63         //@cond
  64         template <typename Base> struct pack: public Base
  65         {
  66             typedef Generator permutation_generator;
  67         };
  68         //@endcond
  69     };
  70
  71     namespace v {
  72
  73         /// Permutation generator of arbitrary length based on \p rand()
  74         /**
  75             The class is suitable for \p opt::permutation_generator option.
  76
  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.
  80
  81             \p Int template argument specifies the type of generated value, it should be any integer.
  82         */
  83         template <typename Int=int>
  84         class random_permutation
  85         {
  86         public:
  87             typedef Int     integer_type;   ///< Type of generated value
  88         protected:
  89             //@cond
  90             integer_type        m_nCur;
  91             integer_type        m_nStart;
  92             integer_type const  m_nMod;
  93             //@endcond
  94
  95         public:
  96             /// Initializes the generator of arbitrary length \p nLength
  97             random_permutation( size_t nLength )
  98                 : m_nCur(0)
  99                 , m_nStart(0)
 100                 , m_nMod( integer_type(nLength) )
 101             {
 102                 reset();
 103             }
 104
 105             /// Returns the curent value
 106             operator integer_type() const
 107             {
 108                 return m_nCur % m_nMod;
 109             }
 110
 111             /// Goes to next value. Returns \p false if the sequence is exhausted
 112             bool next()
 113             {
 114                 return (++m_nCur % m_nMod) != m_nStart;
 115             }
 116
 117             /// Resets the generator to produce new sequence
 118             void reset()
 119             {
 120                 m_nCur = m_nStart = integer_type( rand() ) % m_nMod;
 121             }
 122         };
 123
 124         /// Permutation generator of power-of-2 length based on \p rand()
 125         /**
 126             The class is suitable for \p opt::permutation_generator option.
 127
 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.
 132
 133             \p Int template argument specifies the type of generated value, it should be any integer.
 134         */
 135         template <typename Int=int>
 136         class random2_permutation
 137         {
 138         public:
 139             typedef Int     integer_type;   ///< Type of generated value
 140
 141         protected:
 142             //@cond
 143             integer_type        m_nCur;
 144             integer_type        m_nStart;
 145             integer_type const  m_nMask;
 146             //@endcond
 147
 148         public:
 149             /// Initializes the generator of length \p nLength
 150             /**
 151                 An assertion is raised if \p nLength is not a power of two.
 152             */
 153             random2_permutation( size_t nLength )
 154                 : m_nCur(0)
 155                 , m_nStart(0)
 156                 , m_nMask( integer_type(nLength) - 1 )
 157             {
 158                 // nLength must be power of two
 159                 assert( (nLength & (nLength - 1)) == 0 );
 160                 reset();
 161             }
 162
 163             /// Returns the current value
 164             operator integer_type() const
 165             {
 166                 return m_nCur & m_nMask;
 167             }
 168
 169             /// Goes to next value. Returns \p false if the sequence is exhausted
 170             bool next()
 171             {
 172                 return (++m_nCur & m_nMask) != m_nStart;
 173             }
 174
 175             /// Resets the generator to produce new sequence
 176             void reset()
 177             {
 178                 m_nCur = m_nStart = integer_type( rand() ) & m_nMask;
 179             }
 180         };
 181
 182         /// Permutation generator based on \p std::shuffle
 183         /**
 184             The class is suitable for \p opt::permutation_generator option.
 185
 186             The generator produces a permutation of <tt>[0, nLen)</tt> sequence.
 187             The generator instance allocates a memory block.
 188
 189             Template parameters:
 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
 193         */
 194         template <typename Int=int, class RandomGenerator = std::mt19937, class RandomDevice = std::random_device >
 195         class random_shuffle_permutation
 196         {
 197         public:
 198             typedef Int     integer_type;             ///< Type of generated value
 199             typedef RandomGenerator random_generator; ///< random generator
 200             typedef RandomDevice random_device;       ///< random device
 201
 202         protected:
 203             //@cond
 204             integer_type *      m_pCur;
 205             integer_type *      m_pFirst;
 206             integer_type *      m_pLast;
 207             //@endcond
 208
 209         public:
 210             /// Initializes the generator of arbitrary length \p nLength
 211             random_shuffle_permutation( size_t nLength )
 212                 : m_pCur( nullptr )
 213             {
 214                 m_pFirst = new integer_type[nLength];
 215                 m_pLast = m_pFirst + nLength;
 216                 std::iota(m_pFirst, m_pLast, integer_type{0} );
 217                 reset();
 218             }
 219
 220             ~random_shuffle_permutation()
 221             {
 222                 delete [] m_pFirst;
 223             }
 224
 225             /// Returns the current value
 226             operator integer_type() const
 227             {
 228                 return *m_pCur;
 229             }
 230
 231             /// Goes to next value. Returns \p false if the sequence is exhausted
 232             bool next()
 233             {
 234                 return ++m_pCur < m_pLast;
 235             }
 236
 237             /// Resets the generator to produce new sequence
 238             void reset()
 239             {
 240                 std::shuffle( m_pFirst, m_pLast, random_generator{ random_device{}() });
 241                 m_pCur = m_pFirst;
 242             }
 243         };
 244
 245         /// Skew permutation generator
 246         /**
 247             This generator produces offset permutation based on \p Generator:
 248                 <tt>int(Generator) + nOffset</tt>
 249             where \p Generator - a permutation generator.
 250
 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>
 253         */
 254         template <typename Generator>
 255         class skew_permutation
 256         {
 257         public:
 258             typedef Generator base_generator;   ///< Original permutation generator
 259             typedef typename base_generator::integer_type   integer_type; ///< Type of generated value
 260
 261         protected:
 262             //@cond
 263             base_generator      m_Gen;
 264             integer_type const  m_nOffset;
 265             //@endcond
 266
 267         public:
 268             /// Initializes the generator
 269             skew_permutation(
 270                 integer_type nOffset,   ///< The offset, i.e. first value of generated sequence
 271                 size_t nLength          ///< The length of sequence
 272                 )
 273                 : m_Gen( nLength )
 274                 , m_nOffset( nOffset )
 275             {}
 276
 277             /// Returns the current value
 278             operator integer_type() const
 279             {
 280                 return integer_type(m_Gen) + m_nOffset;
 281             }
 282
 283             /// Goes to next value. Returns \p false if the sequence is exhausted
 284             bool next()
 285             {
 286                 return m_Gen.next();
 287             }
 288
 289             /// Resets the generator to produce new sequence
 290             void reset()
 291             {
 292                 m_Gen.reset();
 293             }
 294         };
 295
 296     } // namespace v
 297
 298 }} // namespace cds::opt
 299
 300 #endif // #ifndef CDSLIB_OPT_PERMUTATION_H