#include <ctime></ctime>

#include <iostream></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.y/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(color.g, color.b, color.r, 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);

		}

	}

}