/**
* Mersenne Twister
*/

package
{

	public class MersenneTwister
	{
		private static const N:int = 624;
		private static const M:int = 397;
		private static const MATRIX_A:uint   = 0x9908b0df;
		private static const UPPER_MASK:uint = 0x80000000;
		private static const LOWER_MASK:uint = 0x7fffffff;
		
		private var mt:Array = new Array(N);
		private var mti:int = N+1;
		
		private var mag01:Array = [0x0, MATRIX_A];
		
		public function MersenneTwister()
		{
			
		}
		
		//---------------------------------------------------------------------------------------------------INIT
		/**
		 * @private
		 */
		public function init_genrand( seed:uint ):void
		{
			mti = 0;
			mt[0]= seed & 0xffffffff;
			for( mti=1; mti<N; mti++ ){
				mt[mti] = $multi(1812433253 , (mt[mti-1]^(mt[mti-1] >>> 30))) + mti;
				mt[mti] &= 0xffffffff;
			}
		}
		
		/**
		 * @private
		 */
		public function init_by_array( init_key:Array ):void
		{
			var key_length:uint = init_key.length;
			var i:int;
			var j:int;
			var k:int;
			
			init_genrand(19650218);
			i=1; j=0;
			k = (N>key_length ? N : key_length);
			for (; k; k--)
			{
				mt[i] = (mt[i]^$multi((mt[i-1]^(mt[i-1] >>> 30)) , 1664525)) + init_key[j] + j;
				mt[i] &= 0xffffffff;
				i++; j++;
				if (i>=N) { mt[0] = mt[N-1]; i=1; }
				if (j>=key_length) j=0;
			}
			for (k = N - 1; k; k--)
			{
				mt[i] = (mt[i]^$multi((mt[i-1]^(mt[i-1] >>> 30)) , 1566083941 )) - i;
				mt[i] &= 0xffffffff;
				i++;
				if (i>=N) { mt[0] = mt[N-1]; i=1; }
			}
			mt[0] = 0x80000000;
		}
		
		
		//---------------------------------------------------------------------------------------------------GENERATE
		/**
		 * generates a random number on [0,0xffffffff]-interval
		 */
		public function genrand_int32():uint
		{
			var y:uint;
			if ( mti >= N )
			{
				var kk:int;
				if( mti==N+1 )
					init_genrand(5489);
				
				for (kk = 0; kk < N - M; kk++)
				{
					y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
					mt[kk] = mt[kk+M] ^ (y >>> 1) ^ mag01[y & 0x1];
				}
				for (; kk < N - 1; kk++)
				{
					y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
					mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ mag01[y & 0x1];
				}
				y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
				mt[N-1] = mt[M-1] ^ (y >>> 1) ^ mag01[y & 0x1];
				mti = 0;
			}
			y = mt[mti++];
			y ^= (y >>> 11);
			y ^= (y << 7) & 0x9d2c5680;
			y ^= (y << 15) & 0xefc60000;
			y ^= (y >>> 18);
			return y;
		}
		
		/**
		 * generates a random number on [0,0x7fffffff]-interval
		 */
		private function genrand_int31():uint
		{
			return genrand_int32() >> 1;
		}
		
		/**
		 * generates a random number on [0,1]-real-interval
		 */
		public function genrand_real1():Number
		{
			return genrand_int32()*1.0/4294967295.0;
		}
		
		/**
		 * generates a random number on [0,1)-real-interval
		 */
		public function genrand_real2():Number
		{
			return genrand_int32()*1.0/4294967296.0;
		}
		
		/**
		 * generates a random number on (0,1)-real-interval
		 */
		public function genrand_real3():Number
		{
			return (genrand_int32()+0.5)*1.0/4294967296.0;
		}
		
		//---------------------------------------------------------------------------------------------------bigint
		
		private function $multi(a:uint, b:uint):uint
		{
            var a_low:uint  = a & 0xffff;
            var a_high:uint = a >>> 16;
            var b_low:uint  = b & 0xffff;
            var b_high:uint = b >>> 16;
            return (((((a_low * b_low >>> 16) + a_low * b_high) & 0xffff) + a_high * b_low ) & 0xffff) << 16 | a_low * b_low & 0xffff;
        }
	}
	
}