'use strict';

class AABB {
	constructor(x, y, width, height) {
		this.x = x; this.y = y;
		this.width = width; this.height = height;
	}

	contains(point) {
		if (point.x >= this.x && point.y >= this.y
		    && point.x < this.x + this.width
			&& point.y < this.y + this.height)
			return true;
		return false;
	}

	intersects(aabb) {
		const overlap = (ax, arange, bx, brange) => {
			const range = ax < bx ? arange : brange;
			if (Math.abs(bx - ax) < range)
				return true;
			return false;
		};

		if (overlap(this.x, this.width, aabb.x, aabb.width) &&
		    overlap(this.y, this.height, aabb.y, aabb.height))
			return true;
		return false;
	}
}


/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 *
 * QUADTREE
 *
 * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 */

class QTNodeType {
	constructor(name) { this.name = name; }
	toString() { return `QTNode.${this.name}`; }
}


class QTNode {
	static Empty = new QTNodeType('Empty');
	static Leaf = new QTNodeType('Leaf');
	static Branch = new QTNodeType('Branch');

	constructor(x, y, width, height) {
		this.aabb = new AABB(x, y, width, height);
		this.type = QTNode.Empty;
	}

	insert(point) {
		if (this.aabb.contains(point)) {
			if (this.type == QTNode.Empty) {
				this.type = QTNode.Leaf;
				this.point = point;
				return true;
			}
			else if (this.type == QTNode.Leaf) {
				this.type = QTNode.Branch;
				this.subdivide();
				let result = this.insert(this.point);
				if (!result) return false;
				this.point = undefined;
				return this.insert(point);
			}
			else {
				// Branch
				if (this.subnode[0].insert(point)) return true;
				if (this.subnode[1].insert(point)) return true;
				if (this.subnode[2].insert(point)) return true;
				if (this.subnode[3].insert(point)) return true;
				return false; // something strange has happened!!
			}
		}
		return false;
	}

	subdivide() {
		const x = this.aabb.x; const y = this.aabb.y;
		const w = this.aabb.width/2; const h = this.aabb.height/2;

		this.subnode = [
			new QTNode(x, y, w, h),
			new QTNode(x+w, y, w, h),
			new QTNode(x, y+h, w, h),
			new QTNode(x+w, y+h, w, h),
		];
	}

	getPointsInRegion(aabb) {
		if (this.type == QTNode.Empty) return [];
		if (!this.aabb.intersects(aabb)) return [];
		if (this.type == QTNode.Leaf) return [this.point];
		
		return [
			...this.subnode[0].getPointsInRegion(aabb),
			...this.subnode[1].getPointsInRegion(aabb),
			...this.subnode[2].getPointsInRegion(aabb),
			...this.subnode[3].getPointsInRegion(aabb),
		];
	}
}


class QuadTree {
	constructor(width, height) {
		this.root = new QTNode(0, 0, width, height);
	}

	insert(point) {
		return this.root.insert(point);
	}

	closest(point) {
		const getLeaf = (point, node) => {
			if (!node.aabb.contains(point)) return null;
			if (node.type == QTNode.Empty ||
			    node.type == QTNode.Leaf) return node;
			
			for (let subnode of node.subnode) {
				const leaf = getLeaf(point, subnode);
				if (leaf !== null) return leaf;
			}

			return null;
		}

		const leaf = getLeaf(point, this.root);
		if (leaf === null) return leaf;

		const dim = 2*Math.max(leaf.aabb.width, leaf.aabb.height);
		const region = new AABB(point.x - dim, point.y - dim, 2*dim, 2*dim);
		const points = this.root.getPointsInRegion(region);

		let closest = null;
		let min_dist = 100 * this.root.aabb.width * this.root.aabb.height;
		const dist = (a, b) => (a.x - b.x)**2 + (a.y - b.y)**2;
		for (let pt of points) {
			const d = dist(point, pt);
			if (d < min_dist) {
				closest = pt;
				min_dist = d;
			}
		}
		return closest;
	}
}

export { AABB, QTNode, QuadTree };