cds/opt/permutation.h

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