• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
getUint64(void)52 	deUint64		getUint64			(void)			{ deUint32 upper = getUint32(); return (deUint64)upper << 32ull | (deUint64)getUint32(); }
getUint32(void)53 	deUint32		getUint32			(void)			{ return deRandom_getUint32(&m_rnd);			}
getUint16(void)54 	deUint16		getUint16			(void)			{ return (deUint16)deRandom_getUint32(&m_rnd);	}
getUint8(void)55 	deUint8			getUint8			(void)			{ return (deUint8)deRandom_getUint32(&m_rnd);	}
56 
57 	template <class InputIter, class OutputIter>
58 	void			choose				(InputIter first, InputIter last, OutputIter result, int numItems);
59 
60 	template <typename T, class InputIter>
61 	T				choose				(InputIter first, InputIter last);
62 
63 	// \note Weights must be floats
64 	template <typename T, class InputIter, class WeightIter>
65 	T				chooseWeighted		(InputIter first, InputIter last, WeightIter weight);
66 
67 	template <class Iterator>
68 	void			shuffle				(Iterator first, Iterator last);
69 
70 	bool			operator==			(const Random& other) const;
71 	bool			operator!=			(const Random& other) const;
72 
73 private:
74 	deRandom		m_rnd;
75 } DE_WARN_UNUSED_TYPE;
76 
77 // Inline implementations
78 
getFloat(float min,float max)79 inline float Random::getFloat (float min, float max)
80 {
81 	DE_ASSERT(min <= max);
82 	return min + (max-min)*getFloat();
83 }
84 
getDouble(double min,double max)85 inline double Random::getDouble (double min, double max)
86 {
87 	DE_ASSERT(min <= max);
88 	return min + (max-min)*getDouble();
89 }
90 
getInt(int min,int max)91 inline int Random::getInt (int min, int max)
92 {
93 	DE_ASSERT(min <= max);
94 	if (min == (int)0x80000000 && max == (int)0x7fffffff)
95 		return (int)getUint32();
96 	else
97 		return min + (int)(getUint32() % (deUint32)(max-min+1));
98 }
99 
100 // Template implementations
101 
102 template <class InputIter, class OutputIter>
choose(InputIter first,InputIter last,OutputIter result,int numItems)103 void Random::choose (InputIter first, InputIter last, OutputIter result, int numItems)
104 {
105 	// Algorithm: Reservoir sampling
106 	// http://en.wikipedia.org/wiki/Reservoir_sampling
107 	// \note Will not work for suffling an array. Use suffle() instead.
108 
109 	int ndx;
110 	for (ndx = 0; first != last; ++first, ++ndx)
111 	{
112 		if (ndx < numItems)
113 			*(result + ndx) = *first;
114 		else
115 		{
116 			int r = getInt(0, ndx);
117 			if (r < numItems)
118 				*(result + r) = *first;
119 		}
120 	}
121 
122 	DE_ASSERT(ndx >= numItems);
123 }
124 
125 template <typename T, class InputIter>
choose(InputIter first,InputIter last)126 T Random::choose (InputIter first, InputIter last)
127 {
128 	T val = T();
129 	DE_ASSERT(first != last);
130 	choose(first, last, &val, 1);
131 	return val;
132 }
133 
134 template <typename T, class InputIter, class WeightIter>
chooseWeighted(InputIter first,InputIter last,WeightIter weight)135 T Random::chooseWeighted (InputIter first, InputIter last, WeightIter weight)
136 {
137 	// Compute weight sum
138 	float	weightSum	= 0.0f;
139 	int		ndx;
140 	for (ndx = 0; (first + ndx) != last; ndx++)
141 		weightSum += *(weight + ndx);
142 
143 	// Random point in 0..weightSum
144 	float p = getFloat(0.0f, weightSum);
145 
146 	// Find item in range
147 	InputIter	lastNonZero	= last;
148 	float		curWeight	= 0.0f;
149 	for (ndx = 0; (first + ndx) != last; ndx++)
150 	{
151 		float w = *(weight + ndx);
152 
153 		curWeight += w;
154 
155 		if (p < curWeight)
156 			return *(first + ndx);
157 		else if (w > 0.0f)
158 			lastNonZero = first + ndx;
159 	}
160 
161 	DE_ASSERT(lastNonZero != last);
162 	return *lastNonZero;
163 }
164 
165 template <class Iterator>
shuffle(Iterator first,Iterator last)166 void Random::shuffle (Iterator first, Iterator last)
167 {
168 	using std::swap;
169 
170 	// Fisher-Yates suffle
171 	int numItems = (int)std::distance(first, last);
172 
173 	for (int i = numItems-1; i >= 1; i--)
174 	{
175 		int j = getInt(0, i);
176 		swap(*(first + i), *(first + j));
177 	}
178 }
179 
180 template<typename T>	T			randomScalar	(de::Random& rnd, T minValue, T maxValue);
randomScalar(de::Random & rnd,float minValue,float maxValue)181 template<> inline		float		randomScalar	(de::Random& rnd, float minValue, float maxValue)		{ return rnd.getFloat(minValue, maxValue); }
randomScalar(de::Random & rnd,deInt32 minValue,deInt32 maxValue)182 template<> inline		deInt32		randomScalar	(de::Random& rnd, deInt32 minValue, deInt32 maxValue)	{ return rnd.getInt(minValue, maxValue); }
randomScalar(de::Random & rnd,deUint32 minValue,deUint32 maxValue)183 template<> inline		deUint32	randomScalar	(de::Random& rnd, deUint32 minValue, deUint32 maxValue)	{ return minValue + rnd.getUint32() % (maxValue - minValue + 1); }
184 
185 } // de
186 
187 #endif // _DERANDOM_HPP
188