framework/delibs/decpp/deRandom.hpp

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