/*
 * Copyright (c) 2009 Veselin Georgiev
 *
 * Cutting the bullshit:
 *  all sources here are free software; you can use them for everything you
 *  want. Just don't blame me if something goes wrong; if something happens
 *  (including, but not limited to:
 *     coredumps, formatted harddrives, ping timeouts, winamp sound skips,
 *     fried CPUs, sudden mother-in-law visits, fraglimits, viagra spam,
 *     barking dogs, earthquakes, frog rain, Windows Vista installations,
 *     anrieff playing the bass guitar, dangerous sporks, apocalypse,
 *     concrete donkey, or even Chuck Norris getting your butt kicked...
 *  ), then you know you have been warned. Four times.
 *
 * Btw, Chuck Norris now doesn't code neither Python, nor Ruby. He's hacking
 * with Makefiles.
 */
// The Mersenne Twister class is sourced from:
// http://www.qbrundage.com/michaelb/pubs/essays/random_number_generation.html
//
// thanks to Michael Brundage!

#ifndef __MTRANDOM_H__
#define __MTRANDOM_H__
#define MT_LEN       624
#define MT_IA           397
#define MT_IB           (MT_LEN - MT_IA)
#define UPPER_MASK      0x80000000
#define LOWER_MASK      0x7FFFFFFF
#define MATRIX_A        0x9908B0DF
#define TWIST(b,i,j)    ((b)[i] & UPPER_MASK) | ((b)[j] & LOWER_MASK)
#define MAGIC(s)        (((s)&1)*MATRIX_A)

class MTRandom {
	int mt_index;
	unsigned mt_buffer[MT_LEN];
public:
	MTRandom(unsigned seed)
	{
		mt_buffer[0] = seed;
		for (unsigned i = 1; i < MT_LEN; i++)
			mt_buffer[i] = (1812433253UL * (mt_buffer[i-1] ^ (mt_buffer[i-1] >> 30)) + i);
		mt_index = 0;
	}
	unsigned next(void)
	{
		unsigned* b = mt_buffer;
		int idx = mt_index;
		unsigned s;
		int i;
		if (idx == MT_LEN*sizeof(unsigned)) {
			idx = 0;
			i = 0;
			for (; i < MT_IB; i++) {
				s = TWIST(b, i, i+1);
				b[i] = b[i + MT_IA] ^ (s >> 1) ^ MAGIC(s);
			}
			for (; i < MT_LEN-1; i++) {
				s = TWIST(b, i, i+1);
				b[i] = b[i - MT_IB] ^ (s >> 1) ^ MAGIC(s);
			}
			s = TWIST(b, MT_LEN-1, 0);
			b[MT_LEN-1] = b[MT_IA-1] ^ (s >> 1) ^ MAGIC(s);
		}
		mt_index = idx + sizeof(unsigned);
		return mt_buffer[idx/4];
	}
};

extern MTRandom rnd;

inline unsigned stl_rand(unsigned N)
{
	return rnd.next() % N;
}

#endif //__MTRANDOM_H__
