Random.hh

#ifndef Random_hh
#define Random_hh


#include "Utils.hh"


/**
 * Defines a random generator used by Board, (Sec)Game and Player.
 */
class Random_generator {

  friend class Board;
  friend class Game;
  friend class SecGame;

  static const long long RANDOM_MOD = ((long long)1)<<31;
  static const long long RANDOM_MASC = RANDOM_MOD - 1;

  long long rnd_seed;

  /**
   * Sets random seed.
   */
  void set_random_seed (int s) {
    if (s < 0) s = -s;
    rnd_seed = s&RANDOM_MASC;
  }

  /**
   * Computes next seed from current seed.
   */
  void next_rnd () {
    rnd_seed = (843314861*rnd_seed + 453816693)&RANDOM_MASC;
  }

  /**
   * Returns a real random number in [0, 1).
   */
  double uniform () {
    next_rnd();
    return double(rnd_seed)/RANDOM_MOD;
  }

public:

  /**
   * Returns a random integer in [l..u]. u - l + 1 must be between 1 and 10^6.
   */
  int random (int l, int u) {
    if (l > u) return l; // wrong interval

    long long m = (long long)u - (long long)l + 1;
    if (m > 1e6) return l; // interval too long

    next_rnd();
    return l + int((u - l + 1)*uniform());
  }

  /**
   * Returns a random permutation of [0..n-1]. n must be between 0 and 10^6.
   */
  inline vector<int> random_permutation (int n) {
    if (n < 0 or n > 1e6) return vector<int>(0); // wrong n

    vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = i;
    for (int i = 0; i < n - 1; ++i) swap(v[i], v[random(i, n - 1)]);
    return v;
  }

};


#endif