#include <memory>

#include "QuadTreeCollisionChecker.h"
#include "Museum.h"

using namespace std;

QuadTreeCollisionChecker::QuadTreeCollisionChecker(Museum & museum) : CollisionChecker(museum) {
	this->boundary = {
		.x = 0.0,
		.y = 0.0,
		.width = static_cast<float>(museum.canvas.data.columns),
		.height = static_cast<float>(museum.canvas.data.rows),
	};

	this->artists = museum.people.get_artists();
	for (auto & _ : this->artists) this->artists_size++;

	if (this->artists_size > this->capacity)
		this->subdivide();
}

QuadTreeCollisionChecker::QuadTreeCollisionChecker(const QuadTreeCollisionChecker * parent, const Rectangle & boundary) : CollisionChecker(parent->museum) {
	this->boundary = boundary;

	this->artists = parent->artists;
	this->artists_size = parent->artists_size;

	this->cull();

	if (this->artists_size > this->capacity)
		this->subdivide();
}

void QuadTreeCollisionChecker::subdivide() {
	float half_width = this->boundary.width / 2;
	float half_height = this->boundary.height / 2;

	// squares smaller than artists will subdivide infinitely
	if (half_width <= 0.5) return;
	if (half_height <= 0.5) return;

	this->subtree[0] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
		.x = this->boundary.x,
		.y = this->boundary.y,
		.width = half_width,
		.height = half_height,
	}));
	this->subtree[1] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
		.x = this->boundary.x + half_width,
		.y = this->boundary.y,
		.width = half_width,
		.height = half_height,
	}));
	this->subtree[2] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
		.x = this->boundary.x,
		.y = this->boundary.y + half_height,
		.width = half_width,
		.height = half_height,
	}));
	this->subtree[3] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
		.x = this->boundary.x + half_width,
		.y = this->boundary.y + half_height,
		.width = half_width,
		.height = half_height,
	}));

	// now all artists are stored in subtrees, so they no longer have to be
	// stored in this quad
	this->artists.clear();
	this->artists_size = 0;
}

void QuadTreeCollisionChecker::cull() {
	// remove artists that are *completely* outside the boundary
	this->artists_size -= this->artists.remove_if([this](const Artist * artist) -> bool {
		if (artist->data.x + 0.5 < this->boundary.x) return true;
		if (artist->data.y + 0.5 < this->boundary.y) return true;
		if (artist->data.x > this->boundary.x + this->boundary.width) return true;
		if (artist->data.y > this->boundary.y + this->boundary.height) return true;
		return false;
	});
}

void QuadTreeCollisionChecker::check() {
	if (this->artists_size > 0) {
		auto begin = this->artists.begin();
		auto end = this->artists.end();
		for (auto it1 = begin; it1 != end; ++it1) {
			auto it2 = it1;
			++it2;
			for (; it2 != end; ++it2) {
				this->compare(**it1, **it2);
			}
		}
	}
	for (size_t i = 0; i < 4; i++) {
		if (this->subtree[i] == nullptr) continue;
		this->subtree[i]->check();
	}
}