1 #ifndef _DERANDOM_HPP
2 #define _DERANDOM_HPP
3 /*-------------------------------------------------------------------------
4 * drawElements C++ Base Library
5 * -----------------------------
6 *
7 * Copyright 2014 The Android Open Source Project
8 *
9 * Licensed under the Apache License, Version 2.0 (the "License");
10 * you may not use this file except in compliance with the License.
11 * You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 *
21 *//*!
22 * \file
23 * \brief Random number generator utilities.
24 *//*--------------------------------------------------------------------*/
25
26 #include "deDefs.hpp"
27 #include "deRandom.h"
28
29 #include <iterator> // std::distance()
30 #include <algorithm> // std::swap()
31
32 namespace de
33 {
34
35 //! Random self-test - compare returned values against hard-coded values.
36 void Random_selfTest (void);
37
38 class Random
39 {
40 public:
Random(deUint32 seed)41 Random (deUint32 seed) { deRandom_init(&m_rnd, seed); }
~Random(void)42 ~Random (void) {}
43
getFloat(void)44 float getFloat (void) { return deRandom_getFloat(&m_rnd); }
getDouble(void)45 double getDouble (void) { return deRandom_getDouble(&m_rnd); }
getBool(void)46 bool getBool (void) { return deRandom_getBool(&m_rnd) == DE_TRUE; }
47
48 float getFloat (float min, float max);
49 double getDouble (double min, double max);
50 int getInt (int min, int max);
51
getInt64(void)52 deInt64 getInt64 (void) { deUint32 upper = getUint32(); return static_cast<deInt64>((deUint64)upper << 32ull | (deUint64)getUint32() ); }
getUint64(void)53 deUint64 getUint64 (void) { deUint32 upper = getUint32(); return (deUint64)upper << 32ull | (deUint64)getUint32(); }
getUint32(void)54 deUint32 getUint32 (void) { return deRandom_getUint32(&m_rnd); }
getUint16(void)55 deUint16 getUint16 (void) { return (deUint16)deRandom_getUint32(&m_rnd); }
getUint8(void)56 deUint8 getUint8 (void) { return (deUint8)deRandom_getUint32(&m_rnd); }
57
58 template <class InputIter, class OutputIter>
59 void choose (InputIter first, InputIter last, OutputIter result, int numItems);
60
61 template <typename T, class InputIter>
62 T choose (InputIter first, InputIter last);
63
64 // \note Weights must be floats
65 template <typename T, class InputIter, class WeightIter>
66 T chooseWeighted (InputIter first, InputIter last, WeightIter weight);
67
68 template <class Iterator>
69 void shuffle (Iterator first, Iterator last);
70
71 bool operator== (const Random& other) const;
72 bool operator!= (const Random& other) const;
73
74 private:
75 deRandom m_rnd;
76 } DE_WARN_UNUSED_TYPE;
77
78 // Inline implementations
79
getFloat(float min,float max)80 inline float Random::getFloat (float min, float max)
81 {
82 DE_ASSERT(min <= max);
83 return min + (max-min)*getFloat();
84 }
85
getDouble(double min,double max)86 inline double Random::getDouble (double min, double max)
87 {
88 DE_ASSERT(min <= max);
89 return min + (max-min)*getDouble();
90 }
91
getInt(int min,int max)92 inline int Random::getInt (int min, int max)
93 {
94 DE_ASSERT(min <= max);
95 if (min == (int)0x80000000 && max == (int)0x7fffffff)
96 return (int)getUint32();
97 else
98 return min + (int)(getUint32() % (deUint32)(max-min+1));
99 }
100
101 // Template implementations
102
103 template <class InputIter, class OutputIter>
choose(InputIter first,InputIter last,OutputIter result,int numItems)104 void Random::choose (InputIter first, InputIter last, OutputIter result, int numItems)
105 {
106 // Algorithm: Reservoir sampling
107 // http://en.wikipedia.org/wiki/Reservoir_sampling
108 // \note Will not work for suffling an array. Use suffle() instead.
109
110 int ndx;
111 for (ndx = 0; first != last; ++first, ++ndx)
112 {
113 if (ndx < numItems)
114 *(result + ndx) = *first;
115 else
116 {
117 int r = getInt(0, ndx);
118 if (r < numItems)
119 *(result + r) = *first;
120 }
121 }
122
123 DE_ASSERT(ndx >= numItems);
124 }
125
126 template <typename T, class InputIter>
choose(InputIter first,InputIter last)127 T Random::choose (InputIter first, InputIter last)
128 {
129 T val = T();
130 DE_ASSERT(first != last);
131 choose(first, last, &val, 1);
132 return val;
133 }
134
135 template <typename T, class InputIter, class WeightIter>
chooseWeighted(InputIter first,InputIter last,WeightIter weight)136 T Random::chooseWeighted (InputIter first, InputIter last, WeightIter weight)
137 {
138 // Compute weight sum
139 float weightSum = 0.0f;
140 int ndx;
141 for (ndx = 0; (first + ndx) != last; ndx++)
142 weightSum += *(weight + ndx);
143
144 // Random point in 0..weightSum
145 float p = getFloat(0.0f, weightSum);
146
147 // Find item in range
148 InputIter lastNonZero = last;
149 float curWeight = 0.0f;
150 for (ndx = 0; (first + ndx) != last; ndx++)
151 {
152 float w = *(weight + ndx);
153
154 curWeight += w;
155
156 if (p < curWeight)
157 return *(first + ndx);
158 else if (w > 0.0f)
159 lastNonZero = first + ndx;
160 }
161
162 DE_ASSERT(lastNonZero != last);
163 return *lastNonZero;
164 }
165
166 template <class Iterator>
shuffle(Iterator first,Iterator last)167 void Random::shuffle (Iterator first, Iterator last)
168 {
169 using std::swap;
170
171 // Fisher-Yates suffle
172 int numItems = (int)std::distance(first, last);
173
174 for (int i = numItems-1; i >= 1; i--)
175 {
176 int j = getInt(0, i);
177 swap(*(first + i), *(first + j));
178 }
179 }
180
181 template<typename T> T randomScalar (de::Random& rnd, T minValue, T maxValue);
randomScalar(de::Random & rnd,float minValue,float maxValue)182 template<> inline float randomScalar (de::Random& rnd, float minValue, float maxValue) { return rnd.getFloat(minValue, maxValue); }
randomScalar(de::Random & rnd,deInt32 minValue,deInt32 maxValue)183 template<> inline deInt32 randomScalar (de::Random& rnd, deInt32 minValue, deInt32 maxValue) { return rnd.getInt(minValue, maxValue); }
randomScalar(de::Random & rnd,deUint32 minValue,deUint32 maxValue)184 template<> inline deUint32 randomScalar (de::Random& rnd, deUint32 minValue, deUint32 maxValue) { return minValue + rnd.getUint32() % (maxValue - minValue + 1); }
185
186 } // de
187
188 #endif // _DERANDOM_HPP
189