13c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#ifndef _DERANDOM_HPP 23c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#define _DERANDOM_HPP 33c827367444ee418f129b2c238299f49d3264554Jarkko Poyry/*------------------------------------------------------------------------- 43c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * drawElements C++ Base Library 53c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * ----------------------------- 63c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * 73c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * Copyright 2014 The Android Open Source Project 83c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * 93c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * Licensed under the Apache License, Version 2.0 (the "License"); 103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * you may not use this file except in compliance with the License. 113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * You may obtain a copy of the License at 123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * 133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * http://www.apache.org/licenses/LICENSE-2.0 143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * 153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * Unless required by applicable law or agreed to in writing, software 163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * distributed under the License is distributed on an "AS IS" BASIS, 173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * See the License for the specific language governing permissions and 193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * limitations under the License. 203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * 213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry *//*! 223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * \file 233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry * \brief Random number generator utilities. 243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry *//*--------------------------------------------------------------------*/ 253c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 263c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "deDefs.hpp" 273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include "deRandom.h" 283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include <iterator> // std::distance() 303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#include <algorithm> // std::swap() 313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 323c827367444ee418f129b2c238299f49d3264554Jarkko Poyrynamespace de 333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 343c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 353c827367444ee418f129b2c238299f49d3264554Jarkko Poyry//! Random self-test - compare returned values against hard-coded values. 363c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid Random_selfTest (void); 373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 383c827367444ee418f129b2c238299f49d3264554Jarkko Poyryclass Random 393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 403c827367444ee418f129b2c238299f49d3264554Jarkko Poyrypublic: 413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry Random (deUint32 seed) { deRandom_init(&m_rnd, seed); } 423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry ~Random (void) {} 433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry float getFloat (void) { return deRandom_getFloat(&m_rnd); } 453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry double getDouble (void) { return deRandom_getDouble(&m_rnd); } 463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool getBool (void) { return deRandom_getBool(&m_rnd) == DE_TRUE; } 473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry float getFloat (float min, float max); 493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry double getDouble (double min, double max); 503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int getInt (int min, int max); 513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry deUint64 getUint64 (void) { deUint32 upper = getUint32(); return (deUint64)upper << 32ull | (deUint64)getUint32(); } 533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry deUint32 getUint32 (void) { return deRandom_getUint32(&m_rnd); } 543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry deUint16 getUint16 (void) { return (deUint16)deRandom_getUint32(&m_rnd); } 553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry deUint8 getUint8 (void) { return (deUint8)deRandom_getUint32(&m_rnd); } 563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry template <class InputIter, class OutputIter> 583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void choose (InputIter first, InputIter last, OutputIter result, int numItems); 593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry template <typename T, class InputIter> 613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry T choose (InputIter first, InputIter last); 623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // \note Weights must be floats 643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry template <typename T, class InputIter, class WeightIter> 653c827367444ee418f129b2c238299f49d3264554Jarkko Poyry T chooseWeighted (InputIter first, InputIter last, WeightIter weight); 663c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry template <class Iterator> 683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry void shuffle (Iterator first, Iterator last); 693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool operator== (const Random& other) const; 713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry bool operator!= (const Random& other) const; 723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 733c827367444ee418f129b2c238299f49d3264554Jarkko Poyryprivate: 743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry deRandom m_rnd; 753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry}; 763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Inline implementations 783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 793c827367444ee418f129b2c238299f49d3264554Jarkko Poyryinline float Random::getFloat (float min, float max) 803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry DE_ASSERT(min <= max); 823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return min + (max-min)*getFloat(); 833c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 843c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 853c827367444ee418f129b2c238299f49d3264554Jarkko Poyryinline double Random::getDouble (double min, double max) 863c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 873c827367444ee418f129b2c238299f49d3264554Jarkko Poyry DE_ASSERT(min <= max); 883c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return min + (max-min)*getDouble(); 893c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 903c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 913c827367444ee418f129b2c238299f49d3264554Jarkko Poyryinline int Random::getInt (int min, int max) 923c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 933c827367444ee418f129b2c238299f49d3264554Jarkko Poyry DE_ASSERT(min <= max); 943c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (min == (int)0x80000000 && max == (int)0x7fffffff) 953c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return (int)getUint32(); 963c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 973c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return min + (int)(getUint32() % (deUint32)(max-min+1)); 983c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 993c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1003c827367444ee418f129b2c238299f49d3264554Jarkko Poyry// Template implementations 1013c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1023c827367444ee418f129b2c238299f49d3264554Jarkko Poyrytemplate <class InputIter, class OutputIter> 1033c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid Random::choose (InputIter first, InputIter last, OutputIter result, int numItems) 1043c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 1053c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Algorithm: Reservoir sampling 1063c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // http://en.wikipedia.org/wiki/Reservoir_sampling 1073c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // \note Will not work for suffling an array. Use suffle() instead. 1083c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1093c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int ndx; 1103c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (ndx = 0; first != last; ++first, ++ndx) 1113c827367444ee418f129b2c238299f49d3264554Jarkko Poyry { 1123c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (ndx < numItems) 1133c827367444ee418f129b2c238299f49d3264554Jarkko Poyry *(result + ndx) = *first; 1143c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else 1153c827367444ee418f129b2c238299f49d3264554Jarkko Poyry { 1163c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int r = getInt(0, ndx); 1173c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (r < numItems) 1183c827367444ee418f129b2c238299f49d3264554Jarkko Poyry *(result + r) = *first; 1193c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 1203c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 1213c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1223c827367444ee418f129b2c238299f49d3264554Jarkko Poyry DE_ASSERT(ndx >= numItems); 1233c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 1243c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1253c827367444ee418f129b2c238299f49d3264554Jarkko Poyrytemplate <typename T, class InputIter> 1263c827367444ee418f129b2c238299f49d3264554Jarkko PoyryT Random::choose (InputIter first, InputIter last) 1273c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 1283c827367444ee418f129b2c238299f49d3264554Jarkko Poyry T val = T(); 1293c827367444ee418f129b2c238299f49d3264554Jarkko Poyry DE_ASSERT(first != last); 1303c827367444ee418f129b2c238299f49d3264554Jarkko Poyry choose(first, last, &val, 1); 1313c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return val; 1323c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 1333c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1343c827367444ee418f129b2c238299f49d3264554Jarkko Poyrytemplate <typename T, class InputIter, class WeightIter> 1353c827367444ee418f129b2c238299f49d3264554Jarkko PoyryT Random::chooseWeighted (InputIter first, InputIter last, WeightIter weight) 1363c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 1373c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Compute weight sum 1383c827367444ee418f129b2c238299f49d3264554Jarkko Poyry float weightSum = 0.0f; 1393c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int ndx; 1403c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (ndx = 0; (first + ndx) != last; ndx++) 1413c827367444ee418f129b2c238299f49d3264554Jarkko Poyry weightSum += *(weight + ndx); 1423c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1433c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Random point in 0..weightSum 1443c827367444ee418f129b2c238299f49d3264554Jarkko Poyry float p = getFloat(0.0f, weightSum); 1453c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1463c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Find item in range 1473c827367444ee418f129b2c238299f49d3264554Jarkko Poyry InputIter lastNonZero = last; 1483c827367444ee418f129b2c238299f49d3264554Jarkko Poyry float curWeight = 0.0f; 1493c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (ndx = 0; (first + ndx) != last; ndx++) 1503c827367444ee418f129b2c238299f49d3264554Jarkko Poyry { 1513c827367444ee418f129b2c238299f49d3264554Jarkko Poyry float w = *(weight + ndx); 1523c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1533c827367444ee418f129b2c238299f49d3264554Jarkko Poyry curWeight += w; 1543c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1553c827367444ee418f129b2c238299f49d3264554Jarkko Poyry if (p < curWeight) 1563c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return *(first + ndx); 1573c827367444ee418f129b2c238299f49d3264554Jarkko Poyry else if (w > 0.0f) 1583c827367444ee418f129b2c238299f49d3264554Jarkko Poyry lastNonZero = first + ndx; 1593c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 1603c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1613c827367444ee418f129b2c238299f49d3264554Jarkko Poyry DE_ASSERT(lastNonZero != last); 1623c827367444ee418f129b2c238299f49d3264554Jarkko Poyry return *lastNonZero; 1633c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 1643c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1653c827367444ee418f129b2c238299f49d3264554Jarkko Poyrytemplate <class Iterator> 1663c827367444ee418f129b2c238299f49d3264554Jarkko Poyryvoid Random::shuffle (Iterator first, Iterator last) 1673c827367444ee418f129b2c238299f49d3264554Jarkko Poyry{ 1683c827367444ee418f129b2c238299f49d3264554Jarkko Poyry using std::swap; 1693c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1703c827367444ee418f129b2c238299f49d3264554Jarkko Poyry // Fisher-Yates suffle 1713c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int numItems = (int)std::distance(first, last); 1723c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1733c827367444ee418f129b2c238299f49d3264554Jarkko Poyry for (int i = numItems-1; i >= 1; i--) 1743c827367444ee418f129b2c238299f49d3264554Jarkko Poyry { 1753c827367444ee418f129b2c238299f49d3264554Jarkko Poyry int j = getInt(0, i); 1763c827367444ee418f129b2c238299f49d3264554Jarkko Poyry swap(*(first + i), *(first + j)); 1773c827367444ee418f129b2c238299f49d3264554Jarkko Poyry } 1783c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} 1793c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1803c827367444ee418f129b2c238299f49d3264554Jarkko Poyry} // de 1813c827367444ee418f129b2c238299f49d3264554Jarkko Poyry 1823c827367444ee418f129b2c238299f49d3264554Jarkko Poyry#endif // _DERANDOM_HPP 183