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         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