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
32namespace de
33{
34
35//! Random self-test - compare returned values against hard-coded values.
36void Random_selfTest (void);
37
38class Random
39{
40public:
41					Random				(deUint32 seed)	{ deRandom_init(&m_rnd, seed);					}
42					~Random				(void)			{}
43
44	float			getFloat			(void)			{ return deRandom_getFloat(&m_rnd);				}
45	double			getDouble			(void)			{ return deRandom_getDouble(&m_rnd);			}
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
52	deUint64		getUint64			(void)			{ deUint32 upper = getUint32(); return (deUint64)upper << 32ull | (deUint64)getUint32(); }
53	deUint32		getUint32			(void)			{ return deRandom_getUint32(&m_rnd);			}
54	deUint16		getUint16			(void)			{ return (deUint16)deRandom_getUint32(&m_rnd);	}
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
73private:
74	deRandom		m_rnd;
75};
76
77// Inline implementations
78
79inline float Random::getFloat (float min, float max)
80{
81	DE_ASSERT(min <= max);
82	return min + (max-min)*getFloat();
83}
84
85inline double Random::getDouble (double min, double max)
86{
87	DE_ASSERT(min <= max);
88	return min + (max-min)*getDouble();
89}
90
91inline 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
102template <class InputIter, class OutputIter>
103void 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
125template <typename T, class InputIter>
126T 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
134template <typename T, class InputIter, class WeightIter>
135T 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
165template <class Iterator>
166void 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} // de
181
182#endif // _DERANDOM_HPP
183