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