extern crate rand;

use std::iter::{self, Extend};
use std::f64;
use rand::{Rng, StdRng, SeedableRng};
use std::collections::HashMap;

///The base noise struct
pub struct WorleyNoise {
	permutation_x: Vec<usize>,
	permutation_y: Vec<usize>,
	permutation_mask: usize,
	density: f64,
	point_count_table: Vec<u32>,
	cache: HashMap<(u32, u32), Vec<(f64, f64)>>,
	distance_function: Box<Fn(f64, f64) -> f64>,
	value_function: Box<Fn(Vec<f64>) -> f64>
}

impl WorleyNoise {
	const MIN_POINTS: u32 = 1;
	const MAX_POINTS: u32 = 9;
	const POINT_COUNT_TABLE_LEN: usize = 100;
	const DEFAULT_PERMUTATION_BITS: usize = 8;
	const DEFAULT_DENSITY: f64 = 3.0;
	const DEFAULT_CACHE_CAPACITY: usize = 1000;
	
	///Creates a new noise struct with random permutation arrays
	///Uses a default density of 3.0 and a cache capacity of 1000
	pub fn new() -> Self {
		Self::with_settings(Self::DEFAULT_DENSITY, Self::DEFAULT_CACHE_CAPACITY)
	}
	
	///Initializes the struct with the specified density
	pub fn with_density(density: f64) -> Self {
		Self::with_settings(density, Self::DEFAULT_CACHE_CAPACITY)
	}
	
	///Initializes the struct with the specified cache capacity
	pub fn with_cache_capacity(capacity: usize) -> Self {
		Self::with_settings(Self::DEFAULT_DENSITY, capacity)
	}
	
	///Initializes the struct with the specified density and cache capacity
	pub fn with_density_and_cache_capacity(density: f64, capacity: usize) -> Self {
		Self::with_settings(density, capacity)
	}
	
	fn with_settings(density: f64, cache_capacity: usize) -> Self {
		let default_distance_function = |x, y| x * x + y * y;
		let default_value_function = |distances: Vec<f64>| distances.iter()
			.cloned()
			.fold(f64::MAX, f64::min);
		let mut noise = WorleyNoise {
			permutation_x: Vec::new(),
			permutation_y: Vec::new(),
			permutation_mask: 0,
			density: density,
			point_count_table: Vec::new(),
			cache: HashMap::with_capacity(cache_capacity),
			distance_function: Box::new(default_distance_function),
			value_function: Box::new(default_value_function)
		};
		
		noise.set_density(density);
		noise.permutate(Self::DEFAULT_PERMUTATION_BITS);
		
		noise
	}
	
	fn feature_point_count(&self, probability: f64) -> u32 {
		let index = ((self.point_count_table.len() - 1) as f64 * probability).floor() as usize;
		
		self.point_count_table[index]
	}
	
	fn hash(&self, x: u32, y: u32) -> [usize; 1] {
		let x = self.permutation_x[x as usize & self.permutation_mask];
		let y = self.permutation_y[y as usize & self.permutation_mask];
		
		[x ^ y]
	}
	
	fn feature_points(&mut self, quad_x: u32, quad_y: u32, collector: &mut Vec<(f64, f64)>) {
		let points = if let Some(points) = self.cache.get(&(quad_x, quad_y)) {
			points.clone()
		} else {
			let mut points = Vec::new();
			let mut rng = StdRng::from_seed(&self.hash(quad_x, quad_y));
			let count = self.feature_point_count(rng.next_f64());
			
			for _ in 0 .. count {
				let x = rng.next_f64() + quad_x as f64;
				let y = rng.next_f64() + quad_y as f64;
				
				points.push((x, y));
			}
			
			points
		};
		
		collector.extend_from_slice(&points);
		self.cache.insert((quad_x, quad_y), points);
	}
	
	fn adjacent_feature_points(&mut self, quad_x: u32, quad_y: u32) -> Vec<(f64, f64)> {
		let mut points = Vec::with_capacity((self.density * 9.0) as usize);
		let start_x = quad_x.max(1) - 1;
		let start_y = quad_y.max(1) - 1;
		
		for x in start_x .. quad_x + 2 {
			for y in start_y .. quad_y + 2 {
				self.feature_points(x, y, &mut points);
			}
		}
		
		points
	}
	
	///Randomizes the internal permutation arrays
	///Might be slow
	pub fn permutate(&mut self, permutation_table_bit_length: usize) {
		let mut rng = StdRng::new()
			.unwrap();
		let length = 1 << permutation_table_bit_length;
		
		self.permutation_x.reserve(length);
		self.permutation_y.reserve(length);
		self.permutation_x.extend(rng.gen_iter::<usize>().take(length));
		self.permutation_y.extend(rng.gen_iter::<usize>().take(length));
		self.permutation_mask = length - 1;
	}
	
	///Sets the density
	///Might be slow since it precomputes a lot of stuff
	pub fn set_density(&mut self, density: f64) {
		self.point_count_table.clear();
		self.point_count_table.reserve(Self::POINT_COUNT_TABLE_LEN);
		
		for i in Self::MIN_POINTS .. Self::MAX_POINTS + 1 {
			let poisson = density.powi(i as i32) / factorial(i as u32) as f64 * f64::consts::E.powf(-density);
			let count = (poisson * Self::POINT_COUNT_TABLE_LEN as f64).round() as usize;
			
			self.point_count_table.extend(iter::repeat(i).take(count));
		}
	}
	
	///Sets the function to calculate the distance between feature points
	///Default is the squared Euclidean distance
	pub fn set_distance_function<F>(&mut self, function: F) where F: Fn(f64, f64) -> f64 + 'static {
		self.distance_function = Box::new(function);
	}
	
	///Sets the function to pick the final value from the nearby feature points
	///The values are in no particular order
	pub fn set_value_function<F>(&mut self, function: F) where F: Fn(Vec<f64>) -> f64 + 'static {
		self.value_function = Box::new(function);
	}
	
	///Calculates the noise value for the given point
	pub fn value(&mut self, x: f64, y: f64) -> f64 {
		let quad_x = x.floor() as u32;
		let quad_y = y.floor() as u32;
		let points = self.adjacent_feature_points(quad_x, quad_y);
		let distances = points.iter()
			.map(|&(p_x, p_y)| (p_x - x, p_y - y))
			.map(|(x, y)| (self.distance_function)(x, y))
			.collect();
		let val = (self.value_function)(distances);
		
		val
	}
}

fn factorial(x: u32) -> u32 {
	let mut val = 1;
	
	for i in 2 .. x + 1 {
		val *= i;
	}
	
	val
}