import { test, assert } from '../test-assert.js';
import { AABB, QTNode, QuadTree } from './Geometry.js';

const RUN_BENCHMARKS = false;


test('AABB correctly contains/excludes points', () => {
	const box = new AABB(0, 0, 1, 1);

	// interior
	assert.ok(box.contains({ x: 0.5, y: 0.5 }));

	// upper left
	assert.ok(!box.contains({ x: -1, y: -1 }));

	// above
	assert.ok(!box.contains({ x: 0.5, y: -1}));

	// upper right
	assert.ok(!box.contains({ x: 2, y: -1 }));

	// left
	assert.ok(!box.contains({ x: -1, y: 0.5 }));

	// right
	assert.ok(!box.contains({ x: 2, y: 0.5}));

	// lower left
	assert.ok(!box.contains({ x: -1, y: 2 }));

	// below 
	assert.ok(!box.contains({ x: 0.5, y: 2}));

	// lower right
	assert.ok(!box.contains({ x: 2, y: 2 }));
});


test('AABB correctly intersects other AABBs', () => {
	const box = new AABB(1, 1, 4, 4);

	// interior
	assert.ok(box.intersects(new AABB(2, 2, 2, 2,)));

	// upper left
	assert.ok(box.intersects(new AABB(0, 0, 4, 4)));
	assert.ok(!box.intersects(new AABB(0, 0, 0.5, 0.5)));

	// above
	assert.ok(box.intersects(new AABB(2, 0, 2, 2)));
	assert.ok(!box.intersects(new AABB(2, 0, 2, 0.5)));

	// upper right
	assert.ok(box.intersects(new AABB(2, 0, 4, 2)));
	assert.ok(!box.intersects(new AABB(6, 0, 4, 2)));

	// left
	assert.ok(box.intersects(new AABB(0, 2, 2, 2)));
	assert.ok(!box.intersects(new AABB(0, 2, 0.5, 2)));

	// right
	assert.ok(box.intersects(new AABB(4, 2, 2, 2)));
	assert.ok(!box.intersects(new AABB(6, 2, 2, 2)));

	// lower left
	assert.ok(box.intersects(new AABB(0, 4, 4, 4)));
	assert.ok(!box.intersects(new AABB(0, 6, 0.5, 0.5)));

	// below
	assert.ok(box.intersects(new AABB(2, 4, 2, 2)));
	assert.ok(!box.intersects(new AABB(2, 6, 2, 0.5)));

	// lower right
	assert.ok(box.intersects(new AABB(2, 4, 4, 2)));
	assert.ok(!box.intersects(new AABB(6, 6, 4, 2)));
});


test('AABB correctly handles points at the edges', () => {
	const box = new AABB(0, 0, 1, 1);

	assert.ok(box.contains({ x: 0, y: 0 }));
	assert.ok(box.contains({ x: 0.5, y: 0 }));
	assert.ok(box.contains({ x: 0, y: 0.5 }));

	// bad corners
	assert.ok(!box.contains({ x: 1, y: 0 }));
	assert.ok(!box.contains({ x: 0, y: 1 }));
	assert.ok(!box.contains({ x: 1, y: 1 }));

	// bad edges
	assert.ok(!box.contains({ x: 1, y: 0.5 }));
	assert.ok(!box.contains({ x: 0.5, y: 1 }));
});


test('QTNode correctly inserts points', () => {
	const node = new QTNode(0, 0, 1, 1);
	assert.equal(node.type.toString(), 'QTNode.Empty');

	let result = node.insert({ x: -1, y: -1 }); // out of range, should not insert
	assert.ok(!result);
	assert.equal(node.type.toString(), 'QTNode.Empty');

	result = node.insert({ x: 0.5, y: 0.5 }); // in range
	assert.ok(result);
	assert.equal(node.type.toString(), 'QTNode.Leaf');
	assert.deepEqual(node.point, { x: 0.5, y: 0.5 });
});


test('QTNode correctly subdivides', () => {
	const node = new QTNode(0, 0, 2, 2);
	assert.ok(!node.subnode);
	node.subdivide();
	assert.equal(node.subnode.length, 4);

	assert.deepEqual(node.subnode[0], new QTNode(0, 0, 1, 1));
	assert.deepEqual(node.subnode[1], new QTNode(1, 0, 1, 1));
	assert.deepEqual(node.subnode[2], new QTNode(0, 1, 1, 1));
	assert.deepEqual(node.subnode[3], new QTNode(1, 1, 1, 1));
});


test('QTNode correctly inserts multiple points', () => {
	const node = new QTNode(0, 0, 2, 2);
	
	const p0 = { x: 1, y: 1 };
	const p1 = { x: 0.5, y: 0.5 };
	const oob = { x: 10, y: 15 };

	assert.ok(node.insert(p0));
	assert.ok(node.insert(p1));
	assert.ok(!node.insert(oob));

	assert.equal(node.type.toString(), 'QTNode.Branch');
	
	assert.equal(node.subnode[0].type.toString(), 'QTNode.Leaf');
	assert.deepEqual(node.subnode[0].point, p1);

	assert.equal(node.subnode[1].type.toString(), 'QTNode.Empty');
	assert.equal(node.subnode[2].type.toString(), 'QTNode.Empty');

	assert.equal(node.subnode[3].type.toString(), 'QTNode.Leaf');
assert.deepEqual(node.subnode[3].point, p0);
});


const randomPoint = () => ({ x: Math.random(), y: Math.random() });


test('QTNode correctly returns points in region', () => {
	const node = new QTNode(0, 0, 1, 1);
	let points = [];
	for (let i=0; i<100; i++) {
		const pt = randomPoint();
		node.insert(pt);
		points.push(pt);
	}

	const pointsInRegion = aabb => {
		let pts = [];
		for (let pt of points) {
			if (aabb.contains(pt)) pts.push(pt);
		}
		return pts;
	};

	const region = new AABB(0.25, 0.25, 0.5, 0.5);
	let bf_points = pointsInRegion(region);
	let qt_points = node.getPointsInRegion(region);
	const compare = (a, b) => {
		if (a.x == b.x)
			return b.y - a.y;
		return b.x - a.x;
	};
	bf_points.sort(compare);
	qt_points.sort(compare);
	assert.deepEqual(bf_points, qt_points);
});


test('QTNode correctly removes immediate child point', () => {
	const node = new QTNode(0, 0, 1, 1);

	const pt = randomPoint();
	node.insert(pt);
	assert.deepEqual(node.type, QTNode.Leaf);
	
	const pt2 = randomPoint();
	node.remove(pt2);
	assert.deepEqual(node.type, QTNode.Leaf);
	assert.deepEqual(node.point, pt);

	node.remove(pt);
	assert.deepEqual(node.type, QTNode.Empty);
	assert.equal(node.point, undefined);
});


test('QTNode correctly removes point from branch', () => {
	for (let i=0; i<100; i++) {
		const node = new QTNode(0, 0, 1, 1);

		const pt1 = randomPoint();
		const pt2 = randomPoint();
		const pt3 = randomPoint();

		node.insert(pt1); node.insert(pt2); node.insert(pt3);

		assert.deepEqual(node.type, QTNode.Branch);

		node.remove(pt1);
		// should still be a branch because there are two child points yet
		assert.deepEqual(node.type, QTNode.Branch);

		node.remove(pt2);
		// just one now, should be a leaf
		assert.deepEqual(node.type, QTNode.Leaf);

		node.remove(pt3);
		// empty
		assert.deepEqual(node.type, QTNode.Empty);
	}
});


test('QuadTree correctly finds closest point for 10,000 random points', () => {
	const tree = new QuadTree(1, 1);

	let points = [];
	for (let i=0; i<10000; i++) {
		const pt = randomPoint();
		tree.insert(pt);
		points.push(pt);
	}
	
	const distance = (a, b) => Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2);
	const bf_closest = a => {
		let closest = null;
		let min_dist = 1000;
		for (let b of points) {
			let d = distance(a, b);
			if (d < min_dist) {
				min_dist = d;
				closest = b;
			}
		}
		return closest;
	}

	for (let i=0; i<10000; i++) {
		const pt = randomPoint();
		assert.deepEqual(bf_closest(pt), tree.closest(pt));
	}
});


function benchmark(desc, f, iterations) {
	process.stdout.write(`${desc}: `);
	const start = process.uptime();
	for (let i=0; i<iterations; i++) f();
	const elapsed = process.uptime() - start;
	console.log(`${elapsed} seconds`);
}

const closest_benchmark = () => {
	const n_points = 1e5;
	const iterations = 1e4;
	console.log(`> benchmark get closest of ${n_points} random points ${iterations} times`);

	const tree = new QuadTree(1, 1);
	let points = [];
	for (let i=0; i<n_points; i++) {
		const pt = randomPoint();
		tree.insert(pt);
		points.push(pt);
	}

	const distance = (a, b) => Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2);
	const bf_closest = a => {
		let closest = null;
		let min_dist = 1000;
		for (let b of points) {
			let d = distance(a, b);
			if (d < min_dist) {
				min_dist = d;
				closest = b;
			}
		}
		return closest;
	}

	benchmark('\tbrute force', () => {
		const pt = randomPoint();
		bf_closest(pt);
	}, iterations);

	benchmark('\tquadtree', () => {
		const pt = randomPoint();
		tree.closest(pt);
	}, iterations);
}
if (RUN_BENCHMARKS)
	closest_benchmark();