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

extern crate rand;
extern crate rayon;

mod naive_hasher;

use std::iter::{self, Extend};
use std::f64;
use std::collections::HashMap;
use std::sync::RwLock;
use naive_hasher::NaiveBuildHasher;
use rand::{Rng, StdRng, SeedableRng};
use rayon::prelude::*;

///The base noise struct.
///
///Caches already sampled values.
///
///Sampling individual points is relatively slow due to the internal locks.
///
///Use the [`WorleyNoise::values`](#method.values) function if possible.
pub struct WorleyNoise {
	permutation_x: Vec<usize>,
	permutation_y: Vec<usize>,
	permutation_mask: usize,
	density: f64,
	point_count_table: Vec<u32>,
	cache: RwLock<HashMap<(i32, i32), Vec<(f64, f64)>, NaiveBuildHasher>>,
	distance_function: Box<Fn(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 = 100;
	const DEFAULT_RADIUS: u16 = 1;
	const DEFAULT_PERMUTATION_BITS: usize = 8;
	const DEFAULT_DENSITY: f64 = 3.0;
	const DEFAULT_CACHE_CAPACITY: usize = 2500;
	
	///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_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| 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: 0.0,
			point_count_table: Vec::new(),
			cache: RwLock::new(HashMap::with_capacity_and_hasher(capacity, NaiveBuildHasher::default())),
			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() - 1) as f64 * probability).floor() as usize;
		
		self.point_count_table[index]
	}
	
	fn hash(&self, x: i32, y: i32) -> [usize; 1] {
		[self.permutation_x[x as usize & self.permutation_mask] ^ self.permutation_y[y as usize & self.permutation_mask]]
	}
	
	fn feature_points(&self, quad_x: i32, quad_y: i32, collector: &mut Vec<(f64, f64)>) {
		let already_calculated = if let Some(cached) = self.cache.read().unwrap().get(&(quad_x, quad_y)) {
			collector.extend_from_slice(cached);
			
			true
		} else {
			false
		};
		
		if !already_calculated {
			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));
			}
			
			collector.extend_from_slice(&points);
			self.cache.write().unwrap().insert((quad_x, quad_y), points);
		}
	}
	
	fn adjacent_feature_points(&self, quad_x: i32, quad_y: i32) -> Vec<(f64, f64)> {
		let mut points = Vec::with_capacity((self.density * 9.0) as usize);
		let radius = self.radius as i32;
		let start_x = quad_x - radius;
		let start_y = quad_y - radius;
		
		for x in start_x .. quad_x + radius + 1 {
			for y in start_y .. quad_y + radius + 1 {
				self.feature_points(x, y, &mut points);
			}
		}
		
		points
	}
	
	///Calls 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.
	///
	///Might be slow.
	pub fn permutate_seeded(&mut self, permutation_table_bit_length: usize, seed: usize) {
		let mut rng = StdRng::from_seed(&[seed]);
		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.
	///
	///Default is 3.0.
	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 u16) 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 + 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 calculation.
	///
	///A higher radius reduces the amount of possible errors but slows down sampling of individual points.
	///
	///Shouldn't affect performance too much when iterating over a lot of points since the values get cached anyway.
	///
	///Default is 1.
	pub fn set_radius(&mut self, radius: u16) {
		self.radius = radius;
	}
	
	///Calculates the noise value for the given point.
	pub fn value(&self, x: f64, y: f64) -> f64 {
		let points = self.adjacent_feature_points(x.floor() as i32, y.floor() as i32);
		let distances = points.iter()
			.map(|&(p_x, p_y)| (p_x - x, p_y - y))
			.map(|(x, y)| (self.distance_function)(x, y))
			.collect();
		
		(self.value_function)(distances)
	}
	
	///Calculates the noise values for the given points.
	///
	///Uses multiple threads.
	pub fn values(&self, points: &Vec<(f64, f64)>) -> Vec<f64> {
		let mut values = Vec::with_capacity(points.len());
		
		points.par_iter()
			.map(|&(x, y)| self.value(x, y))
			.collect_into(&mut values);
		
		values
	}
}

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