cds/opt/permutation.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_OPT_PERMUTATION_H
  32 #define CDSLIB_OPT_PERMUTATION_H
  33
  34 #include <cstdlib> // rand, srand
  35 #include <random>
  36 #include <algorithm> // std::shuffle
  37 #include <numeric>   // std::iota
  38
  39 #include <cds/opt/options.h>
  40
  41 namespace cds { namespace opt {
  42
  43     /// [type-option] Random permutation generator option setter
  44     /**
  45         The class represents permutation generator of unique integers from <tt> [0, nLength) </tt>
  46         (\p nLenght is not included) in random order.
  47
  48         The generator interface is:
  49         \code
  50         class generator {
  51             // Initializes the generator of length nLength
  52             generator( size_t nLength );
  53
  54             // Returns current value
  55             operator int();
  56
  57             // Goes to next value. Returns false if the permutation is exchausted
  58             bool next();
  59
  60             // Resets the generator to produce the new sequence
  61             void reset();
  62         };
  63         \endcode
  64
  65         <b>Usage example</b>
  66
  67         The permutation generator is intended for <tt>do {} while</tt> loop:
  68         \code
  69         permutation_generator gen( 16 );
  70         int i = gen.begin();
  71         do {
  72             int i = gen;
  73             //...
  74         } while ( gen.next());
  75
  76         // Get other permutation
  77         gen.reset();
  78         do {
  79             int i = gen;
  80             //...
  81         } while ( gen.next());
  82         \endcode
  83
  84         The following \p Generator defined:
  85         - \p opt::v::random_permutation
  86         - \p opt::v::random2_permutation
  87         - \p opt::v::random_shuffle_permutation
  88         - \p opt::v::skew_permutation
  89     */
  90     template <typename Generator>
  91     struct permutation_generator {
  92         //@cond
  93         template <typename Base> struct pack: public Base
  94         {
  95             typedef Generator permutation_generator;
  96         };
  97         //@endcond
  98     };
  99
 100     namespace v {
 101
 102         /// Permutation generator of arbitrary length based on \p rand()
 103         /**
 104             The class is suitable for \p opt::permutation_generator option.
 105
 106             The generator calculates <tt>n = rand()</tt> and produces the sequence
 107             <tt>[n % nLen, (n + 1) % nLen, ..., (n + nLen - 1) % nLen]</tt>.
 108             The generator does not allocate any memory.
 109
 110             \p Int template argument specifies the type of generated value, it should be any integer.
 111         */
 112         template <typename Int=int>
 113         class random_permutation
 114         {
 115         public:
 116             typedef Int     integer_type;   ///< Type of generated value
 117         protected:
 118             //@cond
 119             integer_type        m_nCur;
 120             integer_type        m_nStart;
 121             integer_type const  m_nMod;
 122             //@endcond
 123
 124         public:
 125             /// Initializes the generator of arbitrary length \p nLength
 126             random_permutation( size_t nLength )
 127                 : m_nCur(0)
 128                 , m_nStart(0)
 129                 , m_nMod( integer_type(nLength))
 130             {
 131                 reset();
 132             }
 133
 134             /// Returns the curent value
 135             operator integer_type() const
 136             {
 137                 return m_nCur % m_nMod;
 138             }
 139
 140             /// Goes to next value. Returns \p false if the sequence is exhausted
 141             bool next()
 142             {
 143                 return (++m_nCur % m_nMod) != m_nStart;
 144             }
 145
 146             /// Resets the generator to produce new sequence
 147             void reset()
 148             {
 149                 m_nCur = m_nStart = integer_type( std::rand()) % m_nMod;
 150             }
 151         };
 152
 153         /// Permutation generator of power-of-2 length based on \p rand()
 154         /**
 155             The class is suitable for \p opt::permutation_generator option.
 156
 157             The generator calculates <tt>n = rand()</tt> and produces the sequence
 158             <tt>[n % nLen, (n + 1) % nLen, ..., (n + nLen - 1) % nLen]</tt>.
 159             The generator does not allocate any memory.
 160             \p nLen must be power of two.
 161
 162             \p Int template argument specifies the type of generated value, it should be any integer.
 163         */
 164         template <typename Int=int>
 165         class random2_permutation
 166         {
 167         public:
 168             typedef Int     integer_type;   ///< Type of generated value
 169
 170         protected:
 171             //@cond
 172             integer_type        m_nCur;
 173             integer_type        m_nStart;
 174             integer_type const  m_nMask;
 175             //@endcond
 176
 177         public:
 178             /// Initializes the generator of length \p nLength
 179             /**
 180                 An assertion is raised if \p nLength is not a power of two.
 181             */
 182             random2_permutation( size_t nLength )
 183                 : m_nCur(0)
 184                 , m_nStart(0)
 185                 , m_nMask( integer_type(nLength) - 1 )
 186             {
 187                 // nLength must be power of two
 188                 assert( (nLength & (nLength - 1)) == 0 );
 189                 reset();
 190             }
 191
 192             /// Returns the current value
 193             operator integer_type() const
 194             {
 195                 return m_nCur & m_nMask;
 196             }
 197
 198             /// Goes to next value. Returns \p false if the sequence is exhausted
 199             bool next()
 200             {
 201                 return (++m_nCur & m_nMask) != m_nStart;
 202             }
 203
 204             /// Resets the generator to produce new sequence
 205             void reset()
 206             {
 207                 m_nCur = m_nStart = integer_type( std::rand()) & m_nMask;
 208             }
 209         };
 210
 211         /// Permutation generator based on \p std::shuffle
 212         /**
 213             The class is suitable for \p opt::permutation_generator option.
 214
 215             The generator produces a permutation of <tt>[0, nLen)</tt> sequence.
 216             The generator instance allocates a memory block.
 217
 218             Template parameters:
 219             - \p Int - specifies the type of generated value, it should be any integer.
 220             - \p RandomGenerator - random generator, default is \p std::mt19937
 221             - \p RandomDevice - random device, default is \p std::random_device
 222         */
 223         template <typename Int=int, class RandomGenerator = std::mt19937, class RandomDevice = std::random_device >
 224         class random_shuffle_permutation
 225         {
 226         public:
 227             typedef Int     integer_type;             ///< Type of generated value
 228             typedef RandomGenerator random_generator; ///< random generator
 229             typedef RandomDevice random_device;       ///< random device
 230
 231         protected:
 232             //@cond
 233             integer_type *      m_pCur;
 234             integer_type *      m_pFirst;
 235             integer_type *      m_pLast;
 236             //@endcond
 237
 238         public:
 239             /// Initializes the generator of arbitrary length \p nLength
 240             random_shuffle_permutation( size_t nLength )
 241                 : m_pCur( nullptr )
 242             {
 243                 m_pFirst = new integer_type[nLength];
 244                 m_pLast = m_pFirst + nLength;
 245                 std::iota(m_pFirst, m_pLast, integer_type{0} );
 246                 reset();
 247             }
 248
 249             ~random_shuffle_permutation()
 250             {
 251                 delete [] m_pFirst;
 252             }
 253
 254             /// Returns the current value
 255             operator integer_type() const
 256             {
 257                 return *m_pCur;
 258             }
 259
 260             /// Goes to next value. Returns \p false if the sequence is exhausted
 261             bool next()
 262             {
 263                 return ++m_pCur < m_pLast;
 264             }
 265
 266             /// Resets the generator to produce new sequence
 267             void reset()
 268             {
 269                 std::shuffle( m_pFirst, m_pLast, random_generator{ random_device{}() });
 270                 m_pCur = m_pFirst;
 271             }
 272         };
 273
 274         /// Skew permutation generator
 275         /**
 276             This generator produces offset permutation based on \p Generator:
 277                 <tt>int(Generator) + nOffset</tt>
 278             where \p Generator - a permutation generator.
 279
 280             The class is suitable for \p opt::permutation_generator option
 281             if the goal sequence should be a permutation of <tt>[nOffset, nOffset + nLength)</tt>
 282         */
 283         template <typename Generator>
 284         class skew_permutation
 285         {
 286         public:
 287             typedef Generator base_generator;   ///< Original permutation generator
 288             typedef typename base_generator::integer_type   integer_type; ///< Type of generated value
 289
 290         protected:
 291             //@cond
 292             base_generator      m_Gen;
 293             integer_type const  m_nOffset;
 294             //@endcond
 295
 296         public:
 297             /// Initializes the generator
 298             skew_permutation(
 299                 integer_type nOffset,   ///< The offset, i.e. first value of generated sequence
 300                 size_t nLength          ///< The length of sequence
 301                 )
 302                 : m_Gen( nLength )
 303                 , m_nOffset( nOffset )
 304             {}
 305
 306             /// Returns the current value
 307             operator integer_type() const
 308             {
 309                 return integer_type(m_Gen) + m_nOffset;
 310             }
 311
 312             /// Goes to next value. Returns \p false if the sequence is exhausted
 313             bool next()
 314             {
 315                 return m_Gen.next();
 316             }
 317
 318             /// Resets the generator to produce new sequence
 319             void reset()
 320             {
 321                 m_Gen.reset();
 322             }
 323         };
 324
 325     } // namespace v
 326
 327 }} // namespace cds::opt
 328
 329 #endif // #ifndef CDSLIB_OPT_PERMUTATION_H