git.maemo.org Git - opencv/blob - 3rdparty/include/flann/random.h

   1 /***********************************************************************
   2  * Software License Agreement (BSD License)
   3  *
   4  * Copyright 2008-2009  Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
   5  * Copyright 2008-2009  David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
   6  *
   7  * THE BSD LICENSE
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *************************************************************************/
  30
  31 #ifndef RANDOM_H
  32 #define RANDOM_H
  33
  34 #include <algorithm>
  35 #include <cstdlib>
  36 #include <cassert>
  37
  38 using namespace std;
  39
  40 namespace flann
  41 {
  42
  43 /**
  44  * Seeds the random number generator
  45  */
  46 void seed_random(unsigned int seed);
  47
  48 /*
  49  * Generates a random double value.
  50  */
  51 double rand_double(double high = 1.0, double low=0);
  52
  53 /*
  54  * Generates a random integer value.
  55  */
  56 int rand_int(int high = RAND_MAX, int low = 0);
  57
  58
  59 /**
  60  * Random number generator that returns a distinct number from
  61  * the [0,n) interval each time.
  62  *
  63  * TODO: improve on this to use a generator function instead of an
  64  * array of randomly permuted numbers
  65  */
  66 class UniqueRandom
  67 {
  68         int* vals;
  69     int size;
  70         int counter;
  71
  72 public:
  73         /**
  74          * Constructor.
  75          * Params:
  76          *     n = the size of the interval from which to generate
  77          *              random numbers.
  78          */
  79         UniqueRandom(int n) : vals(NULL) {
  80                 init(n);
  81         }
  82
  83         ~UniqueRandom()
  84         {
  85                 delete[] vals;
  86         }
  87
  88         /**
  89          * Initializes the number generator.
  90          * Params:
  91          *              n = the size of the interval from which to generate
  92          *              random numbers.
  93          */
  94         void init(int n)
  95         {
  96         // create and initialize an array of size n
  97                 if (vals == NULL || n!=size) {
  98             delete[] vals;
  99                 size = n;
 100             vals = new int[size];
 101         }
 102         for(int i=0;i<size;++i) {
 103                         vals[i] = i;
 104                 }
 105
 106                 // shuffle the elements in the array
 107         // Fisher-Yates shuffle
 108                 for (int i=size;i>0;--i) {
 109 //                      int rand = cast(int) (drand48() * n);
 110                         int rnd = rand_int(i);
 111                         assert(rnd >=0 && rnd < i);
 112                         swap(vals[i-1], vals[rnd]);
 113                 }
 114
 115                 counter = 0;
 116         }
 117
 118         /**
 119          * Return a distinct random integer in greater or equal to 0 and less
 120          * than 'n' on each call. It should be called maximum 'n' times.
 121          * Returns: a random integer
 122          */
 123         int next() {
 124                 if (counter==size) {
 125                         return -1;
 126                 } else {
 127                         return vals[counter++];
 128                 }
 129         }
 130 };
 131
 132 }
 133
 134 #endif //RANDOM_H