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