/*
Copyright 2018 Johannes Boczek

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

	http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

//! A basic implementation of Worley noise.
//!
//! I hope a code example is not required, it should be pretty straightforward.

#![warn(missing_docs)]

use std::iter::{
	self,
	Extend
};
use std::f64;
use rand::{
	Rng,
	SeedableRng,
	distributions::{
		Standard
	}
};
use rand_xorshift::{
	XorShiftRng
};
use concurrent_hashmap::{
	Options as HashMapOptions,
	ConcHashMap
};
use fnv::FnvBuildHasher;

#[cfg(not(feature = "web"))]
use rayon::prelude::*;

/// The base noise struct.
///
/// Uses permutation arrays for efficiency. Use the [`WorleyNoise::permutate`](#method.permutate) function to randomize it / adjust the size.
///
/// Caches already sampled values.
///
/// Sampling individual points is relatively slow due to the internal locks.	
/// Use the [`WorleyNoise::values_3d`](#method.values_3d) function if sampling multiple points instead, as it's concurrent.	
/// Use the [`WorleyNoise::values_3d`](#method.values_3d_range) function if sampling a range of points, as it's even faster.
#[cfg(not(feature = "web"))]
pub struct WorleyNoise {
	permutation_table: Vec<u128>,
	permutation_mask: usize,
	density: f64,
	point_count_table: Vec<u32>,
	cache: ConcHashMap<(i32, i32, i32), Vec<(f64, f64, f64)>, FnvBuildHasher>,
	distance_function: Box<Fn(f64, f64, f64) -> f64 + Sync>,
	value_function: Box<Fn(Vec<f64>) -> f64 + Sync>,
	radius: (u16, u16, u16),
}

/// The base noise struct.
///
/// Uses permutation arrays for efficiency. Use the [`WorleyNoise::permutate`](#method.permutate) function to randomize it / adjust the size.
///
/// Caches already sampled values.
///
/// Sampling individual points is relatively slow due to the internal locks.	
/// Use the [`WorleyNoise::values_3d`](#method.values_3d) function if sampling multiple points instead, as it's concurrent.	
/// Use the [`WorleyNoise::values_3d`](#method.values_3d_range) function if sampling a range of points, as it's even faster.
#[cfg(feature = "web")]
pub struct WorleyNoise {
	permutation_table: Vec<u128>,
	permutation_mask: usize,
	density: f64,
	point_count_table: Vec<u32>,
	cache: ConcHashMap<(i32, i32, i32), Vec<(f64, f64, f64)>, FnvBuildHasher>,
	distance_function: Box<Fn(f64, f64, f64) -> f64>,
	value_function: Box<Fn(Vec<f64>) -> f64>,
	radius: (u16, u16, u16),
}

impl WorleyNoise {
	const MIN_POINTS: u32 = 1;
	const MAX_POINTS: u32 = 9;
	const POINT_COUNT_TABLE_LEN: usize = 150;
	const CONCURRENCY: u16 = 64; //Works best for most scenarios
	
	/// The default radius of cubes to include in the calculations
	pub const DEFAULT_RADIUS: u16 = 1;
	
	/// The default bit length of the permutation table used for hashing.
	pub const DEFAULT_PERMUTATION_BITS: usize = 10;
	
	/// The default feature point density for each cube.
	pub const DEFAULT_DENSITY: f64 = 3.0;
	
	/// The default cache capacity.
	pub const DEFAULT_CACHE_CAPACITY: usize = 10000;
	
	/// Creates a new noise struct with random permutation arrays.
	///
	/// Uses the default cache capacity of 2500.
	pub fn new() -> Self {
		Self::with_cache_capacity(Self::DEFAULT_CACHE_CAPACITY)
	}
	
	/// Initializes the struct with the specified cache capacity.
	pub fn with_cache_capacity(capacity: usize) -> Self {
		let default_distance_function = |x, y, z| x * x + y * y + z * z;
		let default_value_function = |distances: Vec<f64>| distances.iter()
			.cloned()
			.fold(f64::MAX, f64::min);
		let cache_options = HashMapOptions {
			capacity: capacity,
			hasher_factory: FnvBuildHasher::default(),
			concurrency: Self::CONCURRENCY
		};
		let mut noise = Self {
			permutation_table: Vec::new(),
			permutation_mask: 0,
			density: 0.0,
			point_count_table: Vec::new(),
			cache: ConcHashMap::with_options(cache_options),
			distance_function: Box::new(default_distance_function),
			value_function: Box::new(default_value_function),
			radius: (Self::DEFAULT_RADIUS, Self::DEFAULT_RADIUS, Self::DEFAULT_RADIUS),
		};
		
		noise.set_density(Self::DEFAULT_DENSITY);
		noise.permutate(Self::DEFAULT_PERMUTATION_BITS);
		
		noise
	}
	
	fn feature_point_count(&self, probability: f64) -> u32 {
		let index = (self.point_count_table.len() as f64 * probability).floor() as usize;
		
		self.point_count_table[index]
	}
	
	fn hash(&self, x: i32, y: i32, z: i32) -> [u8; 16] {
		let mut hash = self.permutation_table[x as usize & self.permutation_mask];
		hash = self.permutation_table[(hash as usize ^ y as usize) & self.permutation_mask];
		hash = self.permutation_table[(hash as usize ^ z as usize) & self.permutation_mask];
		
		hash.to_be_bytes()
	}
	
	fn feature_points_with_cache(&self, cube_x: i32, cube_y: i32, cube_z: i32, collector: &mut Vec<(f64, f64, f64)>) {
		/*
		 * If we have it cached, just put all the cached points into the collector and return.
		 */
		if let Some(cached) = self.cache.find(&(cube_x, cube_y, cube_z)) {
			collector.extend_from_slice(cached.get());
			
			return;
		}
		
		/*
		 * Else, generate a seed from our cube and use it to feed an RNG.
		 */
		let seed = self.hash(cube_x, cube_y, cube_z);
		let mut rng = XorShiftRng::from_seed(seed);
		let count = self.feature_point_count(rng.gen());
		let mut points = Vec::with_capacity(count as usize);
		
		for _ in 0 .. count {
			let x = rng.gen::<f64>() + cube_x as f64;
			let y = rng.gen::<f64>() + cube_y as f64;
			let z = rng.gen::<f64>() + cube_z as f64;
			
			points.push((x, y, z));
		}
		
		collector.extend_from_slice(&points);
		self.cache.insert((cube_x, cube_y, cube_z), points);
	}
	
	fn feature_points(&self, cube_x: i32, cube_y: i32, cube_z: i32, collector: &mut Vec<(f64, f64, f64)>) {
		let seed = self.hash(cube_x, cube_y, cube_z);
		let mut rng = XorShiftRng::from_seed(seed);
		let count = self.feature_point_count(rng.gen());
		
		for _ in 0 .. count {
			let x = rng.gen::<f64>() + cube_x as f64;
			let y = rng.gen::<f64>() + cube_y as f64;
			let z = rng.gen::<f64>() + cube_z as f64;
			
			collector.push((x, y, z));
		}
	}
	
	fn feature_points_from_cube_list(&self, cubes: &Vec<(i32, i32, i32)>) -> Vec<Vec<(f64, f64, f64)>> {
		let points_per_cube = (self.density + 1.0).ceil() as usize;
		let mut feature_points = Vec::with_capacity(cubes.len());
		
		#[cfg(not(feature = "web"))]
		let cube_iter = cubes.par_iter();
		
		#[cfg(feature = "web")]
		let cube_iter = cubes.iter();
		
		let cube_iter = cube_iter.map(|&(x, y, z)| {
			let mut points = Vec::with_capacity(points_per_cube);
			
			self.feature_points(x, y, z, &mut points);
			
			points
		});
		
		#[cfg(not(feature = "web"))]
		cube_iter.collect_into_vec(&mut feature_points);
		
		#[cfg(feature = "web")]
		feature_points.extend(cube_iter);
		
		feature_points
	}
	
	fn adjacent_feature_points(&self, cube_x: i32, cube_y: i32, cube_z: i32) -> Vec<(f64, f64, f64)> {
		let radius_x = self.radius.0 as i32;
		let radius_y = self.radius.1 as i32;
		let radius_z = self.radius.2 as i32;
		let cubes_per_sample = (1 + radius_x * 2) * (1 + radius_y * 2) * (1 + radius_z * 2);
		let points_per_sample = ((self.density + 1.0) * cubes_per_sample as f64).ceil() as usize;
		let mut points = Vec::with_capacity(points_per_sample);
		let start_x = cube_x - radius_x;
		let start_y = cube_y - radius_y;
		let start_z = cube_z - radius_z;
		let end_x = cube_x + radius_x;
		let end_y = cube_y + radius_y;
		let end_z = cube_z + radius_z;
		
		for x in start_x ..= end_x {
			for y in start_y ..= end_y {
				for z in start_z ..= end_z {
					self.feature_points_with_cache(x, y, z, &mut points);
				}
			}
		}
		
		points
	}
	
	fn sample_points_from_point_lists(&self, feature_points: &Vec<Vec<(f64, f64, f64)>>, sample_points: &Vec<(f64, f64, f64)>, (cube_range_x, cube_range_y): (i32, i32)) -> Vec<f64> {
		let (radius_x, radius_y, radius_z) = (
			self.radius.0 as i32,
			self.radius.1 as i32,
			self.radius.2 as i32
		);
		let cubes_per_sample = (1 + radius_x * 2) * (1 + radius_y * 2) * (1 + radius_z * 2);
		let points_per_sample = ((self.density + 1.0) * cubes_per_sample as f64).ceil() as usize;
		let mut values = Vec::with_capacity(sample_points.len());
		
		#[cfg(not(feature = "web"))]
		let sample_point_iter = sample_points.par_iter();
		
		#[cfg(feature = "web")]
		let sample_point_iter = sample_points.iter();
		
		let sample_point_iter = sample_point_iter.map(|&(sample_point_x, sample_point_y, sample_point_z)| {
			let mut adjacent_points = Vec::with_capacity(points_per_sample);
			let cube_x = sample_point_x.floor() as i32;
			let cube_y = sample_point_y.floor() as i32;
			let cube_z = sample_point_z.floor() as i32;
			let start_x = cube_x - radius_x;
			let start_y = cube_y - radius_y;
			let start_z = cube_z - radius_z;
			let end_x = cube_x + radius_x;
			let end_y = cube_y + radius_y;
			let end_z = cube_z + radius_z;
			
			for x in start_x ..= end_x {
				for y in start_y ..= end_y {
					for z in start_z ..= end_z {
						let idx = (
							  (x + radius_x)
							+ (y + radius_y) * cube_range_x
							+ (z + radius_z) * cube_range_x * cube_range_y
						) as usize;
						let points = &feature_points[idx];
						
						adjacent_points.extend_from_slice(&points);
					}
				}
			}
			
			let mut distances = Vec::with_capacity(points_per_sample);
			let distances_iter = adjacent_points.iter()
				.map(|&(x, y, z)| (x - sample_point_x, y - sample_point_y, z - sample_point_z))
				.map(|(x, y, z)| (self.distance_function)(x, y, z));
			
			distances.extend(distances_iter);
			
			(self.value_function)(distances)
		});
		
		#[cfg(not(feature = "web"))]
		sample_point_iter.collect_into_vec(&mut values);
		
		#[cfg(feature = "web")]
		values.extend(sample_point_iter);
		
		values
	}
	
	/// Calls [`WorleyNoise::permutate_seeded`](#method.permutate_seeded) with a random seed.
	pub fn permutate(&mut self, permutation_table_bit_length: usize) {
		self.permutate_seeded(permutation_table_bit_length, rand::random());
	}
	
	/// Randomizes the internal permutation arrays.
	///
	/// Generates permutation arrays with two to the power of `permutation_table_bit_length` entries.
	///
	/// This operation is fairly slow.
	pub fn permutate_seeded(&mut self, permutation_table_bit_length: usize, seed: u128) {
		let seed = seed.to_be_bytes();
		let rng = XorShiftRng::from_seed(seed);
		let length = 1 << permutation_table_bit_length;
		
		self.permutation_table.clear();
		self.permutation_table.reserve(length);
		self.permutation_table.extend(rng.sample_iter::<u128, Standard>(Standard).take(length));
		self.permutation_mask = length - 1;
	}
	
	/// Sets the feature point density.
	///
	/// Might be slow since it precomputes a lot of stuff.
	///
	/// Default is 3.0.
	pub fn set_density(&mut self, density: f64) {
		/*
		 * Okay, this one is difficult to explain.
		 * The `point_count_table` is a precomputed table which contains information about how many feature points a cell has.
		 * The table length is fixed; changing its size only changes "accuracy". You'll hopefully understand what that means later.
		 */
		
		self.point_count_table.clear();
		self.point_count_table.reserve(Self::POINT_COUNT_TABLE_LEN);
		
		/*
		 * Here we iterate through all possible point counts (1 to 9 inclusive) and calculate the probability of a cell having exactly that amount of feature points.
		 * This probability is estimated with the poisson distribution function.
		 * The lambda parameter (the expectation) is `density`.
		 */
		for i in Self::MIN_POINTS ..= Self::MAX_POINTS {
			let poisson = density.powi(i as i32) * f64::consts::E.powf(-density) / factorial(i as u16) as f64;
			let count = (poisson * Self::POINT_COUNT_TABLE_LEN as f64).round() as usize;
			
			/*
			 * Next we determine how many entries in the table the currently iterated feature point count (loop index `i`) should get.
			 * For example: If the current iteration index is 3 and the calculated poisson distribution value is 0.23, the `point_count_table` contains the value 3 23 times (given that the table length is 100).
			 * So the more likely it is that a cell has `i` feature points, the more entries the `point_count_table` has.
			 */
			
			self.point_count_table.extend(iter::repeat(i).take(count));
		}
		
		self.density = density;
	}
	
	/// Sets the function to calculate the distance between feature points.
	///
	/// Default is the squared Euclidean distance.
	#[cfg(not(feature = "web"))]
	pub fn set_distance_function<F>(&mut self, function: F) where F: Fn(f64, f64, f64) -> f64 + Sync + 'static {
		self.distance_function = Box::new(function);
	}
	
	/// Sets the function to calculate the distance between feature points.
	///
	/// Default is the squared Euclidean distance.
	#[cfg(feature = "web")]
	pub fn set_distance_function<F>(&mut self, function: F) where F: Fn(f64, 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.
	///
	/// Default is the minimum value.
	#[cfg(not(feature = "web"))]
	pub fn set_value_function<F>(&mut self, function: F) where F: Fn(Vec<f64>) -> f64 + Sync + 'static {
		self.value_function = Box::new(function);
	}
	
	/// Sets the function to pick the final value from the nearby feature points.
	///
	/// The values are in no particular order.
	///
	/// Default is the minimum value.
	#[cfg(feature = "web")]
	pub fn set_value_function<F>(&mut self, function: F) where F: Fn(Vec<f64>) -> f64 + 'static {
		self.value_function = Box::new(function);
	}
	
	/// Specifies how many adjacent cells should be included in the value calculation for all directions.
	///
	/// A higher radius reduces the amount of possible errors but slows down sampling of individual points.
	///
	/// Default is 1. That means it includes the feature points of the surrounding cells.
	pub fn set_radius(&mut self, radius: u16) {
		self.radius = (radius, radius, radius);
	}
	
	/// Specifies how many adjacent cells should be included in the value calculation for the x direction.
	///
	/// See [`WorleyNoise::set_radius`](#method.set_radius).
	pub fn set_radius_x(&mut self, radius: u16) {
		self.radius.0 = radius;
	}
	
	/// Specifies how many adjacent cells should be included in the value calculation for the y direction.
	///
	/// See [`WorleyNoise::set_radius`](#method.set_radius).
	pub fn set_radius_y(&mut self, radius: u16) {
		self.radius.1 = radius;
	}
	
	/// Specifies how many adjacent cells should be included in the value calculation for the z direction.
	///
	/// See [`WorleyNoise::set_radius`](#method.set_radius).
	pub fn set_radius_z(&mut self, radius: u16) {
		self.radius.2 = radius;
	}
	
	/// Calculates the noise value for the given point.
	pub fn value_3d(&self, x: f64, y: f64, z: f64) -> f64 {
		let points = self.adjacent_feature_points(x.floor() as i32, y.floor() as i32, z.floor() as i32);
		let distances = points.iter()
			.map(|&(px, py, pz)| (px - x, py - y, pz - z))
			.map(|(x, y, z)| (self.distance_function)(x, y, z))
			.collect();
		
		(self.value_function)(distances)
	}
	
	/// Calculates the noise value for the given point with z set to 0.0.
	pub fn value_2d(&self, x: f64, y: f64) -> f64 {
		self.value_3d(x, y, 0.0)
	}
	
	/// Calculates the noise values for the given points.
	pub fn values_3d(&self, points: &Vec<(f64, f64, f64)>) -> Vec<f64> {
		let mut values = Vec::with_capacity(points.len());
		
		#[cfg(not(feature = "web"))]
		{
			points.par_iter()
				.map(|&(x, y, z)| self.value_3d(x, y, z))
				.collect_into_vec(&mut values);
		}
		
		#[cfg(feature = "web")]
		{
			points.iter()
				.map(|&(x, y, z)| self.value_3d(x, y, z))
				.for_each(|val| values.push(val));
		}
		
		values
	}
	
	/// Calculates the noise values for the given points with z set to 0.0.
	pub fn values_2d(&self, points: &Vec<(f64, f64)>) -> Vec<f64> {
		let points_3d = points.iter()
			.map(|(x, y)| (*x, *y, 0.0))
			.collect();
		
		self.values_3d(&points_3d)
	}
	
	/// Calculates the noise values between the given coordinates.
	///
	/// Significantly faster than sampling explicit points.
	///
	/// Does not cache values.
	///
	/// If the sample count is 0 in any dimension, the resulting vector will be empty.
	///
	/// # Panics
	/// * If one of the end coordinates is smaller than the start coordinates
	pub fn values_3d_range(&self, start: (f64, f64, f64), end: (f64, f64, f64), sample_cnt: (u32, u32, u32)) -> Vec<f64> {
		/*
		 * The difference to the regular way of sampling points is that this function first samples all cubes that we're gonna need.
		 * After that we index into the vector of sampled points.
		 */
		
		/*
		 * Precalculate a lot of stuff
		 */
		let (start_x, start_y, start_z) = start;
		let (end_x, end_y, end_z) = end;
		
		if end_x < start_x || end_y < start_y || end_z < start_z {
			panic!("End coordinates can't be smaller than start coordinates");
		}
		
		let (sample_cnt_x, sample_cnt_y, sample_cnt_z) = sample_cnt;
		let (sample_range_x, sample_range_y, sample_range_z) = (
			(end_x - start_x),
			(end_y - start_y),
			(end_z - start_z)
		);
		let (radius_x, radius_y, radius_z) = (
			self.radius.0 as i32,
			self.radius.1 as i32,
			self.radius.2 as i32
		);
		let (cube_start_x, cube_start_y, cube_start_z) = (
			start_x.floor() as i32 - radius_x,
			start_y.floor() as i32 - radius_y,
			start_z.floor() as i32 - radius_z
		);
		let (cube_end_x, cube_end_y, cube_end_z) = (
			end_x.floor() as i32 + radius_x,
			end_y.floor() as i32 + radius_y,
			end_z.floor() as i32 + radius_z
		);
		let (cube_range_x, cube_range_y) = (
			cube_end_x - cube_start_x + 1,
			cube_end_y - cube_start_y + 1
		);
		let cube_cnt = ((1 + cube_end_x - cube_start_x) * (1 + cube_end_y - cube_start_y) * (1 + cube_end_z - cube_start_z)) as usize;
		let sample_cnt = (sample_cnt_x * sample_cnt_y * sample_cnt_z) as usize;
		let mut cubes = Vec::with_capacity(cube_cnt);
		let mut sample_points = Vec::with_capacity(sample_cnt);
		
		/*
		 * Calculate cubes to sample
		 */
		for z in cube_start_z ..= cube_end_z {
			for y in cube_start_y ..= cube_end_y {
				for x in cube_start_x ..= cube_end_x {
					cubes.push((x, y, z));
				}
			}
		}
		
		/*
		 * Sample cubes
		 */
		let feature_points = self.feature_points_from_cube_list(&cubes);
		
		/*
		 * Calculate points to sample
		 */
		for z in 0 .. sample_cnt_z {
			let sample_point_z = start_z + z as f64 * sample_range_z / sample_cnt_z as f64;
			
			for y in 0 .. sample_cnt_y {
				let sample_point_y = start_y + y as f64 * sample_range_y / sample_cnt_y as f64;
				
				for x in 0 .. sample_cnt_x {
					let sample_point_x = start_x + x as f64 * sample_range_x / sample_cnt_x as f64;
					
					sample_points.push((sample_point_x, sample_point_y, sample_point_z));
				}
			}
		}
		
		/*
		 * Fill points to sample using cubes sampled earlier
		 */
		self.sample_points_from_point_lists(&feature_points, &sample_points, (cube_range_x, cube_range_y))
	}
	
	/// Calculates the noise values between the given coordinates with z set to 0.0.
	///
	/// Significantly faster than sampling explicit points.
	///
	/// Does not cache values.
	///
	/// If the sample count is 0 in any dimension, the resulting vector will be empty.
	///
	/// # Panics
	/// * If one of the end coordinates is smaller than the start coordinates
	pub fn values_2d_range(&self, start: (f64, f64), end: (f64, f64), sample_cnt: (u32, u32)) -> Vec<f64> {
		let (start_x, start_y) = start;
		let (end_x, end_y) = end;
		let (sample_cnt_x, sample_cnt_y) = sample_cnt;
		
		self.values_3d_range((start_x, start_y, 0.0), (end_x, end_y, 0.0), (sample_cnt_x, sample_cnt_y, 1))
	}
	
	/// Clears the internal cache to free up memory.
	pub fn clear_cache(&mut self) {
		self.cache.clear();
	}
}

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