ACE/tests/randomize.h

   1 // -*- C++ -*-
   2
   3 // ============================================================================
   4 /**
   5  * @file randomize.h
   6  *
   7  * Randomize the contents of an array.
   8  *
   9  * @author Ossama Othman
  10  *
  11  * @note Based on code originally found in test_config.h and Test_Output.cpp
  12  */
  13 // ============================================================================
  14
  15 #ifndef ACE_TESTS_RANDOMIZE_H
  16 #define ACE_TESTS_RANDOMIZE_H
  17
  18 #include "ace/OS_NS_stdlib.h"
  19
  20 #include <algorithm>
  21 #include <functional>
  22
  23 namespace
  24 {
  25   /**
  26    * @class randomize_index
  27    *
  28    * @brief Functor that randomly swaps the order of two array
  29    *        elements.
  30    *
  31    * @internal Do not directly use this class.  Use the @c randomize()
  32    *           function template found below instead.
  33    *
  34    * This functor generates random array index using high-order bits (e.g.,
  35    * MAX_VAL * rand() / (RAND_MAX + 1.0)) rather than low-order ones
  36    * (e.g. rand() % MAX_VAL) to improve randomness.  The array element
  37    * reference by that index is then swapped with the array element
  38    * provided to the functor.
  39    *
  40    * @note The improved randomness may be overkill for this functor's
  41    *       intended use cases, but it is a good thing to practice/have
  42    *       nonetheless.
  43    *
  44    * @see Numerical Recipes in C: The Art of Scientific Computing
  45    *      (William H. Press, Brian P. Flannery, Saul A. Teukolsky,
  46    *      William T. Vetterling; New York: Cambridge University Press,
  47    *      1992 (2nd ed., p. 277).
  48    */
  49   template<typename T>
  50   class randomize_element
  51   {
  52   public:
  53     typedef T &argument_type;
  54     typedef void result_type;
  55
  56     randomize_element (T * array, size_t size, unsigned int seed)
  57       : array_ (array)
  58       , coefficient_ (static_cast<double> (size) / (RAND_MAX + 1.0f))
  59       , seed_ (seed)
  60     {
  61     }
  62
  63     void
  64     operator() (T & value)    // We need this to be a reference!
  65     {
  66       size_t const index =
  67         static_cast<size_t> (
  68           this->coefficient_ * ACE_OS::rand_r (&this->seed_));
  69
  70       // Swap rather than assign so that we don't lose the original
  71       // value.
  72       std::swap (value, this->array_[index]);
  73     }
  74
  75   private:
  76
  77     // The array.
  78     T * const array_;
  79
  80     // Factor out the constant coefficient.
  81     double const coefficient_;
  82
  83     // Random number generator seed value.
  84     unsigned int seed_;
  85
  86   };
  87
  88   /**
  89    * @fn randomize
  90    *
  91    * @brief Randomize the order of elements in an array.
  92    *
  93    * @param array The array whose elements will be reordered
  94    *              randomly.
  95    * @param size  The number of elements in the array.
  96    * @param seed  The random number generator seed value.  A default
  97    *              value is provided so that the generated random
  98                   number order may be "repeatable" if so desired.
  99    *
 100    * This function template randomizes the order of elements in an
 101    * array of any type.  It is also reentrant (unless the array itself
 102    * is accessed by multiple threads).
 103    * @par
 104    * Sample usage:
 105    * @par
 106    * \verbatim
 107      static size_t const NUM_TIMES = 100;
 108      ACE_Time_Value times[NUM_TIMES] = { ... };
 109      randomize (times,
 110                 NUM_TIMES,
 111                 static_cast<unsigned int> (ACE_OS::time (0L)));
 112     \endverbatim
 113    */
 114   template<typename T>
 115   void
 116   randomize (T * array, size_t size, unsigned int seed = 0)
 117   {
 118     // Randomize all elements of the array.
 119     std::for_each (array,
 120                    array + size,
 121                    randomize_element<T> (array, size, seed));
 122   }
 123 }
 124
 125 #endif  /* !ACE_TESTS_RANDOMIZE_H */