// random.h - v1.0.2
/* 
 * Copyright (c) 2008 Leigh Johnston.  All Rights Reserved.
 *
 * Permission to use, copy, modify and distribute this
 * software and its documentation for any purpose is hereby
 * granted, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * The author makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

#ifndef LIB_RANDOM
#define LIB_RANDOM

namespace lib 
{
	class mersenne_twister
	{
	public:
		// types
		typedef unsigned int value_type;
	private:
		typedef size_t size_type;
		enum { N = 624 };
	public:
		// construction
		mersenne_twister(value_type aSeed = 0)
		{
			seed(aSeed);
		}
	public:
		// operations
		void seed(value_type aSeed) 
		{
			iMT[0] = aSeed;
			for (size_type i = 1; i <= (N-1); ++i)
				iMT[i] = 0x6c078965 * (iMT[i-1] ^ iMT[i-1]>>30) + i;
			iIndex = N;
		}
		value_type get(value_type aUpper) 
		{
			if (iIndex == N)
				generate();

			value_type y = iMT[iIndex++];
			y = y ^ (y >> 11);
			y = y ^ ((y << 7) & (0x9d2c5680));
			y = y ^ ((y << 15) & (0xefc60000));
			y = y ^ (y >> 18);
			return aUpper < maximum_value() ? y % (aUpper + 1) : y;
		}
		value_type get(value_type aLower, value_type aUpper)
		{
			if (aUpper <= aLower)
				return aLower;
			return get(aUpper - aLower) + aLower;
		}
		double getf(double aUpper)
		{
			return (static_cast<double>(get(maximum_value())) / maximum_value()) * aUpper;
		}
		double getf(double aLower, double aUpper)
		{
			if (aUpper <= aLower)
				return aLower;
			return getf(aUpper - aLower) + aLower;
		}
	private:
		// implementation
		value_type maximum_value()
		{
			return 0xffffffff;
		}
		void generate() 
		{
			for (size_type i = 0; i <= (N-1); ++i) 
			{
				value_type y = (iMT[i]>>31) + (iMT[(i+1)%N]>>1);
				if (y & 1)
					iMT[i] = iMT[(i + 397) % N] ^ (y>>1);
				else
					iMT[i] = iMT[(i + 397) % N] ^ (y>>1) ^ (0x9908b0df);
			}
			iIndex = 0;
		}
	private:
		// attributes 
		value_type iMT[N];
		size_type iIndex;
	};

	typedef mersenne_twister random;

	template <typename T>
	struct primes
	{
		static const T sPrimes[];
	};

	template <typename T>
	const T primes<T>::sPrimes[] = 
	{
		2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
		37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
		83, 89, 97, 103, 109, 113, 127, 137, 139, 149,
		157, 167, 179, 193, 199, 211, 227, 241, 257,
		277, 293, 313, 337, 359, 383, 409, 439, 467,
		503, 541, 577, 619, 661, 709, 761, 823, 887,
		953, 1031, 1109, 1193, 1289, 1381, 1493, 1613,
		1741, 1879, 2029, 2179, 2357, 2549, 2753, 2971,
		3209, 3469, 3739, 4027, 4349, 4703, 5087, 5503,
		5953, 6427, 6949, 7517, 8123, 8783, 9497, 10273,
		11113, 12011, 12983, 14033, 15173, 16411, 17749,
		19183, 20753, 22447, 24281, 26267, 28411, 30727,
		33223, 35933, 38873, 42043, 45481, 49201, 53201,
		57557, 62233, 67307, 72817, 78779, 85229, 92203,
		99733, 107897, 116731, 126271, 136607, 147793,
		159871, 172933, 187091, 202409, 218971, 236897,
		256279, 277261, 299951, 324503, 351061, 379787,
		410857, 444487, 480881, 520241, 562841, 608903,
		658753, 712697, 771049, 834181, 902483, 976369,
		1056323, 1142821, 1236397, 1337629, 1447153, 1565659,
		1693859, 1832561, 1982627, 2144977, 2320627, 2510653,
		2716249, 2938679, 3179303, 3439651, 3721303, 4026031,
		4355707, 4712381, 5098259, 5515729, 5967347, 6456007,
		6984629, 7556579, 8175383, 8844859, 9569143, 10352717,
		11200489, 12117689, 13109983, 14183539, 15345007,
		16601593, 17961079, 19431899, 21023161, 22744717,
		24607243, 26622317, 28802401, 31160981, 33712729,
		36473443, 39460231, 42691603, 46187573, 49969847,
		54061849, 58488943, 63278561, 68460391, 74066549,
		80131819, 86693767, 93793069, 101473717, 109783337,
		118773397, 128499677, 139022417, 150406843, 162723577,
		176048909, 190465427, 206062531, 222936881, 241193053,
		260944219, 282312799, 305431229, 330442829, 357502601,
		386778277, 418451333, 452718089, 489790921, 529899637,
		573292817, 620239453, 671030513, 725980837, 785430967,
		849749479, 919334987, 994618837, 1076067617, 1164186217,
		1259520799, 1362662261, 1474249943, 1594975441,
		1725587117, 1866894511, 2019773507, 2185171673,
		2364114217, 2557710269, 2767159799, 2993761039,
		3238918481, 3504151727, 3791104843, 4101556399,
		4294967291
	};

	class random_traversal
	{
	public:
		// types
		typedef unsigned int value_type;
	public:
		// construction
		random_traversal(random& aRandom, value_type aNumElements) : iNumElements(aNumElements), iCurrentPosition(0), iSearches(0)
		{
			const value_type* nextPrime = primes<value_type>::sPrimes;
			while(*nextPrime < iNumElements)
				nextPrime++;
			iPrime = *nextPrime;
			value_type a = aRandom.get(1, 13);
			value_type b = aRandom.get(1, 7);
			value_type c = aRandom.get(1, 5);
			iCurrentPosition = aRandom.get(iNumElements-1);
			iSkip = (a * iNumElements * iNumElements) + (b * iNumElements) + c;
			iSkip &= ~0xC0000000;
			if (iSkip % iPrime == 0)
				iSkip++;
		}
		// operations
		bool done() const { return iSearches == iPrime || iNumElements == 0; }
		unsigned int percent() const { return iSearches * 100 / iPrime; }
		int next()
		{
			if (done())
				return -1;

			bool found = false;
			value_type nextPosition = iCurrentPosition;
			while (!found)
			{
				nextPosition = nextPosition + iSkip;
				nextPosition %= iPrime;
				iSearches++;
				if (nextPosition < iNumElements)
				{
					iCurrentPosition = nextPosition;
					found = true;
				}
			}
			return iCurrentPosition;
		}
	private:
		// attributes
		value_type iNumElements;
		value_type iPrime;
		value_type iSkip;
		value_type iCurrentPosition;
		value_type iSearches;
	};
}


#endif // LIB_RANDOM