define(function(require ) {

var SinCosLUT = require('../SinCosLUT'),
    hasTypedArrays = require('../../internals/has').typedArrays();

/*
Using David Bau's seedrandom.js for PerlinNoise#noiseSeed functionality
 seedrandom.js version 2.0.
 Author: David Bau 4/2/2011
 http://davidbau.com/encode/seedrandom-min.js

 LICENSE (BSD):

 Copyright 2010 David Bau, all rights reserved.

 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are met:

	1. Redistributions of source code must retain the above copyright
			notice, this list of conditions and the following disclaimer.

	2. Redistributions in binary form must reproduce the above copyright
			notice, this list of conditions and the following disclaimer in the
			documentation and/or other materials provided with the distribution.

	3. Neither the name of this module nor the names of its contributors may
			be used to endorse or promote products derived from this software
			without specific prior written permission.

 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/**
 * All code is in an anonymous closure to keep the global namespace clean.
 *
 * @param {number=} overflow
 * @param {number=} startdenom
 * @api private
 */
 var internalMath = {};
 internalMath.pow = Math.pow; //used by seed generator
 internalMath.random = Math.random; //start with the default random generator
(function (pool, math, width, chunks, significance, overflow, startdenom) {


/*
	seedrandom()
	This is the seedrandom function described above.
*/
math['seedrandom'] = function seedrandom(seed, use_entropy) {
	var key = [];
	var arc4;

	// Flatten the seed string or build one from local entropy if needed.
	seed = mixkey(flatten(
		use_entropy ? [seed, pool] :
		arguments.length ? seed :
		[new Date().getTime(), pool, window], 3), key);

	// Use the seed to initialize an ARC4 generator.
	arc4 = new ARC4(key);

	// Mix the randomness into accumulated entropy.
	mixkey(arc4.S, pool);

	// Override Math.random

	// This function returns a random double in [0, 1) that contains
	// randomness in every bit of the mantissa of the IEEE 754 value.

	math['random'] = function random() {  // Closure to return a random double:
		var n = arc4.g(chunks);             // Start with a numerator n < 2 ^ 48
		var d = startdenom;                 //   and denominator d = 2 ^ 48.
		var x = 0;                          //   and no 'extra last byte'.
		while (n < significance) {          // Fill up all significant digits by
			n = (n + x) * width;              //   shifting numerator and
			d *= width;                       //   denominator and generating a
			x = arc4.g(1);                    //   new least-significant-byte.
		}
		while (n >= overflow) {             // To avoid rounding up, before adding
			n /= 2;                           //   last byte, shift everything
			d /= 2;                           //   right using integer math until
			x >>>= 1;                         //   we have exactly the desired bits.
		}
		return (n + x) / d;                 // Form the number within [0, 1).
	};

	// Return the seed that was used
	return seed;
};

/** @constructor */
function ARC4(key) {
	var t, u, me = this, keylen = key.length;
	var i = 0, j = me.i = me.j = me.m = 0;
	me.S = [];
	me.c = [];

	// The empty key [] is treated as [0].
	if (!keylen) { key = [keylen++]; }

	// Set up S using the standard key scheduling algorithm.
	while (i < width) { me.S[i] = i++; }
	for (i = 0; i < width; i++) {
		t = me.S[i];
		j = lowbits(j + t + key[i % keylen]);
		u = me.S[j];
		me.S[i] = u;
		me.S[j] = t;
	}

	// The "g" method returns the next (count) outputs as one number.
	me.g = function getnext(count) {
		var s = me.S;
		var i = lowbits(me.i + 1); var t = s[i];
		var j = lowbits(me.j + t); var u = s[j];
		s[i] = u;
		s[j] = t;
		var r = s[lowbits(t + u)];
		while (--count) {
			i = lowbits(i + 1); t = s[i];
			j = lowbits(j + t); u = s[j];
			s[i] = u;
			s[j] = t;
			r = r * width + s[lowbits(t + u)];
		}
		me.i = i;
		me.j = j;
		return r;
	};
	// For robust unpredictability discard an initial batch of values.
	// See http://www.rsa.com/rsalabs/node.asp?id=2009
	me.g(width);
}

//
// flatten()
// Converts an object tree to nested arrays of strings.
//
/** @param {Object=} result
	* @param {string=} prop
	* @param {string=} typ
	*/
function flatten(obj, depth, result, prop, typ) {
	result = [];
	typ = typeof(obj);
	if (depth && typ == 'object') {
		for (prop in obj) {
			if (prop.indexOf('S') < 5) {    // Avoid FF3 bug (local/sessionStorage)
				try { result.push(flatten(obj[prop], depth - 1)); } catch (e) {}
			}
		}
	}
	return (result.length ? result : obj + (typ != 'string' ? '\0' : ''));
}

//
// mixkey()
// Mixes a string seed into a key that is an array of integers, and
// returns a shortened string seed that is equivalent to the result key.
//
/** @param {number=} smear
	* @param {number=} j */
function mixkey(seed, key, smear, j) {
	seed += '';                         // Ensure the seed is a string
	smear = 0;
	for (j = 0; j < seed.length; j++) {
		key[lowbits(j)] =
			lowbits((smear ^= key[lowbits(j)] * 19) + seed.charCodeAt(j));
	}
	seed = '';
	for (j in key) { seed += String.fromCharCode(key[j]); }
	return seed;
}

//
// lowbits()
// A quick "n mod width" for width a power of 2.
//
function lowbits(n) { return n & (width - 1); }

//
// The following constants are related to IEEE 754 limits.
//
startdenom = math.pow(width, chunks);
significance = math.pow(2, significance);
overflow = significance * 2;

mixkey(math.random(), pool);

// End anonymous scope, and pass initial values.
})(
	[],   // pool: entropy pool starts empty
	internalMath, // math: package containing random, pow, and seedrandom
	256,  // width: each RC4 output is 0 <= x < 256
	6,    // chunks: at least six RC4 outputs for each double
	52    // significance: there are 52 significant digits in a double
);
//end seed


	/*
		PERLIN NOISE taken from the
		[toxi 040903]
		octaves and amplitude amount per octave are now user controlled
		via the noiseDetail() function.
		[toxi 030902]
		cleaned up code and now using bagel's cosine table to speed up
		[toxi 030901]
		implementation by the german demo group farbrausch
		as used in their demo "art": http://www.farb-rausch.de/fr010src.zip
	*/
	var PERLIN_YWRAPB = 4,
		PERLIN_YWRAP = 1 << PERLIN_YWRAPB,
		PERLIN_ZWRAPB = 8,
		PERLIN_ZWRAP = 1 << PERLIN_ZWRAPB,
		PERLIN_SIZE = 4095,
		PERLIN_MIN_AMPLITUDE = 0.001;
	/** @api private */
	var	_noise_fsc = function(self, i){
		var index = ((i + 0.5) * self._perlin_PI) % self._perlin_TWOPI;
		return 0.5 * (1.0 - self._perlin_cosTable[index]);
	};

	/**
	 * @module toxi/math/noise/PerlinNoise
	 * @api public
	 */
	var	PerlinNoise = function(){
		this._perlin_octaves = 4; // default to medium smooth
		this._perlin_amp_falloff = 0.5; // 50% reduction/octave
        this._sinCosLUT = SinCosLUT.getDefaultInstance();
	};

	PerlinNoise.prototype = {
		/**
		noise
		@api public
		@param [x=0] x is optional
		@param [y=0] y is optional
		@param [z=0] z is optional
		*/
		noise: function(x,y,z){
			var i = 0;
			x = x || 0;
			y = y || 0;
			z = z || 0;

			if(!this._perlin){
                this._perlin = hasTypedArrays ? new Float32Array( PERLIN_SIZE ) : [];
				var length = PERLIN_SIZE - 1;
				for(i = 0;i < PERLIN_SIZE + 1; i++){
					this._perlin[i] = internalMath.random();
				}
			}

			this._perlin_cosTable = this._sinCosLUT.getSinLUT();
			this._perlin_TWOPI = this._perlin_PI = this._sinCosLUT.getPeriod();
			this._perlin_PI >>= 1;

			if (x < 0) {
				x = -x;
			}
			if (y < 0) {
				y = -y;
			}
			if (z < 0) {
				z = -z;
			}

			var xi = x,
				yi = y,
				zi = z,
				xf = (x - xi),
				yf = (y - yi),
				zf = (z - zi),
				rxf,
				ryf,
				r = 0,
				ampl = 0.5,
				n1,
				n2,
				n3,
				of;
			for(i = 0; i < this._perlin_octaves; i++){
				of = xi + (yi << PERLIN_YWRAPB) + (zi << PERLIN_ZWRAPB);
				rxf = _noise_fsc(this,xf);
				ryf = _noise_fsc(this,yf);

				n1 = this._perlin[of & PERLIN_SIZE];
				n1 += rxf * (this._perlin[(of + 1) & PERLIN_SIZE] - n1);
				n2 = this._perlin[(of + PERLIN_YWRAP) & PERLIN_SIZE];
				n2 += rxf * (this._perlin[(of + PERLIN_YWRAP + 1) & PERLIN_SIZE] - n2);
				n1 += ryf * (n2 - n1);

				of += PERLIN_ZWRAP;
				n2 = this._perlin[of & PERLIN_SIZE];
				n2 += rxf * (this._perlin[(of + 1) & PERLIN_SIZE] - n2);
				n3 = this._perlin[(of + PERLIN_YWRAP) & PERLIN_SIZE];
				n3 += rxf * (this._perlin[(of + PERLIN_YWRAP + 1) & PERLIN_SIZE] - n3);
				n2 += ryf * (n3 - n2);

				n1 += _noise_fsc(this,zf) * (n2 - n1);

				r += n1 * ampl;
				ampl *= this._perlin_amp_falloff;

				// break if amp has no more impact
				if (ampl < PERLIN_MIN_AMPLITUDE) {
					break;
				}

				xi <<= 1;
				xf *= 2;
				yi <<= 1;
				yf *= 2;
				zi <<= 1;
				zf *= 2;

				if (xf >= 1.0) {
					xi++;
					xf--;
				}
				if (yf >= 1.0) {
					yi++;
					yf--;
				}
				if (zf >= 1.0) {
					zi++;
					zf--;
				}
			}
			return r;
		},
		/**
		@api public
		@param {Number} lod
		@param {Number} falloff
		*/
		noiseDetail: function(lod, falloff){
			if(lod > 0){
				this._perlin_octaves = lod;
			}
			if(falloff && falloff > 0){
				this._perlin_amp_falloff = falloff;
			}
		},
		/**
		@api public
		@param {Number} [what] the random seed
		*/
		noiseSeed: function(what){
			internalMath.seedrandom(what);
		}
	};

	return PerlinNoise;
});
