/*
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.

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`](#method.values) function if sampling multiple points instead as it's concurrent.
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
}

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
	
	pub const DEFAULT_RADIUS: u16 = 1;
	pub const DEFAULT_PERMUTATION_BITS: usize = 10;
	pub const DEFAULT_DENSITY: f64 = 3.0;
	pub const DEFAULT_CACHE_CAPACITY: usize = 2500;
	
	/// 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 = WorleyNoise {
			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
		};
		
		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(&self, cube_x: i32, cube_y: i32, cube_z: i32, collector: &mut Vec<(f64, f64, f64)>) {
		if let Some(cached) = self.cache.find(&(cube_x, cube_y, cube_z)) {
			collector.extend_from_slice(cached.get());
			
			return;
		}
		
		let mut points = Vec::new();
		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;
			
			points.push((x, y, z));
		}
		
		collector.extend_from_slice(&points);
		self.cache.insert((cube_x, cube_y, cube_z), points);
	}
	
	fn adjacent_feature_points(&self, cube_x: i32, cube_y: i32, cube_z: i32) -> Vec<(f64, f64, f64)> {
		let mut cubes_around = 0;
		
		for i in 1 ..= self.radius {
			cubes_around += i;
		}
		
		cubes_around *= 9 + 8 + 9;
		
		let expected_point_count = 1 + (self.density * cubes_around as f64) as usize;
		let mut points = Vec::with_capacity(expected_point_count);
		let radius = self.radius as i32;
		let start_x = cube_x - radius;
		let start_y = cube_y - radius;
		let start_z = cube_z - radius;
		let end_x = cube_x + radius;
		let end_y = cube_y + radius;
		let end_z = cube_z + radius;
		
		for x in start_x ..= end_x {
			for y in start_y ..= end_y {
				for z in start_z ..= end_z {
					self.feature_points(x, y, z, &mut points);
				}
			}
		}
		
		points
	}
	
	/// 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 mut 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.
	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 pick the final value from the nearby feature points.
	///
	/// The values are in no particular order.
	///
	/// Default is the minimum value.
	pub fn set_value_function<F>(&mut self, function: F) where F: Fn(Vec<f64>) -> f64 + Sync + 'static {
		self.value_function = Box::new(function);
	}
	
	/// Specifies how many adjacent cells should be included in the value calculation.
	///
	/// 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;
	}
	
	/// 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.
	///
	/// Uses multiple threads if available.
	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.
	///
	/// Uses multiple threads if available.
	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)
	}
}

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