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 <algorithm> // random_shuffle
   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 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 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::random_shuffle
 180         /**
 181             The class is suitable for opt::permutation_generator option.
 182
 183             The generator produces a permutation of [0, nLen) sequence.
 184             The generator instance allocates a memory block.
 185
 186             \p Int template argument specifies the type of generated value, it should be any integer.
 187         */
 188         template <typename Int=int>
 189         class random_shuffle_permutation
 190         {
 191         public:
 192             typedef Int     integer_type;   ///< Type of generated value
 193
 194         protected:
 195             //@cond
 196             integer_type *      m_pCur;
 197             integer_type *      m_pFirst;
 198             integer_type *      m_pLast;
 199             //@endcond
 200
 201         public:
 202             /// Initializes the generator of arbitrary length \p nLength
 203             random_shuffle_permutation( size_t nLength )
 204                 : m_pCur( nullptr )
 205             {
 206                 m_pFirst = new integer_type[nLength];
 207                 m_pLast = m_pFirst + nLength;
 208                 for ( integer_type i = 0; i < static_cast<integer_type>(nLength); ++i )
 209                     m_pFirst[i] = i;
 210                 reset();
 211             }
 212
 213             ~random_shuffle_permutation()
 214             {
 215                 delete [] m_pFirst;
 216             }
 217
 218             /// Returns the current value
 219             operator integer_type() const
 220             {
 221                 return *m_pCur;
 222             }
 223
 224             /// Goes to next value. Returns \p false if the sequence is exhausted
 225             bool next()
 226             {
 227                 return ++m_pCur < m_pLast;
 228             }
 229
 230             /// Resets the generator to produce new sequence
 231             void reset()
 232             {
 233                 std::random_shuffle( m_pFirst, m_pLast );
 234                 m_pCur = m_pFirst;
 235             }
 236         };
 237
 238         /// Skew permutation generator
 239         /**
 240             This generator produces offset permutation based on \p Generator:
 241                 <tt>int(Generator) + nOffset</tt>
 242             where \p Generator - a permutation generator.
 243
 244             The class is suitable for opt::permutation_generator option
 245             if the goal sequence should be a permutation of <tt>[nOffset, nOffset + nLength)</tt>
 246         */
 247         template <typename Generator>
 248         class skew_permutation
 249         {
 250         public:
 251             typedef Generator base_generator;   ///< Original permutation generator
 252             typedef typename base_generator::integer_type   integer_type; ///< Type of generated value
 253
 254         protected:
 255             //@cond
 256             base_generator      m_Gen;
 257             integer_type const  m_nOffset;
 258             //@endcond
 259
 260         public:
 261             /// Initializes the generator
 262             skew_permutation(
 263                 integer_type nOffset,   ///< The offset, i.e. first value of generated sequence
 264                 size_t nLength          ///< The length of sequence
 265                 )
 266                 : m_Gen( nLength )
 267                 , m_nOffset( nOffset )
 268             {}
 269
 270             /// Returns the current value
 271             operator integer_type() const
 272             {
 273                 return integer_type(m_Gen) + m_nOffset;
 274             }
 275
 276             /// Goes to next value. Returns \p false if the sequence is exhausted
 277             bool next()
 278             {
 279                 return m_Gen.next();
 280             }
 281
 282             /// Resets the generator to produce new sequence
 283             void reset()
 284             {
 285                 m_Gen.reset();
 286             }
 287         };
 288
 289     } // namespace v
 290
 291 }} // namespace cds::opt
 292
 293 #endif // #ifndef CDSLIB_OPT_PERMUTATION_H