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: 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 73 private: 74 deRandom m_rnd; 75 } DE_WARN_UNUSED_TYPE; 76 77 // Inline implementations 78 79 inline float Random::getFloat (float min, float max) 80 { 81 DE_ASSERT(min <= max); 82 return min + (max-min)*getFloat(); 83 } 84 85 inline double Random::getDouble (double min, double max) 86 { 87 DE_ASSERT(min <= max); 88 return min + (max-min)*getDouble(); 89 } 90 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> 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> 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> 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> 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 } // de 181 182 #endif // _DERANDOM_HPP 183
