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