#include <ctime>

#include <iostream>

#include "generator.h"


void
Generator::GenSurface::reset() {
	if (data) delete[] data;
	data = nullptr;
	w = h = 0;
	m_offset = ULongIntVector2();
	m_step = 0;
}

void
Generator::GenSurface::create(const ULongIntPair2 &bounds, ULongInt step) {
	ULongIntPair2 b = bounds;

	reset();
	
	assert(!(step & (step - 1)));
	assert(b.p1.x != b.p0.x);
	assert(b.p1.y != b.p0.y);
	assert(b.p1.x - b.p0.x <= big);
	assert(b.p1.y - b.p0.y <= big);
	
	b.p0.x = b.p0.x & ~(step - 1);
	b.p0.y = b.p0.y & ~(step - 1);
	if (!(b.p0.x & step)) b.p0.x -= step;
	if (!(b.p0.y & step)) b.p0.y -= step;
	
	b.p1.x = ((b.p1.x - 1) & ~(step - 1)) + step;
	b.p1.y = ((b.p1.y - 1) & ~(step - 1)) + step;
	if (!(b.p1.x & step)) b.p1.x += step;
	if (!(b.p1.y & step)) b.p1.y += step;
	
	w = (b.p1.x - b.p0.x)/step + 1;
	h = (b.p1.y - b.p0.y)/step + 1;

	assert(w <= max_side);
	assert(h <= max_side);
	assert(w*h <= max_area);
	
	m_step = step;
	m_offset = b.p0;
	data = new Vector4[w*h];
	
	assert(is_valid());
}

Generator::GenSurface&
Generator::GenSurface::operator= (const GenSurface &other) {
	if (&other != this) {
		reset();
		if (other.is_valid()) {
			w = other.w;
			h = other.h;
			m_offset = other.m_offset;
			m_step = other.m_step;
			data = new Vector4[w*h];
			memcpy(data, other.data, sizeof(Vector4)*w*h);
			assert(is_valid());
		}
	}
	return *this;
}



Generator::Generator(): Generator(random(time(NULL))) { }

Generator::Generator(ULongInt seed):
	max_cache_count(4ll*1024*1024*1024/sizeof(CacheEntry))
{
	set_seed(seed);
	LongIntVector2 a(1, 2);
	LongIntVector2 b(3);
	m_cache[ULongIntVector2()];
	m_cache_top = m_cache.begin();
	m_cache_top->second.next = m_cache_top->second.previous = m_cache_top;
}

void
Generator::set_seed(ULongInt x) {
	for(int i = 0; i < 2; ++i)
		for(int j = 0; j < 4; ++j)
			x = random( m_seeds[i][j] = x );
}


Real
Generator::random(const ULongIntVector2 &coord, int index) const {
	ULongInt rx = coord.x ^ seeds_x()[index];
	ULongInt ry = coord.y ^ seeds_y()[index];
	ULongInt seed = random(rx ^ random(ry));
	seed = random(seed ^ ry);
	seed = random(seed ^ random(rx));
	return random_to_real(seed)*2 - 1;
	//return random_to_normal(seed, random(seed));
}

Vector4
Generator::generate(const ULongIntVector2 &coord, bool shrink_cache) const {
	// search value in cache
	
	Cache::iterator i = m_cache.find(coord);
	bool found = i != m_cache.end();
	if (found) {
		i->second.previous->second.next = i->second.next;
		i->second.next->second.previous = i->second.previous;
		assert(!i->second.in_use);
		if (i->second.in_use) return i->second.value;
	} else {
		i = m_cache.insert(Cache::value_type(coord, CacheEntry())).first;
		++m_cache_count;
	}
	i->second.in_use = true;
	i->second.previous = m_cache_top;
	i->second.next = i->second.previous->second.next;
	m_cache_top = i;
	i->second.previous->second.next = i;
	i->second.next->second.previous = i;

	while (shrink_cache && m_cache_count > max_cache_count) {
		Cache::iterator ri = m_cache_top->second.next;
		if (ri->second.in_use) break;
		ri->second.previous->second.next = ri->second.next;
		ri->second.next->second.previous = ri->second.previous;
		m_cache.erase(ri);
		--m_cache_count;
	}
	
	Vector4 &value = i->second.value;
	if (!found) {
		// generate new value
		
		for(int j = 0; j < 4; ++j)
			value[j] = random(coord, j);
		
		ULongInt x_minus_one = coord.x - 1;
		ULongInt y_minus_one = coord.y - 1;
		ULongInt level_x = coord.x ? (coord.x ^ x_minus_one) >> 1 : (ULongInt)-1;
		ULongInt level_y = coord.y ? (coord.y ^ y_minus_one) >> 1 : (ULongInt)-1;
		ULongInt level = (level_x < level_y ? level_x : level_y) + 1;

		if (level && level < one) {
			value /= one/level;
			if (level_x == level_y) {
				// square corners
				value += ( generate(ULongIntVector2(coord.x - level, coord.y - level))
						 + generate(ULongIntVector2(coord.x - level, coord.y + level))
						 + generate(ULongIntVector2(coord.x + level, coord.y - level))
						 + generate(ULongIntVector2(coord.x + level, coord.y + level)) )*0.25;
			} else {
				// diamond corners
				value += ( generate(ULongIntVector2(coord.x - level, coord.y))
						 + generate(ULongIntVector2(coord.x + level, coord.y))
						 + generate(ULongIntVector2(coord.x, coord.y - level))
						 + generate(ULongIntVector2(coord.x, coord.y + level)) )*0.25;
			}
		}
	}
	i->second.in_use = false;
	
	return value;
}

Vector4
Generator::generate(const Vector2 &coord, const Vector2 &precision) const {
	const int bits = clz(ULongInt(0));
	
	ULongIntVector2 coord_int(
		(ULongInt)(LongInt)(coord.x*one),
		(ULongInt)(LongInt)(coord.y*one) );
	ULongIntVector2 precision_int(
		(ULongInt)(LongInt)(precision.x*one),
		(ULongInt)(LongInt)(precision.y*one) );
	int level_x = bits - clz(precision_int.x);
	int level_y = bits - clz(precision_int.y);
	coord_int.x = (coord_int.x >> level_x) << level_x;
	coord_int.y = (coord_int.y >> level_y) << level_y;
	return generate(coord_int);
}

void
Generator::generate(GenSurface &target) const {
	assert(target.is_valid());
	const ULongInt step = target.step();
	
	if (step && step < one) {
		ULongIntVector2 onev(one, one);
		GenSurface surface(ULongIntPair2(target.p0() - onev, target.p1() + onev), one);
		generate(surface);
		generate(target, surface);
		return;
	}
	
	const ULongInt w = target.width();
	const ULongInt h = target.height();

	const ULongInt report_count = 1ull*1024ull*1024ull;
	std::cout << "    generate base " << w << "x" << h << ": ";
	ULongInt count = 0;
	
	const ULongIntVector2 p0 = target.p0();
	ULongIntVector2 p = p0;
	for(ULongInt y = 0; y < h; ++y, p.x = p0.x, p.y += step) {
		Vector4 *pixel = target[y];
		for(ULongInt x = 0; x < w; ++x, ++pixel, p.x += step) {
			for(int j = 0; j < 4; ++j)
				(*pixel)[j] = random(p, j);
		}
		if ((count += w) >= report_count) { std::cout << "."; count = 0; }
	}

	std::cout << std::endl;
}

void
Generator::generate(GenSurface &target, const GenSurface &source) const {
	assert(target.is_valid());
	assert(source.is_valid());
	assert(target.step());
	assert(target.step() < one);
	assert(source.step());
	assert(source.step() <= one);
	assert(source.step() > target.step());
	
	const ULongInt step = target.step();
	const ULongInt source_step = step << 1;
	
	if (source_step != source.step()) {
		GenSurface surface(ULongIntPair2(target.p0(), target.p1()), source_step);
		generate(surface, source);
		generate(target, surface);
		return;
	}

	const ULongInt tw = target.width();
	const ULongInt th = target.height();

	const ULongInt sw = source.width();
	const ULongInt sh = source.height();
	
	const ULongIntVector2 target_offset = target.offset();
	
	const ULongIntVector2 shift(
		(target.offset().x - source.offset().x)/step,
		(target.offset().y - source.offset().y)/step );
	assert(shift.x);
	assert(shift.y);
	assert(shift.x <= max_side << 1);
	assert(shift.y <= max_side << 1);
	
	assert(sw > (tw - 1 + shift.x)/2 + 1);
	assert(sh > (th - 1 + shift.y)/2 + 1);
	
	const Real deviation_base = 0.65;
	Real deviation = 1;
	for(ULongInt i = one; step < i; i >>= 1)
		deviation *= deviation_base;
	//const Real deviation = Real(step)/one;
	
	ULongIntVector2 coord, start;

	const ULongInt report_count = 2ull*1024ull*1024ull;
	std::cout << "    generate subs " << tw << "x" << th << ": ";
	ULongInt count = 0;
	
	// copy
	ULongInt x0 = 1, y0 = 1;
	coord = start = target_offset + ULongIntVector2(x0, y0)*step;
	for(ULongInt y = y0; y < th; y += 2, coord.x = start.x, coord.y += source_step) {
		Vector4* tp  = &target[y][x0];
		ULongInt sy  = (y  + shift.y)/2;
		ULongInt sx0 = (x0 + shift.x)/2;
		const Vector4* sp  = &source[sy][sx0];
		for(ULongInt x = x0; x < tw; x += 2, coord.x += source_step, tp += 2, ++sp)
			*tp = *sp;
		if ((count += tw) >= report_count) { std::cout << "."; count = 0; }
	}
	
	// square
	x0 = 0, y0 = 0;
	coord = start = target_offset + ULongIntVector2(x0, y0)*step;
	for(ULongInt y = y0; y < th; y += 2, coord.x = start.x, coord.y += source_step) {
		Vector4* tp  = &target[y][x0];
		ULongInt sy  = (y  + shift.y)/2;
		ULongInt sx0 = (x0 + shift.x)/2;
		const Vector4* sp0 = &source[sy][sx0];
		const Vector4* sp1 = &source[sy + 1][sx0];
		for(ULongInt x = x0; x < tw; x += 2, coord.x += source_step, tp += 2, ++sp0, ++sp1) {
			*tp = Vector4(
					random(coord, 0),
					random(coord, 1),
					random(coord, 2),
					random(coord, 3) )*deviation
				+ (sp0[0] + sp0[1] + sp1[0] + sp1[1])*0.25;
		}
		if ((count += tw) >= report_count) { std::cout << "."; count = 0; }
	}

	// diamond 1
	x0 = 1, y0 = 0;
	coord = start = target_offset + ULongIntVector2(x0, y0)*step;
	for(ULongInt y = y0; y < th; y += 2, coord.x = start.x, coord.y += source_step) {
		Vector4* tp  = &target[y][x0];
		ULongInt sy  = (y  + shift.y)/2;
		ULongInt sx0 = (x0 + shift.x)/2;
		const Vector4* sp0 = &source[sy][sx0];
		const Vector4* sp1 = &source[sy + 1][sx0];
		for(ULongInt x = x0; x < tw; x += 2, coord.x += source_step, tp += 2, ++sp0, ++sp1) {
			*tp = Vector4(
					random(coord, 0),
					random(coord, 1),
					random(coord, 2),
					random(coord, 3) )*deviation
				+ (*sp0 + *sp1 + *(tp-1) + *(tp+1))*0.25;
		}
		if ((count += tw) >= report_count) { std::cout << "."; count = 0; }
	}

	// diamond 2
	x0 = 0, y0 = 1;
	coord = start = target_offset + ULongIntVector2(x0, y0)*step;
	for(ULongInt y = y0; y < th; y += 2, coord.x = start.x, coord.y += source_step) {
		Vector4* tp  = &target[y  ][x0];
		Vector4* tp0 = &target[y-1][x0];
		Vector4* tp1 = &target[y+1][x0];
		ULongInt sy  = (y  + shift.y)/2;
		ULongInt sx0 = (x0 + shift.x)/2;
		const Vector4* sp = &source[sy][sx0];
		for(ULongInt x = x0; x < tw; x += 2, coord.x += source_step, tp += 2, tp0 += 2, tp1 += 2, ++sp) {
			*tp = Vector4(
					random(coord, 0),
					random(coord, 1),
					random(coord, 2),
					random(coord, 3) )*deviation
				+ (sp[0] + sp[1] + *tp0 + *tp1)*0.25;
		}
		if ((count += tw) >= report_count) { std::cout << "."; count = 0; }
	}

	std::cout << std::endl;
}


void
Generator::generate(Surface &target, const Pair2 &bounds, bool checks) const {
	if (target.empty()) return;
	
	const int w = target.width();
	const int h = target.height();
	
	std::cout << "generate " << w << "x" << h << std::endl;

	assert(fabs(bounds.p0.x)*one < big);
	assert(fabs(bounds.p0.y)*one < big);
	assert(fabs(bounds.p1.x)*one < big);
	assert(fabs(bounds.p1.y)*one < big);
	
	Vector2 d = bounds.distance();
	d.x /= w;
	d.y /= h;
	const Vector2 precision(fabs(d.x/2.0), fabs(d.x/2.0));
	const Vector2 precision_inv(
		1/std::max(precision.x, real_precision),
		1/std::max(precision.y, real_precision) );
	const Real precision_max = std::max(precision.x, precision.y);
	
	Color gray(0.5, 0.5, 0.5, 0.5);
	if (precision_max >= Real(gray1)/Real(one)) {
		// fill target by gray color
		std::cout << "    gray" << std::endl;
		for(int r = 0; r < h; ++r) {
			Color *p = target[r];
			for(int c = 0; c < w; ++c, ++p)
				*p = gray;
		}
		return;
	}
	
	Real gray_alpha = 0;
	if (precision_max > Real(gray0)/Real(one)) {
		Real l0 = log(Real(gray0)/Real(one));
		Real l1 = log(Real(gray1)/Real(one));
		Real lp = log(precision_max);
		gray_alpha = (lp - l0)/(l1 - l0);
	}
	Real alpha = 1.0 - gray_alpha;
	gray *= gray_alpha;
	
	const ULongIntPair2 gen_bounds(
		ULongIntVector2( ULongInt(floor(bounds.p0.x*one)) - 1,
						 ULongInt(floor(bounds.p0.y*one)) - 1 ),
		ULongIntVector2( ULongInt(ceil (bounds.p1.x*one)) + 1,
						 ULongInt(ceil (bounds.p1.y*one)) + 1 ));
	
	ULongInt step_x = 1, step_y = 1;
	while(step_x < precision.x*one - real_precision && step_x < big) step_x <<= 1;
	while(step_y < precision.y*one - real_precision && step_y < big) step_y <<= 1;
	
	const ULongInt step_max = std::max(step_x, step_y);
	const ULongInt step_min = std::min(step_x, step_y);
	const ULongInt step_diff = step_max / step_min;
	assert(step_diff);

	const ULongInt step_base = step_max/std::min(step_diff, 1ull << 2);
	GenSurface gen_surface(gen_bounds, step_base);
	generate(gen_surface);
	
	std::cout << "    convert" << std::endl;
	const ULongInt step = gen_surface.step();
	const ULongIntVector2 offset(
		gen_surface.offset().x - step/2,
		gen_surface.offset().y - step/2 );
	Vector2 p = bounds.p0;
	for(int r = 0; r < target.height(); ++r, p.x = bounds.p0.x, p.y += d.y) {
		Color *pixel = target[r];
		ULongInt rr = (ULongInt(round(p.y*one)) - offset.y)/step;
		assert(rr < gen_surface.height());
		
		const Real ay = checks ? checks_value(p.y, precision_inv.y) : 1;
		for(int c = 0; c < target.width(); ++c, ++pixel, p.x += d.x) {
			ULongInt cc = (ULongInt(round(p.x*one)) - offset.x)/step;
			assert(cc < gen_surface.width());
			
			const Real ax = checks ? checks_value(p.x, precision_inv.x) : 1;
			const Real a = (ax*ay + 1)*0.5;
			
			const Vector4 &v = gen_surface[rr][cc];
			const Color color = Color( flip_clamp((v.x + 1)*0.5),
									   flip_clamp((v.y + 1)*0.5),
									   flip_clamp((v.z + 1)*0.5),
									   flip_clamp((v.w + 1)*0.5) )*alpha + gray;
			if (a + real_precision >= 1) {
				*pixel = color;
			} else {
				const Color back_color = Color(1 - color.r, 1 - color.g, 1 - color.b, 1 - color.a);
				if (a - real_precision <= 0) {
					*pixel = back_color;
				} else {
					*pixel = color*a + back_color*(1 - a);
				}
			}
		}
	}
}


Real
Generator::checks_value(Real coord, Real inv_precision) const {
	Real x = fabs(coord - floor(coord) - 0.5);
	return clamp(inv_precision*(0.25 - x), -1, 1);
}

Real
Generator::checks_value(const Vector2 &coord, const Vector2 &inv_precision) const {
	Real x = checks_value(coord.x, inv_precision.x)
		   * checks_value(coord.y, inv_precision.y);
	return (x + 1)*0.5;
}

void
Generator::generate_checks(Surface &target, const Pair2 &bounds) const {
	if (target.empty()) return;
	
	const int w = target.width();
	const int h = target.height();
	
	const Color colors[2] = {
		Color(1, 1, 1, 1),
		Color(0, 0, 1, 1) };
	
	Vector2 d = bounds.distance();
	d.x /= w;
	d.y /= h;
	
	Vector2 inv_precision(
		2/std::max(fabs(d.x), real_precision),
		2/std::max(fabs(d.y), real_precision) );

	Vector2 p = bounds.p0;
	for(int r = 0; r < h; ++r, p.x = bounds.p0.x, p.y += d.y) {
		Color *pixel = target[r];
		Real ay = checks_value(p.y, inv_precision.y);
		for(int c = 0; c < w; ++c, ++pixel, p.x += d.x) {
			Real ax = checks_value(p.x, inv_precision.x);
			Real a = (ax*ay + 1)*0.5;
			*pixel = colors[0]*a + colors[1]*(1 - a);
		}
	}
}